针对以最小化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.
展开▼
