Dynamically optimal policies for stochastic scheduling subject to preemptive-repeat machine breakdowns

We consider the problem of finding a dynamically optimal policy to process n jobs on a single machine subject to stochastic breakdowns. We study the preemptive-repeat breakdown model, i.e., if a machine breaks down during the processing of a job, the work done on the job prior to the breakdown is lost and the job will have to be started over again. Our study is built on a general setting, which allows: 1) the uptimes and downtimes of the machine to follow general probability distributions, not necessarily independent of each other; 2) the breakdown process to depend upon the job being processed; and 3) the processing times of the jobs to be random variables following arbitrary distributions. We consider two possible cases for the processing time of a job interrupted by a breakdown: a) it is resampled according to its probability distribution or b) it is the same random variable as that before the breakdown. We introduce the concept of occupying time and find its Laplace and integral transforms. For the problem with resampled processing times, we establish a general optimality equation on the optimal dynamic policy under a unified objective measure. We deduce from the optimality equation the optimal dynamic policies for several problems with well-known criteria, including weighted discounted reward, weighted flowtime, truncated cost, number of tardy jobs under stochastic order, and maximum holding cost. For the problem with same random processing time, we develop the optimal dynamic policy via the theory of bandit process. A set of Gittins indices are derived that give the optimal dynamic policies under the criteria of weighted discounted reward and weighted flowtime.