Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

J.R. Correa, A. Marchetti-Spaccamela, J. Matuschke, L. Stougie, O. Svensson, V. Verdugo, J. Verschae

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time before it can be processed. First we show that a natural adaptation of the seminal approximation algorithm for unrelated machine scheduling [11] yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio decreases to 2 in the restricted assignment setting, matching the result for the classic version. Interestingly, we show that our problem cannot be approximated within a factor better than e/e-1 ≈ 1.582 (unless P = NP). This provides some evidence that it is harder than the classic version, which is only known to be inapproximable within a factor 1.5 - ε. Since our 1 + φ bound remains tight when considering the seemingly stronger machine configuration LP, we propose a new job based configuration LP that has an infinite number of variables, one for each possible way a job may be split and processed on the machines. Using convex duality we show that this infinite LP has a finite representation and can be solved in polynomial time to any accuracy, rendering it a promising relaxation for obtaining better algorithms. © 2014 Springer International Publishing Switzerland.

Fingerprint

Job Scheduling
Approximation algorithms
LP Relaxation
Integrality
Scheduling
Formulation
Approximation Algorithms
Lift-and-project
Convex Duality
Golden ratio
Machine Scheduling
Configuration
Setup Times
Polynomials
Rendering
Polynomial time
Assignment
Decrease
Approximation

Bibliographical note

Proceedings title: Integer Programming and Combinatorial Optimization
Publisher: Springer
Place of publication: Cham Heidelberg NewYork Dordrecht London
Editors: J. Lee, J. Vygen

Cite this

Correa, J. R., Marchetti-Spaccamela, A., Matuschke, J., Stougie, L., Svensson, O., Verdugo, V., & Verschae, J. (2014). Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. Lecture Notes in Computer Science, (8494), 249-260. https://doi.org/10.1007/978-3-319-07557-0_21
Correa, J.R. ; Marchetti-Spaccamela, A. ; Matuschke, J. ; Stougie, L. ; Svensson, O. ; Verdugo, V. ; Verschae, J. / Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. In: Lecture Notes in Computer Science. 2014 ; No. 8494. pp. 249-260.
@article{45b1319d43c84e738a485a8770fc44c5,
title = "Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines",
abstract = "We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time before it can be processed. First we show that a natural adaptation of the seminal approximation algorithm for unrelated machine scheduling [11] yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio decreases to 2 in the restricted assignment setting, matching the result for the classic version. Interestingly, we show that our problem cannot be approximated within a factor better than e/e-1 ≈ 1.582 (unless P = NP). This provides some evidence that it is harder than the classic version, which is only known to be inapproximable within a factor 1.5 - ε. Since our 1 + φ bound remains tight when considering the seemingly stronger machine configuration LP, we propose a new job based configuration LP that has an infinite number of variables, one for each possible way a job may be split and processed on the machines. Using convex duality we show that this infinite LP has a finite representation and can be solved in polynomial time to any accuracy, rendering it a promising relaxation for obtaining better algorithms. {\circledC} 2014 Springer International Publishing Switzerland.",
author = "J.R. Correa and A. Marchetti-Spaccamela and J. Matuschke and L. Stougie and O. Svensson and V. Verdugo and J. Verschae",
note = "Proceedings title: Integer Programming and Combinatorial Optimization Publisher: Springer Place of publication: Cham Heidelberg NewYork Dordrecht London Editors: J. Lee, J. Vygen",
year = "2014",
doi = "10.1007/978-3-319-07557-0_21",
language = "English",
pages = "249--260",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",
number = "8494",

}

Correa, JR, Marchetti-Spaccamela, A, Matuschke, J, Stougie, L, Svensson, O, Verdugo, V & Verschae, J 2014, 'Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines', Lecture Notes in Computer Science, no. 8494, pp. 249-260. https://doi.org/10.1007/978-3-319-07557-0_21

Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. / Correa, J.R.; Marchetti-Spaccamela, A.; Matuschke, J.; Stougie, L.; Svensson, O.; Verdugo, V.; Verschae, J.

In: Lecture Notes in Computer Science, No. 8494, 2014, p. 249-260.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

AU - Correa, J.R.

AU - Marchetti-Spaccamela, A.

AU - Matuschke, J.

AU - Stougie, L.

AU - Svensson, O.

AU - Verdugo, V.

AU - Verschae, J.

N1 - Proceedings title: Integer Programming and Combinatorial Optimization Publisher: Springer Place of publication: Cham Heidelberg NewYork Dordrecht London Editors: J. Lee, J. Vygen

PY - 2014

Y1 - 2014

N2 - We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time before it can be processed. First we show that a natural adaptation of the seminal approximation algorithm for unrelated machine scheduling [11] yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio decreases to 2 in the restricted assignment setting, matching the result for the classic version. Interestingly, we show that our problem cannot be approximated within a factor better than e/e-1 ≈ 1.582 (unless P = NP). This provides some evidence that it is harder than the classic version, which is only known to be inapproximable within a factor 1.5 - ε. Since our 1 + φ bound remains tight when considering the seemingly stronger machine configuration LP, we propose a new job based configuration LP that has an infinite number of variables, one for each possible way a job may be split and processed on the machines. Using convex duality we show that this infinite LP has a finite representation and can be solved in polynomial time to any accuracy, rendering it a promising relaxation for obtaining better algorithms. © 2014 Springer International Publishing Switzerland.

AB - We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time before it can be processed. First we show that a natural adaptation of the seminal approximation algorithm for unrelated machine scheduling [11] yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio decreases to 2 in the restricted assignment setting, matching the result for the classic version. Interestingly, we show that our problem cannot be approximated within a factor better than e/e-1 ≈ 1.582 (unless P = NP). This provides some evidence that it is harder than the classic version, which is only known to be inapproximable within a factor 1.5 - ε. Since our 1 + φ bound remains tight when considering the seemingly stronger machine configuration LP, we propose a new job based configuration LP that has an infinite number of variables, one for each possible way a job may be split and processed on the machines. Using convex duality we show that this infinite LP has a finite representation and can be solved in polynomial time to any accuracy, rendering it a promising relaxation for obtaining better algorithms. © 2014 Springer International Publishing Switzerland.

U2 - 10.1007/978-3-319-07557-0_21

DO - 10.1007/978-3-319-07557-0_21

M3 - Article

SP - 249

EP - 260

JO - Lecture Notes in Computer Science

T2 - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

IS - 8494

ER -