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

摘要

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