A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines

We consider the problem of minimizing the makespan when scheduling tasks on two uniform parallel machines, where one machine is q times as efficient on each task as is the other. We compute the maximum relative error of the LPT (largest processing time first) heuristic as an explicit function of q. In the special case that the two machines are identical (q = 1), our problem and heuristic reduce to the problem and heuristic analyzed by Graham (Graham, R. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 416–429.).