# Simultaneous Hierarchical Clustering for Cell Formation Problems with Production Information

Authors: Yingyu Zhu; Simon Li
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

The purpose of this paper is to advance the similarity coefficient method to solve cell formation (CF) problems in two aspects. Firstly, while numerous similarity coefficients have been proposed to incorporate different production factors in literature, a weighted sum formulation is applied to aggregate them into a nonbinary matrix to indicate the dependency strength among machines and parts. This practice allows flexible incorporation of multiple production factors in the resolution of CF problems. Secondly, a two-mode similarity coefficient is applied to simultaneously form machine groups and part families based on the classical framework of hierarchical clustering. This practice not only eliminates the sequential process of grouping machines (or parts) first and then assigning parts (or machines), but also improves the quality of solutions. The proposed clustering method has been tested through twelve literature examples. The results demonstrate that the proposed method can at least yield solutions comparable to the solutions obtained by metaheuristics. It can yield better results in some instances, as well.


---

## Body

## 1. Introduction

The pressure of mass customization remains high for manufacturers to provide a family of product variants with low cost. To address this challenge, the strategy of group technology (GT) has been applied to focus on the production of part families using manufacturing cells. The general advantage is that each manufacturing cell can be flexibly adjusted to produce customized parts. Toward the successful application of GT, one important key is the design of cellular manufacturing systems (CMS), and cell formation (CF) is one early design decision that defines the machine groups and the part families.Among a wide range of mathematical techniques to solve CF problems, cluster analysis is one of early attempts [1]. One key feature of cluster analysis is the concept of similarity coefficients that are used to quantify the “similarity” between any pairs of machines (or parts) for grouping purpose. The relevant techniques are labeled as similarity coefficient method (SCM) [2]. In this paper, SCM refers to the methodical approaches that use similarity coefficient under the traditional framework of hierarchical (or agglomerative) clustering for solving CF problems. Along the advancement of optimization techniques (especially metaheuristics), SCM has received certain criticisms [3, p. 159], [4], which can be summarized into two aspects below:(i)
Criticism #1: solution optimality: different from the exact solution strategies and metaheuristic algorithms, hierarchical clustering (HC) engages a smaller search space by comparing similarity values. Also, the grouping process in HC is irreversible so that the quality of final solutions may suffer due to some less-optimal subgroups formed earlier.(ii)
Criticism #2: consideration of production factors: beyond the binary machine-part incidence matrix, CF problems need to consider more production factors such as production volumes, operation sequences, and machine reliability. Yet, SCM has been criticized for less capability to effectively handle complex production factors.Concerning Criticism #1, it should be noted that CF problems are essentially NP-hard [5]. Thus, optimal solutions cannot be guaranteed without extensive computational effort. The heuristics and irreversibility of HC can be viewed as the strategy that makes HC simple and quick to apply. Currently, the SCM algorithmic strategy mainly forms groups for the same type of objects at one time (i.e., deciding on machine groups or part families at one time). Yet, the nature of CF problems is about the formation of groups for two sets of objects [6]. Thus, this paper adapts the two-mode similarity coefficient [8] that puts machines and parts into one single hierarchy (i.e., dendrogram or tree) for simultaneous clustering. As a result, we can obtain high-quality CF solutions that are comparable to those from metaheuristic approaches.Concerning Criticism #2, it should be noted that a certain number of similarity coefficients have been developed using production factors in literature, and more details can be found in Section2.1. By taking the implied concern in this criticism, it is observed that the similarity coefficients with production factors are usually formulated in some complex equations. This makes the SCM less extendable to incorporate multiple production factors. To address this concern, this paper proposes the use of nonbinary incidence matrix to indicate the overall dependency strength between a machine and a part. In the analysis, the overall dependency strength is based on the aggregation of individual production factors so that the matrix entries can be quantified and adjusted according to the problem’s context.In this paper, we will address the CF problems with the consideration of production volumes and operation sequences. While this kind of problems has been addressed in literature, the new contributions are twofold. Firstly, the nonbinary incidence matrix is used to show its flexibility to handle different production factors. Secondly, the two-mode similarity coefficient is applied to support simultaneous clustering using HC. The quality of the results is at least comparable to the existing solutions in literature (some cases yield better results) with low computing time.The rest of this paper is organized as follows. Section2 will review the literature works concerning similarity coefficients and solution approaches to address CF problems. Section 3 will specify the CF problem to be addressed in this paper and discuss the use of nonbinary matrix. Section 4 will discuss the similarity analysis to support simultaneous hierarchical clustering. Section 5 will propose the methodical procedure to guide the solution process. Section 6 will demonstrate the proposed method with various examples and discuss the results to support the method’s utility. Section 7 will conclude this paper.


## 2. Literature Review

### 2.1. Similarity Coefficients in CF

While the notion “similarity” sounds intuitive to many people, its formal meaning is not entirely straightforward. By examining the Jaccard similarity coefficient [1] and the classical works from numerical taxonomy [11] and psychology [12], it is found that a similarity measure generally consists of (1) commonality factors (to explain why two objects are similar) and (2) distinction factors (to normalize the measure with respect to some common ground). Then, the variety of similarity coefficients in the CF literature is mainly caused by varying the commonality and distinction factors based on the interpretation of the production information for better CF design.Being aimed at minimizing intercellular movements, the formulations of similarity measures mainly focus on the factors of production volume (to reduce the weight of movements) and operation sequences (to reduce the number of moves). In view of production volume, the early idea is to extend the Jaccard coefficient by multiplying the volume values with the matching and unmatching factors [13]. Then, it remains common to incorporate the production volume as the weight of movements in determining some generalized similarity measures (e.g., [14, 15]).Beyond production volume, another common factor considered to formulate similarity measures is operation sequence, and two major lines of research are found in literature. One line is to evaluate the similarity of two parts based on their sequences of operations. One early work is found in Choobineh [16], where similarity was defined on the common subsequences between two parts. Then, the notions of longest common sequence (LCS) and shortest composite supersequence (SCS) emerged to consider the relative orders (rather than just consecutive orders) [17, 18]. Goyal et al. [19] further refined the similarity measure by considering the bypassing moves and appended sequences. Notably, nonsymmetric similarity measures have also been proposed by considering the number of operation changes required to produce part x based on the sequence of part y [20, 21].In addition to part-part similarity, another line is to evaluate the similarity between two machines. Gupta [14] considered the similarity between two machines based on their consecutive processes to produce some common parts. This similarity idea was also adopted by Alhourani [22] and Wu and Suzuki [23, 24] in their proposals of similarity measures. To extend the generalized similarity by Won and Kim [25], Yin and Yasuda [26] developed the formulation of sequence ratio (SR) that compares the actual and theoretically highest intermachine movements between two machines. Nair and Narendran [3] focused on the intermediate operations that will incur two intercell movements as compared to the first and last operations. This similarity notion was also adopted by Won and Lee [27].The notion of similarity keeps expanding in CF and other manufacturing applications. To support the process of shipbuilding, Yuguang et al. [28] classified the characteristics of similarity in view of assembly processes, equipment, and resources. Alhourani [29] considered machine reliability, where two machines are “less similar” if they have high breakdown costs individually. To analyze the networked operations, Navaei and ElMaraghy [30] developed the similarity measure of two part variants based on common consecutive operations.Besides, the similarity comparison is always made between two objects of the same type. Yet, CF problems are intended to form groups of two types of objects, where traditional clustering methods such as k-means clustering and hierarchical clustering mainly focus on grouping objects of the same type. Boutsinas [31] has highlighted such difference by adapting biclustering techniques to solve CF problems. Li and Mehrabadi [8] have proposed a two-mode coefficient that assesses the appropriateness of putting a machine and a part together in one group. This paper is intended to extend this work by applying the two-mode coefficient to resolve CF problems with more production factors.


### 2.2. Search Strategies for CF Solutions

