A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

Liying Kang, Chi To Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

46 Citations (Scopus)


In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.
Original languageEnglish
Pages (from-to)180-184
Number of pages5
JournalInternational Journal of Production Economics
Issue number1-2
Publication statusPublished - 1 Sep 2007


  • Deteriorating jobs
  • Fully polynomial-time approximation scheme
  • Parallel-machine scheduling

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this