面向异步混合流水车间排产的混合禁忌搜索遗传优化算法  

Improved Genetic Algorithm with Tabu Search for Asynchronous Hybrid Flow Shop Scheduling

作　　者：王思彤 林荣恒 WANG Sitong;LIN Rongheng(College of Computer Science(National Pilot Software Engineering School),Beijing University of Posts and Telecommunications,Beijing 100876,China)

机构地区：[1]北京邮电大学计算机学院(国家示范性软件学院),北京100876

出　　处：《计算机科学》2025年第4期271-279,共9页Computer Science

基　　金：国家重点研发计划(2021YFB3300700)。

摘　　要：相比于传统流水线,混合流水车间具有更高的灵活性,能适应多变的生产场景,但其排产方案的求解复杂度更高,是现代实际制造系统中的常见问题。针对群智能进化算法在解决该问题时计算难度大且搜索效率不高的问题,以最小化总完工时间为优化目标,提出了一种混合禁忌搜索遗传优化算法。该算法根据排产问题中所有工件具有相同生产工艺、工件数量多、各阶段并行机不同速的特点,采用了基于首阶段工件顺序的单层编码、考虑机器选择三层优先级的解码方法、多种遗传算子和禁忌搜索算子,具有更加优秀的搜索性能,在保证解质量的基础上提高了算法的收敛速度。最后,通过40个算例和实际应用案例评估算法性能,并将其与其他算法进行比较。实验结果表明,所提出的算法在求解中规模算例、大规模算例和加工车间案例时表现优秀,排产结果的完工时间平均缩短了10.71%,算法达到最优解所需的迭代次数减少了25.72%,运行时间缩短了10.79%。Compared with the traditional assembly line,the hybrid flow shop has higher flexibility and can adapt to the changing production scenarios.However,the solution complexity of its scheduling scheme is higher,which is a common problem in modern actual manufacturing systems.Aiming at the problems of high computational difficulty and low search efficiency of swarm intelligence evolutionary algorithm in solving this problem,an improved genetic algorithm with tabu search is proposed to minimize the total completion time.According to the characteristics of all workpieces in the scheduling problem with the same production process,the large number of workpieces,and the different speeds of parallel machines in each stage,the proposed algorithm adopts a single-layer coding based on the first-stage workpiece order,a decoding method considering the three-layer priority of machine selection,a variety of genetic operators and tabu search operators.It has better search performance and improves the convergence speed of the algorithm on the basis of ensuring the quality of the solution.Finally,the performance of the algorithm is evaluated by 40 instances and workshop cases,and is compared with other algorithms.The experimental results show that the proposed algorithm performs well in solving medium-scale instances,large-scale instances and processing workshop cases.The completion time of the scheduling results is shortened by 10.71%on average.The number of iterations required for the algorithm to reach the optimal solutions is reduced by 25.72%,and the running time is shortened by 10.79%.

关 键 词：排产优化 改进遗传算法 禁忌搜索 混合流水车间调度 异步并行机 

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