Paper Info
Title
On the Approximability of Single-Machine Scheduling with Precedence Constraints
Abstract
We consider the single-machine scheduling problem to minimize the weighted sum of completion times under precedence constraints. In a series of recent papers, it was established that this scheduling problem is a special case of minimum weighted vertex cover. In this paper, we show that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in the dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining (2-2/f)-approximation algorithms, provided that the set of precedence constraints has fractional dimension of at most f. Our approach yields the best-known approximation ratios for all previously considered special classes of precedence constraints, and it provides the first results for bounded degree and orders of interval dimension 2. On the negative side, we show that the addressed problem remains NP-hard even when restricted to the special case of interval orders. Furthermore, we prove that the general problem, if a fixed cost present in all feasible schedules is ignored, becomes as hard to approximate as vertex cover. We conclude by giving the first inapproximability result for this problem, showing under a widely believed assumption that it does not admit a polynomial-time approximation scheme.
Year
DOI
Venue
2011
10.1287/moor.1110.0512
Math. Oper. Res.
Keywords
DocType
Volume
interval dimension,best-known approximation ratio,Single-Machine Scheduling,special case,general problem,dimension theory,Precedence Constraints,fractional dimension,single-machine scheduling problem,approximation algorithm,precedence constraint,scheduling problem
Journal
36
Issue
ISSN
Citations 
4
0364-765X
10
PageRank 
References 
Authors
0.58
29
4
Name
Order
Citations
PageRank
Christoph Ambühl135718.50
Monaldo Mastrolilli251439.27
Nikolaus Mutsanas3353.00
Ola Svensson434936.31