带运输时间混合流水车间成组调度的协同进化文化基因算法  

Co-evolutionary memetic algorithm for the hybrid flow shop group scheduling with transportation times

作　　者：袁帅鹏 李铁克[1,2] 王柏琳[1,2] YUAN Shuai-peng;LI Tie-ke;WANG Bai-lin(School of Economics and Management,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

出　　处：《控制理论与应用》2023年第3期430-440,共11页Control Theory & Applications

基　　金：国家自然科学基金项目(71701016,71231001);北京市自然科学基金项目(9174038);中央高校基本科研业务费项目(FRF-BD-20-16A)资助。

摘　　要：研究了一类带有序列相关准备时间和阶段间运输时间的混合流水车间成组调度问题,以最小化最大完工时间为目标建立混合整数线性规划模型,结合问题特征提出一种协同进化文化基因算法.算法采用置换序列的方式对工件组间调度、各工件组内工件间调度以及各工件组在各阶段上并行机的指派3个子问题进行统一编码,基于负载均衡思想和改进的先到先得策略将染色体解码为问题的可行解;进化过程中采用多种遗传算子执行全域搜索,并设计了一种基于破坏和重新构造的协同进化局部搜索策略.通过不同问题规模的数据实验和与对比算法的比较分析,验证了所提模型和算法的有效性.This study investigates the hybrid flow shop group scheduling problem with sequence-dependent setup time between groups and job transportation time between machines.A mixed integer linear programming model for minimizing the makespan is established at first.A co-evolutionary memetic algorithm(CMA)is then proposed in view of the problem’s feature.In the CMA,the three sub-problems,namely group scheduling,job scheduling within each group and its assignment at each stage,are coded uniformly,and the chromosome is decoded into a feasible solution based on the idea of load balancing and an improved first-come-first-served strategy.A variety of genetic operators are used to perform a global search during the evolution process,and a collaborative optimization local search strategy based on destruction and reconstruction is designed.Experiments with various problem scales are carried out,and the results verify the efficiency and robustness of the proposed algorithm.

关 键 词：混合流水车间 成组调度 运输时间 协同进化 文化基因算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TH186[自动化与计算机技术—控制科学与工程]