EVALUATION OF SEARCH ALGORITHMS AND CLUSTERING EFFICIENCY MEASURES FOR MACHINE-PART MATRIX CLUSTERING

Clustering a machine-part matrix is the first step in the design of a cellular manufacturing system. It provides a basis for matching the ma chine groups to the part families that they must produce. The problem of clustering a machine-part matrix can be decomposed into two problem s: designing a measure for clustering efficiency (CE) and searching fo r a permutation of rows and columns of the matrix to maximize this mea sure. Clustering is done by permuting the rows and columns of the init ial machine-part matrix to produce a block diagonal form (BDF). The cl ustering efficiency of a machine-part matrix measures the desirability of its BDF as a solution to cell design. This paper evaluates six mea sures of CE and six search methods. Extensive experiments were carried out to find the combination of CE measure and search method that prod uces the best solution in reasonable CPU time. We used several benchma rk machine-part matrices from the literature and several problems obta ined from a local manufacturer. We performed a multivariate analysis o f variance (MANOVA) to compare the search algorithms and the CE measur es.