The Flowshop Scheduling Polyhedron with Setup Times

Abstract: This paper presents the polyhedral structure of two different mixed-integer programming representations of the flowshop scheduling problem with sequence-dependent setup times, denoted by SDST flowshop. The first is related to the asymmetric traveling salesman problem polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh, giving what we call the S-G polytope. It is shown that any facet-defining inequality (facet) of either of these polytopes induces a facet for the SDST flowshop polyhedron. Facets for the S-G polytope and valid mixed-integer inequalities based on variable upper-bound flow inequalities for either formulation are developed as well.