随机加工时间的单机随机调度问题

Stochastic single machine scheduling with random processing times

讨论了加工时间服从均匀分布的单机随机调度问题,目标是使拖后工件数的数学期望最小.采用理论分析的方法,给出了期望加权误工任务数的表达式,研究了工件的最优加工顺序.结果表明:在工件的权重和工件的平均加工时间不成比例的最一般的情况下,最短加工时间和最长加工时间优先规则的联合使用给出了使拖后工件数最少的优先策略,并对算法的最优性进行了证明.该成果对于非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义.

A single machine random scheduling with uniform distributed random processing times is considered and the objective is to find an optimal schedule to minimize the expected number of tardy jobs. By theoretical analysis, the problem formulation of the expected number of tardy jobs can be given. The priority policy of joint use of the shortest expected processing time and the longest prcessing time is optimal when the expected processing time is non-proportional to the number of the jobs. The optimality of the algorithms is proved.