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

Scope and Purpose: Branch and cut (B&C) is an enumeration technique for solving mixed-integer programs based on the polyhedron that results when the integrality requirements are relaxed. In the last 20 years, this technique has shown great promise when applied to several well known combinatorial optimization problems such as the traveling salesman problem. The success of B&C relies on the ability to generate strong valid inequalities (facets) for the associated polyhedron. In this paper, we discuss several facet-defining inequalities for the problem of scheduling a set of jobs in a flowshop environment where the setup times are sequence dependent. Applications exist in printed circuit board assembly, container manufacturing, and the printing industry, to name a few. We begin by outlining a series of routines for identifying violations of these inequalities when the linear programming relaxation is solved. We then present and evaluate a B&C algorithm for finding exact solutions. When compared with traditional branch and bound, the results demonstrate the superiority of the proposed approach.

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.