Minimizing the sum of weighted completion times in a concurrent open shop

Monaldo Mastrolilli(monaldoidsia.ch)
Maurice Queyranne(maurice.queyrannesauder.ubc.ca)
Andreas S. Schulz(schulzmit.edu)
Ola Svensson(olaidsia.ch)
Nelson A. Uhan(nuhanpurdue.edu)

Abstract: We study minimizing the sum of weighted completion times in a concurrent open shop environment. We show several interesting properties of various natural linear programming relaxations for this problem, including that they all have an integrality gap of 2. In addition, we propose a simple combinatorial 2-approximation algorithm that can be viewed as a primal-dual algorithm or a greedy algorithm that starts from the end of the schedule. Finally, we show that this problem is inapproximable within a factor of 6/5 - \epsilon (or within a factor 4/3 - \epsilon if the Unique Games Conjecture is true) for any \epsilon > 0, unless P = NP.

Keywords: scheduling, integrality gap, approximation algorithms, hardness of approximation

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Applications -- OR and Management Sciences (Scheduling )

Citation:

Download: [PDF]

Entry Submitted: 11/11/2008
Entry Accepted: 11/12/2008
Entry Last Modified: 11/11/2008

Modify/Update this entry