交货期服从指数分布的单机随机调度问题

工件完成时间与交货期差的绝对值加权和最小化单机随机调度问题是JIT（just-in-time)生产环境下的典型调度模型，是NP－hard问题，然而，当工件权值与加工时间成正比时，LPT（largest processing time）工件调度是问题的最优解，讨论了该问题加工时间和交货期都为随机变量，其中交货期服从指数分布，且工件权值与加工时间成正比的情形，给出了问题的最优解，并在一定条件下将结果推广到机器随机故障的情形。

Stochastic scheduling on single machine with exponentially distributed common due date

The problem of minimizing total weighted deviations of job completion times from a common due date on a single machine is a typical scheduling model in Just-In-Time production environment. It is NP-hard. However, LPT (largest processing time)job schedule is optimal for the case where job weights are proportional to processing times. In this paper, the stochastic counterpart of this problem with proportional weights in which the processing times and the due date are random variables is considered. When the due date is exponentially distributed with an arbitrary positive rate, the optimal solution of the problem is derived. Under some conditions, the result is extended to the situation where the machine is subject to stochastic breakdowns.