Single-machine scheduling with periodic maintenance to minimize makespan

Min Ji, Yong He, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

136 Citations (Scopus)

Abstract

We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers' attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P = NP, which implies that the LPT algorithm is the best possible.
Original languageEnglish
Pages (from-to)1764-1770
Number of pages7
JournalComputers and Operations Research
Volume34
Issue number6 SPEC. ISS.
DOIs
Publication statusPublished - 1 Jun 2007

Keywords

  • Approximation algorithm
  • Non-approximability
  • Nonresumable jobs
  • Periodic maintenance
  • Single-machine scheduling

ASJC Scopus subject areas

  • Information Systems and Management
  • Management Science and Operations Research
  • Applied Mathematics
  • Modelling and Simulation
  • Transportation

Cite this