TY - GEN
T1 - Scheduling to minimize total weighted completion time
T2 - 5th International Conference Integer Programming and Combinatorial Optimization, IPCO 1996
AU - Schulz, Andreas S.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.
PY - 1996
Y1 - 1996
N2 - There has been recent success in using polyhedral formulations of scheduling problems not only to obtain good lower bounds in practice but also to develop provably good approximation algorithms. Most of these formulations rely on binary decision variables that are a kind of assignment variables. We present quite simple polynomialtime approximation algorithms that are based on linear programming formulations with completion time variables and give the best known performance guarantees for minimizing the total weighted completion time in several scheduling environments. This amplifies the importance of (appropriate) polyhedral formulations in the design of approximation algorithms with good worst-case performance guarantees. In particular, for the problem of minimizing the total weighted completion time on a single machine subject to precedence constraints we present a polynomial-time approximation algorithm with performance ratio better than 2. This outperforms a (4 + ε)-approximation algorithm very recently proposed by Hall, Shmoys, and Wein that is based on time-indexed formulations. A slightly extended formulation leads to a performance guarantee of 3 for the same problem but with release dates. This improves a factor of 5.83 for the same problem and even the 4-approximation algorithm for the problem with release dates but without precedence constraints, both also due to Hall, Shmoys, and Wein. By introducing new linear inequalities, we also show how to extend our technique to parallel machine problems. This leads, for instance, to the best known approximation algorithm for scheduling jobs with release dates on identical parallel machines. Finally, for the flow shop problem to minimize the total weighted completion time with both precedence constraints and release dates we present the first approximation algorithm that achieves a worst-case performance guarantee that is linear in the number of machines. We even extend this to multiprocessor flow shop scheduling. The proofs of these results also imply guarantees for the lower bounds obtained by solving the proposed linear programming relaxations. This emphasizes the strength of linear programming formulations using completion time variables.
AB - There has been recent success in using polyhedral formulations of scheduling problems not only to obtain good lower bounds in practice but also to develop provably good approximation algorithms. Most of these formulations rely on binary decision variables that are a kind of assignment variables. We present quite simple polynomialtime approximation algorithms that are based on linear programming formulations with completion time variables and give the best known performance guarantees for minimizing the total weighted completion time in several scheduling environments. This amplifies the importance of (appropriate) polyhedral formulations in the design of approximation algorithms with good worst-case performance guarantees. In particular, for the problem of minimizing the total weighted completion time on a single machine subject to precedence constraints we present a polynomial-time approximation algorithm with performance ratio better than 2. This outperforms a (4 + ε)-approximation algorithm very recently proposed by Hall, Shmoys, and Wein that is based on time-indexed formulations. A slightly extended formulation leads to a performance guarantee of 3 for the same problem but with release dates. This improves a factor of 5.83 for the same problem and even the 4-approximation algorithm for the problem with release dates but without precedence constraints, both also due to Hall, Shmoys, and Wein. By introducing new linear inequalities, we also show how to extend our technique to parallel machine problems. This leads, for instance, to the best known approximation algorithm for scheduling jobs with release dates on identical parallel machines. Finally, for the flow shop problem to minimize the total weighted completion time with both precedence constraints and release dates we present the first approximation algorithm that achieves a worst-case performance guarantee that is linear in the number of machines. We even extend this to multiprocessor flow shop scheduling. The proofs of these results also imply guarantees for the lower bounds obtained by solving the proposed linear programming relaxations. This emphasizes the strength of linear programming formulations using completion time variables.
UR - http://www.scopus.com/inward/record.url?scp=84947916207&partnerID=8YFLogxK
U2 - 10.1007/3-540-61310-2_23
DO - 10.1007/3-540-61310-2_23
M3 - Conference contribution
AN - SCOPUS:84947916207
SN - 3540613102
SN - 9783540613107
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 301
EP - 315
BT - Integer Programming and Combinatorial Optimization - 5th International IPCO Conference, 1996 Proceedings
A2 - Cunningham, William H.
A2 - McCormick, S.Thomas
A2 - Queyranne, Maurice
PB - Springer Verlag
Y2 - 3 June 1996 through 5 June 1996
ER -