An efficient exact model for the cell formation problem with a variable number of production cells
Preprint
Abstract
The Cell Formation Problem has been studied as an optimization problem in manufacturing for more than 90 years. It consists of grouping machines and parts into manufacturing cells in order to maximize loading of cells and minimize movement of parts from one cell to another. Many heuristic algorithms have been proposed which are doing well even for large-sized instances. However, only a few authors have aimed to develop exact methods and most of these methods have some major restrictions such as a fixed number of production cells for example. In this paper we suggest a new mixed-integer linear programming model for solving the cell formation problem with a variable number of manufacturing cells. The popular grouping efficacy measure is used as an objective function. To deal with its fractional nature we apply the Dinkelbach approach. Our computational experiments are performed on two testsets: the first consists of 35 well-known instances from the literature and the second contains 32 instances less popular. We solve these instances using CPLEX software. Optimal solutions have been found for 63 of the 67 considered problem instances and several new solutions unknown before have been obtained. The computational times are greatly decreased comparing to the state-of-art approaches.Keywords
All Related Versions
This publication has 43 references indexed in Scilit:
- Exact model for the cell formation problemOptimization Letters, 2014
- An exact model for cell formation in group technologyComputational Management Science, 2012
- Machine-part cell formation in group technology using a modified ART1 methodEuropean Journal of Operational Research, 2008
- Generalized part family formation using neural network techniquesJournal of Manufacturing Systems, 1992
- The production data-based similarity coefficient versus Jaccard's similarity coefficientComputers & Industrial Engineering, 1991
- Machine grouping — Expert systems: Comparison between single linkage and average linkage clustering techniques in forming machine cellsComputers & Industrial Engineering, 1988
- Efficient solving of the group technology problemJournal of Manufacturing Systems, 1987
- Grouping of parts and components in flexible manufacturing systemsEuropean Journal of Operational Research, 1986
- Weighted similarity measure heuristics for the group technology machine clustering problemOmega, 1985
- Machine clustering for economic productionEngineering Costs and Production Economics, 1985