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

Permutation Flow Shop Scheduling Optimization with Step Deterioration

作　　者：轩华[1] 张慧贤 李冰[1] XUAN Hua;ZHANG Hui-xian;LI Bing(School of Management Engineering,Zhengzhou University,Zhengzhou 450001,China;School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

机构地区：[1]郑州大学管理工程学院,河南郑州450001 [2]北京交通大学交通运输学院,北京100044

出　　处：《控制工程》2021年第5期911-917,共7页Control Engineering of China

基　　金：国家自然科学基金资助项目(U1804151,U1604150)。

摘　　要：针对带阶梯恶化的置换流水车间问题(PFSP-SD),考虑到工件的实际加工时间是其开工时间的阶梯函数,提出了一种融合变邻域搜索过程、NEH启发式和遗传算法的混合启发式算法以最小化总拖期。在该算法中,引入基于提前交货期规则的NEH(NEHedd)启发式改进初始种群,设计了遗传算法的部分片段交叉和反转逆序变异操作以得到改进的GA解,进而提出了基于四种邻域生成机制的变邻域搜索过程以进一步提高解的质量。实验测试表明,利用NEHedd生成40%的初始种群效果最好;针对不同规模问题,用NEHedd、NEHedd_GA、VNS以及NEHedd_GA_VNS进行仿真测试。实验结果表明,所提算法能有效提高解的质量,在求解PFSP-SD时具有明显优势。This paper studies permutation flow shop problem with step deterioration(PFSP-SD).Considering that the actual processing time of a job is a step function of its starting time,a hybrid heuristic algorithm is proposed combining variable neighborhood search procedure(VNSP),NEH(Nawas,Enscore and Ham)heuristic and genetic algorithm(GA)to minimize total tardiness.NEH heuristic using early due date rule(NEHedd)is introduced to improve the initial population,and the partial segmentation crossover and reverse mutation operations of genetic algorithm are designed to obtain the improved GA solutions.The variable neighborhood search procedure based on four neighborhood generation schemes are then used to further enhance the solution quality.Experimental tests show that it is best to generate 40%of the initial population with NEHedd.For different scale problems,simulation tests with NEHedd,NEHedd_GA,VNS and NEHedd_GA_VNS show that the proposed algorithm can effectively improve solution quality and have obvious advantages in solving the PFSP-SD.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]