| 基于插入-分段的无等待流水作业调度复合启发式算法 |
| |
| 引用本文： | 李亚志,朱夏.基于插入-分段的无等待流水作业调度复合启发式算法[J].东南大学学报(自然科学版),2013(3):483-488. |
| |
| 作者姓名： | 李亚志 朱夏 |
| |
| 作者单位： | 东南大学计算机科学与工程学院;东南大学计算机网络与信息集成教育部重点实验室 |
| |
| 基金项目： | 国家自然科学基金资助项目(61003158) |
| |
| 摘 要： | 为求解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邻域结构的方法则提高了算法性能.
|
| 关 键 词： | 无等待流水作业 总完工时间 邻域结构 启发式算法 |
| 本文献已被 CNKI 等数据库收录！ |
|
