Applying extra-resource analysis to load balancing

Previously, extra-resource analysis has been used to argue that certain on-line algorithms are good choices for solving specific problems because these algorithms perform well with respect to the optimal off-line algorithm when given extra resources. We now introduce a new application for extra-resource analysis: deriving a qualitative divergence between off-line and on-line algorithms. We do this for the load-balancing problem, the problem of assigning a list of jobs on m identical machines to minimize the makespan, the maximum load on any machine. We analyze the worst-case performance of on-line and off-line approximation algorithms relative to performance of the optimal off-line algorithm when the approximation algorithms have k extra machines. Our main results are the following: The Longest-Processing-Time ( ℒ 𝒫 𝒯 ) algorithm will produce a schedule with makespan no larger than that of the optimal off-line algorithm if ℒ 𝒫 𝒯 has at least (4m − 1)/3 machines while the optimal off-line algorithm has m machines. In contrast, no on-line algorithm can guarantee the same with any number of extra machines.