求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法  

An iterated greedy algorithm based on population evolution for distributed blocking flowshop scheduling with balanced energy costs criterion

作　　者：韩雪 王玉亭[1] 韩玉艳[1] 李俊青 HAN Xue;WANG Yu-ting;HAN Yu-yan;LI Jun-qing(School of Computer Science,Liaocheng University,Liaocheng Shandong 252000,China;School of Computer Science,Shandong Normal University,Jinan Shandong 250000,China)

机构地区：[1]聊城大学计算机学院,山东聊城252000 [2]山东师范大学计算机学院,山东济南250000

出　　处：《控制理论与应用》2024年第6期1147-1155,共9页Control Theory & Applications

基　　金：国家自然科学基金项目(61803192,62173216,62173356);聊城大学光岳青年学者创新团队项目(LCUGYTD2022–03)资助。

摘　　要：在经典分布式流水车间调度问题基础上,本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP),以均衡各工厂能耗成本为优化目标,提出了基于群体优化的迭代贪婪算法(PEIG).该算法针对零缓冲区和多工厂生产模式,设计了问题特性的启发式方法;针对迭代贪婪算法(IGA)的优势和不足,提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法,以进一步平衡所提算法的全局探索和局部搜索能力.通过270个测试算例的数值仿真,以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性,能为中大规模的DBFSP SDST提供更优的调度方案.Based on the classical distributed flowshop scheduling problem,this paper constructs the mixed linear integer programming mode(MILP)of distributed blocking flowshop scheduling problem with sequence-dependent setup time(DBFSP SDST),and the optimization objective is to balance the energy consumption cost of each factory.To tackle this problem,an iterated greedy algorithm based on the population evolution(PEIG)is proposed.In PEIG,firstly,a problem-specific heuristic is well designed based on the blocking constraint and multiple factories model.Secondly,for the advantages and disadvantages of the traditional IG algorithm,the local search strategies based on the population operation,the multiple neighborhood search structures,and the cross-factory destruction-reconstruction strategy are proposed to further balance the global exploration and exploitation abilities of the proposed algorithm.The 270 test instances numerical simulations and statistical comparison with four representative algorithms show that the proposed algorithm has superior performance and can provide a better scheduling scheme for medium and large-scale DBFSP SDST than the compared algorithms.

关 键 词：分布式 阻塞流水调度 能耗成本 群体局部搜索策略 迭代贪婪算法 

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