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 image, where c is the number of colors. This improves upon Toveyʹs c-approximation.