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

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