Abstract
This paper presents a new heuristic for solving a facility layout problem. The proposed heuristic works on the non-greedy systematic pairwise exchange of two facilities, that is 2-exchange neighbourhood search based on non-greedy strategy. The proposed heuristic is applied on a large number of test problems provided by different authors in the quadratic assignment problem (QAP) library (Burkard, Karisch, Rendl, J Glob Optim 10(1):391–403, 1997) with problem size ranging from 12 to 256. Out of the 135 test problems available in the QAP library, the proposed heuristic reached optimal solutions for 64 test problems and matched the best known available solution for the other 15 test problems. For the remaining 56 test problems, the proposed approach reports highly encouraging solutions for 44 test problems (within the 2 % of deviation from the optimal/best known solutions), and for the remaining 12 problems, the proposed approach provides fair solution in reasonable time. Comparison with other meta-heuristic approaches (Ro-TS, RE-TS, GEN and SA) shows the effectiveness of the proposed heuristic.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Armour GC, Buffa ES (1963) A heuristic algorithm and simulation approach to relative location of facilities. Manag Sci 9(2):294–309
Banerjee P, Montreuil B, Moodie CL, Kashyap RL (1992) A modeling of interactive facilities layout designer reasoning using qualitative patterns. Int J Prod Res 30(3):433–453
Bazarra MS, Sherali HD (1980) Bender’s partitioning scheme applied to a new formulation of the quadratic assignment problem. Nav Res Logist Q, Issue 1:29–41
Bazaraa MS, Kirca O (1983) A branch-and-bound-based heuristic for solving the QAP. Nav Res Logist Q 30(2):287–304
Block TE (1978) FATE: a new construction algorithm for facilities layout. J Eng Prod 2:111–120
Bozer YA, Meller RD (1994) An improvement-type layout algorithm for single and multiple floor facilities. Manag Sci 40(7):918–932
Burkard RE, Stratman KH (1978) Numerical investigations on quadratic assignment problems. Nav Res Logist Q 25(1):129–148
Burkard RE, Bonniger T (1983) A heuristic for quadratic Boolean program with application to quadratic assignment problems. Eur J Oper Res 13(4):374–386
Burkard RE (1984) Locations with spatial interaction—quadratic assignment problem. In: Francis RL, Mirchandani PB (eds) Discrete location theory. Academic, New York
Burkard RE, Rendl F (1984) A thermodynamically motivated simulation procedure for combinatorial optimization problems. Eur J Oper Res 17(2):169–174
Burkard RE, Karisch S, Rendl F (1997) QAPLIB—a quadratic assignment problem library. J Glob Optim 10(1):391–403
Christofides N, Benavent E (1989) An exact algorithm for the quadratic assignment problem on a tree. Oper Res 37(5):760–768
Deisenroth MP, Apple JM (1972) A computerized plant layout analysis and evaluation technique. Technical paper, Annual AIIE Conference, Norcross, GA
Diponegoro A, Sarker BR (2003) Machine assignment in a nonlinear multi-product flowline. J Oper Res Soc 54:472–489
Edwards HK, Gillett BE, Hale ME (1970) Modular allocation technique (MAT). Manag Sci 17(3):161–169
Fleurent C, Ferland JA (1994) Genetic hybrids for the quadratic assignment problem. DIMACS Ser Math Theor Comput Sci 16(IRO-870):190–206
Foulds LR (1983) Techniques for facilities layout: deciding which pairs of activities should be adjacent. Manag Sci 29(12):1414–1426
Gavett JW, Plyter NV (1966) The optimal assignment of facilities to locations by branch and bound. Oper Res 14(2):210–232
Gilmore PC (1962) Optimal and suboptimal algorithms for the quadratic assignment problem. J Soc Ind Appl Math 10(2):305–313
Goetschalckx M (1992) An interactive layout heuristic based on hexagonal adjacency graphs. Eur J Oper Res 63(2):304–321
Hassan MMD, Hogg GL, Smith DR (1986) SHAPE: a construction algorithm for area placement evaluation. Int J Prod Res 24(5):1283–1295
Hassan MMD, Hogg GL (1987) A review of graph theory applications to the facilities layout problem. Omega 15(4):291–300
Hassan MMD, Hogg GL (1989) On converting a dual graph into a block layout. Int J Prod Res 27(7):1149–1160
Heragu SS, Kusiak A (1990) Machine layout: an optimization and knowledge based approach. Int J Prod Res 28(4):615–635
Heragu SS (1992) Recent models and techniques for solving the layout problem. Eur J Oper Res 57(2):136–144
Hillier FS (1963) Quantitative tools for plant layout analysis. J Ind Eng 14(1):33–40
Hillier FS, Connors MM (1966) Quadratic assignment problem algorithms and the location of indivisible facilities. Manag Sci 13(1):42–57
Kaku BK, Thompson GL (1986) An exact algorithm for the general quadratic assignment problem. Eur J Oper Res 23(3):382–390
Khalil TM (1973) Facilities relative allocation technique (FRAT). Int J Prod Res 11(2):183–194
Koopmans TC, Beckman M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76
Kochhar JS, Heragu SS (1998) MULTI-HOPE: a tool for multiple floor layout problems. Int J Prod Res 36(12):3421–3435
Kusiak A, Heragu SS (1987) The facility layout problem. Eur J Oper Res 29(3):229–251
Land AH (1963) A problem of assignment with interrelated costs. Oper Res Q 14:185–198
Lawler EL (1963) The quadratic assignment problem. Manag Sci 9(4):586–599
Lee R, Moore JM (1967) CORELAP—computerized relationship layout planning. J Ind Eng 18:195–200
Li Y, Pardalos PM, Resende MGC (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. DIMACS Ser Discret Math Theor Comput Sci 16:237–261
Matai R, Singh SP, Mittal ML (2010) Facility layout problem: a state-of-the-art review. Vilakshan, XIMB J Manag 7(2):81–106
Meller RD, Bozer YA (1996) A new simulated annealing algorithm for the facility layout problem. Int J Prod Res 34(6):1675–1692
Meller RD, Gau KY (1996) The facility layout problem: recent and emerging trends and perspectives. J Manuf Syst 15(5):351–366
Meller RD, Gau KY (1996) Facility layout objective functions and robust layouts. Int J Prod Res 34(10):2727–2742
Muther R, McPherson K (1970) Four approaches to computerized layout planning. Ind Eng 21:39–42
Neghabat F (1974) An efficient equipment layout algorithm. Oper Res 22(3):622–628
Nugent CE, Vollman TE, Ruml J (1968) An experimental comparison of techniques for the assignment of facilities to locations. Oper Res 16(1):150–173
Nehi HM, Gelareh S (2007) A survey of meta-heuristic solution methods for the quadratic assignment problem. Appl Math Sci 1(46):2293–2312
O’Brien C, Abdel-Barr SEZ (1980) An interactive approach to computer aided facility layout. Int J Prod Res 18(2):201–211
Picone CJ, Wilhelm WE (1984) A perturbation scheme to improve Hillier’s solution to the facilities layout problem. Manag Sci 30(10):1238–1249
Ramkumar AS, Ponnambalam SG, Jawahar N, Suresh RK (2008) Iterated fast local search algorithm for solving quadratic assignment problems. Robot Comput-Integr Manuf 24(3):392–401
Ramkumar AS, Ponnambalam SG, Jawahar N (2009) A new iterated fast local search heuristic for solving QAP formulation in facility layout design. Robot Comput-Integ Manuf 25(3):620–629
Rosenblatt MJ, Lee HL (1987) A robustness approach to facilities design. Int J Prod Res 25(4):479–486
Sahni S, Gonzalez P (1976) P-Complete approximation problems. J ACM 23(3):555–565
Scriabin M, Vergin RC (1976) Computer and visual methods for plant layout—a rejoinder. Manag Sci 23(l):104–105
Seehof JM, Evans WO (1967) Automated layout design program. J Ind Eng 18:690–695
Seppannen JJ, Moore JM (1970) Facilities planning with graph theory. Manag Sci 17(4):242–253
Singh SP, Sharma RRK (2006) A survey on various approaches to solve facility layout problem. Int J Adv Manuf Technol 30:425–433
Singh SP, Sharma RRK (2008) Two-level modified simulated annealing based approach for solving facility layout problem. Int J Prod Res 46(13):3563–3582
Singh SP, Singh VK (2010) An improved heuristic approach for multi-objective approach for facility layout problem. Int J Prod Res 48(4):1171–1194
Singh SP, Singh VK (2011) Three-level AHP based heuristic approach to solve multi-objective facility layout problem. Int J Prod Res 49(4):1105–1125
Taillard E (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput 17:443–445
Tam KY (1992) A simulated annealing algorithm for allocating space to manufacturing cells. Int J Prod Res 30(1):63–87
Tompkins JA, Reed R (1976) An applied model for the facilities design problem. Int J Prod Res 14(5):583–595
Vollman TE, Nugent CE, Zartler (1968) A computerized model for office layout. J Ind Eng 19(7):321–327
Zoller K, Adendorff K (1972) Layout planning by computer simulation. AIIE Trans 4(2):116–125
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Matai, R., Singh, S.P. & Mittal, M.L. A non-greedy systematic neighbourhood search heuristic for solving facility layout problem. Int J Adv Manuf Technol 68, 1665–1675 (2013). https://doi.org/10.1007/s00170-013-4965-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-013-4965-2