Minimizing mean flow time with release time constraint

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

doi:10.1016/0304-3975(90)90100-V

Minimizing mean flow time with release time constraint

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

Research output: Contribution to journal › Article › peer-review

57 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 language	English (US)
Pages (from-to)	347-355
Number of pages	9
Journal	Theoretical Computer Science
Volume	75
Issue number	3
DOIs	https://doi.org/10.1016/0304-3975(90)90100-V
State	Published - Oct 1 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(90)90100-V

Cite this

@article{9945cb7d1c1f468a8c619735c3d72b5f,

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 Leung, {Joseph Y.T.} and Young, {Gilbert H.}",

year = "1990",

month = oct,

day = "1",

doi = "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",

}

TY - JOUR

T1 - Minimizing mean flow time with release time constraint

AU - Du, Jianzhong

AU - Leung, Joseph Y.T.

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 - 10.1016/0304-3975(90)90100-V

DO - 10.1016/0304-3975(90)90100-V

M3 - Article

AN - SCOPUS:0025505801

SN - 0304-3975

VL - 75

SP - 347

EP - 355

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

Minimizing mean flow time with release time constraint

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this