A Level Algorithm for Preemptive Scheduling

Edward C. Horvath, Shui Lam, Ravi Sethi

Research output: Contribution to journalArticlepeer-review

98 Scopus citations


Muntz and Coffman give a level algorithm that constructs optimal preemptive schedules on identical processors when the task system is a tree or when there are only two processors available. Their algorithm is adapted here to handle processors of different speeds. The new algorithm is optimal for independent tasks on any number of processors and for arbitrary task systems on two processors, but not on three or more processors, even for trees. By taking the algorithm as a heuristic on m processors and using the ratio of the lengths of the constructed and optimal schedules as a measure, an upper bound on its performance is derived in terms of the speeds of the processors. It is further shown that 1.23√m is an upper bound over all possible processor speeds and that the 1.23√m bound can be improved at most by a constant factor, by giving an example of a system for which the bound 0.35√m can be approached asymptotically.

Original languageEnglish (US)
Pages (from-to)32-43
Number of pages12
JournalJournal of the ACM (JACM)
Issue number1
StatePublished - Jan 1 1977

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'A Level Algorithm for Preemptive Scheduling'. Together they form a unique fingerprint.

Cite this