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

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.

Authors:

• Parham Azimi
• Hamid Reza Charmchi

Keywords:

• Budget constraint
• Dynamic facility layout problem
• Integer programming
• Simulation

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.