Minimizing the Number of Exceptional Edges in Cellular Manufacturing Problem

详细信息    查看全文

• 作者：S. Arumugam ^{s.arumugam.klu@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; J. Saral ^{saral2184@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Cellular manufacturing problem ; part grouping ; bipartite graph ; subdivision graph ; exceptional edge
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：53
• 期：Complete
• 页码：465-472
• 全文大小：192 K

文摘

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$m\times p$ matrix A=(a_ij)$A=(a_{ij})$, where 03f399f54fe07" title="Click to view the MathML source">a_ij=1$a_{ij}=1$ or 0 according as the part p_j$p_j$ is processed on the machine f45f359136aed3b5c" title="Click to view the MathML source">m_i$m_i$. This data can be represented as a bipartite graph with bipartition X, Y   where f45f359136aed3b5c" title="Click to view the MathML source">m_i$m_i$ is joined to p_j$p_j$ if 03f399f54fe07" title="Click to view the MathML source">a_ij=1$a_{ij}=1$. Given a partition π   of V(G)$V(G)$ into k   subsets V₁,V₂,...,V_k$V_1,V_2,...,V_k$ such that |V_i|≥2$|V_i|\ge 2$ and the induced subgraph 〈V〉$〈V〉$ is connected, any edge of G   with one end in V_i$V_i$ and other end in V_j$V_j$ with i≠j$i\ne 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 K_n,K_m,n$K_n,K_{m,n}$ and the wheel W_n$W_n$.