引用本文:韩雪,王玉亭,韩玉艳,李俊青.求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法[J].控制理论与应用,2024,41(6):1147~1155.[点击复制]
HAN Xue,WANG Yu-ting,HAN Yu-yan,LI Jun-qing.An iterated greedy algorithm based on population evolution for distributed blocking flowshop scheduling with balanced energy costs criterion[J].Control Theory and Technology,2024,41(6):1147~1155.[点击复制]
求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法
An iterated greedy algorithm based on population evolution for distributed blocking flowshop scheduling with balanced energy costs criterion
摘要点击 662  全文点击 175  投稿时间：2022-10-15  修订日期：2024-02-27
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  DOI: 10.7641/CTA.2023.20900
  2024,41(6):1147-1155
中文关键词  分布式  阻塞流水调度  能耗成本  群体局部搜索策略  迭代贪婪算法
英文关键词  distributed  blocking flowshop scheduling  energy consumption cost  local search strategy based on population  iterated greedy algorithm
基金项目  国家自然科学基金项目(61803192, 62173216, 62173356), 聊城大学光岳青年学者创新团队项目(LCUGYTD2022–03)资助
作者单位E-mail
韩雪 聊城大学 1979123154@qq.com 
王玉亭* 聊城大学 wangyuting@lcu-cs.com 
韩玉艳 聊城大学  
李俊青 山东师范大学  
中文摘要
      在经典分布式流水车间调度问题基础上, 本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(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.