Due to the combinatorial nature of grouping decisions, the search space for CF solutions is often large. In view of this fundamental challenge, some reviews have already classified CF methods based on the solution search strategies [2, 4, 32]. While this paper does not intend to propose a new taxonomy, we want to highlight that SCM should be classified as heuristics in view of its algorithmic procedure. To explain this point, we employ the classification of search strategies for CF solutions in two main categories [32]: (1) exact solution approach and (2) approximate solution approach, which includes metaheuristics and heuristics.The main feature of exact solution approach is the assurance of optimal solutions. To employ this approach, the first step is to formulate CF problems using integer variables for assignment and grouping decisions such as the p-median methods [33, 34] and the generalized CF models [35, 36]. Notably, using integer programming models only does not imply the obtainment of optimal solutions. Early literature has reported that exact solution methods (e.g., branch-and-bound) implemented in software (such as LINDO) can only address relatively small problems [34, 37]. Further advancements have tackled the “fractional” grouping efficacy objective through approximately linearizing the grouping efficacy formulation [38] and strategically fixing the demonstrator values in a series of linear integer problems [39]. Brusco [6] has strengthened the potential of exact solution approach by strategically setting the lower and upper bounds in a branch-and-bound approach with clarifying the scalability of the proposed algorithm.In contrast to exact solution approach, approximate solution approach does not guarantee the optimality of solutions. By relaxing this requirement, the algorithmic strategies based on metaheuristics and heuristics are generally applied to search for high-quality solutions without enumerative exploration. According to Blum and Roli [40], one important feature of metaheuristic algorithms is the control of the balance between diversification and intensification in the solution search process. The results of using metaheuristics for solving CF problems are abundant in literature, as reviewed in Papaioannou and Wilson [4]. Examples include tabu search [41], simulated annealing [42, 43], and genetic algorithm [44, 45]. Yet, the use of metaheuristics is not without challenges. As commented by Stawowy [46, p. 1], the approaches by metaheuristics have a tendency for more complex algorithms and are sometimes not easy for CF practitioners. Also, Renzi et al. [32, p. 415] have indicated that the choice of a metaheuristic method (mainly pointing to genetic algorithms) may not be informed by the research results from optimization literature. Brusco [7, p. 293] has remarked on some common metaheuristics that need to make certain nontrivial “implementation decisions” in order to obtain desirable outcomes.Compared to metaheuristics, heuristics does not carry the algorithmic feature of diversification and intensification. Instead, it mainly employs the greedy and hill-climbing algorithmic strategy to promptly improve the solution quality based on the short-term results. Without backtracking, one advantage is its simplicity and low computational effort. This explains that some early CF solution approaches (e.g., [47, 48]) are heuristic by nature as they can even be applied without using computers. By examining the procedure of hierarchical clustering (or SCM) closely, it should be classified as a heuristic solution approach since it progressively picks the object pair with highest similarity and forms intermediate groups. The nature of this strategy is close to the greedy algorithm [49, p. 64]. Thus, hierarchical clustering also inherits the characteristics of heuristic solution approach such as lower computational effort and weaker guarantee to high-quality solutions.Even though the cost of computation is getting low, clustering methods and SCM have still been applied in CF in recent years, as reviewed in Section2.1. One supporting reason is that SCM is more flexible to handle less-formalized information [2], while exact solution and metaheuristic approaches require a complete optimization model to operate the algorithms. Another reason is simplicity, where the complexity of some metaheuristic algorithms can hinder the practical applications. In this context, by inheriting the advantages of SCM, this paper will show that two-mode similarity can yield comparable solution quality for the CF problems considering production volumes and operation sequences.


## 2.1. Similarity Coefficients in CF

While the notion “similarity” sounds intuitive to many people, its formal meaning is not entirely straightforward. By examining the Jaccard similarity coefficient [1] and the classical works from numerical taxonomy [11] and psychology [12], it is found that a similarity measure generally consists of (1) commonality factors (to explain why two objects are similar) and (2) distinction factors (to normalize the measure with respect to some common ground). Then, the variety of similarity coefficients in the CF literature is mainly caused by varying the commonality and distinction factors based on the interpretation of the production information for better CF design.Being aimed at minimizing intercellular movements, the formulations of similarity measures mainly focus on the factors of production volume (to reduce the weight of movements) and operation sequences (to reduce the number of moves). In view of production volume, the early idea is to extend the Jaccard coefficient by multiplying the volume values with the matching and unmatching factors [13]. Then, it remains common to incorporate the production volume as the weight of movements in determining some generalized similarity measures (e.g., [14, 15]).Beyond production volume, another common factor considered to formulate similarity measures is operation sequence, and two major lines of research are found in literature. One line is to evaluate the similarity of two parts based on their sequences of operations. One early work is found in Choobineh [16], where similarity was defined on the common subsequences between two parts. Then, the notions of longest common sequence (LCS) and shortest composite supersequence (SCS) emerged to consider the relative orders (rather than just consecutive orders) [17, 18]. Goyal et al. [19] further refined the similarity measure by considering the bypassing moves and appended sequences. Notably, nonsymmetric similarity measures have also been proposed by considering the number of operation changes required to produce part x based on the sequence of part y [20, 21].In addition to part-part similarity, another line is to evaluate the similarity between two machines. Gupta [14] considered the similarity between two machines based on their consecutive processes to produce some common parts. This similarity idea was also adopted by Alhourani [22] and Wu and Suzuki [23, 24] in their proposals of similarity measures. To extend the generalized similarity by Won and Kim [25], Yin and Yasuda [26] developed the formulation of sequence ratio (SR) that compares the actual and theoretically highest intermachine movements between two machines. Nair and Narendran [3] focused on the intermediate operations that will incur two intercell movements as compared to the first and last operations. This similarity notion was also adopted by Won and Lee [27].The notion of similarity keeps expanding in CF and other manufacturing applications. To support the process of shipbuilding, Yuguang et al. [28] classified the characteristics of similarity in view of assembly processes, equipment, and resources. Alhourani [29] considered machine reliability, where two machines are “less similar” if they have high breakdown costs individually. To analyze the networked operations, Navaei and ElMaraghy [30] developed the similarity measure of two part variants based on common consecutive operations.Besides, the similarity comparison is always made between two objects of the same type. Yet, CF problems are intended to form groups of two types of objects, where traditional clustering methods such as k-means clustering and hierarchical clustering mainly focus on grouping objects of the same type. Boutsinas [31] has highlighted such difference by adapting biclustering techniques to solve CF problems. Li and Mehrabadi [8] have proposed a two-mode coefficient that assesses the appropriateness of putting a machine and a part together in one group. This paper is intended to extend this work by applying the two-mode coefficient to resolve CF problems with more production factors.


## 2.2. Search Strategies for CF Solutions

Due to the combinatorial nature of grouping decisions, the search space for CF solutions is often large. In view of this fundamental challenge, some reviews have already classified CF methods based on the solution search strategies [2, 4, 32]. While this paper does not intend to propose a new taxonomy, we want to highlight that SCM should be classified as heuristics in view of its algorithmic procedure. To explain this point, we employ the classification of search strategies for CF solutions in two main categories [32]: (1) exact solution approach and (2) approximate solution approach, which includes metaheuristics and heuristics.The main feature of exact solution approach is the assurance of optimal solutions. To employ this approach, the first step is to formulate CF problems using integer variables for assignment and grouping decisions such as the p-median methods [33, 34] and the generalized CF models [35, 36]. Notably, using integer programming models only does not imply the obtainment of optimal solutions. Early literature has reported that exact solution methods (e.g., branch-and-bound) implemented in software (such as LINDO) can only address relatively small problems [34, 37]. Further advancements have tackled the “fractional” grouping efficacy objective through approximately linearizing the grouping efficacy formulation [38] and strategically fixing the demonstrator values in a series of linear integer problems [39]. Brusco [6] has strengthened the potential of exact solution approach by strategically setting the lower and upper bounds in a branch-and-bound approach with clarifying the scalability of the proposed algorithm.In contrast to exact solution approach, approximate solution approach does not guarantee the optimality of solutions. By relaxing this requirement, the algorithmic strategies based on metaheuristics and heuristics are generally applied to search for high-quality solutions without enumerative exploration. According to Blum and Roli [40], one important feature of metaheuristic algorithms is the control of the balance between diversification and intensification in the solution search process. The results of using metaheuristics for solving CF problems are abundant in literature, as reviewed in Papaioannou and Wilson [4]. Examples include tabu search [41], simulated annealing [42, 43], and genetic algorithm [44, 45]. Yet, the use of metaheuristics is not without challenges. As commented by Stawowy [46, p. 1], the approaches by metaheuristics have a tendency for more complex algorithms and are sometimes not easy for CF practitioners. Also, Renzi et al. [32, p. 415] have indicated that the choice of a metaheuristic method (mainly pointing to genetic algorithms) may not be informed by the research results from optimization literature. Brusco [7, p. 293] has remarked on some common metaheuristics that need to make certain nontrivial “implementation decisions” in order to obtain desirable outcomes.Compared to metaheuristics, heuristics does not carry the algorithmic feature of diversification and intensification. Instead, it mainly employs the greedy and hill-climbing algorithmic strategy to promptly improve the solution quality based on the short-term results. Without backtracking, one advantage is its simplicity and low computational effort. This explains that some early CF solution approaches (e.g., [47, 48]) are heuristic by nature as they can even be applied without using computers. By examining the procedure of hierarchical clustering (or SCM) closely, it should be classified as a heuristic solution approach since it progressively picks the object pair with highest similarity and forms intermediate groups. The nature of this strategy is close to the greedy algorithm [49, p. 64]. Thus, hierarchical clustering also inherits the characteristics of heuristic solution approach such as lower computational effort and weaker guarantee to high-quality solutions.Even though the cost of computation is getting low, clustering methods and SCM have still been applied in CF in recent years, as reviewed in Section2.1. One supporting reason is that SCM is more flexible to handle less-formalized information [2], while exact solution and metaheuristic approaches require a complete optimization model to operate the algorithms. Another reason is simplicity, where the complexity of some metaheuristic algorithms can hinder the practical applications. In this context, by inheriting the advantages of SCM, this paper will show that two-mode similarity can yield comparable solution quality for the CF problems considering production volumes and operation sequences.


