Stochastic scheduling subject to machine breakdowns: The preemptive-repeat model with discounted reward and other criteria

Xiaoqiang Cai*, Xiaoqian Sun, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


We consider the problem of scheduling a set of jobs on a single machine subject to random breakdowns. We focus on the preemptive-repeat model, which addresses the situation where, 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 from the beginning again when the machine resumes its work. We allow that (i) the uptimes and downtimes of the machine follow general probability distributions, (ii) the breakdown process of the machine depends upon the job being processed, (iii) the processing times of the jobs are random variables following arbitrary distributions, and (iv) after a breakdown, the processing time of a job may either remain a same but unknown amount, or be resampled according to its probability distribution. We first derive the optimal policy for a class of problems under the criterion to maximize the expected discounted reward earned from completing all jobs. The result is then applied to further obtain the optimal policies for other due date-related criteria. We also discuss a method to compute the moments and probability distributions of job completion times by using their Laplace transforms, which can convert a general stochastic scheduling problem to its deterministic equivalent. The weighted squared flowtime problem and the maintenance checkup and repair problem are analyzed as applications.

Original languageEnglish
Pages (from-to)800-817
Number of pages18
JournalNaval Research Logistics
Issue number6
Publication statusPublished - Sept 2004
Externally publishedYes


  • Delayed delivery
  • Discounted reward
  • Machine breakdowns
  • Preemptive-repeat
  • Stochastic scheduling
  • Weighted number of tardy jobs
  • Weighted squared flowtime


Dive into the research topics of 'Stochastic scheduling subject to machine breakdowns: The preemptive-repeat model with discounted reward and other criteria'. Together they form a unique fingerprint.

Cite this