An Improved DPSO Algorithm for Cell Formation Problem

Document Type : Research Paper


1 Industrial Engineering college, Islamic Azad university, South Tehran Branch

2 Department of Decision Science and Knowledge Engineering, University of Economic Sciences, Tehran, Iran


Cellular manufacturing system, an application of group technology, has been considered as an effective method to obtain productivity in a factory. For design of manufacturing cells, several mathematical models and various algorithms have been proposed in literature. In the present research, we propose an improved version of discrete particle swarm optimization (PSO) to solve manufacturing cell formation problem effectively. When a local optimal solution is reached with PSO, all particles gather around it, and escaping from this local optimum becomes difficult. To avoid premature convergence of PSO, we present a new hybrid evolutionary algorithm, called discrete particle swarm optimization-simulated annealing (DPSO-SA), based on the idea that PSO ensures fast convergence, while SA brings search out of local optimum. To illustrate the behavior of the proposed model and verify the performance of the algorithm, we introduce a number of numerical examples. The performance evaluation shows the effectiveness of the DPSO-SA.


Main Subjects

Albadawi, Z., Bashir, H. A., & Chen, M. (2005).A mathematical approach for the formation of
manufacturing cells. Computers & Industrial Engineering,48(1), 3-21.
Aljaber, N., Baek, W., & Chen, C. L. (1997).A tabu search approach to the cell formation
problem. Computers & industrial engineering, 32(1), 169-185.
Banks, A., Vincent, J., &Anyakoha, C. (2008).A review of particle swarm optimization. Part II:
hybridisation, combinatorial, multicriteria and constrained optimization, and indicative
applications. Natural Computing, 7(1), 109-124.
Bertsimas, D., &Tsitsiklis, J. (1993).Simulated annealing. Statistical science,8(1), 10-15.
Boulif, M., &Atif, K. (2006).A new branch-&-bound-enhanced genetic algorithm for the
manufacturing cell formation problem. Computers & operations research,33(8), 2219-2245.
Burbidge, J. L.(1989). Production Flow Analysis. Oxford: Clarendon Press.
Caux, C., Bruniaux, R., &Pierreval, H. (2000). Cell formation with alternative process plans and
machine capacity constraints: A new combined approach. International Journal of Production
Economics, 64(1), 279-284.
Chu, C. H., &Hayya, J. C. (1991).A fuzzy clustering approach to manufacturing cell
formation. The international journal of production research, 29(7), 1475-1487.
Dimopoulos, C., &Zalzala, A. M. (2000). Recent developments in evolutionary computation for
manufacturing optimization: problems, solutions, and comparisons. Evolutionary Computation,
IEEE Transactions on, 4(2), 93-113.
Gonçalves, J. F., &Resende, M. G. (2004).An evolutionary algorithm for manufacturing cell
formation. Computers & Industrial Engineering, 47(2), 247-273.
Hachicha, W., Masmoudi, F., &Haddar, M. (2008). Principal component analysis model for
machine-part cell formation problem in group technology. arXiv preprint arXiv:0803.3343.
Hwang, H., &Ree, P. (1996).Routes selection for the cell formation problem with alternative part
process plans. Computers & industrial engineering, 30(3), 423-431.
Kao, Y., & Lin, C. H. (2012).A PSO-based approach to cell formation problems with alternative
process routings. International Journal of Production Research,50(15), 4075-4089.
Kennedy, J., &Eberhart, R. (1995).Particle swarm optimization.Proceeding of IEEE
International Conference on Neural Networks, 4, 1942-1948.
Kirkpatrick, S., Gelatt, C. D., &Vecchi, M. P. (1983).Optimization by simmulated
annealing. science, 220(4598), 671-680.
Kusiak, A. (1987). The generalized group technology concept. International journal of
production research, 25(4), 561-569.
Li, J., Chu, C. H., Wang, Y., & Yan, W. (2007).An improved fuzzy clustering method for
cellular manufacturing. International journal of production research,45(5), 1049-1062.
Li, X., Baki, M. F., &Aneja, Y. P. (2010).An ant colony optimization metaheuristic for machine–
part cell formation problems. Computers & Operations Research, 37(12), 2071-2081.
Nagi, R., Harhalakis, G., &Proth, J. M. (1990). Multiple Routings and Capacity Consideration in
Group Technology Applications. International Journal of Production Research,28, pp. 2243-
Nair, G. J., &Narendran, T. T. (1998). CASE: A clustering algorithm for cell formation with
sequence data. International Journal of Production Research, 36(1), 157-180.
Niknam, T. (2006, November). An approach based on particle swarm optimization for optimal
operation of distribution network considering distributed generators. In IEEE Industrial
Electronics, IECON 2006-32nd Annual Conference on (pp. 633-637).IEEE.
Niknam, T., Amiri, B., Olamaei, J., &Arefi, A. (2009). An efficient hybrid evolutionary
optimization algorithm based on PSO and SA for clustering.Journal of Zhejiang University
Science A, 10(4), 512-519.
Noktehdan, A., Karimi, B., &HusseinzadehKashan, A. (2010). A differential evolution algorithm
for the manufacturing cell formation problem using group based operators. Expert Systems with
Applications, 37(7), 4822-4829.
Nouri, H., & Hong, T. S. (2013). Development of bacteria foraging optimization algorithm for
cell formation in cellular manufacturing system considering cell load variations. Journal of
Manufacturing Systems, 32(1), 20-31.
Mahdavi, I., Teymourian, E., Baher, N. T., &Kayvanfar, V. (2013).An integrated model for
solving cell formation and cell layout problem simultaneously considering new
situations. Journal of Manufacturing Systems,32(4), 655-663.
Olamaei, J., Niknam, T., &Gharehpetian, G. (2008). Application of particle swarm optimization
for distribution feeder reconfiguration considering distributed generators. Applied Mathematics
and computation, 201(1), 575-586.
Pailla, A., Trindade, A. R., Parada, V., & Ochi, L. S. (2010). A numerical comparison between
simulated annealing and evolutionary approaches to the cell formation problem. Expert Systems
with Applications, 37(7), 5476-5483.
Paydar, M. M., &Sahebjamnia, N. (2009).Designing a mathematical model for cell formation
problem using operation sequence. Journal of Applied Operational Research, 1(1), 30-38.
Poli, R., Kennedy, J., & Blackwell, T. (2007). Particle swarm optimization.Swarm
intelligence, 1(1), 33-57.
Saeidi, S., Solimanpur, M., Mahdavi, I., &Javadian, N. (2014).A multi-objective genetic
algorithm for solving cell formation problem using a fuzzy goal programming approach. The
International Journal of Advanced Manufacturing Technology, 70(9-12), 1635-1652.
Sankaran, S., &Kasilngam, R. G. (1990).An integrated approach to cell formation and part
routing in group technology manufacturing systems.Engineering Optimization+ A35, 16(3), 235-
Sayadi, M. K., Hafezalkotob, A., &Naini, S. G. J. (2013). Firefly-inspired algorithm for discrete
optimization problems: An application to manufacturing cell formation. Journal of
Manufacturing Systems, 32(1), 78-84.
Shafer, S. M., & Meredith, J. R. (1990).A comparison of selected manufacturing cell formation
techniques. The international journal of production research, 28(4), 661-673.
Shiyas, C. R., &MadhusudananPillai, V. (2014).A mathematical programming model for
manufacturing cell formation to develop multiple configurations. Journal of Manufacturing
Systems, 33(1), 149-158.
Shunk, D. L. (1985). Group Technology Provides Organized Approach to Realizing Benefits of
CIMS.Industrial Engineering, 17, 74-81.
Sofianopoulou, S.(1999). Manufacturing cells design with alternative process plans and/or
replicate machines. International Journal of Production Research,37(3), 707-720.
Sun, D., Lin, L., &Batta, R. (1995).Cell formation using tabusearch.Computers& industrial
engineering, 28(3), 485-494.
Tavakkoli-Moghaddam, R., Javadian, N., Khorrami, A., &Gholipour-Kanani, Y. (2010).Design
of a scatter search method for a novel multi-criteria group scheduling problem in a cellular
manufacturing system. Expert Systems with Applications, 37(3), 2661-2669.
Tavakkoli-Moghaddam, R., Ranjbar-Bourani, M., Amin, G. R., &Siadat, A. (2012).A cell
formation problem considering machine utilization and alternative process routes by scatter
search. Journal of Intelligent Manufacturing, 23(4), 1127-1139.
Won, Y. (2000).Two-phase approach to GT cell formation using efficient p-median
formulations. International Journal of Production Research, 38(7), 1601-1613.
Wu, T. H., Chang, C. C., &Yeh, J. Y. (2009).A hybrid heuristic algorithm adopting both
Boltzmann function and mutation operator for manufacturing cell formation
problems. International Journal of Production Economics, 120(2), 669-688.
Wu, T. H., Chung, S. H., & Chang, C. C. (2009). Hybrid simulated annealing algorithm with
mutation operator to the cell formation problem with alternative process routings. Expert Systems
with Applications, 36(2), 3652-3661.
Wu, T. H., Low, C., & Wu, W. T. (2004). A tabu search approach to the cell formation
problem. The International Journal of Advanced Manufacturing Technology, 23(11-12), 916-
Yang, M. S., & Yang, J. H. (2008). Machine-part cell formation in group technology using a
modified ART1 method. European Journal of Operational Research, 188(1), 140-152.
Zhao, C., & Wu, Z. (2000).A genetic algorithm for manufacturing cell formation with multiple
routes and multiple objectives. International Journal of Production Research, 38(2), 385-395.