**ABSTRACT**

The main objective of this research is to develop a mathematical computerized approach for designing cellular manufacturing systems. This method is based on extraction and optimizing the initial cells from the similarity coefficient matrix by using eigenvalues and eigenvectors. Furthermore, alternative solutions will be generated by identifying the required number of cells. Part assignment is then done by using any method from the literature. The last step of this developed computerized approach is to choose the optimal solution (s) from the alternative optimal solutions. A program was developed by the researchers to find all the above steps of the developed mathematical computerized approach directly. The optimal solution is the solution which gives the minimum sum of voids and exceptions. This method gives the designer the ability and flexibility of choosing between alternative optimal solutions. To evaluate and compare the performance of our developed mathematical computerized approach with the original mathematical approach, three of the well known methods have been used for this comparison and evaluation (grouping efficiency, grouping efficacy and grouping index). The grouping measures obtained by using our developed computerized approach is better than the results obtained by using the original mathematical approach, which means that our developed computerized approach gives the optimal solution (minimum sum of voids and exceptions).

PDF Abstract XML References Citation

####
**How to cite this article**

*Journal of Applied Sciences, 6: 1915-1923.*

**DOI:**10.3923/jas.2006.1915.1923

**URL:**https://scialert.net/abstract/?doi=jas.2006.1915.1923

**INTRODUCTION**

Many algorithms for cell formation have been developed for the past three decades in cellular manufacturing. Some use binary data for cell formation and others use production data such as operation sequence, processing times, production volumes, etc. for cell formation (Mahesh and Srinivasan, 2002). In a Cellular Manufacturing System (CMS), the parts that are similar in their processing requirements are grouped into part families and the machines that need to process the parts form the machine-cells. Many researchers have developed algorithms for the better formation of cells. Ideally, cells should be designed in such a way that the part families identified are fully processes in a machine-cell so that the machine-cells are mutually independent with no inter-cell movement. In real-life, however, it may not always be economical or practical to prescribe mutually independent cells (Wang and Sarker, 2002). Cellular manufacturing provides an excellent production infrastructure that facilitates the incorporation of basic elements for successful implementation of modern manufacturing technologies, such as Just-In-Time (JIT), Computer Aided Design (CAD), Computer Aided Manufacturing (CAM), Flexible Manufacturing Systems (FMS), Computer Integrated Manufacturing (CIM), etc. (Soleymanpour *et al*., 2002).

Cell formation which involves identification of machine groups and part families is the first step in designing a cellular manufacturing system. A number of cell formation methods have been developed. These methods are classified by Selim *et al*. (1998) into descriptive procedures, **cluster analysis** based procedures, graph partition approaches, **artificial intelligence** approaches and mathematical programming approaches. Generally, the performance of many of the existing methods deteriorates as the problem under consideration becomes larger. Moreover, deciding the number of cells may not be straightforward. In some methods, the number of cells is a dependent variable, while in others it has to be identified in advance (Albadawi *et al*., 2003).

Generally, the cell formation problems are represented in a matrix format named machine-part incident matrix in which all the elements are zero-one and an element 1 (0) indicates that a specific machine is used (not used) to process a specific part (Sarker and Islam, 2000). The problem is equivalent to block diagonalizing a zero-one input matrix. Grouping of components into families and machines into cells results in a transformed matrix with diagonal blocks where ones occupy the diagonal blocks and zeros occupy the off-diagonal blocks. The resulting diagonal blocks represent the manufacturing cells (Nair and Narendran, 1998).

