A branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times

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.