Statistical Analysis of Similarity Measures for Solving Cell Formation Problems

Hierarchical clustering (HC) has been used to solve cell formation (CF) problem, which has advantages of solution convergence and not requiring the number of cells as the input. While evolutionary algorithms (EA) are more common in recent years due to their capability in solution searching, they also imply more time and complexity involved in problem solving. At the same time, some studies have shown that HC can give comparable results if the CF structures are not very “messy”. The term messiness is used to indicate the potential of a given CF problem to yield nearly independent machine groups and part families. Then, the purpose of this research is to distinguish whether a CF problem is “messy” or not so that the users can decide whether using economical HC or relatively demanding EA for problem solving. In the methodology, the similarity values of machine pairs are first determined for a given incidence matrix for CF. Then, histogram is used to report the distribution of similarity values. By analyzing this histogram, it is found that the distribution of similarity values of a less messy problem often presents a U-shape. To further quantify this observation, the Kolmogorov-Smirnov test (K-S test) is applied to examine how well the distribution of similarity values fits the normal cumulative distribution function (CDF). The result indicates that the similarity values of messy CF problems tend to demonstrate normal distribution in view of the K-S test.