| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 基于目标增量的无等待流水调度快速迭代贪婪算法 |
| 作者 | 朱夏 李小平 王茜 |
| 作者单位 | (东南大学计算机科学与工程学院 南京 210096) (计算机网络和信息集成教育部重点实验室 南京 210096) |
| 发表年份 | 2009 |
| 发表月份 | 1期(132—141) |
| 文章摘要 | 摘要 最小化总完工时间无等待流水调度是典型的NP-完全问题，广泛存在于实际生产系统.改变传统求解调度序列目标函数的模式，提出目标增量法，通过目标函数变化量判断新解的优劣，大大降低算法所需计算时间；通过证明启发式算法基本操作的目标增量性质，设计两种基本目标增量法以快速评估新产生解的质量.提出快速迭代贪婪算法FIG(Fast Iterative Greedy algorithm)求解该问题，构造初始解生成算法，提出分段式重构局部搜索方法和迭代改进全局搜索策略以进一步提高解的质量.基于110个经典Benchmark实例，将提出的FIG算法与目前求解该问题较好的启发式算法PH1p和元启发式算法SRTS、DPSOvnd进行比较，实验结果表明FIG在性能上优于SRTS和PH1p，略逊于DPSOvnd；在效率上优于SRTS和DPSOvnd，略逊于PH1p. 关键词：无等待流水调度；目标增量；启发式算法；总完工时间最小 DOI号: 10.3724/SP.J.1016.2009.00132 |