Two DEA Based Ant Algorithms for CMS Problems

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.

Authors:

• Hossein Ali Akbarpour
• Fatemeh Dadkhah

Keywords:

• Ant algorithm
• Cellular manufacturing system
• Data envelopment analysis
• Efficiency

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.