Approximating Precedence-Constrained Single Machine Scheduling by Coloring

Abstract. This paper investigates the relationship between the dimen-sion theory of partial orders and the problem of scheduling precedence-constrained jobs on a single machine to minimize the weighted comple-tion time. Surprisingly, we show that the vertex cover graph associated to the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory. This equivalence gives new insights on the structure of the problem and allows us to benefit from known results in dimension theory. In particular, the vertex cover graph associated to the scheduling problem can be colored efficiently with at most k colors whenever the associated poset admits a polynomial time computable k-realizer. Based on this approach, we derive new and better approximation algorithms for special classes of precedence constraints, including convex bipartite and semi-orders, for which we give (1 + 1 3)-approximation algorithms. Our technique also generalizes to a richer class of posets obtained by lexicographic sum.