Manufacturing Cell Formation by State-Space Search

Abstract

This paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize intercell flow. This problem is replaced to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible.<P>This problem is NP-hard. Thus, nonheuristic methods cannot address problems of typical industrial dimensions because they would require exorbitant amounts of computing time, while fast heuristic methods may suffer from sub-optimality.<P>We present a branch-and-bound state-space search algorithm that attempts to overcome both these deficiencies. One of the major strengths of this algorithm is its efficient branching and search strategy. In addition, the algorithm employs the efficient Inter-Cell Traffic Minimization Method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.