Minimizing mean flow time with release time constraint

Jianzhong Du, Joseph Leung, Gilbert H. Young

Research output: Contribution to journalArticle

50 Citations (Scopus)

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

Fingerprint

Release Time
Flow Time
NP-complete problem
Scheduling
Polynomials
Polynomial time
Schedule

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Du, Jianzhong ; Leung, Joseph ; Young, Gilbert H. / Minimizing mean flow time with release time constraint. In: Theoretical Computer Science. 1990 ; Vol. 75, No. 3. pp. 347-355.
@article{c7349164425e4d619bfda8e76d21a0ef,
title = "Minimizing mean flow time with release time constraint",
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.",
author = "Jianzhong Du and Joseph Leung and Young, {Gilbert H.}",
year = "1990",
month = "10",
day = "1",
doi = "https://doi.org/10.1016/0304-3975(90)90100-V",
language = "English (US)",
volume = "75",
pages = "347--355",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "3",

}

Minimizing mean flow time with release time constraint. / Du, Jianzhong; Leung, Joseph; Young, Gilbert H.

In: Theoretical Computer Science, Vol. 75, No. 3, 01.10.1990, p. 347-355.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Minimizing mean flow time with release time constraint

AU - Du, Jianzhong

AU - Leung, Joseph

AU - Young, Gilbert H.

PY - 1990/10/1

Y1 - 1990/10/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025505801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025505801&partnerID=8YFLogxK

U2 - https://doi.org/10.1016/0304-3975(90)90100-V

DO - https://doi.org/10.1016/0304-3975(90)90100-V

M3 - Article

VL - 75

SP - 347

EP - 355

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -