Approximation schemes for scheduling a maintenance and linear deteriorating jobs

Wenchang Luo, Lin Chen

Research output: Contribution to journalArticle

9 Scopus citations

Abstract

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
Volume8
Issue number2
DOIs
StatePublished - May 2012

Keywords

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

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

  • Cite this