Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work

Yunqiang Yin, Jianyou Xu, Edwin Tai Chiu Cheng, Chin Chia Wu, Du Juan Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

35 Citations (Scopus)


We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo-polynomial dynamic programming algorithms and a fully polynomial-time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms.
Original languageEnglish
Pages (from-to)172-183
Number of pages12
JournalNaval Research Logistics
Issue number2
Publication statusPublished - 1 Mar 2016


  • fully polynomial-time approximation scheme
  • late work
  • scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this