The setup polytope of N-sparse posets

Schrader, Rainer and Wambach, Georg (1999) The setup polytope of N-sparse posets.
Published in: Annals of Operations Research Vol. 92. pp. 125-142.


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 numberproblem and the bump number problem. We suggest a new polyhedral model for the precedence-induced setup problem. To every linear extension L = e1 e2 en ... of a poset P = (P1 <) with n elements, we associate a 0, 1-vector x L in R P with xe L = 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.

Full text not available from this repository. (Request a copy)
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr96-248
Depositing User: Rainer Schrader
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 14:59