A comparative evaluation of nine well-known algorithms for solving the cell formation problem in group technology

Nine algorithms, developed to solve the cell formation problem, are evaluated and compared for their ability to produce good solutions to large problems. A primary performance measure and two secondary performance measures are presented for gauging the quality of a solution to be the cell formation problem. Eight problems from the open literature and 60 randomly generated, large problems are analyzed. The analysis shows that there is no solution algorithm that performs better on all performance measures for problems from both the literature and the randomly generated data sets. One algorithm, called the ISNC algorithm and based on clustering around seeds, performs significantly better than all other algorithms on the primary performance measure (and performs well on the secondary measures) for the randomly generated data set, and performs well for the problems from the literature. Therefore this algorithm appears to be the most appropriate algorithm to use as a general purpose solution algorithm for CF problems having between 25 and 50 machines, 35 and 50 parts, and densities between 10 and 20%. (It may not be appropriate for larger problems, since its computational and space requirements appear to be high.) After the ISNC algorithm, there is no significant difference between most of the other algorithms. However, different kinds of solutions are developed by some of these other algorithms. The well-known SC/ROC and ROC/ROC algorithms develop solutions which consist of relatively small cells (where each machine in the cell is visited by most of the parts assigned to that cell) and one large cell for those parts not assigned to the small cells.