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

摘要：

为求解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