混合迭代贪婪算法求解准时生产分布式流水线调度问题

作者：钱斌^*; 刘荻飞; 胡蓉; 张梓琪

来源：控制与决策, 2022, 37(11): 3042-3051.

DOI：10.13195/j.kzyjc.2021.0426

• 分布式流水线调度
• 总延迟时间
• 混合迭代贪婪算法
• 下界

针对以最小化总延迟时间为优化目标的分布式置换流水线问题(distributed permutation flowshop scheduling problem, DPFSP),建立问题排序模型,并提出混合迭代贪婪算法(hybrid iterated greedy, HIG)进行求解.基于问题特点提出最小工期差值(smallest due date difference value, SDV)规则及3种工厂分配规则,同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法.首先,通过实验确定使用分配规则1将工件向各工厂进行分配,同时结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解;其次,为了增加解的多样性,提出一种关键工厂的移除策略和适用于问题的模拟退火机制;然后,设计基于4种有效邻域操作的两阶段变邻域下降搜索策略,用于在HIG每代中对问题解空间的不同区域进行较深入和细致的搜索;最后,通过仿真实验和算法比较验证了采用HIG求解所提出问题的有效性.

• 单位
  昆明理工大学; 自动化学院