The setup problem is the following single-machine scheduling problem: There are n jobs with individual processing times, arbitrary precedence relations and sequence-dependent setup costs (or changeover times). The setup cost sef arises in a schedule if job f is processed immediately after job e, e.g., the machine must be cleaned of e and prepared for f. The goal is to find a schedule minimizing the total setup costs (and thus, for changeover times, the makespan). We consider the case of ‘precedence-induced’ setup costs where a nonzero term sef occurs only if e and f are unrelated with respect to the precedence relations. Moreover, we assume that the setup costs depend only on f, i.e., sef = sf for all e which are unrelated to f. Two special cases of the setup problem with precedence-induced setup costs are the jump number problem and the bump number problem. We suggest a new polyhedral model for the precedence-induced setup problem. To every linear extension L = e1e2…en of a poset P = (P1<) with n elements, we associate a 0, 1-vector xL ∈ℝP with xLe = 1 if and only if e starts a chain in L (e = e1 or e = ei+1 ∥ ei). The setup polytope S is the convex hull of the incidence vectors of all linear extensions of P. For N-sparse posets P, i.e., posets whose comparability graph is P4-sparse, we give a complete linear description of S. The integrality part of the proof employs the concept of box total dual integrality.
