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

• 作者: 朱夏 李亚志
• 来源期刊: 东南大学学报（自然科学版）
• 学科: 工学
• 关键词: 无等待流水作业 总完工时间 邻域结构 启发式算法
• 年，卷（期）: 2013,（3）
• 页码范围: 483-488
• 页数: 6页
• 分类号: TP391.7
• 字数: 4949字
• 语种: 中文
• DOI: 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邻域结构的方法则提高了算法性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李亚志	东南大学计算机科学与工程学院	1	3	1.0	1.0
2	朱夏	东南大学计算机网络与信息集成教育部重点实验室	9	212	6.0	9.0