Scheduling deteriorating jobs on a single machine subject to breakdowns

Xiaoqiang Cai, Xianyi Wu*, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)
7 Downloads (Pure)


We investigate the problem of scheduling a set of jobs to minimize the expected makespan or the variance of the makespan. The jobs are subject to deteriorations which are expressed as linear increments of the processing requirements. The machine is subject to preemptive-resume breakdowns with exponentially distributed uptimes and downtimes. It has been well known in the classical models that the expectation and variance of the makespan of deteriorating jobs can be minimized analytically by an index policy if no machine breakdowns are involved. Such basic features, however, change dramatically when breakdowns and deteriorations are present together. In this paper, we derive conditions for jobs to be processible in the sense that they will be eventually completed, and the characteristics of the time that a job occupies the machine. We further find that the expected makespan can still be minimized by a simple index policy that is independent of the breakdown process, but this is no longer the case for the variance of the makespan.

Original languageEnglish
Pages (from-to)173-186
Number of pages14
JournalJournal of Scheduling
Issue number2
Publication statusPublished - Apr 2011


Dive into the research topics of 'Scheduling deteriorating jobs on a single machine subject to breakdowns'. Together they form a unique fingerprint.

Cite this