## 3. Analysis of the CF Problem Using Nonbinary Matrix

### 3.1. Context of the CF Problem

In a cell formation (CF) problem, there exists a set of machines(m1,m2,…) and parts (p1,p2,…). The variations of CF problems stem from the production factors that are considered in the problems. This paper specifically considers operation sequences and part demands. Let S=[sij] be the matrix capturing the information of operation sequences [50], and it is defined as follows:(1)sij=gifpjrequiresmito  process  at  thegth  step0ifpjdoes  not  requiremi.Also, let vj be the demands of part pj. Using an example from Solimanpur et al. [9], Figure 1 presents a matrix form that captures the sequence information of five machines and seven parts with their demands. Generally, the purpose of CF is to form the machine groups and part families so that some measure of solution quality can be optimized. In this paper, we choose grouping efficacy and intercellular movements as the quality measures. While these measures are well recognized in CF literature, they will be discussed in the next subsection.Figure 1
Sample matrix with sequence and demand information [9].


### 3.2. Measures of Solution Quality

To compare the quality of CF solutions, one common measure is grouping efficacy (denoted asμ) [6], and its formulation is provided below:(2)μ=ne-noutne+nin,where ne, nout, nin are the total numbers of all operations (i.e., number of nonzero matrix entries), operations outside the cells (i.e., exceptional elements), and voids (i.e., zero matrix entries) inside the cells, respectively. In an ideal solution, there is no operation outside the cells (i.e., nout = 0) and no void inside the cells (i.e., nin = 0), leading to μ = 1.To incorporate the sequence and demand information in the solution comparison, the objective function by Solimanpur et al. [9] is employed, and it basically consists of two measures: intercellular movements (f1) and total number of voids (f2). To capture the intercellular movements, we need to distinguish whether the operations are at both ends or in the middle of the sequence. Particularly, if an operation is in the middle and the relevant part and machine are not in the same cell, this part needs to move out and then move in with respect to its own cell (i.e., 2 times). Let D=[dij] be the weighted sequence matrix [3] to capture this idea, and it is defined as follows:(3)dij=0ifsij=01ifpjrequiresmiat  the  start  or  end  of  sequence2ifpjrequiresmiin  the  middle  of  sequence.Let eij and oij be the binary parameters indicating the presence of exceptional and void elements with machine mi and part pj in the solution matrix, respectively. Also, let m and n be the number of machines and parts, respectively. Accordingly, f1 and f2 can be formulated in the following:(4)f1=∑i=1m∑j=1nvj·dij·eij,(5)f2=∑i=1m∑j=1nvj·oij.


### 3.3. Formulation of Nonbinary Matrix

The notion of nonbinary matrix can be viewed as a generalization of the traditional incidence matrix in CF which indicates the binary relation between a machine and part (i.e., whether machinemi is required to process part pj). The “nonbinary” entries can be interpreted as “to what extent pj needs mi based on the production information”. The input of this step is the production information. Specifically in this paper, it refers to sij (operation sequences) and vj (part demands).As discussed earlier, “middle” operations have higher priority than “start/end” operations to be put in the same cell in order to avoid the double counts of intercellular movements. To reflect this idea, the weighted sequence matrixD=[dij] defined in (3) will be used to capture the “nonbinary” notion for operation sequences.With regard to part demands, a high demand ofpj will encourage putting the required machines in the same cell so that we can avoid moving a large batch of pj between cells. To capture this notion, let V=[vij] be the part demand matrix. In the formulation, if mi is required to produce pj with demand vj, then vij=vj. Otherwise, if mi is not required to make pj, vij=0. For illustration, the sample example from Figure 1 is used to generate the weighted sequence matrix D and the part demand matrix V, which are shown in Figures 2(a) and 2(b), respectively.Figure 2
Sample matricesD, V, and A.
(a)
Weighted sequence matrixD (b)
Part demand matrixV (c)
Nonbinary matrixAAfter obtainingD=[dij] and V=[vij] for operation sequences and part demands, respectively, the next process is normalization and weighting to yield the nonbinary matrix as the output of this step. Let A=[aij] be the nonbinary matrix, and its formulation is provided below:(6)aij=w1dij∑i=1mdij+w2vij∑j=1nvj,where w1 and w2 are the weighting factors, and the denominators are applied for normalization. Particularly, the weighting factors are intended to balance the effects from both production factors. To do so, the following constraint is set:(7)w1·∑i,jdij∑idij=w2·∑i,jvij∑jvj.In addition, as we also set w1+w2=1, the values of w1 and w2 can be determined with these two equations. Accordingly, the nonbinary matrix A=[aij] is obtained. The resulting nonbinary matrix A of the sample example is shown in Figure 2(c).


## 3.1. Context of the CF Problem

In a cell formation (CF) problem, there exists a set of machines(m1,m2,…) and parts (p1,p2,…). The variations of CF problems stem from the production factors that are considered in the problems. This paper specifically considers operation sequences and part demands. Let S=[sij] be the matrix capturing the information of operation sequences [50], and it is defined as follows:(1)sij=gifpjrequiresmito  process  at  thegth  step0ifpjdoes  not  requiremi.Also, let vj be the demands of part pj. Using an example from Solimanpur et al. [9], Figure 1 presents a matrix form that captures the sequence information of five machines and seven parts with their demands. Generally, the purpose of CF is to form the machine groups and part families so that some measure of solution quality can be optimized. In this paper, we choose grouping efficacy and intercellular movements as the quality measures. While these measures are well recognized in CF literature, they will be discussed in the next subsection.Figure 1
Sample matrix with sequence and demand information [9].


## 3.2. Measures of Solution Quality

To compare the quality of CF solutions, one common measure is grouping efficacy (denoted asμ) [6], and its formulation is provided below:(2)μ=ne-noutne+nin,where ne, nout, nin are the total numbers of all operations (i.e., number of nonzero matrix entries), operations outside the cells (i.e., exceptional elements), and voids (i.e., zero matrix entries) inside the cells, respectively. In an ideal solution, there is no operation outside the cells (i.e., nout = 0) and no void inside the cells (i.e., nin = 0), leading to μ = 1.To incorporate the sequence and demand information in the solution comparison, the objective function by Solimanpur et al. [9] is employed, and it basically consists of two measures: intercellular movements (f1) and total number of voids (f2). To capture the intercellular movements, we need to distinguish whether the operations are at both ends or in the middle of the sequence. Particularly, if an operation is in the middle and the relevant part and machine are not in the same cell, this part needs to move out and then move in with respect to its own cell (i.e., 2 times). Let D=[dij] be the weighted sequence matrix [3] to capture this idea, and it is defined as follows:(3)dij=0ifsij=01ifpjrequiresmiat  the  start  or  end  of  sequence2ifpjrequiresmiin  the  middle  of  sequence.Let eij and oij be the binary parameters indicating the presence of exceptional and void elements with machine mi and part pj in the solution matrix, respectively. Also, let m and n be the number of machines and parts, respectively. Accordingly, f1 and f2 can be formulated in the following:(4)f1=∑i=1m∑j=1nvj·dij·eij,(5)f2=∑i=1m∑j=1nvj·oij.


## 3.3. Formulation of Nonbinary Matrix

The notion of nonbinary matrix can be viewed as a generalization of the traditional incidence matrix in CF which indicates the binary relation between a machine and part (i.e., whether machinemi is required to process part pj). The “nonbinary” entries can be interpreted as “to what extent pj needs mi based on the production information”. The input of this step is the production information. Specifically in this paper, it refers to sij (operation sequences) and vj (part demands).As discussed earlier, “middle” operations have higher priority than “start/end” operations to be put in the same cell in order to avoid the double counts of intercellular movements. To reflect this idea, the weighted sequence matrixD=[dij] defined in (3) will be used to capture the “nonbinary” notion for operation sequences.With regard to part demands, a high demand ofpj will encourage putting the required machines in the same cell so that we can avoid moving a large batch of pj between cells. To capture this notion, let V=[vij] be the part demand matrix. In the formulation, if mi is required to produce pj with demand vj, then vij=vj. Otherwise, if mi is not required to make pj, vij=0. For illustration, the sample example from Figure 1 is used to generate the weighted sequence matrix D and the part demand matrix V, which are shown in Figures 2(a) and 2(b), respectively.Figure 2
Sample matricesD, V, and A.
(a)
Weighted sequence matrixD (b)
Part demand matrixV (c)
Nonbinary matrixAAfter obtainingD=[dij] and V=[vij] for operation sequences and part demands, respectively, the next process is normalization and weighting to yield the nonbinary matrix as the output of this step. Let A=[aij] be the nonbinary matrix, and its formulation is provided below:(6)aij=w1dij∑i=1mdij+w2vij∑j=1nvj,where w1 and w2 are the weighting factors, and the denominators are applied for normalization. Particularly, the weighting factors are intended to balance the effects from both production factors. To do so, the following constraint is set:(7)w1·∑i,jdij∑idij=w2·∑i,jvij∑jvj.In addition, as we also set w1+w2=1, the values of w1 and w2 can be determined with these two equations. Accordingly, the nonbinary matrix A=[aij] is obtained. The resulting nonbinary matrix A of the sample example is shown in Figure 2(c).


## 4. Similarity Analysis

### 4.1. Background

In the context of SCM, similarity is often used to measure the potential of putting two objects in the same group before any formation of groups. While the direct interpretation of similarity is about the resemblance of two objects, Yin and Yasuda [2] have refined the notion of similarity as “appropriateness” (p. 335). That is, the similarity of two objects depends on the purpose of grouping, which defines the context of appropriateness. For example, suppose that we have three different pens: (Pen 1) blue ball pen, (Pen 2) green ball pen, and (Pen 3) green highlighter. In view of the writing function, we may say that Pens 1 and 2 are more similar due to the width of a pen stroke. Yet, if we want to categorize pens based on colors for organization purpose, we may say that Pens 2 and 3 are more similar.Despite the appropriateness notion, similarity in SCM is often used to compare two objects of the same type as if it follows the resemblance notion of similarity. For example, the similarity coefficients reviewed in Section2.1 were developed for either any two machines or any two parts. We refer to these as one-mode similarity, where the term “mode” is defined as an object type in social network analysis [51]. Yet, the nature of CF problems is about the formation of groups for two sets of objects. Consequently, a clustering procedure needs to be conducted in two stages, either forming machine groups first or part families first. In this case, the solution quality may be impacted since the groups formed earlier restrict the possible results of second grouping or assignment decisions.To extend the appropriateness notion of similarity in CF, this paper uses the two-mode similarity coefficient to assess how it is appropriate to group a machine and a part in the same group. While more details can be found in Section4.3, the key feature of two-mode similarity is to support simultaneous hierarchical clustering so that both machines and parts can form the hierarchy in the same tree. Our numerical examples show that this approach can provide high-quality CF solutions at least comparable to literature results.To regulate the notion of similarity and support the concatenation of their values, the following conditions are applied to regulate the numerical properties of similarity values. These conditions or axioms are based on the work by Sneath and Sokal [11, page 120]. Let fs(a,b) be the function that computes the similarity values between two objects a and b. Then, a valid similarity function needs to satisfy the following conditions:Condition #1:0≤fs(a,b)≤1.Condition #2:fs(a,b)=fs(b,a).Condition #3:fs(a,a)=1.Condition #1 is the boundary condition that any similarity value is bounded between 0 and 1. It sets the numerical range and tendency (e.g., “1” implies perfect similarity) for aggregation. Condition #2 is the symmetry condition that the order of comparison does not influence the similarity value. Condition #3 states that the comparison between two identical objects should yield the maximum similarity value.


### 4.2. Min/Max Similarity Coefficient

The purpose of the min/max coefficient is to assess the similarity between any two machines and any two parts using the nonbinary matrixA=aij defined in Section 3.3. In particular, two machines have nonzero similarity if they need to produce some common parts. Let smmij be the min/max coefficient of two machines mi and mj, and its formulation is given below:(8)smmij=∑k=1nmin⁡aik,ajk∑k=1nmax⁡aik,ajk.Likewise, two parts have nonzero similarity if their productions require some common machines. Let sppij be the min/max coefficient of two parts pi and pj, and its formulation is given below:(9)sppij=∑k=1mmin⁡aki,akj∑k=1mmax⁡aki,akj.Notably, the min/max coefficient satisfies the three similarity conditions discussed in Section 4.1. In addition, if the input A=[aij] is a binary matrix, the min/max coefficient will give the same results as the Jaccard coefficient. In other words, the min/max coefficient can be viewed as the generalization of the Jaccard coefficient, where the nonbinary values in A=aij are treated as the weights, in addition to the binary information, to assess the degree of similarity.


### 4.3. Two-Mode Similarity Coefficient

The purpose of the two-mode coefficient is to assess the similarity between a machine and a part using the nonbinary matrixA=[aij] defined in Section 3.3. As discussed earlier, the term two-mode is used to indicate the similarity assessment between two objects of different types. Along the notion of appropriateness, the similarity between machine mi and part pj is nonzero if mi is used to produce pj. Let smpij be the two-mode coefficient of mi and pj, and its formulation is given below:(10)smpij=2aij∑k=1naik+∑k=1makj.Regarding the numerical tendency, if the value of aij is high, the resulting similarity will also be high. The denominator basically normalizes the similarity value by summing the nonbinary entries aij of the row of mi and the column of pj. Also, it captures how exclusive mi and pj are related to each other. For example, if mi is only used to produce pj (but not other parts), the row of mi in the nonbinary matrix has mainly zero values except the entry aij. The two-mode coefficient is intended to capture this tendency putting mi andpj in the same cell due to this exclusiveness.For more elaboration, ifpj does not require mi, the two-mode coefficient is equal to zero. If aij is the only nonzero entry for mi and pj (i.e., machine mi is only used to produce pj), the two-mode coefficient is equal to one (i.e., no reason to separate mi and pj in different cells). The numerator is set as 2×aij in order to satisfy the boundary condition of similarity discussed in Section 4.1. Notably, the symmetry condition is also satisfied, while the condition of identical objects is not applicable for the two-mode coefficient.


### 4.4. Concatenated Similarity Matrix

