指针网络与遗传算法求解置换流水车间调度问题  

Pointer Network and Genetic Algorithm for Solving Permutation Flow Shop Scheduling Problem

作　　者：蔡国帅 金淳[2] 华顺刚[1] Cai Guoshuai;Jin Chun;Hua Shungang(School of Mechanical Engineering,Dalian University of Technology,Dalian,Liaoning 116024,China;School of Economics and Management,Dalian University of Technology,Dalian,Liaoning 116024,China)

机构地区：[1]大连理工大学机械工程学院,辽宁大连116024 [2]大连理工大学经济管理学院,辽宁大连116024

出　　处：《机电工程技术》2022年第7期76-80,174,共6页Mechanical & Electrical Engineering Technology

摘　　要：针对置换流水车间调度问题,以最小化最大完工时间为目标,提出了一种将指针网络与遗传算法结合的求解框架。首先,对置换流水车间调度问题的算例进行预处理,以使不同算例的机器维度一致,使得训练的指针网络可以用于不同标准算例的求解,并利用策略梯度法对指针网络的参数进行优化。其次,将指针网络的输出结果结合NEH算法初始化遗传算法种群,以提高初始种群质量;结合重启机制和局部搜索技术,以提高算法的全局搜索能力,通过不断迭代获得最终的调度解。最后,运用PN-HGA算法对Reeves标准测试集进行仿真测试,以最优相对误差与平均相对误差为评价标准,与其他智能优化算法进行比较,在大部分的标准算例上取得了更好的结果,从而验证了算法的有效性。Aiming at the permutation flow shop scheduling problem,with the goal of minimizing the maximum completion time,a solution framework combining pointer network and genetic algorithm was proposed.First,the calculation examples of the replacement flow shop scheduling problem were preprocessed to make the machine dimensions of different calculation examples consistent,so that the trained pointer network could be used to solve different standard calculation examples,and the policy gradient method was used to determine the parameters of the pointer network optimize.Secondly,the output results of the pointer network with the NEH algorithm were combined to initialize the genetic algorithm population to improve the quality of the initial population;the restart mechanism and local search technology were combined to improve the algorithm's global search ability,and obtained the final scheduling solution through continuous iteration.Finally,the PN-HGA algorithm was used to simulate the Reeves standard test set,and the best relative error and the average relative error were used as the evaluation criteria.Compared with other intelligent optimization algorithms,it has achieved better results in most standard calculation examples.As a result,the effectiveness of the algorithm is verified.

关 键 词：置换流水车间调度 指针网络 遗传算法 NEH启发式算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]