The complexity of scheduling starting time dependent tasks with release times

Research output: Journal article publicationJournal articleAcademic researchpeer-review

78 Citations (Scopus)

Abstract

We consider a family of problems of scheduling a set of starting time dependent tasks with release times and linearly increasing/decreasing processing rates on a single machine to minimize the makespan. We first present an equivalence relationship between several pairs of problems. Based on this relationship, we show that the makespan problem with arbitrary release times and identical increasing processing rates is strongly NP-complete and the corresponding case with only one non-zero release time is at least NP-complete in the ordinary sense. On the other hand, the makespan problem with arbitrary release times and identical decreasing processing rates is solvable in O(n6log n) time by a dynamic programming algorithm. Using a different approach, we also show that, when the normal processing times are identical, the makespan problem with arbitrary release times and increasing/decreasing processing rates is strongly NP-complete and the corresponding case with only one non-zero release time is at least NP-complete in the ordinary sense.
Original languageEnglish
Pages (from-to)75-79
Number of pages5
JournalInformation Processing Letters
Volume65
Issue number2
Publication statusPublished - 1 Dec 1998

Keywords

  • Computational complexity
  • Release time
  • Scheduling
  • Sequencing
  • Time dependence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this