The case where all the ones occupy the diagonal blocks and all the zeros, occupy the off-diagonal blocks is called perfect diagonal blocks. However, this case is rarely accomplished in practice. For that, the most desirable solution of cellular manufacturing systems is that which gives minimum number of zero entries inside a diagonal block (known as voids) and minimum number of one entries outside the diagonal blocks (known as the exceptional elements). A void indicates that a machine assigned to a cell is not required for the processing of a part in the cell. An exceptional element is created when a part requires processing on a machine that is not available in the allocated cell of the part. Voids and exceptional elements have adverse implications in terms of system operations (Adil *et al*., 1996). The implementation of cellular manufacturing has been reported to result in significant benefits for the manufacturing procedure (Dimopoulos and Mort, 2001). One of the difficulties of GT is the objective evaluation of solutions to the part family-machine cell formation problem (Sandbothe, 1998). The effectiveness of a solution is usually measured by its grouping efficiency (Chandrasekharan and Rajagopalan, 1986) or grouping efficacy (Kumar and Chandrasekharan, 1990b) or the total number of voids in the diagonal blocks and the number of ones outside the blocks (Viswanathan, 1995). Several studies related to the part-family and machine-cell formation problems in the context of the cellular manufacturing systems. A review of these studies can be found in Viswanathan (1995), Talluri *et al*. (1997), Eckstein and Rohleder (1998), Selim *et al*. (1998), Adil and Gindy (2000) and Mansour *et al*. (2000).

Albadawi *et al*. (2003), developed a new mathematical approach for designing cellular manufacturing systems. Unfortunately, their method can not always find the optimal solution where the summation of (exceptions+voids) is minimum. For that the objective of this research is to develop a modified mathematical approach for designing cellular manufacturing systems based on their similarity coefficient matrix.

**ALBADAWI et al. APPROACH**

Their approach involves the following major steps (Albadawi *et al*., 2003)

• | Generation of similarity coefficient matrix for the machines. |

• | Extraction of initial cells. |

• | Optimizing the initial cell formation. |

• | Assigning parts to cells using integer programming. |

Similarity coefficient matrix is a mathematical representation that measures the correlation relationship between different machines, represented in a matrix Smxm, where m is the number of machines. Large numbers in the matrix (more than 0.5) indicate a strong relationship between the two machines and vise versa, while number 1 means exactly the same formation of the corresponding machines.

The machine-part matrix can be regarded as a given data set of m different binary patterns. Each pattern corresponds to an n dimensional column vector, where n is the number of parts. Similarity coefficient, Sij between any two machines is defined by the following Eq. 1:

(1) |

Where,

Xijk | = | Operation on Part k performed both on machine i and j. |

Yik | = | Operation on part k performed on machine i. |

Zjk | = | Operation on part k performed on machine j. |

N | = | Number of parts in the original incidence matrix. |

**CRITICAL ANALYSIS OF ALBADAWI et al. APPROACH**

After studying their approach, the following observations were found:

• | The user of this method is forced to use a restricted (specified) number of cells, which is supposed to get the optimal solution. |

• | The optimal solution in their method in reality yields the cells formation for the near optimal solution only. |

The optimal number of cells is the minimum number of voids inside the cells and minimum number of ones outside the cells. To complete the analysis of their approach, the following problem is presented. This problem contains 6-machines and 10-parts and its machine-part matrix is given below in Table 1.

Table 1: | The original incidence matrix for the 6x10 King (1980a) problem |

Table 2: | Similarity coefficient matrix |

Table 3: | The eigenvalues of the similarity coefficient matrix |

Table 4: | Machine-cell matrix (the eigenvectors) |

**Generation of similarity coefficient matrix:** Applying Eq. 1 we get:

Applying the same equation to the machine-component matrix given in Table 1 yielded the similarity coefficient matrix given in Table 2.

**Extraction of initial cells: **To extract out initial cells, we find the eigenvalues and the eigenvectors.

**Eigenvalues:** The word eigenvalue is a mixture of German and English. The German prefix eigen can be translated as proper, which stems from the older literature where eigenvalues were known as proper values; they were also called latent roots (Haward, 1994). Eigenvalues can be obtained using Eq. 2.

(2) |

Where:

det | = | Determinant of the (λI-SCM) matrix. |

SCM | = | Is the similarity coefficient matrix. |

I | = | Is the Identity matrix. |

λ | = | Is the characteristic root (eigenvalue). |

Applying this equation to the similarity matrix in Table 2, we get the matrix as shown below, where S is the similarity matrix.

This is called the characteristic equation of S; the eigenvalues of S can be found by solving Eq. 2 for λ, this yields the following results in Table 3.

**Eigenvectors:** By substituting the eigenvalues found in the last step in Eq. 3, we get the eigenvectors of the similarity coefficient matrix listed in the Table 4.

(3) |

Where, Y is the Eigenvector.

