TY - JOUR

T1 - An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

AU - Chekuri, Chandra

AU - Bender, Michael

N1 - Funding Information:
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. 2001 Elsevier Science 1A preliminary version of this paper appeared in the “Proceedings of Integer Programming and Combinatorial Optimization (IPCO),” 1998 [1]. 2This work was done while the author was a graduate student at Stanford University, where he was supported by an IBM Cooperative Fellowship. 3This work was done while the author was a graduate student at Harvard University, where he was supported by National Science Foundation grant CCR-95-04436.

PY - 2001/11

Y1 - 2001/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0013027033&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013027033&partnerID=8YFLogxK

U2 - 10.1006/jagm.2001.1184

DO - 10.1006/jagm.2001.1184

M3 - Article

AN - SCOPUS:0013027033

SN - 0196-6774

VL - 41

SP - 212

EP - 224

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -