The facility layout problem.

*(English)*Zbl 0612.90035The facility layout problem is surveyed. Various formulations of the facility layout problem and the algorithms for solving this problem are presented. Twelve heuristic algorithms are compared on the basis of their performance with respect to eight test problems commonly used in the literature. Certain issues related to the facility layout problem and some aspects of the machine layout problem in flexible manufacturing systems are also presented.

##### MSC:

90B05 | Inventory, storage, reservoirs |

90B30 | Production models |

90C90 | Applications of mathematical programming |

90C10 | Integer programming |

PDF
BibTeX
XML
Cite

\textit{A. Kusiak} and \textit{S. S. Heragu}, Eur. J. Oper. Res. 29, 229--251 (1987; Zbl 0612.90035)

Full Text:
DOI

##### References:

[1] | Armour, G.C.; Buffa, E.S., A heuristic algorithm and simulation approach to relative allocation of facilities, Management science, 9, 2, 294-300, (1963) |

[2] | Balas, E.; Mazzola, J.B., Quadratic 0-1 programming by a new linearization, () |

[3] | Bazaraa, M.S., Computerized layout design: A branch and bound approach, AIIE transactions, 7, 4, 432-437, (1975) |

[4] | Bazaraa, M.S.; Elshafei, A.N., An exact branch and bound procedure for quadratic assignment problems, Naval research logistics quarterly, 26, 109-121, (1979) · Zbl 0405.90051 |

[5] | Bazaraa, M.S.; Kirca, O., A branch-and-bound-based heuristic for solving the QAP, Naval research logistics quarterly, 30, 287-304, (1983) · Zbl 0575.90041 |

[6] | Bazaraa, M.S.; Sherali, M.D., Benders’ partitioning scheme applied to a new formulation of the quadratic assignment problem, Naval research logistics quarterly, 27, 1, 29-41, (1980) · Zbl 0432.90060 |

[7] | Bazaraa, M.S.; Sherali, M.D., On the use of exact and heuristic cutting plane methods for the quadratic assignment problem, Journal of operations research society, 33, 1, 991-1003, (1982) · Zbl 0497.90042 |

[8] | Block, T.E., A note on ‘comparison of computer algorithms and visual based method for plant layout’ by M. scraiabin and R.C. vergin, Management science, 24, 2, 235-237, (1977) · Zbl 0374.90036 |

[9] | Block, T.E., \scfate: A new construction algorithm for facilities layout, Journal of engineering production, 2, 111-120, (1978) |

[10] | Block, T.E., On the complexity of facilities layout problems, Management science, 25, 3, 280-285, (1979) · Zbl 0409.90035 |

[11] | Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), North-Holland New York · Zbl 1134.05001 |

[12] | Buffa, E.S.; Buffa, E.S., Sequence analysis for functional layouts, The journal of industrial engineering, The journal of industrial engineering, 6, 25-13, (1955) |

[13] | Buffa, E.S., On a paper by scriabin and vergin, Management science, 23, 1, 104, (1976) |

[14] | Buffa, E.S.; Armour, G.C.; Vollmann, T.E., Allocating facilities with \sccraft, Harvard business review, 42, 136-158, (1964) |

[15] | Burkard, R.E., Die störungsmethode zur lösung quadratisches zuordnungsprobleme, Operations research verfahren, 16, 84-108, (1973) |

[16] | Burkard, R.E., Locations with spatial interaction—quadratic assignment problem, () · Zbl 0559.90056 |

[17] | Burkard, R.E.; Bonninger, T., A heuristic for quadratic Boolean program with applications to quadratic assignment problems, European journal of operational research, 13, 374-386, (1983) · Zbl 0509.90058 |

[18] | Burkard, R.E.; Stratman, K.H., Numerical investigations on quadratic assignment problems, Naval research logistics quarterly, 25, 129-144, (1978) |

[19] | Carrie, A.S.; Moore, J.M.; Roczniak, M.; Seppanen, J.J., Graph theory and computer-aided facilities design, Omega, 6, 4, 353-361, (1978) |

[20] | Cinar, U., Facilities planning: A systems analysis and space allocation approach, () |

