改进迭代贪婪算法求解可重入流水车间调度问题  

Improved iterated greedy algorithm for reentrant flow shop scheduling problem

作　　者：吴秀丽[1] 李雨馨 匡源 崔建杰 WU Xiuli;LI Yuxin;KUANG Yuan;CUI Jianjie(College of Mechanical Engineering,University of Science and Technology Beijing,Beijing 100083,China)

机构地区：[1]北京科技大学机械工程学院,北京100083

出　　处：《计算机集成制造系统》2024年第7期2364-2380,共17页Computer Integrated Manufacturing Systems

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

摘　　要：可重入混合流水车间是在混合流水车间的基础上增加了可重入特性,具有更高的调度复杂性。为了求解可重入混合流水车间调度问题,首先建立了调度优化模型,优化目标为最小化最大完工时间,然后提出一种带精英调整的学习型迭代贪婪算法(LIG-EA)。LIG-EA算法采用基于工件的编码方式,对重组后的染色体进行解码。种群分为精英个体和普通个体两部分,对精英个体进行精英破坏重建和基于关键工件的染色体调整,对普通个体进行学习机制的构建和普通个体的破坏重建。为提高初始种群质量,采用NEH启发式算法进行种群初始化,并针对可重入混合流水车间的重入特性,在重建操作中增加了插入有效性判断,提高了算法的运行速度。通过大量实验表明LIG-EA算法能够有效求解可重入混合流水车间调度问题。The reentrant hybrid flow shop adds the reentrant feature to the hybrid flow shop and has a higher scheduling complexity.To solve the reentrant hybrid flow shop scheduling problem,a scheduling optimization model was established with the objective of minimizing the maximum completion time,and then a Learning Iterated Greedy algorithm with Elite Adjustment(LIG-EA)was proposed.The LIG-EA algorithm used job-based encoding,and then decoded the reconstituted chromosomes.The population was divided into two parts,elite individuals and ordinary individuals,and elite destruction with reconstruction and chromosome adjustment based on key jobs were carried out for elite individuals,and the construction of learning mechanisms and destruction with reconstruction for ordinary individuals.To improve the initial population quality,the NEH heuristic algorithm was used for population initialization,and the insertion validity judgment was added to the reconstruction operation for the re-entry characteristics of the reentrant hybrid flow shop to improve the speed of the algorithm.Through extensive experiments,the results showed that the LIG-EA algorithm could effectively solve the reentrant hybrid flow shop scheduling problem.

关 键 词：可重入混合流水车间调度 迭代贪婪算法 精英解集构建 关键工件调整 学习机制构建 

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