Two DEA Based Ant Algorithms for CMS Problems

Authors: Hossein Ali Akbarpour, Fatemeh Dadkhah

Abstract:

This paper considers a multi criteria cell formation problem in Cellular Manufacturing System (CMS). Minimizing the number of voids and exceptional elements in cells simultaneously are two proposed objective functions. This problem is an Np-hard problem according to the literature, and therefore, we can-t find the optimal solution by an exact method. In this paper we developed two ant algorithms, Ant Colony Optimization (ACO) and Max-Min Ant System (MMAS), based on Data Envelopment Analysis (DEA). Both of them try to find the efficient solutions based on efficiency concept in DEA. Each artificial ant is considered as a Decision Making Unit (DMU). For each DMU we considered two inputs, the values of objective functions, and one output, the value of one for all of them. In order to evaluate performance of proposed methods we provided an experimental design with some empirical problem in three different sizes, small, medium and large. We defined three different criteria that show which algorithm has the best performance.

Keywords: Ant algorithm, Cellular manufacturing system, Data envelopment analysis, Efficiency

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332316

References:

[1] T. Ertay, and D. Ruan, "Data envelopment analysis based decision model for optimal operator allocation in CMS," European Journal of Operational Research, 2005, 164, 800-810.
[2] A. J. Ruiz-Torres, and F. J. Lo'pez, "Using the FDH formulation of DEA to evaluate a multi-criteria problem in parallel machine scheduling," Computers & Industrial Engineering, 2004, 47, 107-121.
[3] I. Mahdavi, B. F. Javadi, K. Alipour and J. Slomp, "Designing a new mathematical model for cellular manufacturing system based on cell utilization," Applied Mathematics and Computation, 2007, 190, 662- 670.
[4] I. Mahdavi, M. M. Paydar, M. Solimanpur and A. Heidarzade, "Genetic algorithm approach for solving a cell formation problem in cellular manufacturing," Expert Systems with Applications, 2009, 36, 6598- 6604.
[5] A. Charnes, W.W. Cooper, and E. Rhodes, "Measuring the efficiency of decision making units," European Journal of Operation Research, 1978, 429-444.
[6] R. D. Banker, A. Charnes, and W.W. Cooper, "Some models for estimating technical and scale inefficiencies in data envelopment analysis," Management Science, 1984, 30, 1078-1092.
[7] M. R. Alirezaee and M. Afsharian, "A complete ranking of DMUs using restrictions in DEA models," Applied Mathematics and Computation, 2007, 189, 1550-1559.
[8] M. Dorigo, G. Di Caro and L. M. Gamberdella, "Ant Algorithms for Discrete Optimization," Artificial Life, MIT Press, 1999.