摘要
因实际生产中调度问题的规模很大,分析其近似算法的绝对性能比很难,有时甚至不可能,所以研究近似算法的渐近性能比就很有必要．本文针对随机柔性Flow shop加权完成时间调度问题,使用单机松弛和概率分析方法,证明了基于加权最短期望处理时间需求的启发式策略是渐近最优的．
Due to the large size of scheduling problem in reality, it is more difficult, sometimes impossible, to analyze the absolute performance ratio of its approximation algorithm. It is thus necessary to study the asymptotical performance ratio of approximation algorithm for scheduling problem. By using single machine relaxation and probabilistic analysis, this paper proves that the policy of heuristic based on weighted shortest expected processing requirement is asymptotically optimal for the stochastic flexible flow shop weighted completion time schedulin~ oroblem.
出处
《控制理论与应用》
EI
CAS
CSCD
北大核心
2006年第4期523-525,共3页
Control Theory & Applications
基金
安徽省自然科学基金资助项目(050460404)
中国科学技术大学研究生创新基金资助项目(KD2004056)
关键词
调度
随机柔性Flow
SHOP
启发式策略
渐近最优
scheduling
stochastic flexible Flow shop scheduling
policy of heuristic
asymptotic optimal
