多机flowshop加权完成时间调度问题的渐近最优算法研究

最近chou、queyranne和simchi—levi，liu分别证明了恒速平行机调度问题和flowshop调度问题的基于有效作业加权最短处理时间的启发式算法是渐近最优的。本文使用分组机器模型的方法证明：即使对于多机flowshop加权完成时间调度问题，基于有效作业加权最短处理时间的启发式算法也是渐近最优的。关键词调度，多机flowshop调度，启发式算法，渐近最优分析