Form matrix theory, the similarity coefficient matrix should have m independent eigenvectors. Each eigenvector represents a cell. To determine how many cells are needed to group machines, the user has two options, either to identify the required number of cells in advance, or consider it as a dependent variable. In both cases, the cells have to be ranked in a descending order according to their corresponding eigenvalues. If the number of cells has to be determined by the user, then cells with highest eigenvalues should be selected. Otherwise, cells with eigenvalues greater than or equal 1 should be selected (Kleinbaum and Kupper, 1978).

The computed eigenvalues for the matrix given in Table 2 are listed in Table 3. Table 4 displays the coefficients that relate the machines to these cells (eigenvectors). Each row of Table 4 consists of the coefficients used to express a machine in terms of the cells. Cells with large coefficients (in absolute value) for a machine are closely related to that machine.

Table 5: | Machine-cell matrix after rotation |

Table 6: | Final cell formation |

No. of exceptions = 2, No. of voids = 7, Σ (e + v) = 9 |

Sometimes, it is difficult to decide whether machine m is related to cell 1 or 2. Thus, to achieve more interpretability, the initial cells corresponding to the resulting eigenvalues have to be optimized.

**Optimizing the initial cell formation:** Although the matrix of initial cells indicates the relationship between the cells and the individual machines, it is usually difficult to identify meaningful cells based on this matrix. Often the machines and cells do not appear correlated in any interpretable pattern. To achieve more interpretability, the initial cells (eigenvectors) corresponding to the resulting eigenvalues are further rotated through one of the many rotation techniques, such as the varimax method (Kleinbaum and Kupper, 1978).

**Varimax rotation:** Varimax (Variance-Maximizing) rotation is also known as Kaiser normalization.

Varimax rotation aims to maximize the sum of variances of squared loadings in the columns of the factor matrix. This produces in each column (Cell) loadings which are either high or near zero. A clever feature of Varimax, as Nunnally (1978) points out, is that the procedure is applied to the loadings squared rather than the actual loadings. As it removes the negative signs in the columns, this also removes the effects of such negatives on the variance, effects which are quite artificial since they depend on how a variable is scored (Paul, 1994).

A program Called (STATISTICA, Release 5.0 A, Copyright© StatSoft, Inc. 1984-1995) was used to perform the Varimax rotation of the matrices in this project.

Applying the Varimax method to the first two initial cells shown in Table 4 yielded the matrix shown in Table 5.

As shown in Table 5, machines 2, 3 and 4 have the highest loading on cell 1, while machines 1, 5 and 6 have the highest loading on cell 2. Therefore, the best grouping for the six machines (using this method) is to group them into two cells. Cell 1 consists of machines 2, 3 and 4, while cell 2 consists of machines 1, 5 and 6.

**Assigning parts to cells:** The last step of this approach is to assign parts to cells. Different criteria could be used to assign parts to cells. For example, if the goal is to minimize the number of exceptional elements, then the following simple **integer programming** model is used, as shown in Eq. 4 below.

(4) |

Subject to:

Where, rkc = 1 if part k is assigned to cell c, 0 otherwise. Nkc is the number of visits to cell c by part k (Albadawi *et al*., 2003).

Applying the model to the problem under consideration has yielded the cell design given in Table 6.

According to their method the optimal number of cells is equal to two and the minimum number of sum of voids and exceptions is equal to nine, which is supposed to be the optimal solution. The question is, can we find another solution for the same problem that gives a value less than 9 ? If such a value is found, this means that their approach does not give the optimal number of cells, i.e., (e+v is less than 9).

Now the developed mathematical computerized approach for designing cellular manufacturing systems will be used to solve the same problem, then the results will be compared according to the sum of (exceptions + voids).

**THE DEVELOPED MATHEMATICAL COMPUTERIZED APPROACH FOR DESIGNING CELLULAR MANUFACTURING SYSTEMS**

The Proposed computerized approach involves the following major steps:

• | Generation of similarity coefficient matrix for the machines. |

• | Extraction of initial cells. |

• | Optimizing the initial cell formation. |

• | Generate alternative solutions. |

• | Assigning parts to cells. |

• | Choose the optimal solution. |

**Generation of similarity coefficient matrix:** The user can apply Eq. 1 discussed above to get the similarity coefficient matrix, which given in the Table 2.

