基于插入-分段的无等待流水作业调度复合启发式算法

Insertion-segment based composite heuristic algorithm for no-wait flow shop scheduling problems

为求解NP-难的总完工时间最小化的无等待流水作业调度问题,提出一种有效复合启发式算法.通过分析基本操作的目标增量性质,构造基于插入-分段(I-S)的邻域结构和操作,提出了基于I-S的复合启发式算法(ISCH).ISCH算法与基于比较的启发式算法(BE)、基于置换的复合启发式算法(PH1(p))、Framinan等提出的复合启发式算法(FNM)和基于可变邻域搜索的混合遗传算法(GA-VNS)的比较结果表明,ISCH算法性能最佳,其平均相对偏差的均值较BE算法降低2.04%,平均运行时间为FNM算法的18.43%.当存在时间约束时,ISCH算法的平均相对偏差较GA-VNS算法降低0.99%.该算法中,目标增量方法的选用降低了运行时间,基于I-S邻域结构的方法则提高了算法性能.

To solve the NP-hard（no-deterministic polynomial-time hard） no-wait flow shop scheduling problem with total completion time minimization,an effective composite heuristic algorithm is presented.By analyzing the increment properties of fundamental operators and constructing an insertion-segment（I-S） based neighborhood structure and its operation,an insertion-segment based composite heuristic algorithm（ISCH） is proposed.The comparison results of the ISCH algorithm,the heuristic algorithm based on comparison（BE）,the heuristic algorithm based on pair-wise exchange（PH1（p））,the heuristic algorithm presented by Framinan et al.（FNM） and the hybrid genetic algorithm with variable neighborhood search（GA-VNS） show that the ISCH algorithm outperforms the other algorithms.The average value of the average relative percent deviation（ARPD） of the ISCH algorithm is less than that of BE algorithm by 2.04%.And the average computation time of the ISCH algorithm is 18.43% of that of the FNM algorithm.When time is limited,the ARPD of the ISCH algorithm is lower than that of the GA-VNS algorithm by 0.99%.In this algorithm,the increment-properties-based method can decrease the computation time,and the method based on I-S neighborhood structure can enhance the efficiency.