多机Flow shop加权完成时间调度问题的启发式算法分析

摘要：

因实际生产中调度问题的规模很大,分析其近似算法的绝对性能比很难,有时甚至不可行,所以研究近似算法的渐近性能比就很有必要.本文针对多机Flow shop加权完成时间调度问题,使用单机松弛和概率分析方法,证明了基于加权最短处理时间需求的启发式算法是渐近最优的.

关键词：多机Flow shop调度、启发式算法、渐近最优分析

所属期刊栏目：27

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

资助基金：安徽省自然科学基金050460404;中国科技大学校科研和教改项目KD2004056

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

页数：共4页

页码：1317-1320