Schrader, Rainer and Wambach, Georg
(1999)
The setup polytope of Nsparse posets.
Published in:
Annals of Operations Research Vol. 92.
pp. 125142.
Abstract
The setup problem is the following singlemachine scheduling problem: There are n jobs with individual processing times, arbitrary precedence relations and sequencedependent 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 ''precedenceinduced'' 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 precedenceinduced setup costs are the jump numberproblem and the bump number problem. We suggest a new polyhedral model for the precedenceinduced setup problem. To every linear extension L = e1 e2 en ... of a poset P = (P1 <) with n elements, we associate a 0, 1vector 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 Nsparse posets P, i.e., posets whose comparability graph is P4sparse, 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)
Export as: 

Editorial actions: 
View Item (Login required) 