Approximation schemes for scheduling a maintenance and linear deteriorating jobs

Wenchang Luo, Lin Chen

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


In this paper, we study two problems of scheduling a set of linear deteriorating non-resumable jobs on a single machine with a mandatory main-tenance. The maintenance has to be started prior to a given deadline. Not only the jobs but also the maintenance are required to be scheduled. Two goals are investigated. One is to minimize the makespan and the other is to minimize the total completion time. For both objectives, we show that two problems are weakly NP-hard and propose fully polynomial time approximation schemes respectively.

Original languageEnglish
Pages (from-to)271-283
Number of pages13
JournalJournal of Industrial and Management Optimization
Issue number2
StatePublished - May 2012


  • Approximation scheme
  • Complexity
  • Deteriorating job
  • Maintenance
  • Scheduling


Dive into the research topics of 'Approximation schemes for scheduling a maintenance and linear deteriorating jobs'. Together they form a unique fingerprint.

Cite this