Splitting versus setup trade-offs for scheduling to minimize weighted completion time
Author
dc.contributor.author
Correa Haeussler, José
Author
dc.contributor.author
Verdugo, Víctor
Author
dc.contributor.author
Verschae, José
Admission date
dc.date.accessioned
2016-12-20T19:40:46Z
Available date
dc.date.available
2016-12-20T19:40:46Z
Publication date
dc.date.issued
2016
Cita de ítem
dc.identifier.citation
Operations Research Letters 44 (2016) 469–473
es_ES
Identifier
dc.identifier.other
10.1016/j.orl.2016.04.011
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/142012
Abstract
dc.description.abstract
We study scheduling problems when jobs can be split and a setup is required before processing each part, to minimize the weighted sum of completion times. Using a simple splitting strategy and a reduction to an orders scheduling problem we derive a 2-approximation algorithm for the case with uniform weights and setups, improving upon previous work. We extend this idea to the general identical machine case and conclude by designing a constant factor approximation algorithm when machines are unrelated.
es_ES
Patrocinador
dc.description.sponsorship
Nucleo Milenio Informacion y Coordinacion en Redes ICM/FIC
P10-024F
EU-IRSES grant EUSACOU
FONDECYT
11140579