Parallel-machine scheduling of deteriorating jobs with potential machine disruptions

Yunqiang Yin, Yan Wang, Edwin Tai Chiu Cheng, Wenqi Liu, Jinhai Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

69 Citations (Scopus)


This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo-polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable.
Original languageEnglish
Pages (from-to)17-28
Number of pages12
JournalOmega (United Kingdom)
Publication statusPublished - 1 Jun 2017


  • Deteriorating jobs
  • Disruptive environment
  • Fully polynomial-time approximation scheme
  • Scheduling

ASJC Scopus subject areas

  • Strategy and Management
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'Parallel-machine scheduling of deteriorating jobs with potential machine disruptions'. Together they form a unique fingerprint.

Cite this