An efficient approximation algorithm for minimizing makespan on uniformly related machines

We give a new and efficient approximation algorithm for scheduling precedence-constrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of in machines. Jobs have processing times and machines have speeds. It takes p(j)/s(i) units of time for machine i with speed s(i) to process job j with processing requirement p(j) Precedence constraints between jobs are given in the form of a partial order. If j k, processing of job k cannot start until job j's execution is completed. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule. Chudak and Shmoys (1997, ``Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),{''} pp. 581-590) gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of O(rootm) due to Jaffe (1980, Theoret. Comput. Sci. 26, 1-17). Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n(3)) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest. (C) 2001 Elsevier Science.