A simple heuristic to minimize makespan on parallel processors with unequal capacities

Jobs with fixed processing times must be assigned to m parallel processors to minimize makespan. There is a limit on the number of jobs that may be assigned to each processor. When these limits are equal, there are several fast and effective heuristics available. However, when processor capacities are not identical, the heuristic performance degrades. The authors present a new simple greedy heuristic for nonidentical limits. The key idea is to forecast makespans from partial solutions. For the case m=2, the heuristic has asymptotically optimal performance.