Evaluation of search algorithms and clustering efficiency measures for machine-part matrix clustering

Abstract

Clustering a machine-part matrix is the first step in the design of a cellular manufacturing system. It provides a basis for matching the machine groups to the part families that they must produce. The problem of clustering a machine-part matrix can be decomposed into two problems: designing a measure for clustering efficiency (CE) and searching for a permutation of rows and columns of the matrix to maximize this measure. Clustering is done by permuting the rows and columns of the initial machine-part matrix to produce a block diagonal form (BDF). The clustering efficiency of a machine-part matrix measures the desirability of its BDF as a solution to cell design. This paper evaluates six measures of CE and six search methods. Extensive experiments were carried out to find the combination of CE measure and search method that produces the best solution in reasonable CPU time. We used several benchmark machine-part matrices from the literature and several problems obtained from a local manufacturer. We performed a multivariate analysis of variance (MANOVA) to compare the search algorithms and the CE measures.