Strong LP formulations for scheduling splittable jobs on unrelated machines

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by dierent machines while incurring an arbitrary setup time. In this paper we present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. First we show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same factor. By applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + ⏀, where ⏀ is the golden ratio. Since this bound remains tight for the seemingly stronger machine conguration LP, we propose a new, innite, job conguration LP, that we prove has a nite representation and can be solved in polynomial time up to any accuracy. Interestingly, we show that our problem cannot be approximated within a factor better than e/ (e-1) ~ 1.582 (unless P = NP), which is larger than the inapproximability bound of 1.5 for the original problem.