**Extraction of initial cells:** Eigenvalues and eigenvectors can be found using Eq. 2 and 3 to get the results as shown in Table 3 and 4, respectively.

**Optimizing the initial cell formation:** After applying the Varimax rotation (according to this developed method) to the problem included, sometimes; yielding one or more machines that have the loading of less than 0.7, that means the corresponding machine are not highly correlated to that machine. At this case, the user has to solve the problem for that highest loading (s) available, that is at least 0.35 greater than the nearest loading. But if there are many loadings that have values with difference of lower than 0.35, solve the problem for them all.

**Generate alternative solutions:** The eigenvalues and the eigenvectors are shown in the Table 3 and 4, respectively, which were found using the same methodology used in the last method, but it is not a good idea to specify the number of cells that retains the optimal solution according to the values of the eigenvalues that are greater than one. To determine how many cells are needed to group machines, the user must identify the required number of cells in advance, by solving the problem according to the following criteria:

• | If there are at least one of the S1, S2, S3, …, Sn≠0, then solve the problem for (2)~(m – S1 – S2 - …… -Sn) cells; where m is the number of machines included in the problem, while S1, S2, … and Sn, is the exactly similar machines in the original matrix (which have a loading equals to one in the similarity coefficient matrix except of the diagonal), see example (1) in Appendix A. |

• | If all S1, S2, S3, …, Sn = 0, this means that, there is no exact similarity between the machines in the original matrix and the problem has to be solved for (2) ~ (m–1) cells. |

Compare the results, then one of the solutions obtained in this range will be the optimal solution (minimum summation of exceptions and voids).

The same problem [6x10 King (1980a)] will be solved by using our developed mathematical computerized approach. We note that m = 6, while the values of S1, S2, …..,Sn = 0, thus; there is no exactly similar machines in this problem. So; we have to solve this problem for (2)~(6 – 1 = __5__) cells to get the optimal solution.

Table 7: | Machine cell matrix after rotation for two cells |

Table 8: | Machine cell matrix after rotation for three cells |

Table 9: | Machine cell matrix after rotation for four cells |

Table 10: | Machine cell matrix after rotation for five cells |

Applying the varimax rotation method to the initial cells shown in Table 4 yields the matrices shown in Table 7-10, for 2, 3, 4 and 5 cells, respectively.

**Solution for 2 cells:** As shown in Table 7, machines 2, 3 and 4 have the highest loading on cell 1, while machines 1, 5 and 6 have the highest loading on cell 2. {cell 1 = (2 3 4), cell 2 = (1 5 6)}.

**Solution for 3 cells:** As shown in Table 8, machines 2, 3 and 4 have the highest loading on cell 1, machines 5 has the highest loading on cell 2, while machine 1 has the highest loading on cell 3. It is clear that the loading of machine 6 is less than 0.7 in the three cells, so; we have to solve the problem by using machine 6 in the 2 and cell 3, because it has the highest loading in these two cells. {cell 1 = (2 3 4), cell 2 = (5 6), cell 3 = (1)} OR {cell 1 = (2 3 4), cell 2 = (5), cell 3 = (1 6)}.

**Solution for 4 cells:** As shown in Table 9, machines 2, 3 and 4 have the highest loading on cell 1, machine 5 has the highest loading on cell 2, machine 1 has the highest loading on cell 3, while machine 6 has the highest loading on cell 4. {cell 1 = (2 3 4), cell 2 = (5), cell 3 = (1), cell 4 = (6)}.

**Solution for 5 cells:** As shown in Table 10, machines 2, 3 have the highest loading on cell 1, machine 5 has the highest loading on cell 2, machine 1 has the highest loading on cell 3, machine 6 has the highest loading on cell 4, while machine 4 has the highest loading on machine5.{cell 1 = (2 3), cell 2 = (5), cell 3 = (1), cell 4 = (6), cell 5 = (4)}.

**Assigning parts to cells:** The fifth step of our mathematical computerized approach is to assign parts to cells with minimum sum of voids and exceptions.

Different criteria could be used to assign parts to cells. Applying any method from the literature, we get the following results shown in Table 11-15.

**Distribution for 2 cells**

