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 -