×

Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines. (English) Zbl 1377.90034

Goemans, Michel (ed.) et al., Integer programming and combinatorial optimization. 16th international conference, IPCO 2013, Valparaíso, Chile, March 18–20, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36693-2/pbk). Lecture Notes in Computer Science 7801, 387-398 (2013).
Summary: Configuration-LPs have proved to be successful in the design and analysis of approximation algorithms for a variety of discrete optimization problems. In addition, lower bounds based on configuration-LPs are a tool of choice for many practitioners especially those solving transportation and bin packing problems. In this work we initiate a study of linear programming relaxations with exponential number of variables for unrelated parallel machine scheduling problems with total weighted sum of completion times objective. We design a polynomial time approximation scheme to solve such a relaxation for \(R|r_{ij}| \sum w_j C_j\) and a fully polynomial time approximation scheme to solve a relaxation of \(R \| \sum w_j C_j\). As a byproduct of our techniques we derive a polynomial time approximation scheme for the one machine scheduling problem with rejection penalties, release dates and the total weighted sum of completion times objective.
For the entire collection see [Zbl 1258.90003].

MSC:

90B35 Deterministic scheduling theory in operations research
68W25 Approximation algorithms
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI