加工时间服从均匀分布的单机随机排序问题

Stochastic single machine scheduling with uniform distributed processing times

讨论了工件的加工时间服从均匀分布的单机随机调度问题,目标是使拖后工件数的数学期望最小。采用理论分析的方法,研究了工件的最优加工顺序。结果表明:在(1)工件的权重相等(2)工件的权重与工件的平均加工时间成比例的两种情况下,最短期望加工时间优先规则的不可中断静态优先策略和不可中断动态优先策略是确定使拖后工件数最少的优先策略,并对算法的最优性进行了证明。该成果对非正规目标函数的单机随机排序问题的解决具有一定的参考价值和指导意义。

A single machine 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 from a common due date. By theoretical analysis, the problem formulation of the expected number of tardy jobs can be given and the shortest expected processing time first is optimal in the cases of the equal weighty and the expected processing time is proportional to weighty of the jobs. Non-preemptive static list policy and non-preemptive dynamic policy of the problem are established and the optimality of the algorithms is proved for two special cases which face the equal weighty of jobs and the proportional weighty with processing times.