A dynamic programming–enhanced simulated annealing algorithm for solving bi-objective cell formation problem with duplicate machines

Mohammadi, M.; Forghani, K.

Abstract: Cell formation process is one of the first and the most important steps in designing cellular manufacturing systems. It consists of identifying part families according to the similarities in the design, shape, and presses of parts and dedicating machines to each part family based on the operations required by the parts. In this study, a hybrid method based on a combination of simulated annealing algorithm and dynamic programming was developed to solve a bi-objective cell formation problem with duplicate machines. In the proposed hybrid method, each solution was represented as a permutation of parts, which is created by simulated annealing algorithm, and dynamic programming was used to partition this permutation into part families and determine the number of machines in each cell such that the total dissimilarity between the parts and the total machine investment cost are minimized. The performance of the algorithm was evaluated by performing numerical experiments in different sizes. Our computational experiments indicated that the results were very encouraging in terms of computational time and solution quality.

How to cite this paper

 Mohammadi, M & Forghani, K. (2015). A dynamic programming–enhanced simulated annealing algorithm for solving bi-objective cell formation problem with duplicate machines.Decision Science Letters , 4(2), 261-276.

References

Adil, G.K., & Rajamani, D. (2000). The trade-off between intracell and intercell moves in group technology cell formation. Journal of Manufacturing Systems, 19, 305–317.

Aktürk, M.S., & Balkose, H.O. (1996). Part-machine grouping using a multi-objective cluster analysis. International Journal of Production Research, 34, 2299–2315.

Ar?kan, F., & Güng?r, Z. (2009). Modeling of a manufacturing cell design problem with fuzzy multi-objective parametric programming. Mathematical and Computer Modelling, 50, 407–420.

Arkat, J., Saidi, M., & Abbasi, B. (2007). Applying simulated annealing to cellular manufacturing system design. International Journal of Advanced Manufacturing Technology, 32, 531–536.

Balakrishnan, J., & Jog, P.D. (1995). Manufacturing cell formation using similarity coefficients and a parallel genetic TSP algorithm: formulation and comparison. Mathematical and Computer Modelling, 21, 61–73.

Banerjee, I., & Das, P. (2012). Group technology based adaptive cell formation using predator-prey genetic algorithm. Applied Soft Computing, 12, 559–572.

Boctor, F.F. (1991). A linear formulation of the machine-part cell formation problem. International Journal of Production Research, 29, 343–356.

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, 279–284.

Chan, F.T.S., Lau, K.W., Chan, P.L.Y., & Choy, K.L. (2006). Two-stage approach for machine-part grouping and cell layout problems. Robotics and Computer-Integrated Manufacturing, 22, 217–238.

Chang, P.T., & Lee, E.S. (2000). Multisolution method for cell formation exploring practical alternatives in group technology manufacturing. Computers and Mathematics with Applications, 40, 1285–1296.

Chen, W.H., & Srivastava, B. (1994). Simulated annealing procedures for forming machine cells in group technology. European Journal of Operational Research, 75, 100–111.

Chiang, C.P., & Lee, S.D. (2004). Joint determination of machine cells and linear intercell layout. Computers and Operations Research, 31, 1603–1619.

Filho, E.V.G., & Tiberti, A.J. (2006). A group genetic algorithm for the machine cell formation problem. International Journal of Production Economics, 102, 1–21.

Garbie, I.H., Parsaei, H.R., & Leep, H.R. (2008). Machine Cell Formation Based on a New Similarity Coefficient. Journal of Industrial and Systems Engineering, 1, 318–344.

Ghezavati, V.R., & Saidi-Mehrabad, M. (2011). An efficient hybrid self-learning method for stochastic cellular manufacturing problem: A queuing-based analysis. Expert Systems with Applications, 38, 1326–1335.

Ghosh, T., Sengupta, S., Chattopadhyay, M., & Dan, P.K. (2011). Meta-heuristics in cellular manufacturing: A state-of-the-art review. International Journal of Industrial Engineering Computations, 2, 87–122.

Jeon, G., & Leep, H.R. (2006). Forming part families by using genetic algorithm and designing machine cells under demand changes. Computers and Operations Research, 33, 263–283.

Kao, Y., & Lin, C.H. (2012). A PSO-based approach to cell formation problems with alternative process routings. International Journal of Production Research, 50, 4075–4089.

Kaufmann, L., & Broeckx, F. (1978). An algorithm for the quadratic assignment problem using Benders’ decomposition. European Journal of Operational Research, 2, 204–211.

Kazerooni, M.L., Luong, H.S., & Abhary, K. (1997). A genetic algorithm based cell design considering alternative routing. International Journal of Computer Integrated Manufacturing Systems, 10, 93–107.

Kioon, S.A., Bulgak, A.A., & Bektas, T. (2009). Integrated cellular manufacturing systems design with production planning and dynamic system reconfiguration. European Journal of Operational Research, 192, 414–428.

Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimisation by simulated annealing. Science, 220, 671–680.

McAuley, J. (1972). Machine grouping for efficient production. The Production Engineer, 51, 53–57.

Mungwattana, A. (2000). Design of cellular manufacturing systems for dynamic and uncertain production requirements with presence of routing flexibility. PhD thesis, Faculty of the Virginia Polytechnic Institute and State University.

Onwubolu, G.C., & Mutingi, M. (2001). A genetic algorithm approach to cellular manufacturing systems. Computers and Industrial Engineering, 39, 125–144.

Saeedi, S., Solimanpur, M., Mahdavi, I., & Javadian, N. (2010). Heuristic approaches for cell formation in cellular manufacturing. Journal of Software Engineering and Applications, 3, 674–682.

Saghafian, S., & Akbari Jokar, M.R. (2009). Integrative cell formation and layout design in cellular manufacturing systems. Journal of Industrial and Systems Engineering, 3, 97–115.

Singh, N. (1993). Design of cellular manufacturing systems: An invited review. European Journal of Operational Research, 69, 284–291.

Solimanpur, M., Vrat, P., & Shankar, R. (2004). A multi-objective genetic algorithm approach to the design of cellular manufacturing systems. International Journal of Production Research, 42, 1419–1441.

Tavakkoli-Moghaddam, R., Aryanezhad, M.B., Safaei, N. & Azaron, A. (2005). Solving a dynamic cell formation problem using metaheuristics. Applied Mathematics and Computation, 170, 761–780.

Tavakkoli-Moghaddam, R., Safaei, N., & Sassani, F. (2008). A new solution for a dynamic cell formation problem with alternative routing and machine costs using simulated annealing. Journal of the Operational Research Society, 59, 443–454.

Wemmerl?v, U., & Hyer, N.L. (1989). Cellular manufacturing in the US industry: A survey of users. International Journal of Production Research, 27, 1511–1530.

Yin, Y., & Yasuda, K. (2005). Similarity coefficient methods applied to the cell formation problem: a comparative investigation. Computers and Industrial Engineering, 48, 471–489.

Yin, Y., & Yasuda, K. (2006). Similarity coefficient methods applied to the cell formation problem: a taxonomy and review. International Journal of Production Economics, 101, 329–352.