Premium
A nonidentical parallel processor scheduling problem
Author(s) -
Hall Nicholas G.,
Rhee K. Anthony,
Rhee Wansoo T.
Publication year - 1988
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(198806)35:3<419::aid-nav3220350310>3.0.co;2-5
Subject(s) - computer science , bin packing problem , job shop scheduling , scheduling (production processes) , mathematical optimization , generalization , heuristic , parallel computing , bin , algorithm , mathematics , schedule , mathematical analysis , operating system
The problem considered in this article is a generalization of the familiar makespan problem, in which n jobs are allocated among m parallel processors, so as to minimize the maximum time (or cost) on any processor. Our problem is more general, in that we allow the processors to have (a) different initial costs, (b) different utilization levels before new costs are incurred, and (c) different rates of cost increase. A heuristic adapted from the bin‐packing problem is shown to provide solutions which are close to optimal as the number of iterations is allowed to increase. Computational testing, over a large number of randomly generated problem instances, suggests that heuristic errors are, on average, very small.