Report Number: CS-TR-72-310
Institution: Stanford University, Department of Computer Science
Title: Anomalies in scheduling unit-time tasks.
Author: Kaufman, Marc T.
Date: June 1972
Abstract: In this paper we examine the problem of scheduling a set of
tasks on a system with a number of identical processors.
Several timing anomalies are known to exist for the general
case, in which the execution time can increase when
inter-task constraints are removed or processors are added.
It is shown that these anomalies also exist when tasks are
restricted to be of equal (unit) length. Several,
increasingly restrictive, heuristic scheduling algorithms are
reviewed. The "added processor" anomaly is shown to persist
through all of them, though in successively weaker form.