×
Huntley, Christopher L.; Brown, Donald E.

A parallel heuristic for quadratic assignment problems. (English) Zbl 0723.90044

Comput. Oper. Res. 18, No. 3, 275-289 (1991).
Summary: The quadratic assignment problem represents an important class of problems with applications as diverse as facility layout and data analysis. The importance of these applications coupled with the fact that the quadratic assignment problem is NP-hard has encouraged the development of heuristics because optimal seeking procedures have been restricted to very small versions of the problem. This paper describes a new parallel heuristic, SAGA, for the quadratic assignment problem. SAGA is a cascaded hybrid of a genetic algorithm and simulated annealing. In addition to details regarding SAGA and its implementation, this paper also describes the performance of SAGA on two standard problems taken from the literature. The results from these problems show SAGA to be superior to the most commonly employed heuristic in solution quality, and for large problems it is also superior in solution time.

Cited in 22 Documents

MSC:

90B80 Discrete location and assignment
90C27 Combinatorial optimization
65Y05 Parallel numerical computation
90-08 Computational methods for problems pertaining to operations research and mathematical programming
68W15 Distributed algorithms
90C20 Quadratic programming

Keywords:

quadratic assignment; NP-hard; parallel heuristic; genetic algorithm; simulated annealing
PDF BibTeX XML Cite
\textit{C. L. Huntley} and \textit{D. E. Brown}, Comput. Oper. Res. 18, No. 3, 275--289 (1991; Zbl 0723.90044)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Aneke, N.; Carrie, A., Flow complexity—a data suitability index for flowline systems, Int. J. prod. res., 21, 425, (1983)
[2] Armour, G.; Buffa, E., A heuristic algorithm and simulation approach to the relative allocation of facilities, Mgmt sci., 9, 294-309, (1963)
[3] Block, T., A note on “comparison of computer algorithms and visual based methods for plant layout” by M. scriabin and R.C. vergin, Mgmt sci., 24, 235-237, (1977) · Zbl 0374.90036
[4] Block, T., On the complexity of facility layout problems, Mgmt sci., 25, 280, (1979) · Zbl 0409.90035
[5] Bonomi, E.; Lutton, J., The asymptotic behavior of quadratic sum assignment problems: a statistical mechanics approach, Eur. J. ops res., 26, 295-300, (1986) · Zbl 0598.90065
[6] Brotchie, J., A generalized design approach to solution of the non-convex quadratic programming problem, Appl. math. model, 11, 291-295, (1987) · Zbl 0631.90048
[7] D. Brown, C. Huntley and A. Spillane, SAGA: a heuristic procedure for facility layout. Submitted.
[8] Buffa, E.; Armour, G.; Vollmann, T., Allocating facilities with CRAFT, Harv. bus. rev., 136-158, (1964), March-April
[9] Burkard, R.; Offermann, J., Entwurf von schreibmaschinentastaturen mittens quadratischer zuordnungsprobleme, Z. opl res., 21, 121-132, (1977) · Zbl 0353.90095
[10] Burkard, R.; Rendl, F., A thermodynamically motivated simulation procedure for combinatorial optimization problems, Eur. J. ops res., 17, 169-174, (1984) · Zbl 0541.90070
[11] Burkard, R.; Stratmann, L., Numerical investigation on quadratic assignment problems, Nav. res. logist. Q., 25, 129-148, (1978) · Zbl 0391.90066
[12] Coleman, D., Plant layout: computers versus humans, Mgmt sci., 24, 107, (1977)
[13] Collins, N.; Eglese, R.; Golden, B., Simulated annealing—an annotated bibliography, University of maryland working paper series, MS/8 88-019, (1988) · Zbl 0669.65047
[14] Connolly, D., Combinatorial optimization using simulated annealing, ()
[15] Devore, J., Probability and statistics for engineering and the sciences, (1982), Brook-Cole Monterey, Calif · Zbl 0514.62001
[16] Dutta, A.; Koehler, G.; Whinston, A., On optimal allocation in a distributed processing environment, Mgmt sci., 28, 839-853, (1982) · Zbl 0487.90057
[17] Evans, C.; Kumar, S., Space allocation decisions in a large organization—a case study, Indian J. mgmt sys., 3, 55-64, (1987)
[18] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[19] Gilmore, P., Optimal and suboptimal algorithms for the quadratic assignment problem, SIAM, 10, 305-313, (1962) · Zbl 0118.15101
[20] Goldberg, D.; Lingle, R., Alleles, loci, and the traveling salesman problem, () · Zbl 0674.90095
[21] Goldberg, D., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Reading, Mass · Zbl 0721.68056
[22] Graves, G.; Whinston, A., An approach for the quadratic assignment problem, Mgmt sci., 16, 453-471, (1970) · Zbl 0193.18803
[23] Grefenstette, J., Incorporating problem specific knowledge into genetic algorithms, (), 42-60
[24] Herroellen, W.; Van Gils, A., On the use of flow dominance in complexity measures for facility layout problems, Int. J. prod. res., 23, 97-108, (1985)
[25] Hillier, F., Quantitative tools for plant layout analysis, J. ind. engng., 14, 33-40, (1963)
[26] Hillier, F.; Connors, M., Quadratic assignment problem algorithms and the location of indivisible facilities, Mgmt sci., 13, 42-57, (1966)
[27] Hitchings, G.; Cottam, M., An efficient heuristic for solving the layout design problem, Omega, 14, 205-214, (1976)
[28] Holland, J., Adaptation in natural and artificial systems, (1975), University of Michigan Press Ann Arbor, Mich
[29] Hubert, L.; Schultz, J., Quadratic assignment as a general data analysis strategy, Br. J. math. psychol., 29, 190-241, (1976) · Zbl 0356.92027
[30] Huntley, C., An adaptive aid for facility layout, ()
[31] Khalil, T., Facilities relative allocation technique (FRAT), Int. J. prod. res., 11, 183-194, (1973)
[32] Kirkpatrick, S.; Gelatt, D.; Vecchi, M., Optimization by simulated annealing, Science, 220, 621-630, (1983) · Zbl 1225.90162
[33] Koopmans, T.; Beckmann, M., Assignment problems and the location of indivisible economic activities, Econometrica, 25, 53-76, (1957) · Zbl 0098.12203
[34] Lawler, E., The quadratic assignment problem, Mgmt sci., 9, 586-599, (1963) · Zbl 0995.90579
[35] Nugent, C.; Vollmann, R.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, Ops res., 16, 150-173, (1968)
[36] Ritzman, L., The efficiency of computer algorithms for plant layout, Mgmt sci., 18, 240-248, (1972) · Zbl 0252.68015
[37] Sahni, S.; Gonzalez, T., P-complete approximation problems, J. ass. comput. Mach., 23, 555-565, (1976) · Zbl 0348.90152
[38] Scriabin, M.; Vergin, R., Comparison of computer algorithms and visual based methods for plant layout, Mgmt sci., 22, 172-181, (1975)
[39] Sharpe, R.; Marksjo, B., Facility layout optimization using the metropolis algorithm, Envir. plann. B, 12, 443-453, (1985)
[40] Skiscim, C.; Golden, B., Using simulated annealing to solve routing and location problems, Nav. res. logist. Q., 33, 261, (1986) · Zbl 0593.90054
[41] Steinberg, L., The backboard wiring problem: a placement algorithm, SIAM rev., 3, 37-50, (1961) · Zbl 0097.14703
[42] Trybus, T.; Hopkins, L., Humans versus computer algorithms for the plant layout problem, Mgmt sci., 26, 570, (1980)
[43] Vollmann, T.; Buffa, E., The facilities layout problem in perspective, Mgmt sci., 12, 450-468, (1966)
[44] Wales, R.; Askin, R., An algorithm for NC turret punch press tool location and hit sequencing, IIE trans., 16, 280-287, (1984)
[45] Wilhelm, M.; Ward, T., Solving quadratic assignment problems by “simulated annealing”, IIE trans., 19, 107-199, (1987)
[46] R. Wimmert, A mathematical method of equipment location. J. ind. Engng{\bf9}, 498-505.
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.