Abstract

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. © 2006 Elsevier B.V. All rights reserved.