1. 서 론

Group technology is recognized as a manufacturing philosophy to improve manufacturing flexibility and production efficiency by grouping parts and machines into families and cells based on similar or dissimilar characteristics. Cellular manufacturing is an application of Group technology that applies the mass production effect to various products and mediumsized production in batch manufacturing systems. As reasons for the establishment of a cellular manufacturing system (CMS), Wemmerlov and Hyer [42] and Wemmerlov and Johnson [43] mention that CMS offers many benefits : reduced throughput time, reduced setup time, reduced work-in-process inventory, improved part/product quality, shortened response time to customer orders and reduced material handling distances/ times. 

The implementation of CMS consists of three phases : (1) cell formation; (2) cell design; and (3) cell management. Cell formation (CF) implements machine-part grouping, cell design decides machine layout and cell management deals with scheduling of groups. Among CMS phases, one of the important problems faced in the implementation of CMS is CF. The three fundamental tasks of CF : (1) grouping parts into families; (2) grouping machines into cells; and (3) assigning of families and cells into groups [34]. The primary objective of CF is to identify part families and machine cells so as to minimize intercellular flows of parts travelling between machine cells [15]. 

CF has received a great deal of attention from researchers and many approaches have been developed. The CF problem is known to be NP-complete [21]. Therefore, most approaches employ methodologies based on heuristics in nature. Recently, meta-heuristics have been introduced as tools producing better solutions in comparison with other traditional methodologies. However, heuristics have the disadvantage of high computational complexity [10]. The trade-off between the quality of solutions and the computational complexity has been an interesting topic to researchers, which means that study on new solution procedures is required to find high quality solutions in low computational time. 

Cluster analysis deals with a sorting problem that allocates m objects into n clusters based on the resemblance relationship on all pairs of objects. Even though cluster analysis has been conducted by various methods, it follows the main procedure as follows [27] : (1) defining a proximity measure : a proximity measure representing the degree of resemblance between two objects is defined; (2) choosing a basis for clustering : clustering criterion is chosen; and (3) identifying seeds : points forming clusters are identified. Srinivasan and Narendran [37] classified cluster analysis with hierarchical and non-hierarchical clustering methods. Hierarchical clustering methods (HCM) are achieved by grouping machines or parts based on the dendogram which is constructed by a resemblance measure. Non-hierarchical clustering methods (NHCM) begin with the initial seeds selected from a resemblance measure, and then repeat the procedure of seeding and clustering. Due to the efficiency and the simplicity of these methods, many researchers have employed cluster analysis for solving CF in CMS since the 1970s. However, methodologies based on cluster analysis have not yielded better solutions in relation to recent intelligent heuristics. 

In order to develop an efficient clustering procedure, this paper proposes a cluster analysis-based approach (CAA) for solving the CF problems considering only processing requirement. The objective of CF is to group machines and parts into cells and families so as to minimize intercellular movements and maximize machine utilization within clusters. CAA is developed by incorporating and modifying two cluster analysis methods, HCM and NHCM. As a reminder of this paper, Section 2 reviews literature and background information related to CF. Section 3 describes the entire procedure of CAA proposed to solve CF in detail. A simple illustrative example is given to depict the application of the proposed approach in Section 4. In Section 5, the performance of the proposed approach is experimented on various CF problems taken from the literature and compared with the existing methodologies. Finally, the conclusions of this paper and future works are discussed in Section 6. 

2. Cell Formation Considering Processing Requirements

2.1 Literature Review

Methodologies based on cluster analysis can be classified into array-based clustering, hierarchical clustering and nonhierarchical clustering [34]. Since Burbidge [4] introduced the first array-based clustering methods (ACM) called the production flow analysis based on group analysis, many approaches based on cluster analysis have been reported. 

ACM, which are suitable for small problems, deal with the rearrangement of columns and rows in a machine-part incidence matrix (MPIM) in order to form non-zeroes into diagonal blocks. McCormick et al. [25] developed the bondenergy algorithm which maximizes the sum of column and row bond energies which are created when the values of adjoining element pairs are equal to one. Rank order clustering (ROC) algorithm [19] is a method to group machines and parts by organizing columns and rows in the order of decreasing binary weights. Rank order clustering 2 [20] is an enhanced ROC which locates rows or columns with entry ‘1’ to the head of the matrix. Chandrasekharan and Rajagopalan [6] proposed a modified ROC which inserts the stage of hierarchical clustering for cells resulting from ROC. Vitanov et al. [41] developed a heuristic rules-based logic algorithm (HERBAL), which can be classified as ACM. The algorithm rearranged each row and column by updating a replica matrix and a cluster seed matrix based on the membership score. 

HCM usually consist of three basic steps : (1) the generation of similarity or dissimilarity coefficients; (2) the construction of the dendogram indicating machine cells or part families at different resemblance levels; and (3) clustering of machines or parts based on the dendogram. McAuley [24] introduced the first HCM called single linkage clustering (SLC), which is based on the Jaccard similarity coefficient, to form groups with the highest similarity. Average linkage clustering (ALC) was adopted by Seifoddini and Wolfe [32, 33]. A group similarity coefficient is defined as the average of Jaccard’s coefficients for all the machines or parts within two clusters. Gupta [14] implemented various HCM such as SLC, ALC, and complete linkage clustering and mentioned that HCM is affected by the chaining problem that means grouping of dissimilar parts into the same family. 

NHCM begins with initial seeds, and then repeat the procedure of seeding and clustering to obtain better machine cells or part families. Chandrasekharan and Rajagopalan [7] introduced the first non-hierarchical procedure called the ideal seed algorithm. The procedure of NHCM includes : (1) generating ideal seeds using a distance measure; and (2) clustering machines and parts from ideal seeds. Also, grouping efficiency was introduced as a measure to evaluate the goodness of block diagolization. ZODIAC [8] is the improved version of the ideal seed algorithm which includes a new generating method of ideal seeds. In this algorithm, ideal seeds are generated by the manipulation of artificial and natural seeds. Srinivasan and Narendran [37] developed GRAFICS based on an assignment clustering model and a maximum density rule (MDR) and mentioned the importance of initial seeds. Srinivasan [38] improved GRAFICS by considering a minimum spanning tree algorithm for the identification of initial seeds. Miltenburg and Zhang [26] compared the existing 9 clustering methods and noted that NHCM are better than ACM and HCM. 

Recently, methodologies based on meta-heuristics have popularly been employed for CF. Papaioannou and Wilson [29] classified meta-heuristics as trajectory methods including simulated annealing (SA) and tabu search (TA) and population- based searches including genetic algorithms (GA), ant colony optimization (ACO) and particle swarm optimization (PSO). 

Trajectory methods search the solution domain from a single-solution-agent. Boctor [3] used a SA approach to deal with large-scale problems. Adil et al. [1] utilized a SA algorithm to solve the proposed assignment allocation algorithm. Zolfaghari and Liang [47] provided the comparative study for SA, GA and TS and reported that SA is better than GA and TS in terms of the grouping efficacy value obtained in a computational time of 10 sec. Lei and Wu [22] proposed TA approach based on HCM and mentioned a similarity coefficient-based method and meta-heuristics as the main approaches for solving CF. Wu et al. [44] and Lin et al. [23] tried to solve the CF problems using SA-based metaheuristics. 

Population-based searches start from multiple agents in parallel. Cheng et al. [11] employed GA, GA-TSP, to solve the cell formation problem formulated as a traveling salesman problem. Dimopoulos and Mort [12] proposed a cluster  clustering method (GP-SLCA) based on genetic programming (GP) known as an evolutionary method and SLC. In GP-SLCA, various similarity coefficients are generated by modifying the Jaccard coefficient through GP, and then these coefficients are input into SLC in order to obtain solutions. Goncalves and Resende [13] considered an approximation of the grouping efficacy in order to assign machines/parts into machine cells/part families at iteration. GA is employed to find the initial machine cells, and the local search is applied to obtain final clusters in the second part. Kao and Li [17] developed a clustering method adopting an ant colony recognition (ACR) algorithm to overcome a chain problem. Spiliopoulos and Sofianopoulou [36] used ACO with an eigenvalue-based bound for soving CF. Tunnukij and Hicks [40] proposed the enhanced algorithm adding a greedy heuristic to a grouping GA to optimize the grouping problems. Anvari et al. [2] developed a PSO-based optimization algorithm with the reduction of intracellular movements and setup time.

Various methodologies have been applied to group machine-part clusters (MPC). An association rule induction (ARI) was applied by Chen [10]. Jeon and Kang [16] investigated a self-organizing map neural networks approach to MPC problems. Kim et al. [18] proposed a heuristic approach using the generalized grouping efficacy. 

2.2 Background

2.2.1 Machine-part Incidence Matrix

MPIM illustrates processing requirements, which is taken from the route cards for parts, between machines and parts [20]. Burbidge [5] mentioned that the relationship of processing requirements between machines and parts in the part routings is useful to identify machine cells and part families. MPIM can be regarded as a data set of any number of different machines and parts and denoted by a matrix M_mxp, where m is the number of machines and p is the number of parts. Each element in MPIM is usually represented by  , which represents an operation for part k on machine i, and may have the entry of ‘0’ or ‘1’. A ‘1’ entry indicates that a part requires processing on a machine, and a ‘0’ entry indicates that a part does not require processing. From MPIM, a similarity coefficient showing the degree of resemblance between two parts or machines, i and j, can be derived and denoted by s_ij.  The resemblance between two machines represents how many identical parts are together processed on the machines. In CF, a similarity coefficient is used to group machines and parts and dealt with as the form of a square matrix that is denoted by SM_mxm. 

2.2.2 Goodness of Clustering

In order to solve CF, all the entries of ‘1’ in MPIM should be collected in the diagonal blocks, and all the entries of ‘0’ should be collected in the off-diagonal blocks, which can be achieved by attempting a block diagonalization. After the block diagonalization, an initial MPIM is converted into a diagonal arrangement of mutually exclusive clusters. However, it is impossible to obtain mutually exclusive clusters in practice. In the block diagonalization, exceptional elements and voids, which indicates ‘1’ in the off-diagonal blocks and ‘0’ in the diagonal blocks respectively, are important factors determining the goodness of the obtained clusters. In CF exceptional elements require extra time/cost and voids can be thought as the opportunity cost. In order to attain quality clusters, exceptional elements and voids should be minimized. Adil et al. [1] mentioned that the trade-off between voids and exceptional elements should be considered in clustering parts and machines. 

In CF literature, various evaluation measures have been reported and many researchers have employed these measures to evaluate their approaches and compare them with other methods. Grouping efficacy [21] and grouping efficiency [7] are the most notable measures in CF. Grouping efficacy quantifies the goodness of clusters based on the number of operations, exceptional elements and voids, and has a scale of zero for the most ill-structured to one for perfect-structured MPIM. However, grouping efficiency shows a value of around 75% even in a very ill-structured matrix [21]. Since grouping efficiency ranges from about 75% to 100% in practice, grouping efficacy has higher priority to grouping efficiency in aspect of the performance evaluation for various-sized MPIM with various difficulties. A grouping efficacy value is improved by the reduction of exceptional elements and voids, which coincides with the objective of CF. Thus, grouping efficacy is very useful as a measure to evaluate the goodness of a solution. This measure is represented as Equation (1) :
 
Where :
e is the number of operations in MPIM
e_e is the number of exceptional elements in MPIM
e_υ is the number of voids in MPIM.

3. Cluster Analysis-based Approach

CAA is based on the procedure of cluster analysis such as the generation of initial seeds and the enhancement of MPC from NHCM as well as the construction of a similarity coefficient matrix and the incorporation of seeds from HCM. The efficiency and simplicity of cluster analysis enable the proposed approach to find high quality solutions within a short amount of time. Yin and Yasuda [46] emphasized that a similarity coefficient-based method is more flexible than other CF methods. Papaioannou and Wilson [29] mentioned that a cluster analysis-based method is simple to implement and can obtain solutions in a reasonable amount of time. CAA consists of four parts : (1) a similarity coefficient matrix is obtained from MPIM; (2) initial clusters are generated from a pairwise exchange clustering (PEC); (3) ALC taken from HCM is employed as a method merging initial clusters in order to form better clusters; and (4) a reverse assignment clustering (RAC) enhances the quality of the solutions obtained from ALC. In particular, CAA does not accept a singleton which has only one machine or part within a cluster. <Figure 1> illustrates the conceptual procedure of CAA. In order to describe CAA, some notations are listed in <Table 1>. 

