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

Michael J. Brusco

IISE Transactions, 2015, vol. 47, issue 6, 653-671

Abstract: 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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2014.971202 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:47:y:2015:i:6:p:653-671

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2014.971202

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().