Combining Ant Colony Optimization and Dynamic Programming for Solving a Dynamic Facility Layout Problem
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:56236", author = "A. Udomsakdigool and S. Bangsaranthip", title = "Combining Ant Colony Optimization and Dynamic Programming for Solving a Dynamic Facility Layout Problem", 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", volume = "4", number = "4", pages = "359-5", }