<Figure 1> The Conceptual Illustration of a Clustering Approach for CF.

3.1 Similarity Coefficient Matrix

CAA starts from constructing a similarity coefficient matrix based on MPIM. A similarity measure is developed by modifying Jaccard’s similarity coefficient which is first in troduced by McAuley [24] in CF. While Jaccard’s similarity considers only parts processed in both machines as a numerator, this paper considers the similarity measure including the parts not processed as well as processed on both machines in order to reduce exceptional elements and voids. This similarity is defined as the ratio of the number of parts having identical coefficients for both machines to the number of parts having a coefficient of ‘1’ in either machine i or j as shown in Equation (2) :
 

Since the constructed matrix has the largest value in the diagonal location, it always leads an assignment of each machine into a cluster including only itself. Thus, the coefficients in the diagonal location have to be replaced with ‘0’  to prevent a self-loop. And then, in order to consider the correlation with all machines in the similarity coefficient matrix, the similarity coefficients are modified by double centering transformation as ms_ij = s_ij ― s_ⅰ ― s_ⅰ + s_... The final matrix is constructed by calculating ms_ij in the row i and column j and has a symmetric square form where the sum of each row and column is equal to zero. In the next step the obtained matrix is used as input data to generate initial MPC.

<Table 1> List of Notations.

3.2 Pairwise Exchange Clustering

Since the solution obtained from NHCM is affected by initial seeds, many researchers have employed various methodologies in order to generate better initial seeds. In the CF literature, an assignment problem has been converted as the clustering problem for finding MPC. Shtub [35] modelled the CF problem as the generalized assignment problem considering the minimization of allocation costs as the objective function. Srinivasan et al. [39] developed an assignment clustering model that solves an assignment problem with the maximization objective for finding initial seeds. Adil et al. [1] proposed an assignment allocation algorithm to solve a nonlinear mathematical programming with the objective of the minimization of the weighted sum of voids and exceptional elements. The proposed approach employs an assignment algorithm based on a pairwise exchange method which is a general algorithm used to improve an existing facility layout problem. In this paper, the assignment algorithm, which maximizes the total sum of similarity coefficients within machine cells, starts with an initial cluster and then searches for better solutions by a pairwise exchange of machines. In order to find the quality MPC in a short time, PEC employs the non-decreasing objective function and termination rules. 

Step 1. Initial machine cells are grouped by assigning each machine into a cell including only itself. Among elements in a similarity coefficient matrix the assigned and unassigned elements, which indicate the elements assigned into machine cells and elements other than the assigned elements respectively, are determined by initial machine cells. Similarity coefficients corresponding to the assigned and unassigned elements are defined as a_s = ms_ss and  = ms_s, for all s and x. <Table 2> illustrates an example of the assigned and unassigned elements. The objective value is set to OBJ = 0. 

<Table 2> The Assigned and Unassigned Machines.

Step 2. A machine pair to be exchanged is selected by comparing the sum of differences between the assigned and unassigned elements calculated as  =  ― a_s  and =  ― a_t, for all s, t, x, y. The sum of two differences,  + , represents the increment of the objective value produced by exchanging a pair of machines. If  the associated machine pair p(s, t) is considered as a candidate. Among candidates, a machine pair p(s, t) with  for all s, t, x, y is selected as the best machine pair to be exchanged and the objective value is updated as new_OBJ = mv + old_ OBJ. If mv < 0, since the objective function is not improved, an algorithm keeps the current machine cells and goes to step 5. Otherwise, go to step 3. 

Step 3. The machines selected as the best machine pair are exchanged. New subtours identified by exchanging the machine pair represent new machine cells as  for the best machine pair p(s, t). Similarity coefficients of new assigned and unassigned elements are updated as a_s = ma_s, a_t = ms_ty  and <Table 3> shows the example of the assigned and unassigned elements newly defined after a pairwise exchange of machines, B and C. In <Table 3>, two subtours are observed as A-A and B-C-B. These subtours indicate new machine cells defined as C₁ = { A } and C₂= { B, C }     . 

