A new Heuristic Algorithm for the Dynamic Facility Layout Problem with Budget Constraint

Authors: Parham Azimi, Hamid Reza Charmchi

Abstract:

In this research, we have developed a new efficient heuristic algorithm for the dynamic facility layout problem with budget constraint (DFLPB). This heuristic algorithm combines two mathematical programming methods such as discrete event simulation and linear integer programming (IP) to obtain a near optimum solution. In the proposed algorithm, the non-linear model of the DFLP has been changed to a pure integer programming (PIP) model. Then, the optimal solution of the PIP model has been used in a simulation model that has been designed in a similar manner as the DFLP for determining the probability of assigning a facility to a location. After a sufficient number of runs, the simulation model obtains near optimum solutions. Finally, to verify the performance of the algorithm, several test problems have been solved. The results show that the proposed algorithm is more efficient in terms of speed and accuracy than other heuristic algorithms presented in previous works found in the literature.

Keywords: Budget constraint, Dynamic facility layout problem, Integer programming, Simulation

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

References:

[1] Drira, A, Pierreval, H., Hajri-Gabouj, H., 2007. Facility layout problems: A survey. Annual Reviews in Control. 31, 255-267.
[2] Tompkins, J., White, J., Bozer, Y., Tanchoco, J., 2003. Facilities planning. third ed. John Wiley & Sons, New Jersey.
[3] Dong, M., Wua, C., Hou, F., 2009. Shortest path based simulated annealing algorithm for dynamic facility layout problem under dynamic business environment. Expert Systems with Applications.36, 11221- 11232.
[4] Gary, Y., Chen, K.J., Rogers, A., 2009. Multi-objective evaluation of dynamic facility layout using ant colony optimization. Proceedings of the 2009 Industrial Engineering Research Conference.
[5] Page, A.L., 1991. New product development survey: Performance and best practices. PDMA conference.
[6] Balakrishnan, J., Cheng, C.H., 2009. The dynamic plant layout problem: Incorporating rolling horizons and forecast uncertainty. Omega, 37, 165 - 177.
[7] Kouvelis, P., Kurawarwala, A. A., Gutierrez, G. J., 1992. Algorithms for robust single and multiple periods layout planning for manufacturing systems. European Journal of Operations Research. 632, 287-303
[8] Rosenblatt M.J., 1986. The dynamics of plant layout. Management Science. 321, 76-86.
[9] Urban, T. L., 1998. Solution procedures for the dynamic facility layout problem. Annals of operations research.761, 323-342.
[10] Lacksonen, T.A., Enscore, E.E., 1993. Quadratic assignment algorithms for the dynamic layout problem. International Journal of Production Research.313, 503-17.
[11] Balakrishnan, J., Cheng, C. H., 2000. Genetic search and the dynamic layout problem: An improved algorithm. Computers and Operations Research 276, 587-593.
[12] Kaku, B., Mazzola, J. B., 1997. A tabu search heuristic for the plant layout problem. INFORMS Journal on Computing. 94, 374-384.
[13] Baykasoglu, A., Gindy, N. N. Z., 2001. A simulated annealing algorithm for dynamic facility layout problem. Computers and Operations Research. 2814, 1403-1426.
[14] Balakrishnan, J., Cheng, C.H., Daniel, G. Conway, A., Lau, C.M., 2003. A hybrid genetic algorithm for the dynamic plant layout problem. International Journal of Production Economics.86, 107-120.
[15] Erel, J.B., Ghosh, J., Simon, J.T., 2005. New heuristic for the dynamic layout problem. Journal of the Operational Research Society.568, 1001.
[16] McKendall, A.R, Shang, J., 2006a. Hybrid ant systems for the dynamic facility layout problem .Computers & Operations Research. 333, 790- 803.
[17] McKendall, A.R., Shang, J., Kuppusamy, S., 2006b. Simulated annealing heuristics for the dynamic facility layout problem, Computers & Operations Research. 33, 2431-2444.
[18] Rodriguez, J.M., MacPhee, F.C., Bonham, D.J., Bhavsar, V.C., 2006. Solving the dynamic plant layout problem using a new hybrid metaheuristic algorithm. International Journal of High Performance Computing and Networking. 45/6, 286-294.
[19] Krishnan, K.K., Cheraghi, S.H., Nayak, C. N., 2006. Dynamic frombetween charts: A new tool for solving dynamic facility layout problems. International Journal of Industrial and Systems Engineering. 11/2, 182-200.
[20] Balakrishnan, J., Cheng, C. H., 1998. Dynamic layout Algorithms: A state-of-the art survey. Omega .264, 507-521.
[21] Kulturel-Konak, S., 2007. Approaches to uncertainties in facility layout problems: Perspectives at the beginning of the 21st century. Journal of Intelligent Manufacturing. 182, 273-284.
[22] Dunker, T., Radons, G., Westkamper, E., 2005. Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem. European Journal of Operational Research. 1651, 55-69.
[23] McKendall A.R., Hakobyan, A., 2010. Heuristics for the dynamic facility layout problem with unequal-area departments. European Journal of Operational Research. 201, 171-182.
[24] Balakrishnan, J., Jacobs, F. R., Venkataramanan, M. A.,1992. Solutions for the constrained dynamic facility layout problem. European Journal of Operational Research, 57(2), 280-286.
[25] Baykasoglu, A., Dereli, T., Sabuncu, I., 2006. An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems. Omega, 34(4), 385-396.
[26] Sahin, R., Ertogral, K., Turkbey, O., 2010. A simulated annealing heuristic for the dynamic facility layout problem with budget constraint. Computers & Industrial Engineering, 59, 308-313.
[27] Azimi P., Daneshvar Ghorbai P., 2010. An efficient heuristic algorithm for the traveling salesman problem. 8th Heinz Nixdorf Symposium in Advanced Manufacturing and Sustainable logistics, Paderborn, Germany.