A Note on the Precedence-Constrained Class Sequencing Problem

We give a short proof of a result of Tovey ["Non-approximability of precedence-constrained sequencing to minimize setups," Discrete Appl. Math. 134:351–360, 2004] on the inapproximability of a scheduling problem known as precedence-constrained class sequencing. In addition, we present an approximation algorithm with performance guarantee (c+1)/2, where c is the number of colors. This improves upon Tovey's c-approximation.

The final version of this article can be found at http://dx.doi.org/10.1016/j.dam.2006.03.038.