The asymptotic performance of heuristic algorithms for the multiprocessor scheduling problem is considered. Let rLS denote the ratio 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 rLS 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, rLS approaches 1 at a rate faster than O(m/n1−β) for any 0 < β < 1. Similar results are also obtained for the Multifit algorithm due to Coffman, Garey and Johnson.
