ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.

Ravi Sethi

Research output: Contribution to journalArticlepeer-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 languageEnglish (US)
Pages (from-to)320-330
Number of pages11
JournalMathematics of Operations Research
Volume2
Issue number4
DOIs
StatePublished - 1977

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'ON THE COMPLEXITY OF MEAN FLOW TIME SCHEDULING.'. Together they form a unique fingerprint.

Cite this