Performance analysis of policy of heuristic for the stochastic flexible flow shop weighted completion time scheduling problem
随机柔性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 scheduling problem.