TY - GEN
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.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.
PY - 1998
Y1 - 1998
N2 - We give a new efficient approximation algorithm for scheduling precedence constrained jobs on machines with different speeds. The setting is as follows. There are n jobs where job j requires pj units of processing. The jobs are to be scheduled on a set of m machines. Machine i has a speed si; it takes pj/si units of time for machine i to process job j. The precedence constraints on the jobs are given in the form of a partial order. If j≺k, processing of k cannot start until j’s execution if finished. Let Cj denote the completion time of job j. The objective is to find a schedule to minimize Cmax = maxj Cj, conventionally called the makespan of the schedule. We consider non-preemptive schedules where each job is processed on a single machine with no preemptions. Recently Chudak and Shmoys [1] gave an algorithm with an approximation ratio of O(logm) significantly improving the earlier ratio of 0(√m) due to Jaffe [7]. Their algorithm is based on solving a linear programming relaxation of the problem. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n3) time. In the process we also obtain a constant factor approximation algorithm for the special case of precedence constraints induced by a collection of chains. Our algorithm is based on a new lower bound which we believe is of independent interest. By a general result of Shmoys, Wein, and Williamson [10] our algorithm can be extended to obtain an O(log m) approximation ratio even if jobs have release dates.
AB - We give a new efficient approximation algorithm for scheduling precedence constrained jobs on machines with different speeds. The setting is as follows. There are n jobs where job j requires pj units of processing. The jobs are to be scheduled on a set of m machines. Machine i has a speed si; it takes pj/si units of time for machine i to process job j. The precedence constraints on the jobs are given in the form of a partial order. If j≺k, processing of k cannot start until j’s execution if finished. Let Cj denote the completion time of job j. The objective is to find a schedule to minimize Cmax = maxj Cj, conventionally called the makespan of the schedule. We consider non-preemptive schedules where each job is processed on a single machine with no preemptions. Recently Chudak and Shmoys [1] gave an algorithm with an approximation ratio of O(logm) significantly improving the earlier ratio of 0(√m) due to Jaffe [7]. Their algorithm is based on solving a linear programming relaxation of the problem. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n3) time. In the process we also obtain a constant factor approximation algorithm for the special case of precedence constraints induced by a collection of chains. Our algorithm is based on a new lower bound which we believe is of independent interest. By a general result of Shmoys, Wein, and Williamson [10] our algorithm can be extended to obtain an O(log m) approximation ratio even if jobs have release dates.
UR - http://www.scopus.com/inward/record.url?scp=84958764503&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958764503&partnerID=8YFLogxK
U2 - 10.1007/3-540-69346-7_29
DO - 10.1007/3-540-69346-7_29
M3 - Conference contribution
AN - SCOPUS:84958764503
SN - 354064590X
SN - 9783540645900
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 383
EP - 393
BT - Integer Programming and Combinatorial Optimization - 6th International IPCO Conference, 1998, Proceedings
A2 - Andrew Boyd, E.
A2 - Bixby, Robert E.
A2 - Rios-Mercado, Roger Z.
PB - Springer
T2 - 6th International Integer Programming and Combinatorial Optimization Conference, IPCO 1998
Y2 - 22 June 1998 through 24 June 1998
ER -