We give a new and efficient approximation algorithm for scheduling precedenceconstrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of m 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 โ m 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.