To execute simultaneous hierarchical clustering, the similarity information of both machines and parts are treated at the same time. Then, three types of similarity matrices are classified below:(i)
Machine-machine similarity: anm×m symmetric matrix (denoted as Smm=[smmij]) is used to capture the similarity values between any two machines. The min/max coefficient is used in this case.(ii)
Part-part similarity: ann×n symmetric matrix (denoted as Spp=[sppij]) is used to capture the similarity values between any two parts. The min/max coefficient is used in this case.(iii)
Machine-part similarity: anm×n rectangular matrix (denoted as Smp=[smpij]) is used to capture the similarity values between a machine and a part. The two-mode coefficient is used in this case.To combine these three types of similarity matrices, the concatenated similarity matrix (CSM) is defined in (11). In this definition, the superscript Trefers to the matrix transpose, and wm, wp, and wmp are the scalars of weighting factors. Notably, CSM is a symmetric matrix with the dimension of (m+n)×(m+n). Since CSM is constructed by various types of similarity coefficients, the weighting factors (i.e., wm, wp, and wmp) are used to adjust the grouping effects from Smm, Spp, and Smp:(11)CSM=wm·Smmwmp·Smpwmp·SmpTwp·Spp.After obtaining CSM, both machines and parts are treated as if they belong to the same type of objects. Then, traditional procedures of hierarchical clustering can be applied using CSM as an input to construct a tree (or dendrogram) that can group both machines and parts at the same time. The next section will discuss the application of hierarchical clustering that takes CSM to solve the CF problem.In this paper, we employ two approaches to set the weighting factors. The first approach is simply settingwm=wp=wmp=1, and it is intended to preserve the original grouping influence from the min/max and two-mode coefficients. The second approach is to set wm=wp=1, and wmp is set using (12) in order to balance the effect from the two-mode coefficient. After that, the concatenated similarity matrix (CSM) is normalized through division of its largest entry(12)wmp=max⁡Smm+max⁡Spp2max⁡Smp.


## 4.1. Background

In the context of SCM, similarity is often used to measure the potential of putting two objects in the same group before any formation of groups. While the direct interpretation of similarity is about the resemblance of two objects, Yin and Yasuda [2] have refined the notion of similarity as “appropriateness” (p. 335). That is, the similarity of two objects depends on the purpose of grouping, which defines the context of appropriateness. For example, suppose that we have three different pens: (Pen 1) blue ball pen, (Pen 2) green ball pen, and (Pen 3) green highlighter. In view of the writing function, we may say that Pens 1 and 2 are more similar due to the width of a pen stroke. Yet, if we want to categorize pens based on colors for organization purpose, we may say that Pens 2 and 3 are more similar.Despite the appropriateness notion, similarity in SCM is often used to compare two objects of the same type as if it follows the resemblance notion of similarity. For example, the similarity coefficients reviewed in Section2.1 were developed for either any two machines or any two parts. We refer to these as one-mode similarity, where the term “mode” is defined as an object type in social network analysis [51]. Yet, the nature of CF problems is about the formation of groups for two sets of objects. Consequently, a clustering procedure needs to be conducted in two stages, either forming machine groups first or part families first. In this case, the solution quality may be impacted since the groups formed earlier restrict the possible results of second grouping or assignment decisions.To extend the appropriateness notion of similarity in CF, this paper uses the two-mode similarity coefficient to assess how it is appropriate to group a machine and a part in the same group. While more details can be found in Section4.3, the key feature of two-mode similarity is to support simultaneous hierarchical clustering so that both machines and parts can form the hierarchy in the same tree. Our numerical examples show that this approach can provide high-quality CF solutions at least comparable to literature results.To regulate the notion of similarity and support the concatenation of their values, the following conditions are applied to regulate the numerical properties of similarity values. These conditions or axioms are based on the work by Sneath and Sokal [11, page 120]. Let fs(a,b) be the function that computes the similarity values between two objects a and b. Then, a valid similarity function needs to satisfy the following conditions:Condition #1:0≤fs(a,b)≤1.Condition #2:fs(a,b)=fs(b,a).Condition #3:fs(a,a)=1.Condition #1 is the boundary condition that any similarity value is bounded between 0 and 1. It sets the numerical range and tendency (e.g., “1” implies perfect similarity) for aggregation. Condition #2 is the symmetry condition that the order of comparison does not influence the similarity value. Condition #3 states that the comparison between two identical objects should yield the maximum similarity value.


## 4.2. Min/Max Similarity Coefficient

The purpose of the min/max coefficient is to assess the similarity between any two machines and any two parts using the nonbinary matrixA=aij defined in Section 3.3. In particular, two machines have nonzero similarity if they need to produce some common parts. Let smmij be the min/max coefficient of two machines mi and mj, and its formulation is given below:(8)smmij=∑k=1nmin⁡aik,ajk∑k=1nmax⁡aik,ajk.Likewise, two parts have nonzero similarity if their productions require some common machines. Let sppij be the min/max coefficient of two parts pi and pj, and its formulation is given below:(9)sppij=∑k=1mmin⁡aki,akj∑k=1mmax⁡aki,akj.Notably, the min/max coefficient satisfies the three similarity conditions discussed in Section 4.1. In addition, if the input A=[aij] is a binary matrix, the min/max coefficient will give the same results as the Jaccard coefficient. In other words, the min/max coefficient can be viewed as the generalization of the Jaccard coefficient, where the nonbinary values in A=aij are treated as the weights, in addition to the binary information, to assess the degree of similarity.


## 4.3. Two-Mode Similarity Coefficient

The purpose of the two-mode coefficient is to assess the similarity between a machine and a part using the nonbinary matrixA=[aij] defined in Section 3.3. As discussed earlier, the term two-mode is used to indicate the similarity assessment between two objects of different types. Along the notion of appropriateness, the similarity between machine mi and part pj is nonzero if mi is used to produce pj. Let smpij be the two-mode coefficient of mi and pj, and its formulation is given below:(10)smpij=2aij∑k=1naik+∑k=1makj.Regarding the numerical tendency, if the value of aij is high, the resulting similarity will also be high. The denominator basically normalizes the similarity value by summing the nonbinary entries aij of the row of mi and the column of pj. Also, it captures how exclusive mi and pj are related to each other. For example, if mi is only used to produce pj (but not other parts), the row of mi in the nonbinary matrix has mainly zero values except the entry aij. The two-mode coefficient is intended to capture this tendency putting mi andpj in the same cell due to this exclusiveness.For more elaboration, ifpj does not require mi, the two-mode coefficient is equal to zero. If aij is the only nonzero entry for mi and pj (i.e., machine mi is only used to produce pj), the two-mode coefficient is equal to one (i.e., no reason to separate mi and pj in different cells). The numerator is set as 2×aij in order to satisfy the boundary condition of similarity discussed in Section 4.1. Notably, the symmetry condition is also satisfied, while the condition of identical objects is not applicable for the two-mode coefficient.


## 4.4. Concatenated Similarity Matrix

To execute simultaneous hierarchical clustering, the similarity information of both machines and parts are treated at the same time. Then, three types of similarity matrices are classified below:(i)
Machine-machine similarity: anm×m symmetric matrix (denoted as Smm=[smmij]) is used to capture the similarity values between any two machines. The min/max coefficient is used in this case.(ii)
Part-part similarity: ann×n symmetric matrix (denoted as Spp=[sppij]) is used to capture the similarity values between any two parts. The min/max coefficient is used in this case.(iii)
Machine-part similarity: anm×n rectangular matrix (denoted as Smp=[smpij]) is used to capture the similarity values between a machine and a part. The two-mode coefficient is used in this case.To combine these three types of similarity matrices, the concatenated similarity matrix (CSM) is defined in (11). In this definition, the superscript Trefers to the matrix transpose, and wm, wp, and wmp are the scalars of weighting factors. Notably, CSM is a symmetric matrix with the dimension of (m+n)×(m+n). Since CSM is constructed by various types of similarity coefficients, the weighting factors (i.e., wm, wp, and wmp) are used to adjust the grouping effects from Smm, Spp, and Smp:(11)CSM=wm·Smmwmp·Smpwmp·SmpTwp·Spp.After obtaining CSM, both machines and parts are treated as if they belong to the same type of objects. Then, traditional procedures of hierarchical clustering can be applied using CSM as an input to construct a tree (or dendrogram) that can group both machines and parts at the same time. The next section will discuss the application of hierarchical clustering that takes CSM to solve the CF problem.In this paper, we employ two approaches to set the weighting factors. The first approach is simply settingwm=wp=wmp=1, and it is intended to preserve the original grouping influence from the min/max and two-mode coefficients. The second approach is to set wm=wp=1, and wmp is set using (12) in order to balance the effect from the two-mode coefficient. After that, the concatenated similarity matrix (CSM) is normalized through division of its largest entry(12)wmp=max⁡Smm+max⁡Spp2max⁡Smp.


## 5. Methodical Procedure

As discussed by Yin and Yasuda [2], the similarity coefficient method (SCM) generally has a prescribed procedure. Essentially, this paper adapts this SCM procedure and proposes a 4-step method for problem solving. Figure 3 illustrates the overview of these procedural steps, with emphasis on the input and output information of each step [52].Figure 3
Illustration of the methodical workflow.Step 1 (process production information into nonbinary matrix).
The purpose of this step is to convert the production information into a nonbinary matrix that indicates the relational strength betweenmi and pj. Higher relational strength implicates that the corresponding mi and pi should be put in the same cell. In this paper, the production information considered is operation sequences (i.e., S=[sij]) and part demands (i.e., vj). The output of this step is the nonbinary matrix, A=[aij], whose formulation has been discussed in Section 3.3.Step 2 (determine the similarity values).
This step corresponds to the application of similarity coefficients in SCM. The purpose of this step is to evaluate the similarity values of machine-machine (i.e.,Smm), part-part (i.e., Spp), and machine-part (i.e., Smp) based on the nonbinary matrix. The similarity coefficients used in this step are the min/max coefficient for Smm and Spp (i.e., (8) and (9)) and the two-mode coefficient for Smp (i.e., (10)). The output of this step is the concatenated similarity matrix (CSM), which has been discussed in Section 4.4.Step 3 (build the tree and block diagonal matrix).
This step corresponds to the application of hierarchical clustering algorithms to construct the tree (or dendrogram). Using the tree’s nodes, the block diagonal matrix (BDM) is obtained by rearranging the rows and columns of the input matrix. The purpose of this step is to preliminarily sort the input matrix by putting similar objects close to each other.In this paper, the average-linkage algorithm in hierarchical clustering [53] is applied to CSM in order to build the tree with both machines and parts. Taking the CSM as the input, the tree is constructed based on the similarity values between any two objects. If two objects have a high similarity value, they will be likely grouped to form a branch of the tree. As objects can be either machines or parts, one single tree is constructed for these two object types. Figure 4 shows the resulting tree using the sample matrix (i.e., Figure 1), where the nodes include both machines and parts (i.e., mi, and pj), and a branch is created after joining two nodes (denoted as brk). For example, m2 and p5 are joined to make br2 in Figure 4.Figure 4
Tree result of the sample matrix constructed from hierarchical clustering.Notably, the hierarchical clustering process already places the highly similar objects close to each other. Thus, if we reorder the rows and columns of the nonbinary matrix based on the node sequence from the tree, we can arrange the nonzero matrix entries getting close to the matrix’s diagonal, forming a block diagonal matrix (BDM). To improve the quality of BDM, a node sequencing algorithm is applied [54]. The basic idea of this algorithm is to check whether switching tree branches (e.g., p2 and p5) can yield a better BDM or not. If so, branch-switch is carried out. This process starts from the top branch, proceeding down to the lower branches. Figure 5 shows the sample of BDM, which is obtained by reordering the rows and columns of the sample matrix (i.e., Figure 1) based on the tree node sequence in Figure 4.Figure 5
Sample of the block diagonal matrix.Step 4 (partition the block diagonal matrix).
Note that structural constraints (e.g., number of cells and size limits) are not required to yield the block diagram matrix (BDM). Then, the purpose of this Step4 is to determine machine groups and part families by dividing the BDM with the consideration of structural constraints. In the CF literature, various approaches have been proposed to yield final CF solutions based on the BDM such as the minimal spanning tree approach (Chen and Irani 1993) and the evolutionary algorithm approach [55]. In this paper, the tree structure is utilized for finalizing the cell formation process.Using the previous sample example, Figure6 illustrates the partitioning concept based on the tree and BDM. By breaking the top branch of the tree, two subsets of nodes are indicated. As each subset contains both machines and parts, it basically defines a block on the BDM. These blocks then define the contents of the cells in the final CF solution. In the algorithmic implementation, the tree’s branches are broken from top to bottom to collect the positions to define the blocks over the BDM. These positions are applied to the BDF progressively until the structural criteria of cells (e.g., the number of cells) are satisfied.Figure 6
Illustration of the partitioning concept based on tree.


## 6. Numerical Examples and Comparison

To examine the proposed method, three examples are first discussed in Section6.1 to check (1) the use of hierarchical clustering to handle the sequence information, (2) the min/max similarity coefficient to handle the nonbinary information, and (3) the ability to handle a large matrix problem. Then in Section 6.2, benchmark results based on metaheuristics will be used to examine the solution quality from the proposed method.


### 6.1. Three Examples to Examine the Basic Functionality

The first example is obtained from Nair and Narendran [3], and it has 20 machines and 20 parts. Based on the previous discussion, the similarity analysis is conducted by first constructing the weighted sequence matrix using (3), and then the min/max coefficient is applied to evaluate Smm and Spp. The weights of the CSM are applied based on (12). As a result, the five-cell solution is obtained and shown in Figure 7. The solution in Figure 7 is essentially the same as the original solution by Nair and Narendran [3] in view of the composition of machines and parts in individual cells. Notably, their original solution was obtained by using nonhierarchical clustering, which requires the identification of “disjoint machines” to define centroids as initial inputs of the clustering process. In contrast, the proposed clustering method does not require the centroids as the method’s inputs to initiate the solution process. This feature is considered as one practical advantage of the proposed method as compared to the nonhierarchical approach.Figure 7
Solution of the example with sequence information only.The second example is obtained from Venugopal and Narendran [10], and it has 20 machines and 20 parts. The nonbinary value between mi and pj is interpreted as the normalized workload of mi required to produce pj, and it is calculated based on processing time, machine available time, and production volume. In this case, higher values imply stronger correlations; that is, the corresponding machines and parts should be grouped in one cell. Figure 8(a) shows the CF solution after applying the proposed method. In this solution, five cells are defined. Tentatively, we observe that the values of intercell entries are relatively small. Also, this solution generally shows the BDM, which arranges the blocks along the diagonal. This BDM can help users to view the overall structure easier and support the rearrangement of the block’s contents (if necessary).Figure 8
Solution comparison of the nonbinary example.
(a)
Our solution (b)
Solution from Venugopal and Narendran [10]For comparison, Figure8(b) shows the original solution by Venugopal and Narendran [10] that was obtained by using simulated annealing. These two solutions are almost the same except that the original solution has only four cells. The large block of the original solution (whose matrix’s labels are highlighted in Figure 8(b)) is essentially the combination of two smaller blocks in our solution (whose labels are also highlighted in Figure 8(b)). Purely from the aspect of solution quality, these two solutions are similar. Yet, the BDM of our solution has some advantage if we want to flexibly change the number of cells from four to five (or vice versa). Table 1 records the numerical results for both our solution and the original solution. As seen, our solution has a higher (better) value of grouping efficacy.Table 1
Comparison of numerical metrics of the nonbinary example.
Number of cells Exception(nout) Void (nin) Grouping efficacy (μ) Original solution 4 53 55 0.3494 Our solution 5 62 19 0.3769The third example comes from Chandrasekharan and Rajagopalan [56], which was originally a CF problem of 40 machines and 100 parts with binary information only. To examine the handling of sequence and demand information, the operation sequence is generated for each part based on the order of the machine indices (a method used by Spiliopoulos and Sofianopoulou [57]). The demand of each part was randomly generated using a discrete uniform distribution with a range of [1,100] (a method used by Solimanpur et al. [9]). By applying the proposed method, a solution is obtained and represented in Figure 9, where the parts’ demands are shown on the last row. The grouping efficacy of this solution is 0.8403, which matches the result in Chandrasekharan and Rajagopalan [56] and other recent results [7, 39]. Also, the execution time of this problem is less than 0.5 second based on Matlab implementation using a typical computer (speed: 3.1 GHz, RAM: 8 GB). Thus, the solution time is considered fast as compared to other optimization approaches.Figure 9
Solution of the large example with sequence and demand information.


### 6.2. Comparison with the Results from Metaheuristics

