Article ID: | iaor201111567 |
Volume: | 36 |
Issue: | 4 |
Start Page Number: | 653 |
End Page Number: | 669 |
Publication Date: | Nov 2011 |
Journal: | Mathematics of Operations Research |
Authors: | Mastrolilli Monaldo, Ambhl Christoph, Mutsanas Nikolaus, Svensson Ola |
Keywords: | job shop, NP-hard, approximation algorithms, vertex cover |
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/