具有机器可利用性的双目标置换流水车间调度

研究了具有机器可利用性的置换流水车间调度问题,引入CDS启发式算法和局域搜索构造出改进遗传算法,用于同时最小化总加权完成时间和总加权拖期。应用CDS启发式算法产生40%初始工件加工序列群,其余60%的初始工件加工序列群则通过随机程序产生,以此来提高初始工件加工序列群的质量。针对交叉和变异之后的工件加工序列,设计基于两两交换、单工件插入和多工件插入3种邻域解生成机制的局域搜索,以提高解的搜索空间。将所提出的改进遗传算法与基于遗传算法的3种启发式算法进行仿真实验,结果表明:所提算法在平均77.65 s内相对于其他算法的目标改进率分别为5.05%、3.09%、7.33%,这也说明了所提算法在较短的时间内能得到更好的目标值;随着问题规模的增大,改进效果更佳。