基于种群迭代贪婪算法无等待流水车间调度  

A Population-based Iterated Greedy Algorithm for No-wait Job Shop Scheduling

作　　者：董海 王瀚鹏 Dong Hai;Wang Han-peng(School of Applied Technology,Shenyang University,Shenyang 110044,China;School of Mechanical Engineering,Shenyang University,Shenyang 110044,China)

机构地区：[1]沈阳大学应用技术学院,辽宁沈阳110044 [2]沈阳大学机械工程学院,辽宁沈阳110044

出　　处：《控制工程》2023年第5期944-953,共10页Control Engineering of China

基　　金：国家自然科学基金资助项目(71672117);中央引导地方科技发展资金计划项目(2021JH6/10500149)。

摘　　要：针对无等待流水车间调度问题,提出一种基于种群迭代的改进贪婪算法解决以最小化最大完工时间为目标的此类问题。首先,采用改进NEH(Nawaz–Enscore–Ham)算法提升初始种群的质量,提高种群的多样性,并得出初始解,确定最优个体;其次,采用种群迭代贪婪算法对确定的种群序列进行破坏与重新构建,将新序列插入指定位置,并对获得的候选方案进行本地搜索,获得新的解决方案,同时取代劣势解决方案;最后,通过仿真实例将种群迭代贪婪算法与其他智能优化算法在平均相对偏差率、最佳相对偏差率、算法收敛性上进行对比,结果表明种群迭代贪婪算法求解所提问题的高效性和稳定性。Aiming at the problem of no-wait flow shop scheduling,this paper proposes a population iterated greedy algorithm to solve such problems with makespan minimization.First,the improved NEH algorithm is used to improve the quality of the initial population,increase the diversity of the population,and obtain the initial solution to determine the optimal individual;second,the population iterated greedy algorithm is used to destroy and rebuild the determined population sequence,and the new sequence Insert the specified position,and perform a local search on the obtained candidate solutions to obtain new solutions and replace inferior solutions at the same time.Finally,through simulation examples,the population iterated greedy algorithm is compared with other intelligent optimization algorithms in the average relative deviation rate and the best relative The comparison of the three indicators of deviation rate and algorithm convergence shows that the population iterated greedy algorithm is efficient and stable in solving the proposed problem.

关 键 词：无等待流水车间 种群迭代贪婪算法 最大完工时间 NEH算法 本地搜索 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]