求解一类并行多机调度问题的混合启发式算法

摘要：

该文研究了一类工件具有不同释放时间的并行多机调度问题,调度目标为使总流程时间最小.针对该类调度问题具有强NP-hard的特点,首先构造了的一种启发式算法,该算法能够在很短的时间内找到次优解.由于通常启发式算法会随着问题规模的扩大导致求解的质量有所下降,结合遗传算法的全局搜索能力,提出了一种混合启发式算法进一步改善解的质量.仿真结果表明该算法很好地结合了启发式算法和遗传算法的特点,能够在较短的时间内求解较大规模的调度问题,算法的计算量小,鲁棒性好.

关键词：优化调度、并行多机、启发式算法、遗传算法

所属期刊栏目：21

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划2002 AA412010

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

页数：共4页

页码：121-123,54