带阶梯恶化的置换流水车间调度优化研究

作者：轩华^*; 张慧贤; 李冰

来源：控制工程, 2021, 28(05): 911-917.

DOI：10.14107/j.cnki.kzgc.20190410

• 阶梯恶化
• 置换流水车间
• 总拖期
• NEHedd启发式
• 混合遗传算法
• 变邻域搜索

针对带阶梯恶化的置换流水车间问题(PFSP-SD),考虑到工件的实际加工时间是其开工时间的阶梯函数,提出了一种融合变邻域搜索过程、NEH启发式和遗传算法的混合启发式算法以最小化总拖期。在该算法中,引入基于提前交货期规则的NEH(NEHedd)启发式改进初始种群,设计了遗传算法的部分片段交叉和反转逆序变异操作以得到改进的GA解,进而提出了基于四种邻域生成机制的变邻域搜索过程以进一步提高解的质量。实验测试表明,利用NEHedd生成40%的初始种群效果最好;针对不同规模问题,用NEHedd、NEHeddGA、VNS以及NEHeddGAVNS进行仿真测试。实验结果表明,所提算法能有效提高解的质量,在求解PFSP-SD时具有明显优势。

• 单位
  交通运输学院; 北京交通大学; 郑州大学