Jonathan F. Bard
Graduate Program in Operations Research
University of Texas at Austin
Abstract: This paper presents a branch-and-bound enumeration scheme for the makespan minimization of the permutation flow shop scheduling problem with sequence-dependent setup times. The algorithm includes the implementation of both lower and upper bounding procedures, a dominance elimination criterion, and special features such as a partial enumeration strategy. A computational evaluation of the overall scheme demonstrates the effectiveness of each component. Test results are provided for a wide range of problem instances.