Scheduling chains to minimize mean flow time

Moshe Dror; Wieslaw Kubiak; Paolo Dell'Olmo

doi:10.1016/s0020-0190(97)00037-9

Scheduling chains to minimize mean flow time

Moshe Dror
, Wieslaw Kubiak
, Paolo Dell'Olmo

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

14 Scopus citations

Abstract

In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong sense.

Original language	English (US)
Pages (from-to)	297-301
Number of pages	5
Journal	Information Processing Letters
Volume	61
Issue number	6
DOIs	https://doi.org/10.1016/s0020-0190(97)00037-9
State	Published - Mar 28 1997
Externally published	Yes

Keywords

Analysis of algorithms
Combinatorial problems
Computational complexity

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/s0020-0190(97)00037-9

Cite this

@article{b458c8a951e046d098189c77d6adacbf,

title = "Scheduling chains to minimize mean flow time",

abstract = "In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong sense.",

keywords = "Analysis of algorithms, Combinatorial problems, Computational complexity",

author = "Moshe Dror and Wieslaw Kubiak and Paolo Dell'Olmo",

year = "1997",

month = mar,

day = "28",

doi = "10.1016/s0020-0190(97)00037-9",

language = "English (US)",

volume = "61",

pages = "297--301",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Scheduling chains to minimize mean flow time

AU - Dror, Moshe

AU - Kubiak, Wieslaw

AU - Dell'Olmo, Paolo

PY - 1997/3/28

Y1 - 1997/3/28

N2 - In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong sense.

AB - In this note we consider the chain precedence relation in scheduling and distinguish between strong chains and weak chains. We prove that for two identical parallel processors the mean flow time problem with strong chains can be solved in polynomial time whereas for weak chains the same problem is NP-hard in the strong sense.

KW - Analysis of algorithms

KW - Combinatorial problems

KW - Computational complexity

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

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

U2 - 10.1016/s0020-0190(97)00037-9

DO - 10.1016/s0020-0190(97)00037-9

M3 - Article

AN - SCOPUS:0008480083

SN - 0020-0190

VL - 61

SP - 297

EP - 301

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Scheduling chains to minimize mean flow time

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this