单机随机调度最优解的Λ形特征

Λ SHAPED PROPERTY OF OPTIMAL SOLUTION FOR STOCHASTIC SINGLE MACHINE SCHEDULING

讨论具有随机加工时间的单机调度问题，目的是确定ｎ个工件的一个排序使得完成时间与一公共交货期差的绝对值加权和的期望最小．在假定加工时间和交货期都服从负指数分布时，建立了此随机调度问题等价的确定形式，并讨论了最优解的Λ形特征．然后，在一定条件下将上述结果推广到机器随机故障的情形．

We consider a problem of scheduling n jobs with random processing times on a single machine in order to minimize the expected total weighted absolute deviations of completion times about a common due date.The deterministic equivalent of the stochastic scheduling is derived when the processing times and the due date are exponentially distributed,and Λ shaped property of the optimal sequences is established.Under appropriate assumptions,the results are extended to the situation where the machine is subject to stochastic breakdowns.