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

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

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

英文关键词  distributed  blocking flowshop scheduling  energy consumption cost  local search strategy based on population  iterated greedy algorithm

中文摘要

      在经典分布式流水车间调度问题基础上, 本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(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.