An optimal tree search method for the manufacturing systems cell formation problem

A solution methodology producing exact solutions to the manufacturing systems cell formation problem is presented. A distance matrix representing the closeness between pairs of machines with regard to the parts they process is taken into account. The proposed approach is an optimal tree search method which employs two different bounds; a classical bound for the Quadratic Assignment Problem and a recently proposed one for the Quadratic Transportation Problem, as well as a new heuristic for the cell formation problem. A special tree search was designed in order to reduce the size of the tree, minimize the computational effort required in time consuming calculations and exploit symmetries of the problem. Computational results indicate that the proposed algorithm is very efficient in generating optimal solutions at low computational cost.