Artículos de revistas
Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
Fecha
2015Registro en:
Mathematical Programming Volumen: 154 Número: 1-2 Dec 2015
0025-5610
DOI: 10.1007/s10107-014-0831-8
Autor
Correa Haeussler, José
Marchetti Spaccamela, Alberto
Matuschke, Jannik
Stougie, Leen
Svensson, Ola
Verdugo, Víctor
Verschae Tannenbaum, José
Institución
Resumen
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