On the Asymptotic Optimality of Multiprocessor Scheduling Heuristics for the Makespan Minimization Problem
Sunan Han, Dawei Hong, Joseph Y.-T. Leung
ORSA Journal on Computing · 1995 · Volume 7 · Issue 2
Abstract
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 α t dF ( 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.
Keywords
probability, scheduling
Enable JavaScript for citation tools and additional paper interactions.