The benchmark results were obtained from the work by Solimanpur et al. [9], where nine examples of CF problems are used for the comparison in this study. Notably, the original work by Solimanpur et al. [9] mainly adopted the CF matrices from literature, and they added the information of part demands and operation sequences if necessary. To conduct an even-ground comparison, we adopted the information of CF problems purely from Solimanpur et al. [9] using the original problem codes (e.g., P1, P2, P3,…) with the acknowledgment of original matrices and relevant works as follows.(i)
P1: Mahdavi and Mahadevan [58] developed a heuristic algorithm, namely, CLASS.(ii)
P2: Boe and Cheng [59] developed a (heuristic) close neighbour algorithm to obtain a block diagonal structure.(iii)
P3: Stanfel [60] used a (heuristic) divisive clustering approach.(iv)
P4: Srinivasan [61] used the minimum spanning tree method.(v)
P5: Wu et al. [62] used genetic algorithms.(vi)
P6: Tsai and Lee [63] used mathematical programming.(vii)
P7 and P8: Sudhakara Pandian and Mahapatra [64] used neural networks.Solimanpur et al. [9] applied the ant colony optimization (ACO) method to solve the CF problems. Notably, ACO is one type of metaheuristic methods, and it should exhibit better capability to search for high-quality solutions than heuristic approaches. Adopting the same measure, the quality of solutions is assessed by intercellular movements (i.e., f1 in (4)) and the number of voids as machine utilization (i.e, f2 in (5)). While both f1 and f2 measures are smaller-the-better, the summation of f1 and f2 (i.e., f1+f2) is applied to compare the overall quality of solutions.Table2 shows the comparison results. For clarification, P0 is the test problem in Solimanpur et al. [9]. These results are based on the weighting of the CSM using (12) for all problems here except P1, which uses wm=wp=wmp=1. In this study, we actually run both sets of weighting and report the better results. Admittedly, how to set the weights of the CSM toward the high-quality solutions remains an open question. Yet, our observations over the reported examples indicate that the solutions are not highly sensitive to the weight values. Given that the computational effort of the proposed clustering method is low, it is still feasible to check two different sets of weights suggested in Section 4.4 for each problem.Table 2
Comparison with the results by the ACO method [9].
Problem Size(m×n) Number of cells Solution from the ACO method Proposed clustering method Total improvement (%) f 1 f 2 f 1 + f 2 f 1 f 2 f 1 + f 2 P0 15 × 25 3 863 803 1666 863 803 1666 0.00 P1 8 × 20 3 800 0 800 800 0 800 0.00 P2 20 × 35 4 2058 2584 4642 1671 2911 4582 1.31 P3 30 × 50 13 2102 3268 5370 3619 1228 4847 10.79 P4 24 × 40 9 3772 2172 5944 2585 2067 4652 27.77 P5 9 × 10 2 377 1039 1416 309 1005 1314 7.76 P6 7 × 10 3 74 453 527 222 153 375 40.53 P7 10 × 12 3 589 288 877 236 368 604 45.20 P8 25 × 40 6 1685 4247 5932 1394 3421 4815 23.20As observed, the proposed clustering method can yield better solutions for most problems (i.e., from P2 to P8). Beyond the simple comparison of the value off, it is noted that the values of f1 and f2 are often in the trade-off situation (i.e., better value of f1 traded with weaker value of f2), and no solutions are dominated in view of Pareto optimality. Concerning our solution results that are the same (i.e., P0 and P1), we consider that Solimanpur et al. [9] have already obtained very high-quality solutions for P0 and P1. In this view, our solutions can at least match these best solutions reported in literature.


### 6.3. Remarks on the Advantages of the Proposed Method

In summary of this section, the main advantage of the proposed method is its ability to yield high-quality CF solutions (comparable to the results by metaheuristics) without compromising the computational efficiency of heuristic solution approach. In other words, the proposed method can be viewed as one that improved heuristics based on hierarchical clustering to search for high-quality solutions. Table3 compares the proposed method (on the last row) with the major types of algorithmic approaches that have been discussed in Section 2.1. The columns of this table list the comparison aspects, which are discussed below:(i)
Solution search strategy: this aspect has been discussed in Section2.1. Its intent is to recall the basic difference of various strategies in searching for CF solutions. Such information serves the foundation to explain their performance differences.(ii)
Guarantee of optimal solutions: only the exact solution approach can guarantee optimal solutions. The traditional view considers that metaheuristics has better potential for high-quality solutions than heuristics. Yet, the proposed method of this paper shows that an improved heuristic approach can yield high-quality results comparable to the results by metaheuristics (i.e., results in Section6.2) due to the use of the two-mode coefficient.(iii)
Need optimization model? this is a practical issue concerning the skills required by users to apply the relevant algorithms. Notably, the quality of an optimization model is essential to implement metaheuristics for process convergence and high-quality solutions. Arguably, similarity should be an easier concept, where users can focus on the pairwise relations between two objects. The consideration of production factors can be aggregated individually in a nonbinary matrix (i.e., (6)).(iv)
Computational time: the exact solution approach would take long computational time, and it is not practical for large problems. For example, Brusco [6, page 662] has stated that they did not test the exact solution approach for a problem with the total number of machines and parts equal to or more than 65. Concerning metaheuristics, we have checked the times required to solve the problems in Section 6.2 from Solimanpur et al. [9], where the times range from 0.87 second (for P6) to 106.94 seconds (for P3). In contrast, as reported in Section 6.1, the proposed method takes 0.5 second for the problem with 40 machines and 100 parts. It verifies that the solution search by the proposed method (as one heuristics) takes short times.Table 3
Comparison of algorithmic approaches to CF problems.
Solution search strategy Guarantee of optimal solutions Need optimization model? Computational time Exact solution approach Branch-and-bound approach for exhaustive search Yes Yes Long, not feasible for a large problem  Metaheuristics Systematic diversification and intensification No, good potential for high-quality solutions Yes Medium  Heuristics Greedy and hill-climbing strategy, short-term results without backtracking No, fair potential for high-quality solutions No Short  Proposed method (improved heuristics) Same as heuristics No, comparable to metaheuristics No Short, example: 0.5 second for 40 × 100 matricesIn sum, the proposed method is considered an improved heuristic approach since it can yield solutions of comparable quality with the solutions by metaheuristics. At the same time, it can keep the benefit of short computational times in most heuristic approaches.


## 6.1. Three Examples to Examine the Basic Functionality

The first example is obtained from Nair and Narendran [3], and it has 20 machines and 20 parts. Based on the previous discussion, the similarity analysis is conducted by first constructing the weighted sequence matrix using (3), and then the min/max coefficient is applied to evaluate Smm and Spp. The weights of the CSM are applied based on (12). As a result, the five-cell solution is obtained and shown in Figure 7. The solution in Figure 7 is essentially the same as the original solution by Nair and Narendran [3] in view of the composition of machines and parts in individual cells. Notably, their original solution was obtained by using nonhierarchical clustering, which requires the identification of “disjoint machines” to define centroids as initial inputs of the clustering process. In contrast, the proposed clustering method does not require the centroids as the method’s inputs to initiate the solution process. This feature is considered as one practical advantage of the proposed method as compared to the nonhierarchical approach.Figure 7
Solution of the example with sequence information only.The second example is obtained from Venugopal and Narendran [10], and it has 20 machines and 20 parts. The nonbinary value between mi and pj is interpreted as the normalized workload of mi required to produce pj, and it is calculated based on processing time, machine available time, and production volume. In this case, higher values imply stronger correlations; that is, the corresponding machines and parts should be grouped in one cell. Figure 8(a) shows the CF solution after applying the proposed method. In this solution, five cells are defined. Tentatively, we observe that the values of intercell entries are relatively small. Also, this solution generally shows the BDM, which arranges the blocks along the diagonal. This BDM can help users to view the overall structure easier and support the rearrangement of the block’s contents (if necessary).Figure 8
Solution comparison of the nonbinary example.
(a)
Our solution (b)
Solution from Venugopal and Narendran [10]For comparison, Figure8(b) shows the original solution by Venugopal and Narendran [10] that was obtained by using simulated annealing. These two solutions are almost the same except that the original solution has only four cells. The large block of the original solution (whose matrix’s labels are highlighted in Figure 8(b)) is essentially the combination of two smaller blocks in our solution (whose labels are also highlighted in Figure 8(b)). Purely from the aspect of solution quality, these two solutions are similar. Yet, the BDM of our solution has some advantage if we want to flexibly change the number of cells from four to five (or vice versa). Table 1 records the numerical results for both our solution and the original solution. As seen, our solution has a higher (better) value of grouping efficacy.Table 1
Comparison of numerical metrics of the nonbinary example.
Number of cells Exception(nout) Void (nin) Grouping efficacy (μ) Original solution 4 53 55 0.3494 Our solution 5 62 19 0.3769The third example comes from Chandrasekharan and Rajagopalan [56], which was originally a CF problem of 40 machines and 100 parts with binary information only. To examine the handling of sequence and demand information, the operation sequence is generated for each part based on the order of the machine indices (a method used by Spiliopoulos and Sofianopoulou [57]). The demand of each part was randomly generated using a discrete uniform distribution with a range of [1,100] (a method used by Solimanpur et al. [9]). By applying the proposed method, a solution is obtained and represented in Figure 9, where the parts’ demands are shown on the last row. The grouping efficacy of this solution is 0.8403, which matches the result in Chandrasekharan and Rajagopalan [56] and other recent results [7, 39]. Also, the execution time of this problem is less than 0.5 second based on Matlab implementation using a typical computer (speed: 3.1 GHz, RAM: 8 GB). Thus, the solution time is considered fast as compared to other optimization approaches.Figure 9
Solution of the large example with sequence and demand information.


