Manufacturing cell formation by state-space search

Subrata Ghosh, Ambuj Mahanti, Rakesh Nagi, Dana S. Nau

Research output: Contribution to journalArticlepeer-review


This paper addresses the problem of grouping machines in order to design cellular manufacturing cells, with an objective to minimize inter-cell flow. This problem is related to one of the major aims of group technology (GT): to decompose the manufacturing system into manufacturing cells that are as independent as possible. 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 poor solution quality. 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 fast Inter-Cell Traffic Minimization Method to provide good upper bounds, and computes lower bounds based on a relaxation of merging.

Original languageEnglish (US)
Pages (from-to)35-54
Number of pages20
JournalAnnals of Operations Research
StatePublished - 1996
Externally publishedYes


  • Branch-and-bound algorithm
  • Cellular manufacturing
  • Group technology
  • Machine grouping
  • State-space search

ASJC Scopus subject areas

  • General Decision Sciences
  • Management Science and Operations Research


Dive into the research topics of 'Manufacturing cell formation by state-space search'. Together they form a unique fingerprint.

Cite this