| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4651564 | Electronic Notes in Discrete Mathematics | 2016 | 8 Pages |
The input for a cellular manufacturing problem consists of a set X of m machines, a set Y of p parts and an m×pm×p matrix A=(aij)A=(aij), where aij=1aij=1 or 0 according as the part pjpj is processed on the machine mimi. This data can be represented as a bipartite graph with bipartition X, Y where mimi is joined to pjpj if aij=1aij=1. Given a partition π of V(G)V(G) into k subsets V1,V2,...,VkV1,V2,...,Vk such that |Vi|≥2|Vi|≥2 and the induced subgraph 〈V〉〈V〉 is connected, any edge of G with one end in ViVi and other end in VjVj with i≠ji≠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,nKn,Km,n and the wheel WnWn.
