Computational Experience with a Branch-and-Cut Algorithm for Flowshop Scheduling with Setups

Abstract: This paper presents a branch-and-cut (B&C) algorithm for the problem of minimizing the makespan associated with scheduling n jobs in an m-machine flowshop with setup times (SDST flowshop). Two different mathematical formulations are considered. Model A is based on a traveling salesman problem-like formulation. Model B uses fewer binary variables and constraints, but is less structured than model A. A number of valid inequalities, including facet-inducing inequalities, for these two different formulations are evaluated. It was found that the B&C approach outperforms conventional branch and bound. With respect to computational effort, model B proved superior.