求解置换流水车间调度问题的混合鸟群算法  

Hybrid bird swarm algorithm for solving permutation flowshop scheduling problem

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

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

出　　处：《计算机应用》2022年第9期2952-2959,共8页journal of Computer Applications

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

摘　　要：针对置换流水车间调度问题(PFSP),提出了一种混合鸟群算法(HBSA)以更加有效地最小化最大完工时间。首先,为了改善初始种群的质量和多样性,结合一种基于NEH(Nawaz-Enscore-Ham)的启发式算法和混沌映射提出了一种新的种群初始化方法;其次,为了使算法能够处理离散的调度问题,采用最大排序值(LRV)规则将连续的位置值转换为离散的工件排序;最后,为了强化算法对解空间的探索能力,借鉴变邻域搜索(VNS)和迭代贪婪(IG)算法的思想针对个体最佳工件排序和种群最佳工件排序分别提出了局部搜索方法。针对广泛使用的Rec标准测试集进行了仿真测试,并与目前有效的元启发式算法——刘等提出的混合差分进化算法(L-HDE)、混合共生生物搜索算法(HSOS)、离散狼群算法(DWPA)、多班级教学优化算法(MCTLBO)相比较,结果表明,HBSA取得的最佳相对误差(BRE)、平均相对误差(ARE)的平均值比上述四种算法至少下降了73.3%、76.8%,从而证明HBSA具有更强的寻优能力和更好的稳定性。尤其是针对测试算例Rec25和Rec27,仅HBSA的求解结果达到了目前已知最优解,进一步证明了其优越性。A Hybrid Bird Swarm Algorithm(HBSA) was proposed to minimize the makespan more efficiently for Permutation Flowshop Scheduling Problem(PFSP). Firstly,to improve the quality and diversity of initial population,a new population initialization method was put forward by combining a NEH(Nawaz-Enscore-Ham)based heuristic algorithm and chaotic mapping. Secondly,to deal with the discrete scheduling problem by the algorithm,the Largest Ranked Value(LRV)rule was adopted to convert continuous position values to discrete job permutation. Finally,to enhance the ability of the algorithm to explore the solution space,local search methods for the individual best job permutation and population best job permutation were proposed on the basis of the ideas of Variable Neighborhood Search(VNS)and Iterative Greedy(IG)algorithms respectively. The proposed algorithm was simulated and tested on the widely used benchmark test set Rec and compared with Hybrid Differential Evolution algorithm proposed by Liu et al(L-HDE)algorithm,Hybrid Symbiotic Organisms Search(HSOS)algorithm,Discrete Wolf Pack Algorithm(DWPA)and Multi-Class Teaching-Learning-Based Optimization(MCTLBO)algorithm,which are the effective meta-heuristic algorithms for PFSP. The results show that the average values of Best Relative Error(BRE)and Average Relative Error(ARE)achieved by HBSA are at least 73. 3% and 76. 8% lower than those of the above four algorithms,thus proving that HBSA has stronger search ability and better stability. It is worth mentioning that,for Rec25 and Rec27 test instances,only HBSA achieves the currently known optimal solutions,which further proves its superiority.

关 键 词：鸟群算法 置换流水车间调度问题 种群初始化 局部搜索 最大完工时间 

分 类 号：TP39[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]