带线性恶化工件的零等待流水车间调度  

Zero-wait Flow Shop Scheduling with Linear Deteriorating Jobs

作　　者：轩华[1] 赵凤娟 李冰[1] XUAN Hua;ZHAO Feng-juan;LI Bing(School of Management Engineering,Zhengzhou University Zhengzhou 450001,China)

机构地区：[1]郑州大学管理工程学院,河南郑州450001

出　　处：《控制工程》2021年第12期2305-2311,共7页Control Engineering of China

基　　金：国家自然科学基金资助项目(U1804151,U1604150);河南省科技攻关计划项目(202102310310)。

摘　　要：研究了以最小化总加权完成时间为目标的带线性恶化工件的零等待流水车间调度,其中工件的加工时间表示为开始时间的线性恶化函数,每个工件在不同机器有各自的恶化率。为了对该问题进行求解,提出了一种融合CDS启发式算法、局部搜索和自适应遗传算法的混合启发式算法。引入CDS启发式算法改善初始工件加工序列群,设计遗传参数自适应更新策略以执行交叉和变异算子。为扩展遗传算法解的搜索空间,基于交换和插入操作提出四种邻域结构,以完成局部搜索二次优化过程。最后,通过仿真实验测试不同规模的实例。实验结果表明,所提出的混合启发式算法在求解质量和运行时间方面均有良好表现。The zero-wait flow shop scheduling with deteriorating jobs is studied with the objective of minimizing total weighted completion time. In this problem, the job processing time is denoted by a linear deterioration function of the start time and each job has its deterioration rate on different machines. To solve this problem, a hybrid heuristic algorithm combining CDS heuristic algorithm, local search and adaptive genetic algorithm is proposed. The CDS heuristic algorithm is introduced to improve the initial job processing sequence group and the adaptive updating strategy of genetic parameters is designed to perform crossover and mutation operators. To expand the search space of the genetic algorithm solutions, four neighborhood structures based on exchange and insertion operations are provided to complete re-optimization of the local search.Finally, examples of different scales are tested through simulation experiments. The experimental results show that the proposed hybrid heuristic algorithm has good performance in terms of solution quality and running time.

关 键 词：零等待流水车间 线性恶化工件 总加权完成时间 混合启发式算法 

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