An exact algorithm for maximizing grouping efficacy in part–machine clustering

The Grouping Efficacy Index (GEI) is well-recognized as a measure of the quality of a solution to a part–machine clustering problem. During the past two decades, numerous approximation procedures (heuristics and metaheuristics) have been proposed for maximization of the GEI. Although the development of effective approximation procedures is essential for large part–machine incidence matrices, the design of computationally feasible exact algorithms for modestly sized matrices also affords an important contribution. This article presents an exact (branch-and-bound) algorithm for maximization of the GEI. Among the important features of the algorithm are (i) the use of a relocation heuristic to establish a good lower bound for the GEI; (ii) a careful reordering of the parts and machines; and (iii) the establishment of upper bounds using the minimum possible contributions to the number of exceptional elements and voids for yet unassigned parts and machines. The scalability of the algorithm is limited by the number of parts and machines, as well as the inherent structure of the part–machine incidence matrix. Nevertheless, the proposed method produced globally optimal solutions for 104 test problems spanning 31 matrices from the literature, many of which are of nontrivial size. The new algorithm also compares favorably to a mixed-integer linear programming approach to the problem using CPLEX.