Stochastic scheduling subject to preemptive-repeat breakdowns with incomplete information

Xiaoqiang Cai*, Xianyi Wu, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

22 Citations (Scopus)


This paper considers the problem of scheduling a set of jobs on a single machine subject to stochastic breakdowns with incomplete information on the probability distributions involved in the decision process. We focus on the preemptiverepeat discipline, under which a machine breakdown leads to the loss of the work done on the job being processed. The breakdown process of the machine is allowed to depend on the job it is processing. The processing times required to complete the jobs, and the machine uptimes and downtimes, are random variables with incomplete information on their probability distributions characterized by unknown parameters. We establish the preemptive-repeat model with incomplete information and investigate its probabilistic characteristics. We show that optimal static policies can be obtained for a wide range of performance measures, which are determined by the prior distributions of the unknown parameters. We derive optimal dynamic policies via Gittins indices represented by the posterior distributions, which are updated adaptively based on processing histories. Under appropriate conditions, the optimal dynamic policies can be calculated by one-step reward rates in a closed form. As a by-product, we also show that our incomplete information model subsumes the traditional preemptive-repeat models with complete information as extreme cases.

Original languageEnglish
Pages (from-to)1236-1249
Number of pages14
JournalOperations Research
Issue number5
Publication statusPublished - Sept 2009


Dive into the research topics of 'Stochastic scheduling subject to preemptive-repeat breakdowns with incomplete information'. Together they form a unique fingerprint.

Cite this