Stochastic single machine scheduling with an exponentially distributed due date

In this paper, we consider a single machine scheduling problem with random processing times to minimize the expected total weighted deviations of completion times from a random common due date. The processing times and the due date are exponentially distributed. The optimal schedules are shown to be Lambda-shaped, i.e., the sequence of w(t)lambda(t) (= w(t)/E(p(i)), p(i) is the processing time of job i) (i = 1, 2,..., n) has a single local maximum, where w(i) and lambda(i) denote the weight and the processing time rate of job i, respectively. Moreover, the case where the machine is subject to stochastic breakdowns is also discussed. (C) 2001 Elsevier Science B.V, All rights reserved.