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

可重入混合流水车间是在混合流水车间的基础上增加了可重入特性,具有更高的调度复杂性。为了求解可重入混合流水车间调度问题,首先建立了调度优化模型,优化目标为最小化最大完工时间,然后提出一种带精英调整的学习型迭代贪婪算法(LIG-EA)。LIG-EA算法采用基于工件的编码方式,对重组后的染色体进行解码。种群分为精英个体和普通个体两部分,对精英个体进行精英破坏重建和基于关键工件的染色体调整,对普通个体进行学习机制的构建和普通个体的破坏重建。为提高初始种群质量,采用NEH启发式算法进行种群初始化,并针对可重入混合流水车间的重入特性,在重建操作中增加了插入有效性判断,提高了算法的运行速度。通过大量实验表明LIG-EA算法能够有效求解可重入混合流水车间调度问题。