Bounds for the Optimal Scheduling of n Jobs on m Processors
- 1 November 1964
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 11 (2) , 268-279
- https://doi.org/10.1287/mnsc.11.2.268
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.Keywords
This publication has 0 references indexed in Scilit: