The setup polytope of N‐sparse posets

R. Schrader and G. Wambach

Annals of Operations Research, 1999, vol. 92, issue 0, 125-142

Abstract: 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

Date: 1999
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018926512983 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:92:y:1999:i:0:p:125-142:10.1023/a:1018926512983

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018926512983

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().