CLUSTERING EFFECTIVENESS OF PERMUTATION GENERATION HEURISTICS FOR MACHINE-PART MATRIX CLUSTERING

The first step in the design of a cellular manufacturing system (CMS) is the clustering of the binary machine-part matrix. This provides a v isual basis for matching the machine groups to the part families they produce. Essentially, this requires that the orders of the machines an d parts in the initial matrix be permuted independently a finite numbe r of times. If machine-part clusters exist, they will appear as blocks of 1's along the diagonal of the matrix. Our study focuses on identif ying a generic measure for the compactness of a good block diagonal fo rm (BDF) in the fin al matrix produced by any heuristic. A difficult m atrix in the literature known to have cluster overlap in both dimensio ns was solved using various graph theoretic heuristics for permutation generation. The compactness of the BDF in each of the final matrixes was evaluated using a new measure of BDF compactness developed by the authors. Comparisons were made with other measures of clustering effec tiveness. The paper concludes with a discussion on how these measures could help to identify near-optimal BDFs to simplify machine grouping for detailed cell formation analyses.