Minimizing mean flow time with release time constraint

Jianzhong Du, Joseph Y.T. Leung, Gilbert H. Young

Research output: Contribution to journalArticlepeer-review

53 Scopus citations

Abstract

We consider the problem of preemptively scheduling a set of n independent tasks with release times on m identical processors with the objective of minimizing the mean flow time. For one processor, Baker gives an O(n log n) time algorithm to find an optimal schedule. Lawler asks the question whether the problem can be shown to be solvable in polynomial time or shown to be NP-hard for m≥2. In this paper we answer this question by showing that it is NP-hard for each fixed m≥2.

Original languageEnglish (US)
Pages (from-to)347-355
Number of pages9
JournalTheoretical Computer Science
Volume75
Issue number3
DOIs
StatePublished - Oct 1 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Minimizing mean flow time with release time constraint'. Together they form a unique fingerprint.

Cite this