Minimizing the Number of Exceptional Edges in Cellular Manufacturing Problem

The input for a cellular manufacturing problem consists of a set X of m machines, a set Y of p parts and an m×p matrix A=(aij), where aij=1 or 0 according as the part pj is processed on the machine mi. This data can be represented as a bipartite graph with bipartition X, Y where mi is joined to pj if aij=1. Given a partition π of V(G) into k subsets V1,V2,...,Vk such that |Vi|≥2 and the induced subgraph 〈V〉 is connected, any edge of G with one end in Vi and other end in Vj with i≠j, is called an exceptional edges. The cellular manufacturing problem is to find a partition π with minimum number of exceptional edge. In this paper we determine this number for the subdivision graph of Kn,Km,n and the wheel Wn.