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

Stochastic scheduling on single machine with exponentially distributed common due date

工件完成时间与交货期差的绝对值加权和最小化单机调度问题是 JIT(just- in- time)生产环境下的典型调度模型 ,是 NP- hard问题 .然而 ,当工件权值与加工时间成正比时 ,L PT(largest processing tim e)工件调度是问题的最优解 .讨论了该问题加工时间和交货期都为随机变量 ,其中交货期服从指数分布 ,且工件权值与加工时间成正比的情形 ,给出了问题的最优解 。

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.