Bounds for the Optimal Scheduling of n Jobs on m Processors. Eastman, W. L.; Even, S.; and Isaacs, I. M. MANAGEMENT SCIENCE, 11(2):268--279, November, 1964.
Bounds for the Optimal Scheduling of n Jobs on m Processors [link]Paper  doi  abstract   bibtex   
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.
@article{eastman_bounds_1964,
	title = {Bounds for the {Optimal} {Scheduling} of n {Jobs} on m {Processors}},
	volume = {11},
	url = {http://mansci.journal.informs.org/cgi/content/abstract/11/2/268},
	doi = {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.},
	number = {2},
	urldate = {2008-12-03TZ},
	journal = {MANAGEMENT SCIENCE},
	author = {Eastman, W. L. and Even, S. and Isaacs, I. M.},
	month = nov,
	year = {1964},
	pages = {268--279}
}
Downloads: 0