Bounds for the Optimal Scheduling of n Jobs on m Processors

Abstract

The problem of scheduling n jobs on m identical processors has been introduced by R. McNaughton, but as yet no efficient algorithm has been found for determining an optimal sequencing of jobs. In this paper lower and upper bounds are given for the cost of an optimal schedule. Since the two bounds are not far apart, they may be helpful in practical scheduling problems. A procedure is described for obtaining a schedule which costs less than the given upper bound.