An exact method for solving the manufacturing cell formation problem
- 4 August 2011
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 50 (15) , 4038-4045
Abstract
The cell formation problem is extensively studied in the literature, but very few authors have proposed exact methods. In this paper a linear binary programming formulation is introduced to generate a solution for the cell formation problem. To verify the behaviour of the proposed model, a set of 35 benchmark problems is solved using the branch and cut method implemented in the IBM ILOG CPLEX 10.11 Optimiser. Moreover, these results allow us to validate the quality of the solution generated with heuristic methods proposed in the literature. This experimentation indicates that, for the smaller problems, the best-known solutions are the same as those generated with CPLEX 10.11 Optimiser. These results indicate a fair confidence in the optimality of the best-known solutions generated by the heuristic methods. Furthermore, our approach is the first exact method providing results of this quality.Keywords
This publication has 44 references indexed in Scilit:
- A TSP-based heuristic for forming machine groups and part familiesInternational Journal of Production Research, 1998
- Similarity coefficient algorithms for solving the group technology problemInternational Journal of Production Research, 1992
- A close neighbour algorithm for designing cellular manufacturing systemsInternational Journal of Production Research, 1991
- GRAFICS—a nonhierarchical clustering algorithm for group technologyInternational Journal of Production Research, 1991
- A Jinear formulation of the machine-part cell formation problemInternational Journal of Production Research, 1991
- Entropic measures of manufacturing flexibilityInternational Journal of Production Research, 1987
- ZODIAC—an algorithm for concurrent formation of part-families and machine-cellsInternational Journal of Production Research, 1987
- A cost-based heuristic for group technology configurationInternational Journal of Production Research, 1987
- Application of the Similarity Coefficient Method in Group TechnologyIIE Transactions, 1986
- MODROC: an extension of rank order clustering for group technologyInternational Journal of Production Research, 1986