<Table 3> The Assigned and Unassigned Machines After Exchanging Machine B and C.

Step 4. A subtraction step is employed to prevent the reselection of the same machine pair and a never-ending cycle of an algorithm. PEC selects a bigger one out of two differences, bu = max(, )for the best machine pair, as a subtractive value. If bv < 0, mv < 0 must be true, which violates a non-decreasing objective function. And if bv = 0, a never-ending cycle happens in the case that both differences are equal to zero. Therefore, If bv ≦ 0, an algorithm keeps the current machine cells and goes to step 5. Otherwise, the given matrix is updated by subtracting bv from all similarity coefficients in the column of the new assigned machine with bv such as for all t and go to step 2. 

Step 5. Parts are allocated to machine cells by MDR and the largest ratio rule (LRR). MDR is first adapted by allocating each part into a machine cell having the maximum operation out of all machine cells. In addition to MDR which has been used in the literature, LRR defined as shown in Equation (3) is newly introduced as a tie breaker when the same MDR value exits : 

By LRR, parts are allocated to a machine cell with the smallest number of voids among clusters having the same density. If MDR and LRR are utilized sequentially, exceptional elements and voids can be minimized. The resulting MPC is evaluated by grouping efficacy and compared with the best solutions. 

3.3 Average Linkage Clustering

In order to find better solutions, MPC are merged into clusters with similar characteristics by ALC. Seifoddini [30, 31] suggested the use of ALC in order to overcome the chaining problem and reported that ALC has a better performance than SLC in the aspect of intercellular moves. ALC forms groups in terms of group similarity coefficients calculated by Equation (4) :
 

As soon as MPC are merged by ALC, the part assignment and evaluation steps used in PEC are implemented. If the obtained MPC is better, RAC is executed. Otherwise, ALC is repeated. If the remaining machine cells are less than 3 or if the same clusters as the existing clusters are reproduced, the entire procedure of CAA is terminated. In the case of singleton, the machine is merged to a machine cell with the largest group similarity coefficient. ALC enables CAA to restrict the number of clusters or machines within a cluster. For example, if the number of clusters is limited to four, ACL is conducted until four clusters are generated, and then CAA is terminated. 

3.4 Reverse Assignment Clustering

RAC is the enhancement clustering method that reforms MPC obtained from ALC in the aspect of the machine workload. In RAC, machines are assigned into part families based on the number of operations in each part family, which is opposite to a part allocation. In this paper the largest workload ratio rule (LWRR) I and II are proposed to regroup machines and are sequentially used. And then, parts are again assigned into the new machine cells according to MDR and LRR. Finally, the obtained clusters are evaluated and compared with the previous solution. If no better solution exists or if the same clusters as the existing clusters are reproduced, the algorithm goes back to ALC in order to merge the remaining clusters. Otherwise, RAC is repeated. If a singleton exists, the ratio value is set to 0 in the beginning of RAC. LWRR I and II for each machine are calculated as Equation (5) and Equation (6), respectively.
 

<Table 4> Machine-part Incidence Matrix.

<Table 5> Similarity Coefficient Matrix.

4. Illustrative Example

The procedure of the proposed CAA is illustrated by an example taken from Chandrasekharan and Rajagopalan [9]. This example includes 8 machines and 20 parts processed by the machines. <Table 4> shows MPIM with zero-one indicators from a route chart. From <Table 4> initial similarity coefficients for all machine pairs are calculated by the pro posed definition. For example, Initial similarity coefficient between a machine 1 and 2 is s₁₂ = (4+5)/15 = 0.6 as Equation (2). After double centering transformation, the final matrix is developed in terms of the proposed similarity measure and represented in <Table 5>. In the first iteration of PEC, a machine 3 and 7 are selected as the best machine pair with 1.1678 (-0.6504)+1.1678 (-0.6504) = 3.6364 and are grouped to the same cell. Since the best machine pair has the same difference, all coefficients in the column corresponding to either machine 3 or 7 are subtracted by 1.8182. At the 8^th iteration, since the objective value is not improved any more, the proposed assignment algorithm is terminated and four machine cells are obtained as MC1 = {1, 8}, MC2 = {2, 4}, MC3 = {3, 7} and MC4 = {5, 6}. In a part allocation, a part 1 having the same density in MC1 and 4 is assigned by LRR. Due to the same LRR values for MC1 and 4, a part 1 can be allocated into either two machine cells. In this case MC1 is selected. Thus, part families are PF1 = {1, 3, 4, 9, 10, 14, 16}, PF2 = {7, 18, 20}, PF3 = {5, 6, 8, 11, 12, 13, 17, 19} and PF4 = {2, 15}. The obtained MPC have 51 exceptional elements, no void and a grouping efficacy of 0.4396. In ALC, the machine cells obtained from PEC are merged by an average group similarity coefficient matrix as shown in <Table 6>.

