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

摘要：

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

关键词：无等待流水调度、目标增量、启发式算法、总完工时间最小

所属期刊栏目：32

分类号：TP278(自动化技术及设备)

资助基金：国家自然科学基金60504029,60672092;国家"八六三"高技术研究发展计划项目基金2008AA04Z103

在线出版日期：2009-04-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：132-141