Table 11: | Final cell formation for two cells |

No. of exceptions = 2, No. of voids = 7, Σ (e+v) = 9 |

**Distribution for 3 cells First optimal solution for 3 cells**

Table 12: | Final cell formation for three cells (first optimal solution) |

No. of exceptions = 4, No. of voids = 4, Σ (e + v) = 8 |

**Second optimal solution for 3 cells**

Table 13: | Final cell formation for three cells (second optimal solution) |

No. of exceptions = 4, No. of voids = 4, Σ (e + v) = 8 |

**Distribution for 4 cells**

Table 14: | Final cell formation for four cells |

No. of exceptions = 6, No. of voids = 3, Σ (e + v) = 9 |

**Distribution for 5 cells**

Table 15: | Final cell formation for five cells |

No. of exceptions = 9, No. of voids = 1, Σ (e+v) = 10 |

Table 16: | The first optimal solution |

Σ (e+v) = 8 |

Table 17: | The second optimal solution |

Σ (e+v) = 8 |

Table 18: | The grouping measures for the 6x10 King (1980a) problem |

**Choose the optimal solution:** It is clear that the optimal solution is satisfied when the number of cells = 3 and the corresponding cell formation is given in Table 12 or 13, where, Σ (e+v) = 8. The first optimal solution is given in Table 16 or 17.

In this example, it is obvious that the distribution which yields the optimal solution is satisfied when the number of cells = 3, where the sum of exceptions+voids is equal to 8. Also, it is clear that we have two optimal solutions (Table 16 and 17). This means that a value less than 9 has been found by our developed mathematical computerized approach.