MC3 and 4 having the largest group similarity coefficient are merged into the same machine cell. The machine cells obtained from ALC are MC1 = {1, 8}, MC2 = {2, 4} and MC3 = {3, 7, 6, 7} and the corresponding part families are PF1 = {1, 3, 4, 9, 10, 14}, PF2 = {18} and PF3 = {2, 5, 6, 7, 8, 11, 12, 13, 15, 16, 17, 19, 20}. In this configuration, 37 exceptional elements and 12 voids appear and the grouping efficacy is 0.5243. Since a singleton cluster exists in a cluster 2, the corresponding LWRR I is set as 0. RAC produces two MPC as MC1 = {1, 2, 4, 8} and MC2 = {3, 5, 6, 7} and PF1 = {1, 2, 3, 4, 9, 10, 14, 15, 18} and PF2 = {5, 6, 7, 8, 11, 12, 13, 16, 17, 19, 20}. The clusters generate 28 exceptional elements and 17 voids. Since a grouping efficacy is improved to 0.5833, RAC is repeated. In the second RAC, since a machine 6 has the same LWRR I value in two part families, LWRR II is used. LWRR II of a machine 6 for each part family is computed as 0.6667 for PF1 and 0.6364 for PF2. According to LWRR II, a machine 6 moves to a machine cell corresponding to part family 1. There are 27 exceptional elements and 18 voids in the new clusters listed in <Table 7> and the corresponding a grouping efficacy is 0.5872. 

<Table 6> Average Group Similarity Coefficient Matrix.

A better solution is updated and RAC is repeated. RAC reproduces the same machine cells and an algorithm goes back to ALC. Since ALC produces the machine cells already obtained in the previous iteration, the entire procedure of CAA is terminated, and the best MPC are equal to those of <Table 7>. <Table 8> shows the block-diagonalized matrix of the best solution. 

<Table 7> Machine-part Clusters from the 2nd RAC.

<Table 8> Block-diagonalized Matrix of the Best Clusters.

5. Performance Evaluation

In order to demonstrate the performance of CAA, the proposed approach is evaluated on test problems taken from the literature and compared with other notable CF methodologies in terms of grouping efficacy. 

5.1 Test Data Set

In this paper, 20 problems taken from the literature is selected. These data sets include a variety of sizes, a range from 5 machines and 7 parts to 40 machines and 100 parts, and difficulties, well-structured and ill-structured matrices. <Table 9> represents the sizes and sources of data sets taken from the literature. These data can be easily accessed from the references mentioned in <Table 9>. Boctor [3] and Chandrasekharan and Rajagopalan [9] provided a variety of data sets to evaluate the effect of the well or ill structured MPIM for GT approaches. Problems 7 to 12 are equivalent to problems 2 to 6 and 9 in Boctor’s paper, and problems 15 to 19 are equivalent to problems 1 to 3, 5 and 6 in Chandrasekharan and Rajagopalan’s paper. In order to evaluate the performance for the large-sized CF problem, a problem including 40 machines and 100 parts taken from Chandrasekharan and Rajagopalan [8] is tested. 

5.2 Computational Results

In order to show the efficiency of the proposed approach, eleven alternative methodologies are selected from the CF literature. These approaches have been frequently compared with other approaches in this field. In particular, methodologies based on cluster analysis are evaluated and is directly compared with CAA. Alternative methods include ZODIAC [8], GRAFICS [37], MST-GRAFICS [38] and HERBAL [41] from a cluster analysis-based method, GA [28], GP-SLCA [12], EA [13], ACR [17], EnGGA [40], and SACF [44] from meta-heuristic. 