## 6.2. Comparison with the Results from Metaheuristics

The benchmark results were obtained from the work by Solimanpur et al. [9], where nine examples of CF problems are used for the comparison in this study. Notably, the original work by Solimanpur et al. [9] mainly adopted the CF matrices from literature, and they added the information of part demands and operation sequences if necessary. To conduct an even-ground comparison, we adopted the information of CF problems purely from Solimanpur et al. [9] using the original problem codes (e.g., P1, P2, P3,…) with the acknowledgment of original matrices and relevant works as follows.(i)
P1: Mahdavi and Mahadevan [58] developed a heuristic algorithm, namely, CLASS.(ii)
P2: Boe and Cheng [59] developed a (heuristic) close neighbour algorithm to obtain a block diagonal structure.(iii)
P3: Stanfel [60] used a (heuristic) divisive clustering approach.(iv)
P4: Srinivasan [61] used the minimum spanning tree method.(v)
P5: Wu et al. [62] used genetic algorithms.(vi)
P6: Tsai and Lee [63] used mathematical programming.(vii)
P7 and P8: Sudhakara Pandian and Mahapatra [64] used neural networks.Solimanpur et al. [9] applied the ant colony optimization (ACO) method to solve the CF problems. Notably, ACO is one type of metaheuristic methods, and it should exhibit better capability to search for high-quality solutions than heuristic approaches. Adopting the same measure, the quality of solutions is assessed by intercellular movements (i.e., f1 in (4)) and the number of voids as machine utilization (i.e, f2 in (5)). While both f1 and f2 measures are smaller-the-better, the summation of f1 and f2 (i.e., f1+f2) is applied to compare the overall quality of solutions.Table2 shows the comparison results. For clarification, P0 is the test problem in Solimanpur et al. [9]. These results are based on the weighting of the CSM using (12) for all problems here except P1, which uses wm=wp=wmp=1. In this study, we actually run both sets of weighting and report the better results. Admittedly, how to set the weights of the CSM toward the high-quality solutions remains an open question. Yet, our observations over the reported examples indicate that the solutions are not highly sensitive to the weight values. Given that the computational effort of the proposed clustering method is low, it is still feasible to check two different sets of weights suggested in Section 4.4 for each problem.Table 2
Comparison with the results by the ACO method [9].
Problem Size(m×n) Number of cells Solution from the ACO method Proposed clustering method Total improvement (%) f 1 f 2 f 1 + f 2 f 1 f 2 f 1 + f 2 P0 15 × 25 3 863 803 1666 863 803 1666 0.00 P1 8 × 20 3 800 0 800 800 0 800 0.00 P2 20 × 35 4 2058 2584 4642 1671 2911 4582 1.31 P3 30 × 50 13 2102 3268 5370 3619 1228 4847 10.79 P4 24 × 40 9 3772 2172 5944 2585 2067 4652 27.77 P5 9 × 10 2 377 1039 1416 309 1005 1314 7.76 P6 7 × 10 3 74 453 527 222 153 375 40.53 P7 10 × 12 3 589 288 877 236 368 604 45.20 P8 25 × 40 6 1685 4247 5932 1394 3421 4815 23.20As observed, the proposed clustering method can yield better solutions for most problems (i.e., from P2 to P8). Beyond the simple comparison of the value off, it is noted that the values of f1 and f2 are often in the trade-off situation (i.e., better value of f1 traded with weaker value of f2), and no solutions are dominated in view of Pareto optimality. Concerning our solution results that are the same (i.e., P0 and P1), we consider that Solimanpur et al. [9] have already obtained very high-quality solutions for P0 and P1. In this view, our solutions can at least match these best solutions reported in literature.


## 6.3. Remarks on the Advantages of the Proposed Method

In summary of this section, the main advantage of the proposed method is its ability to yield high-quality CF solutions (comparable to the results by metaheuristics) without compromising the computational efficiency of heuristic solution approach. In other words, the proposed method can be viewed as one that improved heuristics based on hierarchical clustering to search for high-quality solutions. Table3 compares the proposed method (on the last row) with the major types of algorithmic approaches that have been discussed in Section 2.1. The columns of this table list the comparison aspects, which are discussed below:(i)
Solution search strategy: this aspect has been discussed in Section2.1. Its intent is to recall the basic difference of various strategies in searching for CF solutions. Such information serves the foundation to explain their performance differences.(ii)
Guarantee of optimal solutions: only the exact solution approach can guarantee optimal solutions. The traditional view considers that metaheuristics has better potential for high-quality solutions than heuristics. Yet, the proposed method of this paper shows that an improved heuristic approach can yield high-quality results comparable to the results by metaheuristics (i.e., results in Section6.2) due to the use of the two-mode coefficient.(iii)
Need optimization model? this is a practical issue concerning the skills required by users to apply the relevant algorithms. Notably, the quality of an optimization model is essential to implement metaheuristics for process convergence and high-quality solutions. Arguably, similarity should be an easier concept, where users can focus on the pairwise relations between two objects. The consideration of production factors can be aggregated individually in a nonbinary matrix (i.e., (6)).(iv)
Computational time: the exact solution approach would take long computational time, and it is not practical for large problems. For example, Brusco [6, page 662] has stated that they did not test the exact solution approach for a problem with the total number of machines and parts equal to or more than 65. Concerning metaheuristics, we have checked the times required to solve the problems in Section 6.2 from Solimanpur et al. [9], where the times range from 0.87 second (for P6) to 106.94 seconds (for P3). In contrast, as reported in Section 6.1, the proposed method takes 0.5 second for the problem with 40 machines and 100 parts. It verifies that the solution search by the proposed method (as one heuristics) takes short times.Table 3
Comparison of algorithmic approaches to CF problems.
Solution search strategy Guarantee of optimal solutions Need optimization model? Computational time Exact solution approach Branch-and-bound approach for exhaustive search Yes Yes Long, not feasible for a large problem  Metaheuristics Systematic diversification and intensification No, good potential for high-quality solutions Yes Medium  Heuristics Greedy and hill-climbing strategy, short-term results without backtracking No, fair potential for high-quality solutions No Short  Proposed method (improved heuristics) Same as heuristics No, comparable to metaheuristics No Short, example: 0.5 second for 40 × 100 matricesIn sum, the proposed method is considered an improved heuristic approach since it can yield solutions of comparable quality with the solutions by metaheuristics. At the same time, it can keep the benefit of short computational times in most heuristic approaches.


## 7. Conclusions

Although metaheuristics has been widely applied to solve CF problems, the development of SCM can still be found in recent literature due to its simplicity and efficiency to obtain reasonable solutions. By considering hierarchical clustering as a heuristic approach (rather than a separate class of solution approaches), this paper tries to explore its capability to obtain high-quality solutions as compared to metaheuristics. In the proposed method, the nonbinary matrix is used to incorporate the information of part demands and operation sequences and the two-mode similarity coefficient to simultaneously group machines and parts. In the numerical experiments, we can demonstrate that the proposed method can yield better solutions than those by metaheuristics in some cases reported in literature.In future work, it is planned to revisit different types of CF problems in literature based on the notion of the two-mode coefficient. The overall goal is to establish a general framework based on SCM that can tackle various types of CF problems and yield reasonable solutions for large problems in a limited time. By acknowledging the heuristic nature of SCM, we will also explore the limits of SCM to obtain high-quality solutions and develop some similarity-based guidance to improve the capability of the clustering heuristics.



---

*Source: 2841325-2018-05-20.xml*