A wide variety of practical problems in design, planning, and management can be formulated as quadratic assignment problems, and this paper discusses this class of problem. Since algorithms for producing optimal solutions to such problems are computationally infeasible for all but small problems of this type, heuristic techniques must usually be employed for the solution of real practical problems. This paper explores and compares a variety of solution techniques found in the literature, considering the trade-offs between computational efficiency and quality of solutions generated. Recommendations are made about the key factors to be considered in developing and applying heuristic solution procedures.
Get full access to this article
View all access options for this article.
References
1.
ArmourG CBuffaE S, 1963“A heuristic algorithm and simulation approach to relative location of facilities”Management Science9(2) 294–309
2.
BlockT E, 1978“PLOP—plant layout optimization procedure”School of Engineering, University of Melbourne, Melbourne, Australia, unpublished
3.
BuffaE SVollmanT E, 1966“The facilities layout problem in perspective”Management Science12(10) 451–468
4.
EdwardsH KGillettB EHaleM E, 1970“Modular allocation technique (MAT)”Management Science17(3) 161–169
5.
ElshafeiA N, 1977“Hospital layout as a quadratic assignment problem”Operational Research Quarterly28(1) 167–179
6.
FreemanR JGogertyD CGravesG WBrooksR B S, 1966“A mathematical model of supply support for space operations”Operations Research14(1) 1–15
7.
GareyM RJohnsonD S, 1978“Strong NP-completeness results: Motivation, examples, and implications”Journal of the Association for Computing Machinery25(3) 499–508
8.
GashutzG KAhrensJ H, 1968“Suboptimal algorithms for the quadratic assignment problem”Naval Research Logistics Quarterly15(March) 49–62
9.
GeoffrionA MGravesG W, 1976“Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment/LP approach”Operations Research24(4) 595–610
10.
GilmoreP C, 1962“Optimal and suboptimal algorithms for the quadratic assignment problem”Journal of the Society of Industrial and Applied Mathematics10(2) 305–313
11.
GrahamR L, 1978“The combinatorial mathematics of scheduling”Scientific American March 238(3) 124–132
12.
GravesG WWhinstonA, 1970“An algorithm for the quadratic assignment problem”Management Science17(7) 453–471
13.
HananMKurtzbergJ M, 1972“A review of the placement and quadratic assignment problems”SIAM Review14(2) 324–342
14.
HananMWolffPAguleB, 1976“Some experimental results on placement techniques”Design Automation Conference, 13th, San Francisco, June 1976 (Institute of Electrical Engineers, New York) pp 214–224
15.
HeiderC H, 1972“A decomposition procedure for the quadratic assignment problem” Professional Paper 100, Center for Naval Analyses, Arlington, Virginia
16.
HeiderC H, 1973“An N-step, 2-variable search algorithm for the component placement problem”Naval Research Logistics Quarterly (December)699–724
17.
HillierF S, 1963“Quantitative tools for plant layout analysis”Journal of Industrial Engineering14(1) 33–40
18.
HillierF SConnersM M, 1966“Quadratic assignment problem algorithms and the location of indivisible facilities”Management Science13(1) 42–57
19.
KarpR M, 1972“Reducibility among combinatorial problems” in Complexity of Computer Computations Eds MillerR EThatcherJ W (Plenum Press, New York) pp 85–104
20.
KoopmansJ CBeckmannM J, 1957“Assignment problems and the location of economic activities”Econometrica2553–76
21.
LewisH RPapadimitriouC H, 1978“The efficiency of algorithms”Scientific American January 240(5) 96–109
22.
LiggettR S, 1971“School course-time scheduling algorithm” unpublished computer program for the School of Architecture and Urban Planning, University of California, Los Angeles
23.
LiggettR S, 1972“Bus scheduling algorithm” unpublished proprietary computer program for Educational Coordinates of Sunnyvale, Sunnyvale, California
24.
LiggettR S, 1980“The quadratic assignment problem: An experimental evaluation of solution strategies”Management Science (forthcoming)
25.
LosM, 1976“The Koopmans-Beckmann problem: some computational results”Centre de Recherche sur les Transports, Université de Montréal, Montréal, Canada, February
26.
MacGregorR, 1978“On partitioning a graph: a theoretical and empirical study” PhD thesis, Department of Computer Science, University of California, Berkeley, Calif.
27.
MitchellW J, 1977“Automated spatial synthesis” in Computer Aided Architectural Design (Petrocelli Charter, New York) chapter 13
28.
MutherRMcPhersonK, 1970“Four approaches to computerized layout planning”Industrial Engineering February 39–42
29.
NugentC EVollmanT ERumlJ, 1968“An experimental comparison of techniques for the assignment of facilities to locations”Operations Research16(1) 150–173
30.
NunamakerJNylinWKonsyrskiB, 1971“Processing systems optimization through automatic design and reorganization of program modules” Working Paper, Department of Computer Sciences, Purdue University, Lafayette, Ind.
31.
PierceJ FCrowstonW B, 1971“Tree search algorithms for quadratic assignment problems”Naval Research Logistics Quarterly18(1) 1–36
32.
RitzmanL P, 1972“The efficiency of computer algorithms for plant layout”Management Science18(5, part 1) 240–248
33.
SahniSGonzalesT, 1976“P-complete approximation problems”Journal of the Association for Computing Machinery23(3) 555–565
34.
SteinbergL, 1961“The backboard wiring problem: A placement algorithm”SIAM Review3(1) 37–50
35.
WebbM H J, 1971“Some methods of producing approximate solutions to traveling salesman problems with hundreds or thousands of cities”Operational Research Quarterly22(1) 49–66
36.
WimmertR J, 1957“A quantitative approach to equipment location in intermittent manufacturing” doctoral dissertation, Department of Engineering, Purdue University, Lafayette, Ind.
