We analyze the List scheduling algorithm for the problem of minimizing makespan using a worst-average-case or wac analysis
technique, previously used by Kenyon for analyzing the Best Fit bin packing algorithm. We show that List’s worst-average-case
or wac ratio asymptotically approaches 2, as
m→∞. Thus, List’s worst-case behavior is not overly dependent on the order of job arrivals.
Keywords Online scheduling - List scheduling - Makespan - Competitive analysis - Average-case analysis
C.J. Osborn is supported in part by NSF grant CCR 0105283. This work was done while the author was an undergraduate student
at Michigan State University.
E. Torng is supported in part by NSF grant CCR 0105283.