On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem

The asymptotic performance of heuristic algorithms for the multiprocessor scheduling problem is considered. Let r_LS denote the ratio of the makespan of any list schedule to the optimal makespan. Let m denote the number of processors and n the number of jobs. We show that the mean and variance of r_LS have upper bounds which approach 1 and 0, respectively, at a rate of O(m log n/n), under the assumption that job processing times are independent, identically distributed according to any distribution F over (0, ∞) with ∫_(0,∞)e^αtdF(t) < ∞ for some α > 0. If the processing times are distributed over (0, 1], a slightly faster convergence rate of O(m/n) is obtained. Furthermore, we show that almost surely, r_LS approaches 1 at a rate faster than O(m/n^1−β) for any 0 < β < 1. Similar results are also obtained for the Multifit algorithm due to Coffman, Garey and Johnson.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.