**Evaluation of performance:** To evaluate the performance of the developed mathematical computerized approach and to compare the performance obtained from this method with the original mathematical approach, three of the well known methods will be used for this evaluation (grouping efficiency, grouping efficacy and grouping index.

• | The equation of the grouping efficiency (Chandrasekharan and Rajagopalan, 1986a): |

(5) |

• | The equation of the grouping efficacy (Kumar and Chandrasekharan, 1990): |

(6) |

• | The equation of the grouping index is (Nair and Narendran, 1996) : |

(7) |

Where;

Previous equation can be written in simple form as:

(8) |

Where,

(9) |

q = A weighting factor having a value between zero and one where,

(10) |

Applying these equations to the cell formation from 2 cells to 5 cells, we get the results shown in Table 18 below:

In general; the grouping measures obtained by using our developed mathematical computerized approach is better than the results obtained by using original mathematical approach, which means that our developed mathematical computerized approach gives the optimal solution, i.e., minimum sum of e and v.

**CONCLUSIONS**

By using the original mathematical approach for designing cellular manufacturing systems we find that the claimed optimal solution (in their method) is satisfied when the number of cells equals to two, where the Σ (e+v) = 9; as shown in Table (6), while in reality the optimal solution is satisfied when the number of cells equals to three where the Σ (e+v) = 8 according to the three cell formations shown in Table 16 and 17, by applying our modified mathematical computerized approach for designing cellular manufacturing systems. Therefore it is recommended to use our developed computerized method to get the optimal solution (s) needed, because their approach yields the near optimal solution only. Moreover, our developed computerized approach offers the exact and optimal solution (s), which will give the designer more flexibility to choose between different optimal solutions. Also the designer has the ability to control the cell size. For that our developed computerized approach is useful for small batch oriented production.

Also, it offers the facility designer three choices of part assignment to cells in accordance to his needs (minimum sum of voids and/or exceptions). This assignment will give the designer the flexibility of forming large loose cells and/or small tight cells. The proposed computerized approach can also be used for systems with alternative process plans for the part. Not only does our developed computerized approach provide an optimal solution (s), but also gives the designer the flexibility of choosing the machine (s) inside the cell. Hence, the designer can choose a solution that reduces the affects of some of the physical, technological, or organizational constraints and hence reduces costs.

**Appendix A **Example (1): Table (A1) and (A2) show the original incidence matrix for 15x10 simple Chan and Milner problem (1982) taken from the literature and the similarity coefficient matrix of that problem, respectively.

Table A1: | The original incidence matrix for 15x10 simple Chan and Milner problem (1982) |

Table A2: | The similarity coefficient matrix |

From the similarity coefficient matrix we find that: | |

• | Machines 3 and 14 are exactly the same as machine 1, so; S1 = 2 (Machines 3 and 14). |

• | Machines 9, 10, 13 and 15 are exactly the same as machine 8, so; S2 = 4 (Machines 9, 10, 13 and 15). |

• | Machine 12 is exactly the same as machine 11, so; S3 = 1 (Machine 12). |

• | While m = 15, the number of machines in the original matrix. We conclude that, for the matrix above we have to solve the problem for (2) cells To (m – S1 – S2 - …… - Sn) cells to get the optimal solution. |

Applying the values of m, S1, S2 and S3, we find that:

For the user to find the optimal solution of this problem, he must solve it for (2) ~ (8) cells and one of the six solutions obtained will be the optimal solution.

####
**REFERENCES**

- Adil, B. and N.B.Z. Gindy, 2000. MOCACEF 10 multiple objective capability based approach to form part machine groups for cellular manufacturing applications. Intl. J. Prod. Res., 38: 1133-1161.

Direct Link - Chandrasekharan, M.P. and R. Rajiagopalan, 1986. An ideal seed non hierarchical clustering algorithms for cellular manufacturing. Intl. J. Prod. Res., 24: 457-464.

Direct Link - Chan, H.M. and D.A. Milner, 1982. Direct clustering algorithm for group formation in cellular manufacture. J. Manuf. Syst., 1: 65-75.

CrossRef - Dimopoulos, C. and N. Mort, 2001. A hierarchical clustering methodology based on genetic programming for the solution of simple cell formation problems. Intl. J. Prod. Res., 39: 1-19.

Direct Link - Eckstein, A.L.H. and T.R. Rohleder, 1998. Incorporating human resources in group technology cellular manufacturing. Intl. J. Prod. Res., 36: 1199-1222.

Direct Link - Kumar, C.S. and M.P. Chandrasekharan, 1990. Grouping efficacy a quantities criterion for goodness of block diagonal forms of binary matrices in group technology. Intl. J. Prod. Res., 28: 223-243.

Direct Link - Mahesh, O. and G. Srinivasan, 2002. Incremental cell formation considering alternative machines. Intl. J. Prod. Res., 40: 3291-3310.

Direct Link - Mansour, S.A., S.M. Hussein and S.T. Newman, 2000. A review of the modern approaches to multi criteria cell design. Intl. J. Prod. Res., 38: 1201-1218.

Direct Link - Nair, G.J. and T.T. Narendran, 1996. Grouping index a new quantitative criterion for goodness of block diagonal forms in group technology. Intl. J. Prod. Res., 34: 2767-2782.

Direct Link - Nair, G.J. and T.T. Narendran, 1998. Case a clustering algorithm for cell formation with sequence data. Int. J. Prod. Res., 36: 157-180.

Direct Link - Sandbothe, R.A., 1998. Two observations on the grouping efficacy measure for goodness of block diagonal forms. Int. J. Prod. Res., 36: 3217-3222.

Direct Link - Sarker, B.R. and K.M.S. Islam, 2000. A similarity coefficient measure and machine parts grouping in cellular manufacturing systems. Int. J. Prod. Res., 38: 699-720.

Direct Link - Selim, H.M., R.G. Askin and A.J. Vakharia, 1998. Cell formation in group technology review evaluation and direction for future research. Comp. Ind. Eng. Conf., 34: 3-20.

Direct Link - Soleymanpour, M., P. Vrat and R. Shankar, 2002. A transiently chaotic neural network approach to the design of cellular manufacturing. Intl. J. Prod. Res., 40: 2225-2244.

Direct Link - Viswanathan, S., 1995. Configuring cellular manufacturing systems a quadratic integer programming formulation and a simple interchange heuristic. Intl. J. Prod. Res., 33: 361-376.

Direct Link - Wang, S. and B.R. Sarker, 2002. Locating cells with bottleneck machines in cellular manufacturing systems. Intl. J. Prod. Res., 40: 403-424.

Direct Link - King, J.R., 1980. Machine-component grouping in production flow analysis: An approach using a rank order clustering algorithm. Int. J. Prod. Res., 18: 213-232.

CrossRef