This Article Full Text (PDF) e-companion References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Cai, X. Articles by Zhou, X.

Stochastic Scheduling Subject to Preemptive-Repeat Breakdowns with Incomplete Information

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong
Department of Statistics and Actuarial Science, East China Normal University, Shanghai 200241, China
Department of Actuarial Studies, Macquarie University, Sydney, NSW 2109, Australia
xqcai{at}se.cuhk.edu.hk
xywu{at}stat.ecnu.edu.cn
xzhou{at}efs.mq.edu.au

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 preemptive-repeat 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.

Subject classifications: production/scheduling; stochastic; learning; probability; stochastic model applications; dynamic programming/optimal control; semi-Markov.
History: Received February 2007; revision received July 2008; accepted August 2008.