论文部分内容阅读
最近Chou、Queyranne和Simchi—Levi,Liu分别证明了恒速平行机调度问题和Flow shop调度问题的基于有效作业加权最短处理时间的启发式算法是渐近最优的。本文使用分组机器模型的方法证明:即使对于多机Flow shop加权完成时间调度问题,基于有效作业加权最短处理时间的启发式算法也是渐近最优的。关键词调度,多机Flow shop调度,启发式算法,渐近最优分析