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

被引：11

作者：

常俊林

张春慨

邵惠鹤

机构：

[1] 上海交通大学自动化系

来源：

计算机仿真 | 2004年 / 03期

关键词：

优化调度; 并行多机; 启发式算法; 遗传算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：121 / 123+54 +54

页数：4