| 基于总空闲时间增量的无等待流水作业计划优化算法 |
| |
| 引用本文： | 李小平,吴澄.基于总空闲时间增量的无等待流水作业计划优化算法[J].中国科学(E辑),2008(12). |
| |
| 作者姓名： | 李小平 吴澄 |
| |
| 作者单位： | 东南大学计算机科学与工程学院;东南大学计算机网络和信息集成教育部重点实验室;清华大学自动化系; |
| |
| 基金项目： | 国家自然科学基金(批准号:60504029和60672092); 中国高技术研究发展计划(批准号:2008AA04Z103)资助项目 |
| |
| 摘 要： | 将NP难的最小化最长完工时间无等待流水作业计划问题等价转化为最小化总空闲时间的问题.分析任务之间的独立性,给出算法基本算子的目标增量性质,通过计算目标增量而不是整个目标函数值来判断新作业计划的优劣,可将算法的时间复杂度降低1阶.提出生成初始作业计划算法,实验分析出迭代构造解和再改进解的有效方法;构造出有效的快速迭代启发式算法FCH(fast composite heuristic).FCH和目前求解该问题的有效算法比较,实验结果表明,FCH接近目前的最好性能,需要最少的计算时间.FCH可为大规模无等待作业计划、实时调度和重调度等问题提供有效方法.
|
| 关 键 词： | 无等待作业 启发式算法 最长完工时间 禁忌搜索 |
| 本文献已被 CNKI 等数据库收录！ |
|
