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 m machines. Jobs have processing times and machines have speeds. It takes pj/si units of time for machine i with speed si to process job j with processing requirement pj. 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(n3) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest.
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics