Heuristics and Metaheuristics Approaches for Facility Layout Problems: A Survey

Nurul Nadia Nordin, Lai Soon Lee

Abstract


Facility Layout Problem (FLP) is a NP-hard problem concerned with the arrangement of facilities as to minimize the distance travelled between all pairs of facilities. Many exact and approximate approaches have been proposed with an extensive applicability to deal with this problem. This paper studies the fundamentals of some well-known heuristics and metaheuristics used in solving the FLPs. It is hoped that this paper will trigger researchers for in-depth studies in FLPs looking into more specific interest such as equal or unequal FLPs.

Full Text:

PDF

References


Abdou, G., & Dutta, S.P. (1990). An integrated approach to facilities layout using expert systems.

International Journal Production Research, 28(4), 685-708.

Aiello, G., Scalia, G.L., & Enea, M. (2012). A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding. Expert Systems with Applications, 39, 10352-10358.

Al-Hakim, L.A. (1991). Two graph theoretic procedures for an improved solution to the facilities layout problem. International Journal Production Research, 29(8), 1701-1718.

Amaral, A.R.S. (2006). On the exact solution of a facility layout problem. European Journal of Operational Research, 173(2), 508-518.

Amaral, A.R.S. (2009). A new lower bound for the single row facility layout problem. Discrete Applied Mathematics, 157(1), 183-190.

Armour, G.C., & Buffa, E.S. (1963). A heuristic algorithm and simulation approach to relative location of facilities. Management Science, 9, 294-309.

Asian Productivity Organization. (1971). Manual on plant layout and material handling. Serasia Limited, Hong Kong.

Asl, A.D., & Wong, K.Y. (2015). Solving unequal-area static and dynamic facility layout problems using modified particle swarm optimization. Journal of Intelligent Manufacturing, 1-20.

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

Balakrishnan, J., Cheng, C.H., & Wong, K.F. (2003a). FACOPT: A user friendly facility layout optimization system. Computers & Operations Research, 30(11), 1625-1641.

Balakrishnan, J., Cheng, C.H., Conway, D.G., & Lau, C.M. (2003b). A hybrid genetic algorithm for the dynamic plant layout problem. International Journal of Production Economics, 86(2), 107-120

Bazaraa, M.S. (1975). Computerized layout design: A branch and bound approach. AIIE Transactions, 7, 432-438.

Bozorgi, N., Abedzadeh, M., & Zeinali, M. (2015). Tabu search heuristic for efficiency of dynamic facility layout problem. The International Journal of Advanced Manufacturing Technology, 77(1-4), 689-703.

Benjaafar, S., & Sheikhzadeh, M. (2000). Design of flexible plant layouts. IIE Transactions, 32(4), 309-322.

Bozer, Y.A., Meller, R.D., & Erlebacher, S.J. (1994). An improvement type layout algorithm for single and multiple floor facilities. Management Science, 40(7), 918-932.

Braglia, M., Zanoni, S., & Zavanella, L. (2003). Layout design in dynamic environments: Strategies and quantitative indices. International Journal of Production Research, 41(5), 995-1016.

Burkard, R.E., & Stratman, K.H. (1978). Numerical investigations on quadratic assignment problems. Naval Research Logistics Quarterly, 25, 129-148.

Burkard, R.E., & Rendl, F. (1984). A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operational Research, 17, 169-174.

Camp, D.J., Carter, M.W., & Vannelli, A. (1991). A nonlinear optimization approach for solving facility layout problem. European Journal of Operation Research, 57(2), 174-189.

Chang, M.S., & Lin, H.Y. (2013). An immunized ant colony system algorithm to solve unequal area facility layout problems using flexible bay structure. In Proceedings of the Institute of Industrial Engineers Asian Conference 2013, 9-17.

Chen, G.Y.H. (2013). A new data structure of solution representation in hybrid ant colony optimization for large dynamic facility layout problems. International Journal of Production Economics, 142(2), 362-371.

Cheng, M.Y., & Lien, L.C. (2011). A hybrid ai-based particle bee algorithm for facility layout optimization. Engineering with Computers, 28(1), 57-69.

Cheng, R., Gen, M., & Tozawa, T. (1995). Genetic search for facility layout design under interflows uncertainty. IEEE Transactions, 400-405.

Chwif, L., Barretto, M.R.P., & Moscato, L.A. (1998). A solution to the facility layout problem using simulated annealing. Computers in Industry, 36(1-2), 125-132.

Chiang, W.C., & Kouvelis, P. (1996). An improved tabu search heuristic for solving facility layout design problems. International Journal Production Research, 34, 2565-2586.

Conway, D., & Ventakaramanan, M. (1994). Genetic search and the dynamic facility layout problem.

Computers & Operations Research, 21, 995-960.

de Alvarenga, A.G., Negreiros-Gomes, F.J., & Mestria, M. (2000). Metaheuristic methods for a class of the facility layout problem. Journal of Intelligent Manufacturing, 11(4), 421-430.

Deisenroth, M.P., & Apple, J.M. (1972). A computerized plant layout analysis and evaluation technique (PLANET). Technical Papers 1962, Annual AIIE Twenty-fifth Anniversary Conference and Commission, Norcross, GA, 75-87.

Dorigo, M., Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy. Technical report 91-016 revised, Dipartmento di Politecnico di Milano, Milan.

Drezner, Z. (1980). A heuristic procedure for the layout of a large number of facilities. International Journal of Management Science, 33(7), 907-915.

Drira, A., Pierreval, H., & Gabouj, S.H. (2007). Facility layout problems: a survey. Annual Reviews in Control, 31(2), 255-267.

Dunker, T., Radonsb, G., & Westkampera, E. (2005). Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem. European Journal of Operational Research, 165(1), 55-69

Eberhart, R.C., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1, 39-43.

Edwards, H.K., Gillet, B.E., & Hale, M.C. (1970). Modular allocation technique (MAT). Management Science, 17(3), 161-169

Fortenberry, J.C., & Cox, J.F. (1985). Multiple criteria approach to the facilities layout problem.

International Journal of Production Research, 23(4), 773-782.

Foulds, L.R. (1983). Techniques for facilities layout: Deciding which pairs of activities should be adjacent. Management Science, 29(12), 1414-1426.

Foulds, L.R., & Giffin, J.W. (1985). A graph-theoretic heuristic for minimizing total transportation cost in facilities layout. International Journal Production Research, 23, 1247-1257.

Francis, R.L., McGinnis, L.F. & White, J.A. (1992). Facility layout and location: an analytical approach, Second Edition, Englewood Cliffs, NJ: Prentice Hall.

Gambardella, L.M., Taillard, E.D., & Dorigo, M. (1999). Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 50(2), 167-176.

Gau, K.Y., & Meller, R.D. (1999). An iterative facility layout algorithm. International Journal Production Research, 37(16), 3739-3758.

Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5), 533-549.

Gonçalves, J.F., & Resende, M.G. (2015). A biased random-key genetic algorithm for the unequal area facility layout problem. European Journal of Operational Research, 246(1), 86-107.

Guan, J., & Lin, G. (2016). Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem. European Journal of Operational Research, 248, 899-909.

Hammouche, A., & Webster, D.B. (1985). Evaluation of an application of graph theory to the layout problem. International Journal Production Research, 23(5), 987-1000.

Hani, Y., Amodeo, L., Yalaoui, F., & Chen, H. (2007). Ant colony optimization for solving an industrial layout problem. European Journal of Operational Research, 183(2), 633-642.

Hardin, C.T., & Usher, J.S. (2005). Facility layout using swarm intelligence. International Swarm Intelligence Symposium, 2005, SIS 2005, Proceedings 2005 IEEE, 424-427.

Hasan, M., & Osman, I.H. (1995). Local search algorithm for the maximal planar layout problem.

International Transcript of Operational Research, 2(1), 89-106.

Hassan, M.M.D., Hogg, G.L., & Smith, D.R. (1986). SHAPE: A construction algorithm for area placement evaluation. International Journal of Production Research, 24(5), 1283-1295.

Hassan, M.M.D., & Hogg, G.L. (1987). A review of graph theory applications to the facilities layout problem. Omega, 15(4), 291-300.

Hassan, M.M.D. (1995). Layout design in group technology manufacturing. International Journal of Production Economics, 38(1-2), 173-188.

Heragu, S.S., & Kusiak, A. (1990). Machine layout: an optimization and knowledge based approach. International Journal of Production Research, 28(4), 615-635.

Heragu, S.S., & Alfa, A.S. (1992). Experimental analysis of simulated annealing based algorithms for the layout problem. European Journal of Operational Research, 57(2), 190-202.

Hernandez, L.G., Pierreval, H., Salas-Moreraa, L., & Arauzo-Azofra, A. (2013). Handling qualitative aspects in unequal area facility layout problem: an interactive genetic algorithm. Applied Soft Computing, 13(4), 1718-1727.

Hillier, F.S. (1963). Quantitative tools for plant layout analysis. Journal of Industrial Engineering, 14, 33-40.

Hillier, F.S., & Connors, M.M. (1966). Quadratic assignment problem algorithms and the location of indivisible facilities. Management Science, 13(1), 42-57.

Holland, J.H. (1975). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Michigan Press.

Hosseini-Nasab, H., & Emami, L. (2013). A hybrid particle swarm optimisation for dynamic facility layout problem. International Journal of Production Research, 51(14), 4325-4335.

James, R.W., & Alcorn, P.A. (1991). A guide to facilities planning. New Jersey: Prentice Hall, Englewood Cliffs.

Jue, C., & Yun-Hong, H. (2006). An application of process layout design method to service operation of mass customization. IEEE Transactions, 1008-1013.

Khalil, T.M. (1973). Facilities relative allocation technique (FRAT). International Journal of Productions Research, 11(2), 183-194.

Kim, J.G., & Kim, Y.D. (2000). Layout planning for facilities with fixed shapes and input and output points. International Journal of the Operational Research Society, 38(18), 4635-4653.

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

Knowles, J.D., & Corne, D.W. (2002). Towards landscape analyses to inform the design of a hybrid local for the multiobjective quadratic assignment problem, soft computing system: Design, management and applications. IOS Press, Amsterdam, 271-279.

Kochhar, J.S., & Heragu, S.S. (1998). Multi-hope: A tool for multiple floor layout problems.

International Journal of Production Research, 36(12), 3421-3435.

Kochhar, J.S., & Heragu, S.S. (1999). Facility layout design in a changing environment. International Journal of Production Research, 37(11), 2429-2446.

Komarudin, K. (2009). An improved ant system algorithm for unequal area facility layout problems, Masters Thesis. Faculty of Mechanical Engineering, Universiti Teknologi Malaysia, Malaysia.

Koopmans, T.C., & Beckmann, M.J. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 53-76.

Kothari, R., & Ghosh, D. (2013). Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods. European Journal of Operational Research, 224(1), 93-100.

Kusiak, A., & Heragu, S.S. (1987). The facility layout problem. European Journal of Operational Research, 29, 229-251.

Lee, G.C., & Kim, Y.D. (2000). Algorithms for adjusting shapes of departments in block layouts on the gird-based plane. Omega, 28(1), 111-122.

Lee, R., & Moore, J.M. (1967). CORELAP-Computerized relationship layout planning. Journal of Industrial Engineering, 18, 195-200.

Leung, J. (1992). A graph theoretic heuristic for designing loop-layout manufacturing systems. European Journal Operations Research, 57(2), 243-252.

Liao, C. J., Tseng, C. T., & Luarn, P. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 34(10), 3099-3111.

Mahdi, A.H., Amet, H., & Portman, M.C. (1998). Physical layout with minimization of the transport cost. Research Internal Report, Nancy, France: LORIA.

Matai, R., Singh, S.P., & Mittal, M.L. (2013). Modified simulated annealing based approach for multi objective facility layout problem. International Journal of Operations Research, 51(14), 4273-4288.

McKendall Jr., A.R., & Shang, J. (2006). Hybrid ant systems for the dynamic facility layout problem.

Computers and Operations Research, 33(3), 790-803.

Meller, R.D., & Gau, K.Y. (1996). The facility layout problem: the recent and emerging trends and perspectives. Journal of Manufacturing Systems, 15(5), 351-366.

Mir, M., & Imam, M.H. (2001). A hybrid optimization approach for layout design of unequal-area facilities. Computers and Industrial Engineering, 39(1-2), 49-63.

Nordin, N.N., Zainuddin, Z.M., Salim, S., & Rajeswari, R. (2009). Mathematical modeling and hybrid heuristic for unequal size facility layout problem. Journal of Fundamental of Sciences, 5(1), 79-87.

Ohmori, S., Yoshimoto, K., & Ogawa, K. (2010). Solving facility layout problem via particle swarm optimization. In Proceedings of the Third International Joint Conference on Computational Science and Optimization, 1, 409-413.

Palubeckis, G. (2012). A branch-and-bound algorithm for the single-row equidistant facility layout problem. OR Spectrum, 34, 1-21.

Paul, R.C., Asokan, P., & Prabhakar, V.I. (2006). A solution to the facility layout problem having passages and inner structure walls using particle swarm optimization. International Journal of Advanced Manufacturing Technology, 29(7), 766-771.

Qin, J., Xiang, H., Ye, Y., & Ni, L. (2015). A simulated annealing methodology to multiproduct capacitated facility location with stochastic demand. The Scientific World Journal. Volume 2015, Article ID 826363, 9 pages.

Rezazadeh, H., Ghazanfari, M., Mehrabad, M.S., & Sadjadi, S.J. (2009). An extended discrete particle swarm optimization algorithm for the dynamic facility layout problem. Journal of Zhejiang University-Science, 10(4), 520-529.

Rosenblatt, M.J. (1986). The dynamics of plant layout. Management Science, 32(1), 76-86.

Scholz, D., Petrick, A., & Domschke, W. (2009). STaTS: a slicing tree and tabu search based heuristic for the unequal area facility layout problem. European Journal of Operational Research, 197(1), 166-178.

Seehof, J.M. & Evans, W.O. (1967). Automated layout design program. Journal of Industrial Engineering, 18, 690-695.

Shore, R.H., & Tompkins, J.A. (1980). Flexible facilities design. AIIE Transactions, 12(2), 200-205.

Singh, S.P., & Sharma, R.R.K. (2006). A review of different approaches to the facility layout problems. International Journal of Advance Manufacturing Technology, 30(5), 425-433.

Singh, S.P. (2010). Ant system embedded with local search for solving facility layout problem.

Information Processing and Management, 70, 621-628.

Skorin-Kapov, J. (1990). Tabu search applied to the quadratic assignment problem. ORSA Journal on computing, 2(1), 33-45.

Tam, K. Y. (1992a). A simulated annealing algorithm for allocating space to manufacturing cells. International Journal of Production Research, 30(1), 63-87.

Tam, K. Y. (1992b). Genetic algorithms, function optimization, and facility layout design. European Journal Operational Research, 63, 322-346.

Tate, D.M., & Smith, A.E. (1995). Unequal area facility layout using genetic search. IIE Transactions, 27(4), 465-472.

Technical Note Five: Facility Layout, (2003). Retrieved: http://www.ateneonline.it/chase2e/studenti/tn/6184-7_tn05.pdf

Teo, Y.T., & Ponnambalam, S.G. (2008). A hybrid ACO/PSO heuristic to solve single row layout problem. IEEE International Conference on, 597-602.

Tompkins, J.A., & White, J.A. (1984). Facilities planning, New York: John Wiley and Sons, Inc. Tompkins, J.A., & Reed Jr., R. (1976). An applied model for the facilities design problem.

International Journal Production Research, 14(5), 583-595.

Uddin, M.S. (2015). Hybrid genetic algorithm and variable neighborhood search for dynamic facility layout problem. Open Journal of Optimization, 4(4), 156-167.

Urban, T.L. (1993). A heuristic for the dynamic facility layout problem. IIE transactions, 25(4), 57-63.

Vilarinho, P.M., & Guimarães, R.C. (2003). A facility layout design support system. Investigacao

Operacional, 23, 145-161.

Wang, S., Zuo, X., & Zhao, X. (2014). Solving dynamic double-row layout problem via an improved simulated annealing algorithm. In 2014 IEEE Congress on Evolutionary Computation (CEC), 1299-1304.

White, D.J. (1993). A convex form of the quadratic assignment problem. European Journal Operations Research, 65(3), 407-416.

White, D.J. (1996). A lagrangean relaxation approach for a turbine design quadratic assignment problem. Journal of Operational Research Society, 47, 766-775.

Wu, Y. & Appleton, E. (2002). The optimization of block layout and aisle structure by a genetic algorithm. Computer Industrial Engineering, 41(4), 371-387.

Zetu, D., Banerjee, P., & Schneider, P. (1998). Data input model for virtual reality – aided facility layout. IIE Transactions, 30(7), 597-620.

Zhao, F., Li, G., Hu, H., Du, J., Guo, C., & Li, T. (2014). A novel improved hybrid particle swarm optimisation based genetic algorithm for the solution to layout problems. In Proceeding of the 11th World Congress on Intelligent Control and Automation, 5041-5046.

Zoller, K., & Adendorff, K. (1972). Layout planning by computer simulation. AIIE Transactions, 4(2), 116-125.

Zuo, X., Murray, C.C., & Smith, A.E. (2014). Solving an extended double row layout problem using multiobjective tabu search and linear programming. IEEE Transactions on Automation Science and Engineering, 11(4), 1122-1132.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

The Pertanika Journal of Scholarly Research Reviews, (e-ISSN: 2462-2028, ISSN: 2636-9141) published by Universiti Putra Malaysia Press