A new branch and bound algorithm for cell formation problem

Cell formation (CF) is the first and the most important problem in designing cellular manufacturing systems. Due to its non-polynomial nature, various heuristic and metaheuristic algorithms have been proposed to solve CF problem. Despite the popularity of heuristic algorithms, few studies have attempted to develop exact algorithms, such as branch and bound (B&B) algorithms, for this problem. We develop three types of branch and bound algorithms to deal with the cell formation problem. The first algorithm uses a binary branching scheme based on the definitions provided for the decision variables. Unlike the first algorithm, which relies on the mathematical model, the second one is designed based on the structure of the cell formation problem. The last algorithm has a similar structure to the second one, except that it has the ability to eliminate duplicated nodes in branching trees. The proposed branch and bound algorithms and a hybrid genetic algorithm are compared through some numerical examples. The results demonstrate the effectiveness of the modified problem-oriented branch and bound algorithm in solving relatively large size cell formation problems.