CAA does not allow singleton clusters, but GA, GP-SLCA, SACF and EnGGA include them in their solutions. In practice CMS does not allow singleton clusters except for particular situations. Since in the aspect of grouping efficacy singleton clusters make grouping performance increase, grouping efficacy values including singleton clusters are not provided in this paper. SACF is substituted by Wu et al. [45] where singletons are not allowed. Since EA reported the sol solution using data which is inconsistent with the original reference in problem 2 and 14, the results in those problems are not also provided. 

<Table 9> Test Data Sets.

<Table 10> shows the experimental results of CAA and the results taken from the existing eleven approaches. The performance of CAA is evaluated by grouping efficacy, intercellular movements, machine utilization in MPC and a computational time. In the binary-based CF problems, intercellular movements is equal to the number of exceptional elements and machine utilization can be defined as the ratio of the number of operations in the diagonal blocks to the number of operations and voids in the diagonal blocks. In <Table 10>, blanks represents that the related value is not available in the literature. 

The experimental result shows that CAA is equal to or superior to other approaches for all problems. From the results, the best solution is reported in 18 out of 20 data sets, and the second best solution is reported in 2 problems of which the grouping efficacy values are very close to those of the best solution. Only HERBAL out of all methodologies compared with CAA has better solutions in only two problems, 1 and 19. The test results provide the evidence of the robustness of CAA. In the comparison with meta-heuristics- based approaches, CAA obtains better solutions in all test problems applicable to the approach based on GA. Although the performance of EnGGA is equal to CAA, meta-heuristics has a disadvantage of high computational complexity. SACF based on SA also shows worse results than CAA in 4 out of 13 problems. GP-SLCA and EA based on an evolutionary programming perform worse than CAA for 1 and 2 out of 10 and 12 test problems respectively. ACR based on an ant-colony algorithm perform worse results in 2 problems. In particular all methodologies except for EnGGA and GP-SLCA have results worse than the second best solution, which means that the algorithms show different results in the quality of solutions according to the difficulty of data sets. From the comparison, it can be concluded that CAA is more efficient than meta-heuristics-based approaches. In the case of cluster analysis-based approaches, all methodologies except for HERBAL are apparently inferior to CAA. In particular, while MST-GRAFICS, GRAFICS and ZODIAC based on a NHCM have a solution procedure similar to the proposed approach, CAA shows significantly its superiority over them. Also, CAA outperforms HERBAL in that CAA is better in 4 and worse in 2 out of 11 problems. 

<Table 10> Comparison of CAA and Other Approaches Using Grouping Efficacy.

CAA is coded in MATLAB and run on a personal computer with a 1.6 GHz Intel Pentium M processor. The proposed approach obtains the solution in around one and half seconds even for the largest test problem. The result of the computational performance reports that CAA is very efficient and has an ability to find good quality MPC for well-structured as well as ill-structured MPIM in the configuration of CF in CMS. 

6. Conclusion

This paper describes the approach based on cluster analysis incorporating HCM and NHCM for solving CF. CAA sequentially implements the procedure of similarity coefficient matrix, PEC, ALC and RAC. The objective of the proposed approach is to maximize the machine utilization within clusters as well as to minimize intercellular movements between clusters, which is achieved by the minimization of exceptional elements and voids. CAA searches for the best MPC using grouping efficacy as an evaluation measure. Also, other evaluation measures are easily employed by replacing grouping efficacy. 

This paper reported that CAA produces robust results in comparison with other notable methodologies for the existing 20 data sets, which shows an ability to yield good quality solutions no matter what the difficulty of data sets is, ill or well-structured. In particular, CAA produces much better results than cluster analysis-based approaches having the similar solution procedure. Also, CAA spends around 1.5 seconds in finding solution even for the largest test problem. These results show that CAA is an effective and efficient approach for solving CF in CMS. 

In a real manufacturing situation, various production factors have been considered in the configuration of manufacturing cells, but CAA is interested in only production requirement. In the future, CAA is going to be expanded to an approach to consider real production factors in order to become more realistic. 

36-1-04 심영학 황정윤24-35.pdf318.6KB