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 Λ-shaped, i.e., the sequence of wiλi (=wi/E(pi), pi is the processing time of job i) (i=1,2,...,n) has a single local maximum, where wi and λ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.