[21] | Coleman, D.R., Plant layout: computer versus humans, Management science, 24, 1, 107-112, (1977) |

[22] | Conway, R.W.; Maxwell, W.L., A note on the assignment of facility location, The journal of industrial engineering, 12, 34-36, (1961) |

[23] | Deisenroth, M.P.; Apple, J.M., A computerized plant layout analysis and evaluation technique, (), technical paper |

[24] | Drezner, Z., \scdiscon: A new method for the layout problem, Operations research, 25, 6, 1375-1384, (1980) · Zbl 0447.90025 |

[25] | Dutta, K.N.; Sahu, S., A multigoal heuristic for facilities design problems: \scmughal, International journal of production research, 20, 2, 147-154, (1982) |

[26] | Eades, P.; Foulds, L.R.; Giffin, J., An efficient heuristic for identifying a maximum weight planar subgraph, () · Zbl 0512.05036 |

[27] | Edwards, H.K.; Gillett, B.E.; Hale, M.C., Modular allocation technique (\scmat), Management science, 17, 3, 161-169, (1970) |

[28] | El-Rayah, T.E.; Hollier, R.H., A review of plant design techniques, International journal of production research, 8, 3, 263-279, (1970) |

[29] | Elshafei, A.N., Hospital layout as a quadratic assignment problem, Operations research quarterly, 28, 1, 167-179, (1977) · Zbl 0353.90096 |

[30] | Finke, G.; Burkard, R.E.; Rendl, F., Quadratic assignment problems, (1985), Dept. of Applied Mathematics, Technical University of Nova Scotia Halifax, NS, Canada, working paper |

[31] | Foulds, L.R., Techniques for facilities layout: deciding which pairs of activities should be adjacent, Management science, 29, 2, 1414-1426, (1983) · Zbl 0527.90019 |

[32] | Foulds, L.R.; Gibbons, P.B.; Giffin, J.W., Facilities layout adjacency determination: an experimental comparison of three graph theoretic heuristics, Operations research, 33, 5, 1091-1106, (1985) · Zbl 0574.90022 |

[33] | Foulds, L.R.; Robinson, D.F., A strategy for solving the plant layout problem, Operations research quarterly, 27, 4, 845-855, (1976) · Zbl 0352.90067 |

[34] | Foulds, L.R.; Robinson, D.F., Graph theoretic heuristics for the plant layout problem, International journal of productions research, 16, 1, 27-37, (1978) |

[35] | Francis, R.L.; White, J.A., Facilities layout and location: an analytical approach, (1974), Prentice-Hall Englewoods Cliffs, NJ |

[36] | Frieze, A.M.; Yadegar, J., On the quadratic assignment problem, Discrete applied mathematics, 5, 89-98, (1983) · Zbl 0502.90062 |

[37] | Gaschutz, G.K.; Ahrens, J.H., Suboptimal algorithms for the quadratic assignment problem, Naval research logistics quarterly, 15, 49-62, (1968) |

[38] | Gavett, J.W.; Plyter, N.V., The optimal assignment of facilities to locations by branch and bound, Operations research, 14, 210-232, (1966) |

[39] | Gilmore, P.C., Optimal and suboptimal algorithms for the quadratic assignment problem, Journal of the society for industrial and applied mathematics, 10, 305-313, (1962) · Zbl 0118.15101 |

[40] | Graves, G.W.; Whinston, A.B., An algorithm for the quadratic assignment problem, Management science, 17, 7, 453-471, (1970) · Zbl 0193.18803 |

[41] | Green, R.H.; Al-Hakim, L., A heuristic for facilities layout planning, Omega, 13, 5, 469-474, (1985) |

[42] | Gupta, R.M.; Deisenroth, M.P., Comments on the complexity rating factors for layout problems, Management science, 27, 12, 1460-1464, (1981) · Zbl 0473.90033 |

[43] | Hammouche, A., Evaluation of an application of graph theory to the layout problem, (), August 22-24, Windsor, Ontario |

[44] | Hanan, M.; Kurtzberg, J.M., A review of the placement and quadratic assignment problems, SIAM review, 14, 2, 324-342, (1972) · Zbl 0241.90048 |

[45] | Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064 |

