On the Approximability of Single-Machine Scheduling with Precedence Constraints

• 成果类型: Article
• 署名作者: Ambuehl, Christoph; Mastrolilli, Monaldo; Mutsanas, Nikolaus; Svensson, Ola
• 署名单位: University of Liverpool; Universita della Svizzera Italiana; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0512
• 发表日期: 2011
• 页码: 653-669
• 关键词: fractional dimension; vertex cover; algorithm; bounds; jobs

摘要

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.