Cluster first-sequence last heuristics for generating block diagonal forms for a machine-part matrix

Before detailed cell design analyses, rearranging the binary (or 0-1) machine-part matrix into a compact block diagonal form (BDF) is useful for controlling combinational explosion during subsequent decision-making involving machine duplication, subcontracting, intercell layout design, etc. Several authors have shown that a compact BDF corresponds to the implicit clusters in both dimensions being expressed as row and column permutations. A traditional approach for solving this problem has been to obtain the two permutations independently by solving the permutation problem in each dimension as a (unidimensional) travelling salesman problem (TSP). This paper describes cluster first-sequence last heuristics which combine the properties of the minimal spanning tree (MST) (clusters only) and TSP (sequence only) for improved permutation generation. The BDFs obtained with these heuristics were compared with those obtained using the TSP, linear placement problem (LPP), single linkage cluster analysis (SLCA), rank order clustering (ROC) and occupancy value (OV) algorithms. The ratio of variances (β), which was the variance along the minor axis (VY) divided by the variance along the major axis (VX) of the BDF, was used to evaluate the compactness of all the BDFs without assuming any explicit knowledge of the clusters in either dimension.