[46] | Heragu, S.; Kusiak, A., Machine layout problem in flexible manufacturing systems, () |

[47] | Heragu, S.; Kusiak, A., A construction algorithm for the facility layout problem, () · Zbl 0612.90035 |

[48] | Herroelen, W.; Van Gils, A., On the use of flow dominance in complexity measures for facility layout problems, International journal of production research, 23, 1, 97-108, (1985) |

[49] | Hicks, P.E.; Cowan, T.E., \sccraft-M for layout rearrangement, Industrial engineering, (1976), May, 30-35 |

[50] | Hillier, F.S., Quantitative tools for plant layout analysis, Journal of industrial engineering, 14, 33-40, (1963) |

[51] | Hillier, F.S.; Connors, M.M., Quadratic assignment problem algorithms and the location of indivisible facilities, Management science, 13, 42-57, (1966) |

[52] | Hitchings, G.G.; Cottam, M., An efficient heuristic procedure for solving the layout design problem, Omega, 4, 2, 205-214, (1976) |

[53] | Jacobs, R.F., A note on \scspacecraft for multifloor layout planning, Management science, 30, 5, 648-649, (1984) |

[54] | Johnson, R.V., \scspacecraft for multi-floor layout planning, Management science, 28, 4, 407-417, (1982) |

[55] | Kaku, B.K.; Thompson, G.L., An exact algorithm for the general quadratic assignment problem, European journal of operational research, 23, 382-390, (1986) · Zbl 0581.90054 |

[56] | Kaufman, L.; Broeckx, F., An algorithm for the quadratic assignment problem using benders’ decomposition, European journal of operational research, 2, 204-211, (1978) · Zbl 0378.90065 |

[57] | Kaiman, L., Computer architecture programs, (1970), Centre for Environmental Research 955 Park Square Building, Boston, MA |

[58] | Khalil, T.M., Facilities relative allocation technique (FRAT), International journal of productions research, 11, 2, 183-194, (1973) |

[59] | Koopmans, T.C.; Beckman, M., Assignment problems and the location of economic activities, Econometrica, 25, 53-76, (1957) · Zbl 0098.12203 |

[60] | Krarup, J., Quadratic assignment, Data, 3, 12-15, (1972) |

[61] | Land, A.H., A problem of assignment with interrelated costs, Operations research quarterly, 14, 185-198, (1963) |

[62] | Lavalle, I.; Roucairol, C., Parallel branch and bound algorithms, () |

[63] | Lawler, E.L., The quadratic assignment problem, Management science, 9, 586-599, (1963) · Zbl 0995.90579 |

[64] | Lee, R.; Moore, J.M., \sccorelap—computerized relationship layout planning, Journal of industrial engineering, 18, 195-200, (1967) |

[65] | Levary, R.R.; Kalchik, S., Facilities layout — a survey of solution procedures, Computers and industrial engineering, 9, 2, 141-148, (1985) |

[66] | Lewis, W.P.; Block, T.E., On the application of computer aids to plant layout, International journal of productions research, 18, 1, 11-20, (1980) |

[67] | Ligett, R.S., The quadratic assignment problem: an experimental evaluation of solution strategies, Management science, 27, 4, 442-458, (1981) · Zbl 0454.90046 |

[68] | Little, J.D.C.; Murty, K.G.; Sweeney, D.W.; Karel, C., An algorithm for the travelling salesman problem, Operations research, 11, 972-989, (1963) · Zbl 0161.39305 |

[69] | Love, R.F.; Wong, J.W., Solving quadratic assignment problems with rectilinear distances and integer programming, Naval research logistics quarterly, 23, 623-627, (1976) · Zbl 0377.90091 |

[70] | Moore, J.M., Computer aided facilities design: an international survey, International journal of production research, 12, 1, 21-44, (1974) |

[71] | Moore, J.M., Facilities design with graph theory and strings, Omega, 4, 2, 193-203, (1976) |

[72] | Muller, T., Automated guided vehicles, (1983), IFS Publications Kempston, Bedford |

[73] | Muther, R., Practical plant layout, (1955), McGraw-Hill New York |

[74] | Muther, R., Systematic layout planning, (1973), Cahers Books Boston, MA |

