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] yield 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 = N P). 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
Additional Metadata
THEME Other (theme 6)
Publisher Springer
Persistent URL dx.doi.org/10.1007/978-3-319-07557-0_21
Series Lecture Notes in Computer Science
Conference International Conference on Integer Programming and Combinatorial Optimization
Correa, J, Marchetti Spaccamela, A, Matuschke, J, Svensson, O, Stougie, L, Verdugo, V, & Verschae, J. (2014). Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines. In Proceedings of International Conference on Integer Programming and Combinatorial Optimization 2014 (IPCO 17) (pp. 249–260). Springer. doi:10.1007/978-3-319-07557-0_21