Optimal bivariate clustering and a genetic algorithm with an application in cellular manufacturing

摘要

The problem of bivariate clustering for the simultaneous grouping of rows and columns of matrices was addressed with a mixed-integer linear programming model. The model was solved using conventional methodology for very small problems but solving even small to moderate-sized problems was a formidable challenge. Because of the NP-complete nature of this class of problems, a genetic algorithm was developed to solve realistically sized problems of larger dimensions. A commonly encountered example is the simultaneous clustering of parts into part families and machines into machine cells in a cellular manufacturing context for group technology. The attractiveness of employing the optimization model (with objective function being a sum of dissimilarity measures) to provide simultaneous grouping of part types and machine types was compared to solutions found by employing the commonly used grouping efficacy measure. For cellular manufacturing problem instances from the literature, the intrinsic differences between the objective of the proposed model and grouping efficacy is highlighted. The solution to the general model found by employing a genetic algorithm solution technique and applying a simple heuristic was shown to perform as well as other algorithms to find the commonly accepted best known solutions for grouping efficacy. Further examples in industrial purchasing behaviour and market segmentation help reveal the general applicability of the model for obtaining natural clusters. (C) 2003 Elsevier B.V. All rights reserved.