基于离散状态转移算法的无等待流水车间调度研究  

Research on No-Wait Flow Shop Scheduling Based on Discrete State Transition Algorithm

作　　者：余佳英 张宏立[1] 董颖超 Yu Jiaying;Zhang Hongli;Dong Yingchao(School of Electrical Engineering,Xinjiang University,Urumqi 830047,China)

机构地区：[1]新疆大学电气工程学院,新疆乌鲁木齐830047

出　　处：《系统仿真学报》2023年第5期1034-1045,共12页Journal of System Simulation

基　　金：国家自然科学基金(51967019,52065064);天山雪松计划(2020XS03);天山青年计划(2019Q064,2020Q066)。

摘　　要：针对制造行业中广泛存在的无等待流水车间调度问题,提出一种改进的离散状态转移算法进行求解。基于流水车间调度问题的特性,设计工件的编码方式,采用基于工件加工时间标准差为优先级的NEH(Nawaz-Enscore-Ham)方法构造初始解,设计基于插入和交换的多邻域组合搜索策略以提高初始解的质量;提出一种基于群状态的离散状态转移算法,并利用带二次状态转移操作的三种离散操作算子扩大算法的搜索范围;为进一步提高离散状态转移算法的求解性能,设计了基于莱维飞行的破坏重构局部搜索方法,对全局搜索发现的优质解进行细致搜索。仿真实验表明,改进的离散状态转移算法能够有效求解无等待流水车间调度问题。In view of the no-wait flow shop problem(NWFSP)widely existing in the manufacturing industry,an improved discrete state transition algorithm(IDSTA)is proposed to solve the problem.The coding mode of the workpiece is designed based on the characteristics of the flow shop scheduling problem(FSSP).The initial solution is constructed by the Nawaz-Enscore-Ham(NEH)method with the standard deviation of the processing time of the workpiece as the priority,and a multi-neighborhood combinatorial search strategy based on insertion and exchange is designed to improve the quality of the initial solution.A discrete state transition algorithm(DSTA)based on group state is proposed,and the search range of the algorithm is expanded by using three discrete operators with quadratic state transition operations.In order to further improve the solution performance of DSTA,a local search method based on Levy flight for damage reconstruction is designed,and the high-quality solution detected by global search is searched carefully.The simulation experiments show that IDSTA can effectively solve the NWFSP.

关 键 词：无等待约束条件 流水车间调度问题 离散状态转移算法 变邻域搜索 莱维飞行 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP391.9[自动化与计算机技术—计算机科学与技术]