Exact Model for the Cell Formation Problem
The Cell Formation Problem (CFP) consists in an optimal grouping of the given machines and parts into cells, so that machines in every cell process as much as possible parts from this cell (intra-cell operations) and as less as possible parts from another cells (inter-cell operations). The grouping efficacy is the objective function for the CFP which simultaneously maximizes the number of intra-cell operations and minimizes the number of inter-cell operations. Currently there are no exact approaches (known to the authors) suggested for solving the CFP with the grouping efficacy objective. The only exact model which solves the CFP in a restricted formulation is due to Elbenani & Ferland . The restriction consists in fixing the number of production cells. The main difficulty of the CFP is the fractional objective function - the grouping efficacy. In this paper we address this issue for the CFP in its common formulation with a variable number of cells. Our computational experiments are made for the most popular set of 35 benchmark instances. For the 14 of these instances using CPLEX software we prove that the best known solutions are exact global optimums.
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
In this chapter, we introduce a new heuristic for Cell Formation Problem in its most general formulation with grouping efficiency as an objective function. Suggested approach applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated until efficiency can be increased for randomly generated configurations of cells. We consider our preliminary results for 10 popular benchmark instances taken from the literature. Also source instances with the solutions we got can be found in the Appendix.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.
In this paper we introduce a new pattern-based approach within the Linear Assignment Model with the purpose to design heuristics for a combinatorial optimization problem (COP). We assume that the COP has an additive (separable) objective function and the structure of a feasible (optimal) solution to the COP is predefined by a collection of cells (positions) in an input file. We define a pattern as a collection of positions in an instance problem represented by its input file (matrix). We illustrate the notion of pattern by means of some well known problems in COP among them the Linear Ordering Problem, Cell Formation Problem (CFP) just to mention a couple. The CFP is defined on a Boolean input matrix which rows represent machines and columns - parts. The CFP consists in finding three optimal objects: a block-diagonal collection of rectangles, a rows (machines) permutation, and a columns (parts) permutation such that the grouping efficacy is maximized. The suggested heuristic combines two procedures: the pattern-based procedure to build an initial solution and an improvement procedure to obtain a final solution with high grouping efficacy for the CFP. Our computational experiments with the most popular set of 35 benchmark instances show that our heuristic outperforms all well known heuristics and returns either the best known or improved solutions to the CFP.
The Cell Formation Problem (CFP) is an NP-hard optimization problem considered for cellular man- ufacturing systems. Because of its high computational complexity there have been developed a lot of heuristics and almost no exact algorithms for solving this problem. In this paper we suggest a branch- and-bound algorithm which provides exact solutions for the CFP with the grouping efficacy objective function. To linearize this fractional objective function we apply the Dinkelbach approach. Our algorithm finds optimal solutions for 24 of the 35 popular benchmark instances from literature and for the remaining instances it finds good solutions close to the best known. The difference in the grouping efficacy with the best known solutions is always less than 1.5%.
The earliest approaches to the cell formation problem in group technology, dealing with a binary machine-part incidence matrix, were aimed only at minimizing the number of intercell moves (exceptional elements in the block-diagonalized matrix). Later on this goal was extended to simultaneous minimization of the numbers of exceptions and voids, and minimization of intercell moves and within-cell load variation, respectively. In this paper we design the first exact branch-and-bound algorithm to create a Pareto-optimal front for the bi-criterion cell formation problem.
The cell formation problem (CFP) is an NP-hard optimization problem considered for cell manufacturing systems. Because of its high computational complexity several heuristics have been developed for solving this problem. In this paper we present a branch and bound algorithm which provides exact solutions of the CFP. This algorithm finds optimal solutions for 13 problems of the 35 popular benchmark instances from the literature.
A form for an unbiased estimate of the coefficient of determination of a linear regression model is obtained. It is calculated by using a sample from a multivariate normal distribution. This estimate is proposed as an alternative criterion for a choice of regression factors.