求解柔性作业车间调度问题的一种新邻域结构  

A new neighborhood structure for solving the flexible job-shop scheduling problem

作　　者：黄学文[1] 陈绍芬 周阗玉 孙宇婷[1] HUANG Xuewen;CHEN Shaofen;ZHOU Tianyu;SUN Yuting(School of Economics and Management,Dalian University of Technology,Dalian 116024,China)

机构地区：[1]大连理工大学经济管理学院,大连116024

出　　处：《系统工程理论与实践》2021年第9期2367-2378,共12页Systems Engineering-Theory & Practice

基　　金：国家科技支撑计划项目(2015BAF09B01)。

摘　　要：针对柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP),提出了一种新的邻域结构,该邻域结构保证任意一次邻域移动可以改进当前解,从而显著地缩小了邻域规模.在此基础上,在求解FJSP问题的禁忌搜索算法中,设计了基于该邻域结构的两级邻域搜索策略,该策略既增加了邻域搜索的有效性,又保证了最优解的连通性.最后,针对69个FJSP的Benchmark问题进行了测试,实验结果验证了新邻域结构的有效性,并更新了 4个Benchmark问题的历史最优解.For flexible job-shop scheduling problem,a new neighborhood structure is proposed.The neighborhood structure guarantees each move can produce an improved solution,which significantly reduce the size of neighborhood.Based on the neighborhood structure,a two-pace neighborhood search strategy is designed to insert into the procedure of tabu search.The strategy not only enhances search efficiency,but also holds the optimum connectivity.Finally,69 famous benchmark instances of the FJSP are used to verify the performance of the proposed neighbourhood structure and the best known solutions for 4 benchmark instances are updated.

关 键 词：柔性作业车间调度 邻域结构 禁忌搜索算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] F273[自动化与计算机技术—控制科学与工程]