ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.

Ravi Sethi

doi:10.1287/moor.2.4.320

ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.

Ravi Sethi

Computer Science

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

40 Scopus citations

Abstract

There are n tasks to be scheduled for processing on a set of identical parallel machines. When tasks can be processed in any order, optimal schedules can be constructed in O(n log n) time on any number of identical machines. With arbitrary precedence constraints the problem becomes NP-complete even on one machine. However, for series-parallel precedence constraints an O(n log n) algorithm is known for one machine. It is shown that on two or more machines, the problem is NP-complete even if the precedence constraints are tree-like.

Original language	English (US)
Pages (from-to)	320-330
Number of pages	11
Journal	Mathematics of Operations Research
Volume	2
Issue number	4
DOIs	https://doi.org/10.1287/moor.2.4.320
State	Published - 1977

ASJC Scopus subject areas

General Mathematics
Computer Science Applications
Management Science and Operations Research

Access to Document

10.1287/moor.2.4.320

Cite this

@article{f2df424d9aaf474d987f6c1c5e088119,

title = "ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.",

abstract = "There are n tasks to be scheduled for processing on a set of identical parallel machines. When tasks can be processed in any order, optimal schedules can be constructed in O(n log n) time on any number of identical machines. With arbitrary precedence constraints the problem becomes NP-complete even on one machine. However, for series-parallel precedence constraints an O(n log n) algorithm is known for one machine. It is shown that on two or more machines, the problem is NP-complete even if the precedence constraints are tree-like.",

author = "Ravi Sethi",

year = "1977",

doi = "10.1287/moor.2.4.320",

language = "English (US)",

volume = "2",

pages = "320--330",

journal = "Mathematics of Operations Research",

issn = "0364-765X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "4",

}

TY - JOUR

T1 - ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.

AU - Sethi, Ravi

PY - 1977

Y1 - 1977

N2 - There are n tasks to be scheduled for processing on a set of identical parallel machines. When tasks can be processed in any order, optimal schedules can be constructed in O(n log n) time on any number of identical machines. With arbitrary precedence constraints the problem becomes NP-complete even on one machine. However, for series-parallel precedence constraints an O(n log n) algorithm is known for one machine. It is shown that on two or more machines, the problem is NP-complete even if the precedence constraints are tree-like.

AB - There are n tasks to be scheduled for processing on a set of identical parallel machines. When tasks can be processed in any order, optimal schedules can be constructed in O(n log n) time on any number of identical machines. With arbitrary precedence constraints the problem becomes NP-complete even on one machine. However, for series-parallel precedence constraints an O(n log n) algorithm is known for one machine. It is shown that on two or more machines, the problem is NP-complete even if the precedence constraints are tree-like.

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

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

U2 - 10.1287/moor.2.4.320

DO - 10.1287/moor.2.4.320

M3 - Article

AN - SCOPUS:0017558373

SN - 0364-765X

VL - 2

SP - 320

EP - 330

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 4

ER -

ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this