Parallel-machine scheduling of simple linear deteriorating jobs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

52 Citations (Scopus)


We consider parallel-machine scheduling problems in which the processing time of a job is a simple linear increasing function of its starting time. The objectives are to minimize the makespan, total machine load, and total completion time. We show that all the problems are strongly NP-hard with an arbitrary number of machines and NP-hard in the ordinary sense with a fixed number of machines. For the former two problems, we prove that there exists no polynomial time approximation algorithm with a constant worst-case bound when the number of machines is arbitrary unless P = N P. When the number of machines is fixed, we propose two similar fully polynomial-time approximation schemes for the former two problems.
Original languageEnglish
Pages (from-to)3761-3768
Number of pages8
JournalTheoretical Computer Science
Issue number38-40
Publication statusPublished - 6 Sept 2009


  • Computational complexity
  • Makespan
  • Parallel-machine scheduling
  • Total machine load
  • Worst-case bound

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Parallel-machine scheduling of simple linear deteriorating jobs'. Together they form a unique fingerprint.

Cite this