基于目标增量的无等待流水调度快速迭代贪婪算法

• 作者: 朱夏 李小平 王茜
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 无等待流水调度 目标增量 启发式算法 总完工时间最小
• 年，卷（期）: 2009,（1）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 132-141
• 页数: 10页
• 分类号: TP278
• 字数: 8360字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.00132

摘要

最小化总完工时间无等待流水调度是典型的NP-完全问题,广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式,提出目标增量法,通过目标函数变化量判断新解的优劣,大大降低算法所需计算时间;通过证明启发式算法基本操作的目标增量性质,设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题,构造初始解生成算法,提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例,将提出的FIG算法与目前求解该问题较好的启发式算法PHlp和元启发式算法SRTS、DPSOvnd进行比较,实验结果表明FIG在性能上优于SRTS和PHlp,略逊于DPSOvnd;在效率上优于SRTS和DPSOvnd,略逊于PHlp.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王茜	东南大学计算机科学与工程学院	60	1157	18.0	32.0
2	朱夏	东南大学计算机科学与工程学院	9	212	6.0	9.0
3	李小平		1	20	1.0	1.0