[75] | Muther, R.; McPherson, K., Four approaches to computerized layout planning, Industrial engineering, 39-42, (1970), February |

[76] | Neghabat, F., An efficient equipment layout algorithm, Operations research, 22, 622-628, (1974) · Zbl 0279.90043 |

[77] | Nugent, C.E.; Vollmann, T.E.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, Operations research, 16, 150-173, (1968) |

[78] | O’Brien, C.; Abdel Barr, S.E.Z., An interactive approach to computer aided facility layout, International journal of production research, 18, 2, 201-211, (1980) |

[79] | Parker, C.S., An experimental investigation of some strategies for component placement, Operations research quarterly, 27, 1, 71-81, (1976) |

[80] | Picone, C.J.; Wilhelm, W.E., Perturbation scheme to improve Hillier’s solution to the facilities layout problem, Management science, 30, 10, 1238-1249, (1984) · Zbl 0555.90038 |

[81] | Pierce, J.F.; Crowston, W.B., Tree-search algorithms for quadratic assignment problems, Naval research logistics quarterly, 18, 1-36, (1971) · Zbl 0216.54404 |

[82] | Ritzman, L.P., The efficiency of computer algorithms for plant layout, Management science, 18, 5, 240-248, (1972) · Zbl 0252.68015 |

[83] | Ritzman, L.P.; Bradford, J.; Jacobs, R., A multiple objective approach to space planning for Academic facilities, Management science, 25, 9, 895-906, (1979) |

[84] | Rosenblatt, M.J., The facilities layout problem: a multigoal approach, International journal of production research, 17, 4, 323-332, (1979) |

[85] | Sahni, S.; Gonzalez, T., P-complete approximation problem, Journal of associated computing machinery, 23, 3, 555-565, (1976) · Zbl 0348.90152 |

[86] | Scriabin, M.; Vergin, R.C., Comparison of computer algorithms and visual based methods for plant layout, Management science, 22, 2, 172-181, (1975) |

[87] | Scriabin, M.; Vergin, R.C., Computer and visual methods for plant layout—A rejoinder, Management science, 23, 1, 105, (1976) |

[88] | Scriabin, M.; Vergin, R.C., A cluster-analytic approach to facility layout, Management science, 31, 1, 33-49, (1985) · Zbl 0607.90027 |

[89] | Seehof, J.M.; Evans, W.O., Automated layout design program, The journal of industrial engineering, 18, 2, 690-695, (1967) |

[90] | Seppannen, J.J.; Moore, J.M., Facilities planning with graph theory, Management science, 17, 4, B-242-B-253, (1970) |

[91] | Seppannen, J.J.; Moore, J.M., String processing algorithms for plant layout problems, International journal of production research, 13, 3, 239-254, (1975) |

[92] | Shore, R.H.; Tompkins, J.A., Flexible facilities design, AIIE transactions, 12, 2, 200-205, (1980) |

[93] | Steinberg, L., The backboard wiring problem: A placement algorithm, SIAM review, 3, 1, 37-50, (1961) · Zbl 0097.14703 |

[94] | Tompkins, J.A.; Moore, J.M., Computer aided layout: A User’s guide, (1984), AIIE Norcross, GA |

[95] | Tompkins, J.A.; Reed, R., An applied model for the facilities design problem, International journal of productions research, 14, 5, 583-595, (1976) |

[96] | Trybus, T.W.; Hopkins, L.D., Human vs. computer algorithms for the plant layout problem, Management science, 26, 6, 570-574, (1980) |

[97] | Vollmann, T.E.; Buffa, E.S., The facility layout problem in perspective, Management science, 12, 10, B450-B468, (1966) |

[98] | Vollmann, T.E.; Nugent, C.E.; Zartler, A computerized model for office layout, The journal of industrial engineering, 19, 321-327, (1968) |

[99] | Wilson, R.C., A review of facility design models, The journal of industrial engineering, 15, 115-121, (1964) |

[100] | Wimmert, R.J., A mathematical method for equipment location, The journal of industrial engineering, 9, 498-505, (1958) |

[101] | Zoller, K.; Adendorff, K., Layout planning by computer simulation, AIIE transactions, 4, 2, 116-125, (1972) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.