Operations Research · 1978 · 230 citations · 18 references
ManagementComputer ScienceIndustrial EngineeringAlgorithmsOptimizationSchedulingBranch And BoundCombinatorial OptimizationFlow Shop SchedulingInteger ProgrammingMachine SchedulingScheduling TheoryBoundingBounding FunctionsBounding TechniquesFlow ShopLower BoundsPermutation SchedulesPermutation SchedulingWorst-case Bounds
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.
18
The Complexity of Flowshop and Jobshop Scheduling
M. R. Garey, David Johnson, Ravi Sethi · Mathematics of Operations Research · 1976 · 2.6K citations