摘要
针对作业车间调度问题(JSP),在现有邻域结构的基础上进行拓展,提出一种新型邻域结构.通过对现有邻域结构中产生可行邻域解的约束条件进行松弛,能够使得当前解生成更多的可行邻域解.使用禁忌搜索算法将已有的3种常见的邻域结构与该新型邻域结构进行对比,使用TA数据集中的前50个算例进行验证.实验结果表明:设计的新型邻域结构无论在最优值还是平均值,都比其他3种邻域结构具有优势.实验数据表明:新型邻域结构在4种邻域结构中能够搜索的最多可行邻域解.尽管新型邻域结构搜索花费的时间最多,但由于使用了近似评估方法,因此搜索时间在可接受范围内.
A new neighborhood structure for job-shop scheduling problem(JSP)was proposed,which was expanded based on the existing neighborhood structure.By relaxing the constraints that produced feasible neighborhood solutions,the current solution could generate more feasible neighborhood solutions.Tabu search algorithm was adopted to compare the existing three common neighborhood structures with the new neighborhood structure,and the first 50 instances in the TA were used to verify.Experimental results show that the designed new neighborhood structure has advantages over the other three neighborhood structures regardless of the optimal value or the average value.Experimental data show that the new neighborhood structure could search for the most feasible neighborhood solutions among the four neighborhood structures.Although the new neighborhood structure would take the most time,the search time was acceptable because of the usage of approximate calculation method.
作者
桂林
李新宇
高亮
GUI Lin;LI Xinyu;GAO Liang(School of Mechanical Science and Engineering,Huazhong University of Science and Technology,Wuhan 430074 China)
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2021年第7期103-106,119,共5页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
国家自然科学基金资助项目(51825502,51775216)。
关键词
生产调度
作业车间
NP难
禁忌搜索算法
邻域结构
production scheduling
job shop
NP-hard
tabu search algorithm
neighborhood structure
