An efficient approximation algorithm for minimizing makespan on uniformly related machines

We give a new efficient approximation algorithm for scheduling precedence constrained jobs on machines with different speeds. The setting is as follows. There are n jobs where job j requires p_j units of processing. The jobs are to be scheduled on a set of m machines. Machine i has a speed si; it takes p_j/s_i units of time for machine i to process job j. The precedence constraints on the jobs are given in the form of a partial order. If j≺k, processing of k cannot start until j’s execution if finished. Let C_j denote the completion time of job j. The objective is to find a schedule to minimize C_max = maxj C_j, conventionally called the makespan of the schedule. We consider non-preemptive schedules where each job is processed on a single machine with no preemptions. Recently Chudak and Shmoys [1] gave an algorithm with an approximation ratio of O(logm) significantly improving the earlier ratio of 0(√m) due to Jaffe [7]. Their algorithm is based on solving a linear programming relaxation of the problem. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n³) time. In the process we also obtain a constant factor approximation algorithm for the special case of precedence constraints induced by a collection of chains. Our algorithm is based on a new lower bound which we believe is of independent interest. By a general result of Shmoys, Wein, and Williamson [10] our algorithm can be extended to obtain an O(log m) approximation ratio even if jobs have release dates.