Minimizing the sum of weighted completion times in a concurrent open shop
2010 (English)In: Operations Research Letters, ISSN 0167-6377, Vol. 38, no 5, 390-395 p.Article in journal (Refereed) Published
We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than 6/5 if not equal NP, or strictly less than 4/3 if the Unique Games Conjecture also holds. (C) 2010 Elsevier B.V. All rights reserved.
Place, publisher, year, edition, pages
2010. Vol. 38, no 5, 390-395 p.
Scheduling, Integrality gap, Approximation algorithm, Hardness of approximation
IdentifiersURN: urn:nbn:se:kth:diva-46623DOI: 10.1016/j.orl.2010.04.011ISI: 000282458100012ScopusID: 2-s2.0-77957899966OAI: oai:DiVA.org:kth-46623DiVA: diva2:455140
QC 201111082011-11-082011-11-042011-11-08Bibliographically approved