时间期望错位限制下完工时间和的随机重新排序

Stochastic Rescheduling Problem of Total Completed Time under Expected Time Disruption

讨论了工件加工时间服从任意分布,在时间期望错位下的随机重新排序问题,目标是使期望总完工时间最小.根据理论分析的方法,研究了工件的最优加工顺序.结果表明最短期望加工时间优先规则是使目标达到最小的策略,并由该策略得出多项式时间算法或拟多项式时间算法.

The stochastic rescheduling problem with the processing time from arbitrary distribution under expected time disruption is considered and researched,and the objective is to minimize the expected total completed time.According to theoretical analysis method,we study optimal order of job.The result show that Shortest Expected Processing Time First Rule can minimize the objective,and give polynomial time algorithm and pseudo-polynomial time algorithm.