Identification of Bottleneck Elements in Cellular Manufacturing Problem

The cell formation problem which arises in cellular manufacturing can be formulated in graph theoretic terms. The input for a cellular manufacturing problem consists of a set X of m machines and a set Y of p parts and an m × p matrix A = (ai j), where ai j= 1 or 0 according as the part pj is processed on the machine mi. This data can be represented as a bipartite graph G with bipartition X, Y and mi is joined to pj if ai j= 1. Let G1, G2,. . ., Gk be nontrivial connected subgraphs of G such that V(G1), V(G2),. . ., V(Gk ) forms a partition of V(G). Then π = {G1, G2,. . ., Gk} is called a k-cell partition of G. Any edge of G with one end in Gi and the other end in Gj with i * j represents an intercellular movement of a part. The set V(Gi) is called a cell. Any part in a cell which is to be processed by a machine in another cell is called a bottleneck part and any machine which processes a part in another cell is called a bottleneck machine. In this paper we use graph theoretic techniques to develop an efficient algorithm for identifying bottleneck elements with respect to a given solution of the cellular manufacturing problem. If H is the subgraph of G induced by the set of all exceptional edges with respect to the cell partition π, then any vertex of H is a bottleneck element and its degree in H is the strength of the bottleneck elements. Thus the bottleneck elements of high strength identified by our algorithm are to be either duplicated if it is a machine or to be subcontracted if it is a part, in order to ensure a smooth flow in the manufacturing process.