Strong LP formulations for scheduling splittable jobs on unrelated machines

Abstract : A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different 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+ϕ1+ϕ , where ϕϕ is the golden ratio. Since this bound remains tight for the seemingly stronger machine configuration LP, we propose a new job configuration LP that is based on an infinite continuum of fractional assignments of each job to the machines. We prove that this LP has a finite 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 ee−1≈1.582(unless =)ee−1≈1.582(unless P=NP) , which is larger than the inapproximability bound of 1.5 for the original problem.
Type de document :
Article dans une revue
Mathematical Programming, Springer Verlag, 2015, 154 (1-2), pp.305-328. 〈10.1007/s10107-014-0831-8〉
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01249090
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 31 mai 2017 - 10:00:01
Dernière modification le : mercredi 11 avril 2018 - 01:52:56
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 14:52:39

Fichier

RsplitCmax.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

José Correa, Alberto Marchetti-Spaccamela, Jannik Matuschke, Leen Stougie, Ola Svensson, et al.. Strong LP formulations for scheduling splittable jobs on unrelated machines. Mathematical Programming, Springer Verlag, 2015, 154 (1-2), pp.305-328. 〈10.1007/s10107-014-0831-8〉. 〈hal-01249090〉

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

42