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

Xiaoqiang Cai*, Xianyi Wu, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)158-172
Number of pages15
JournalIEEE Transactions on Automation Science and Engineering
Issue number2
Publication statusPublished - Apr 2005
Externally publishedYes


  • Discounted reward
  • Dynamic policy
  • Gittins index
  • Machine breakdowns
  • Min-max criterion
  • Number of tardy jobs
  • Preemptive-repeat
  • Semi-Markov decision process
  • Stochastic scheduling
  • Weighted flow time


Dive into the research topics of 'Dynamically optimal policies for stochastic scheduling subject to preemptive-repeat machine breakdowns'. Together they form a unique fingerprint.

Cite this