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
Other (theme 6)
Lecture Notes in Computer Science
International Conference on Integer Programming and Combinatorial Optimization
Life Sciences and Health

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