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 in 1976 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.