具有机器可利用性的双目标置换流水车间调度-《郑州大学学报(工学版)》

文章信息/Info

Title:: Bi-objective Permutation Flow Shop Scheduling with Machine Availability

Author(s):: XUAN H; LI H Y; LI B; School of Management of Zhengzhou University;

Keywords:: Double target replacement of assembly workshop; machine usability; release time; improve genetic algorithm; neighborhood solving mechanism

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

Abstract:: A permutation flow shop scheduling problem with machine availability was studied. An improvedgenetic algorithm was proposed by inlrodlucing CDS heuristic algorithm and local search so that the total weightedcompletion time and total weighted tardiness were minimized.To improve the quality of the initial job processing sequence group,the CDS heuristic algorithm is applied to generale 40%c of the group and the remaining 60% of theinitial job processing sequence group was yielded by random procedure.For the job processing sequence after cross-over and mutation，three generalion schemes of neighborhood solutions based on pair-wise exchange ，single-job in-sertion and multiple-job insertion were designed to carry out local seauch in order lo exlend the seach space. Theproposed improved genetlic algorithm was tested with three genetic algorithm based heuistic algorithms. The resultsshowed that the target improvemenl rale of the proposed algorithm was 5.05% ，3.09%e and 7.33% in the average77.65 s, compares with olher algorithms. Ilt also showed that the proposed algorithm could obtain better target val-ues in a shorter time. With the increase of the problem scale，the improvement effect was better.