Combining Ant Colony Optimization and Dynamic Programming for Solving a Dynamic Facility Layout Problem

Authors: A. Udomsakdigool, S. Bangsaranthip

Abstract:

This paper presents an algorithm which combining ant colony optimization in the dynamic programming for solving a dynamic facility layout problem. The problem is separated into 2 phases, static and dynamic phase. In static phase, ant colony optimization is used to find the best ranked of layouts for each period. Then the dynamic programming (DP) procedure is performed in the dynamic phase to evaluate the layout set during multi-period planning horizon. The proposed algorithm is tested over many problems with size ranging from 9 to 49 departments, 2 and 4 periods. The experimental results show that the proposed method is an alternative way for the plant layout designer to determine the layouts during multi-period planning horizon.

Keywords: Ant colony optimization, Dynamicprogramming, Dynamic facility layout planning, Metaheuristic

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

References:

[1] R.H. Shore and J.A. Tompkins, "Flexible facilities design," AIIE Transactions, 1980, vol.12, pp. 200-205.
[2] M.J. Rosenblatt, " The dynamics of plant layout," Management Science, 1986, vol. 32, pp. 76- 86.
[3] T.L. Urban, "A heuristic for the dynamic facility layout problem," IIE Transactions, 1993, vol. 25, pp. 57-63.
[4] D. G. Conway, M. A. Venkataramanan, "Genetic search and the dynamic facility layout problem," Computers & Operations Research, 1994, vol. 2, no. 8, pp. 955-960.
[5] B. K. Kaku and J. B. Mazzola, "A tabu search heuristic for the dynamic plant layout problem," INFORMS Journal on Computing , 1997, vol. 9, no. 4, pp. 374-384.
[6] J. Balakrishnan, C. H. Cheng and G. Conway, "An improved pair-wise exchange heuristic for the dynamic plant layout problem," International Journal of Production Research, 2000, vol. 38, no. 13, pp. 3067-3077.
[7] A. Baykasoglu and N. Z. Z. Gindy, "A simulated annealing algorithm for dynamic facility layout problem," Computers&Operations Research, 2001, vol.28, no. 14, pp. 1403-1426.
[8] J. Balakrishnan, C. H. Cheng, G. Conway and C. M. Lau, "A hybrid genetic algorithm for the dynamic plant layout problem," International Journal of Production Economics, 2003, vol. 86, pp. 107-120.
[9] D. Thomas, R. G├╝nter, and W. Engelbert, " Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem," European Journal of Operational Research, 2005, vol. 165, pp. 55-69.
[10] A.R. McKendall Jr, S. Jin, and K. Saravanan, "Simulated annealing heuristics for the dynamic facility layout problem," Computers & Operations Research, 2006, vol.33, pp. 2431-2444.
[11] J. Balakrishnana, and C. H. Cheng, "The dynamic plant layout problem: Incorporating rolling horizons and forecast uncertainty," Omega, 2009, vol. 37, pp. 165 - 177.
[12] J. Balakrishnan, C. H. Cheng, "Dynamic layout algorithms: a state-ofthe- art survey," Omega, International Journal of Management Sciences, 1998, vol. 26, pp. 507-521.
[13] A. Baykasoglu, T. Dereli, and I. Sabuncu, "An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems," Omega, 2006, vol. 34, no. 4, pp. 385-396.
[14] A. R. McKendall Jr., and J. Shang , " Hybrid ant systems for the dynamic facility layout problem," Computers & Operations Research, 2006, vol. 33, no. 3, pp.790-803.
[15] M. Dorigo, and T. St├╝tzle, "Ant colony optimization" The MIT Press, Massachusetts, Cambridge, MA, 2004.