The setup polytope of N‐sparse posets

The setup problem is the following single‐machine scheduling problem:There are n jobs with individual processing times, arbitrary precedence relations andsequence‐dependent setup costs (or changeover times).The setup cost s ef arises in a schedule if job f is processed immediately after job e, e.g., the machine must be cleanedof e and prepared for f. The goal is to find aschedule minimizing the total setup costs (and thus, for changeover times, themakespan).We consider the case of “precedence‐induced” setup costs where a nonzero term s ef occurs only if e and fare unrelated with respect to the precedence relations. Moreover, we assume that the setupcosts depend only on f, i.e., s ef =s f for alle which are unrelated to f. Twospecial cases of the setup problem with precedence‐induced setup costs are the jumpnumberproblem and the bump number problem.We suggest a new polyhedral model for the precedence‐induced setup problem. To everylinear extension L=e 1 e 2 ...e n of a poset P=(P 1 >)with n elements, we associate a 0, 1- vector $$x^L \in \mathbb{R}^P $$ with $$x_e^L =1$$ if and only ife starts a chain in $$L\left( {e=e_1 {\text{ or }}e=e_{i + 1} \parallel e_i } \right)$$ .The setup polytope $$S$$ is the convex hull of the incidence vectors of alllinear extensions of P. For N-sparse posetsP, i.e., posets whose comparability graph isP 4 -sparse, we give a completelinear description of S . The integrality part of the proof employsthe concept of box total dual integrality. Copyright Kluwer Academic Publishers 1999