CAJ | 학술논문

针对以最小化makespan为目标的混合流水车间调度问题，提出了一种两阶段启发式算法。在算法设计中，借鉴求解常规流水车间调度问题的经验，定义了一种相邻交换的邻域结构。算法的第一阶段利用基于排列排序的Nawaz?Enscore?Ham （ NEH）算法求得一个较好的初始解，第二阶段通过邻域搜索来提高解的质量。基于benchmark算例的仿真实验结果表明该算法的有效性，与NEH相比，77个算例的平均偏差降低了2．004％，且其运行时间不超过0．031 s。
침대이최소화makespan위목표적혼합류수차간조도문제，제출료일충량계단계발식산법。재산법설계중，차감구해상규류수차간조도문제적경험，정의료일충상린교환적린역결구。산법적제일계단이용기우배렬배서적Nawaz?Enscore?Ham （ NEH）산법구득일개교호적초시해，제이계단통과린역수색래제고해적질량。기우benchmark산례적방진실험결과표명해산법적유효성，여NEH상비，77개산례적평균편차강저료2．004％，차기운행시간불초과0．031 s。
To solve the hybrid flow shop scheduling problems with makespan criterion, a two?phase heuristic algorithm is presented. In the algorithm design, an adjacent swap neighborhood structure is proposed by using the experience of flow shop scheduling problems for reference. In the first stage, a good initial solution is found by the Nawaz?Enscore?Ham ( NEH) algorithm with permutation schedules. In the second stage, the neighborhood search is used to quickly improve the solution obtained. Last, the experimental results of benchmark instances indicate the effectiveness of the proposed algorithm. Compared with NEH algorithm, the average percentage deviation value by this method is decreased by 2. 004%, and the running time is no longer than 0. 031 s.