基于新混合乌鸦搜索算法的置换流水车间调度  

Permutation flow-shop scheduling problem based on new hybrid crow search algorithm

作　　者：闫红超[1] 汤伟[1] 姚斌[2] YAN Hongchao;TANG Wei;YAO Bin(School of Electrical and Control Engineering,Shaanxi University of Science and Technology,Xi’an 710021,China;School of Electronic Information and Artificial Intelligence,Shaanxi University of Science and Technology,Xi’an 710021,China)

机构地区：[1]陕西科技大学电气与控制工程学院,陕西西安710021 [2]陕西科技大学电子信息与人工智能学院,陕西西安710021

出　　处：《计算机集成制造系统》2024年第5期1834-1846,共13页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(62073206);国家自然科学基金青年科学基金资助项目(61603234);陕西省技术创新引导专项基金资助项目(2020CGHJ-007)。

摘　　要：为了更加有效地求解以最大完工时间最小化为目标的置换流水车间调度问题,提出一种新混合乌鸦搜索算法(NHCSA)。首先,对一种基于NEH的启发式算法进行了改进,在此基础上提出新的方法以改善初始种群的质量和多样性;其次,采用SPV(Smallest-Position-Value)规则进行编码,使算法能够处理离散的调度问题;最后,针对迭代贪婪算法,提出了自动调整重插入工件范围的方法、引入了TB机制,并采用改进的迭代贪婪算法对最佳工件排序进行局部搜索,以提升算法收敛的精度。基于典型测试集进行了仿真测试,结果验证了所提算法的寻优能力和稳定性。尤其是在针对Rec19和Rec25算例的比较中,仅NHCSA取得了当前最优解,进一步证明了其优越性。To solve the permutation flow-shop scheduling problem with the objective to minimize makespan more effectively,a New Hybrid Crow Search Algorithm(NHCSA)was proposed.A NEH-based heuristic was modified,based on which a new method was put forward to ameliorate the quality and diversity of the initial population.Then,the Smallest-Position-Value(SPV)rule was adopted to enable the algorithm to deal with discrete scheduling problems.For the iterated greedy algorithm,a method was come up with to adjust the range of re-inserted jobs automatically,a Tie-Breaking(TB)mechanism was embedded,and the improved iterated greedy algorithm was incorporated as a local search scheme for the best job permutation to improve the searching accuracy of the proposed algorithm.Simulations based on the well-known benchmarks were carried out,and the results validated the optimization ability and stability.Especially in the comparisons for Rec19 and Rec25 test cases,only NHCSA achieved the current optimal solutions,which further proves its superiority.

关 键 词：乌鸦搜索算法 置换流水车间 种群初始化 局部搜索 

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