The Flow Shop Scheduling Polyhedron with Setup Times

Roger Z. Ríos-Mercado () and Jonathan F. Bard ()
Additional contact information
Roger Z. Ríos-Mercado: Universidad Autónoma de Nuevo León, AP 111—F, Cd. Universitaria
Jonathan F. Bard: University of Texas at Austin

Journal of Combinatorial Optimization, 2003, vol. 7, issue 3, No 7, 318 pages

Abstract: Abstract This paper addresses the problem of improving the polyhedral representation of a certain class of machine scheduling problems. Despite the poor polyhedral representation of many such problems in general, it is shown that notably tighter linear programming representations can be obtained for many important models. In particular, we study the polyhedral structure of two different mixed-integer programming formulations of the flow shop scheduling problem with sequence-dependent setup times, denoted by SDST flow shop. The first is related to the asymmetric traveling salesman problem (ATSP) polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh based on the linear ordering problem (LOP) polytope. The main contribution of this work is the proof that any facet-defining inequality (facet) of either of these polytopes (ATSP and LOP) induces a facet for the corresponding SDST flow shop polyhedron. The immediate benefit of this result is that all developments to date on facets and valid inequalities for both the ATSP and the LOP can be applied directly to the machine scheduling polytope. In addition, valid mixed-integer inequalities based on variable upper-bound flow inequalities for either model are developed as well. The derived cuts are evaluated within a branch-and-cut framework.

Keywords: flow shop scheduling; setup times; polyhedral combinatorics; facet-defining inequalities; asymmetric traveling salesman problem; linear ordering problem (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1023/A:1027372722187 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:7:y:2003:i:3:d:10.1023_a:1027372722187

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1027372722187

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().