两阶段流水车间成组调度问题的迭代贪婪算法  

Co-evolutionary iterated greedy algorithm for the two-stage flow shop group scheduling problem

作　　者：袁帅鹏 李铁克[1,3] 王柏琳[1,3] 刘青 YUAN Shuaipeng;LI Tieke;WANG Bailin;LIU Qing(Donlinks School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China;School of State Key Laboratory of Advanced Metallurgy,University of Science and Technology Beijing,Beijing 100083,China;Engineering Research Center of MES Technology for Iron&Steel Production,Ministry of Education,Beijing 100083,China)

机构地区：[1]北京科技大学东凌经济管理学院,北京100083 [2]北京科技大学钢铁冶金新技术国家重点实验室,北京100083 [3]钢铁生产制造执行系统技术教育部工程研究中心,北京100083

出　　处：《系统工程理论与实践》2020年第10期2707-2716,共10页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71701016,71231001);教育部人文社会科学研究青年基金(17YJC630143);北京市自然科学基金(9174038);中央高校基本科研业务费(FRF-BD-18-009A)。

摘　　要：针对两阶段流水车间成组调度问题,在同时考虑序列不相关准备时间和阶段间双向运输时间约束的情况下,以最小化最大完工时间为目标建立了混合整数线性规划模型,结合问题特征提出一种协同进化迭代贪婪算法.算法将工件组间排序和各工件组内工件间排序两个子问题进行统一编码,设计了不同的启发式规则产生问题的初始解,并提出一种协同导向迭代贪婪规则对两个子问题进行联合优化,进而给出了问题的三个下界以评估算法的性能.通过不同规模的数据实验和与对比算法的比较分析,验证了所提算法的高效性和稳健性.Aiming at the two-stage flow shop group scheduling problem,a mixed integer linear programming model for minimizing the makespan was established by simultaneously considering the sequenceindependent setup time and the round-trip transportation time.Then a co-evolutionary iterated greedy algorithm(CIGA)was proposed based on the characteristics of the problem.In the CIGA,the two subproblems,namely group scheduling and job scheduling within each group,were uniformly coded,and several problem-specific heuristic rules were generated to construct the initial solution.A cooperativeoriented iterated greedy rule was also proposed to synergistically evolve the two sub-problems.Moreover,three different lower bounds were developed to evaluate the solution quality of CIGA.Experiments with various problem scales were carried out,and the results verified the efficiency and robustness of the proposed algorithm.

关 键 词：流水车间成组调度 准备时间 双向运输时间 启发式规则 协同进化 迭代贪婪算法 

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