A General Bounding Scheme for the Permutation Flow-Shop Problem

Branch-and-bound methods are commonly used to find a permutation schedule that minimizes maximum completion time in an m-machine flow-shop. In this paper we describe a classification scheme for lower bounds that generates most previously known bounds and leads to a number of promising new ones as well. After a discussion of dominance relations within this scheme and of the implementation of each bound, we report on computational experience that indicates the superiority of one of the new bounds.