Jonathan F. Bard
Graduate Program in Operations Research
University of Texas at Austin
Abstract: This paper presents a branch-and-cut (BAC) algorithm for the exact optimization of the flowshop scheduling problem with setup times, (SDST flowshop). This technique embeds a constraint generation stage (which reduces the size of the region of feasible solutions) into a branch-and-bound (BAB) enumerative scheme. It is found that the BAC approach outperforms the conventional BAB on a set of randomly generated instances representative of real-world data.