STOCHASTIC SINGLE MACHINE SCHEDULING TO MINIMIZE TOTAL WEIGHTED DEVIATIONS OF COMPLETION TIMES FROM A COMMON DUE DATE WITH PROPORTIONAL WEIGHTS

The deterministic problem of minimizing total weighted deviations of job completion times from a common due date on a single machine (abbreviated to TWD problem) is a typical scheduling model in Just-In-Time production environment. The general TWD problem is NP-hard. However, the LPT (Largest Processing Time) job sequence is optimal for the case where the job weights are proportional to processing times. In this paper, we consider the stochastic counterpart of the TWD problem with proportional weights. The processing times and the due date are exponentially distributed random variables with arbitrary positive rates. It is shown that the LEPT (Largest Expected Processing Time) job sequence is optimal. Moreover, the case where the machine is subject to stochastic breakdowns is also discussed.