10.3969/j.issn.1001-0505.2013.03.007
基于插入-分段的无等待流水作业调度复合启发式算法
为求解NP-难的总完工时间最小化的无等待流水作业调度问题,提出一种有效复合启发式算法.通过分析基本操作的目标增量性质,构造基于插入-分段(I-S)的邻域结构和操作,提出了基于I-S的复合启发式算法(ISCH).ISCH算法与基于比较的启发式算法(BE)、基于置换的复合启发式算法(PHl(p))、Framinan等提出的复合启发式算法(FNM)和基于可变邻域搜索的混合遗传算法(GA-VNS)的比较结果表明,ISCH算法性能最佳,其平均相对偏差的均值较BE算法降低2.04%,平均运行时间为FNM算法的18.43%.当存在时间约束时,ISCH算法的平均相对偏差较GA-VNS算法降低0.99%.该算法中,目标增量方法的选用降低了运行时间,基于I-S邻域结构的方法则提高了算法性能.
无等待流水作业、总完工时间、邻域结构、启发式算法
43
TP391.7(计算技术、计算机技术)
国家自然科学基金资助项目61003158
2013-07-12(万方平台首次上网日期,不代表论文的发表时间)
共6页
483-488