Parallel-machine scheduling of simple linear deteriorating jobs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

46 Citations (Scopus)

Abstract

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
Volume410
Issue number38-40
DOIs
Publication statusPublished - 6 Sep 2009

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this