Preemptive scheduling to minimize mean weighted flow time

Joseph Y.T. Leung; Gilbert H. Young

doi:10.1016/0020-0190(90)90229-Q

Preemptive scheduling to minimize mean weighted flow time

Joseph Y.T. Leung
, Gilbert H. Young

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

17 Scopus citations

Abstract

In this note we show that preemptive scheduling to minimize mean weighted flow time is NP-hard even for a set of equal-length tasks.

Original language	English (US)
Pages (from-to)	47-50
Number of pages	4
Journal	Information Processing Letters
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(90)90229-Q
State	Published - Feb 22 1990
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

NP-completeness
NP-hardness
mean weighted flow time
preemptive scheduling

Access to Document

10.1016/0020-0190(90)90229-Q

Cite this

@article{58fc3053a20645de98a28c28ac9e1090,

title = "Preemptive scheduling to minimize mean weighted flow time",

abstract = "In this note we show that preemptive scheduling to minimize mean weighted flow time is NP-hard even for a set of equal-length tasks.",

keywords = "NP-completeness, NP-hardness, mean weighted flow time, preemptive scheduling",

author = "Leung, \{Joseph Y.T.\} and Young, \{Gilbert H.\}",

note = "Funding Information: in part by the ONR grant N00014-87-",

year = "1990",

month = feb,

day = "22",

doi = "10.1016/0020-0190(90)90229-Q",

language = "English (US)",

volume = "34",

pages = "47--50",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Preemptive scheduling to minimize mean weighted flow time

AU - Leung, Joseph Y.T.

AU - Young, Gilbert H.

N1 - Funding Information: in part by the ONR grant N00014-87-

PY - 1990/2/22

Y1 - 1990/2/22

N2 - In this note we show that preemptive scheduling to minimize mean weighted flow time is NP-hard even for a set of equal-length tasks.

AB - In this note we show that preemptive scheduling to minimize mean weighted flow time is NP-hard even for a set of equal-length tasks.

KW - NP-completeness

KW - NP-hardness

KW - mean weighted flow time

KW - preemptive scheduling

UR - https://www.scopus.com/pages/publications/0025386256

UR - https://www.scopus.com/pages/publications/0025386256#tab=citedBy

U2 - 10.1016/0020-0190(90)90229-Q

DO - 10.1016/0020-0190(90)90229-Q

M3 - Article

AN - SCOPUS:0025386256

SN - 0020-0190

VL - 34

SP - 47

EP - 50

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

Preemptive scheduling to minimize mean weighted flow time

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this