A new lower bound for the flow shop group scheduling problem

This paper presents a new lower bound that is used to evaluate nodes in a branch and bound procedure for the flow shop group scheduling problem. This lower bound is compared to the one developed by [CIRP Annals, 25 (1976) 419] and tested on small randomly generated problems. A two-phased heuristic procedure is proposed which uses branch and bound in the first phase to develop a family sequence and then uses an interchange procedure in the second phase to develop job within family sequences. The heuristic procedure is tested on larger randomly generated problems. (C) 2001 Elsevier Science Ltd. All rights reserved.