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

50 Citations (Scopus)

Abstract

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
Volume109
Issue number1-2
DOIs
Publication statusPublished - 1 Sept 2007

Keywords

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

ASJC Scopus subject areas

  • General Business,Management and Accounting
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs'. Together they form a unique fingerprint.

Cite this