Abstract
Within the general problem area of location problems, the layout planning problem or facilities location problem has for years attracted the attention of building planners (architects, industrial engineers) and operations researchers.
The article outlines the general structure of the problem including the well-known prototype formulation “The Quadratic Assignment Problem”, briefly reviews the state of the art in solving such prototype problem formulations, and criticizes these, first from a computational point of view and then—and most important—from a practical, user-oriented point of view. Based upon this assessment, and the author’s own experience in tackling layout problems, a recently developed model, primarily aiming at an appraisal of a given layout according to certain criteria is described. The interactive model can serve as a powerful tool for architects during the process of experimentation with alternative layouts. Besides calculating the “internal transport”, the model can take into account other measures which are usually considered to be of a “qualitative, aesthetic” nature such as noise, availability of daylight et cetera. A number of macro’s facilitates the transition from one layout to another.
Preview
Unable to display preview. Download preview PDF.
References
D. Adolphson and T.C. Hu, “Optimal linear ordering”, SIAM Journal of Applied Mathematics 25 (1973) 403–423.
G.C. Armour and E.S. Buffa, “A heuristic algorithm and simulation approach to the relative location of facilities”, Management Science 9 (1963) 294–309.
C. Beaudelot-Roucairol, “Affectation quadratique”, Doctoral Thesis, Université Pierre et Marie Curie, Paris VI (1976).
J.F. Brotchie, A.R. Toakley and R. Sharpe, “On an urban planning model”, in: Analysis of urban development, Melbourne University, Melbourne (1970).
J.F. Brotchie, R. Sharpe and J. Dickey, “The integration of land use and transportation planning using modelling techniques”, in: Traffic control and transportation systems (North-Holland, Amsterdam, 1974).
E.S. Buffa, G.C. Armour and T.E. Vollmann, “Allocating facilities with CRAFT”, Harvard Business Review 42 (1964) 136–159.
R.E. Burkard, “Die Störungsmethode zur Lösung quadratischer Zuordnungsprobleme”, Operations Research Verfahren 16 (1973) 84–108.
R.E. Burkard and K.-H. Stratmann, “Numerical investigations on quadratic assignment problems”, Naval Research Logistics Quarterly, to appear.
R.E. Burkard and J. Offermann, “Entwurf von Schreibmaschintastaturen mittels quadratischer Zuordnungsprobleme”, Zeitschrift für Operations Research 21 (1977) B121–B132.
N. Christofides and M. Gerrard, “Special cases of the quadratic assignment problem”, Management Sciences Research Report No. 391, Carnegie-Mellon University, Pittsburgh (1976).
S.A. Cook, “The Complexity of theorem-proving procedures”, Proceedings of the 3rd annual ACM symposium on theory of computing (1971) pp. 151–158.
J.W. Dickey and J.W. Hopkins, “Campus building arrangement using TOPAZ”, Transportation Research 6 (1972) 59–68.
J.W. Eyster, J.A. White and W.W. Wierwille, “On solving multifacility location problems using a hyperboloid approximation procedure”, AIIE Transactions 5 (1973) 1–6.
A. David, P. Noviant and C. Roucairol, “A global spatial localization of activities method”, in: Design activity international conference (London, 1973).
R.L. Francis and J.A. White, Facility layout and location (Prentice-Hall, Englewood Cliffs, NJ., 1974).
G.K. Gaschütz and J.H. Ahrens, “Suboptimal algorithms for the quadratic assignment problem”, Naval Research Logistics Quarterly 15 (1968) 49–62.
J.W. Gavett and N.V. Plyter, “The optimal assignment of facilities to locations by branch and bound”, Operations Research 14 (1966) 210–232.
A.M. Geoffrion and G.W. Graves, “Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment/LP approach”, Operations Research 24 (1976) 595–610.
P.C. Gilmore, “Optimal and suboptimal algorithms for the quadratic assignment problem”, SIAM Journal 10 (1962) 305–313.
M. Hanan and J.M. Kurtzberg, “A review of the placement and quadratic assignment problems”, SIAM Review 14 (1972) 324–342.
S.K. Jacobsen and P.M. Pruzan, “Lokalisering—modelle og løsningsmetoder”, IMSOR, Danmarks tekniske Højskole, Lyngby (1976).
R.M. Karp, “Reducibility among combinatorial problems”, in: R.E. Miller and J.W. Thatcher, eds., Complexity of computer computations (Plenum Press, New York, 1972) pp. 85–103.
T.M. Khalil, “Facilities relative allocation technique (FRAT)”, Int. J. Prod. Res. 11 (1973) 181–194.
T.C. Koopmans and M. Beckman, “Assignment problems and the location of economic activities”, Econometrica 25 (1957) 52–76.
J. Krarup, “Quadratic assignment”, DATA 3/72 (1972).
J. Krarup, “The peripatetic salesman and some related unsolved problems”, in: B. Roy, ed., Combinatorial programming: Methods and applications (Reidel, Dordrecht, 1975) pp. 173–178.
J. Krarup and P.M. Pruzan, “Selected Families of discrete location problems. Part I: Center problems. Part II: Median problems”, DIKU-report 77-7, Institute of Datalogy, University of Copenhagen, Copenhagen, (1977). Forthcoming in Annals of Discrete Mathematics.
J. Krarup and P.M. Pruzan, “Selected families of discrete location problems. Part III: The plant location family”, Working Paper No. WP-12-77, University of Calgary, Faculty of Business (Calgary, 1977).
J. Krarup and P.M. Pruzan, “Challenging unsolved center and median problems”, DIKU-report 77-10, Institute of Datalogy, University of Copenhagen (Copenhagen, 1977). To be published by the Polish Academy of Sciences.
E.L. Lawer, “The quadratic assignment problem”, Management Science 9 (1963) 586–599.
E.L. Lawler, “The quadratic assignment problem: A brief review”, in: B. Roy, ed., Combinatorial programming: methods and applications (D. Reidel, Dordrecht, 1975) pp. 351–360.
J.K. Lenstra, Sequencing by enumerative methods (Mathematisch Centrum, Amsterdam, 1976).
R.F. Love, “Locating facilities in 3-dimensional space by convex programming”, Naval Research Logistics Quarterly 16 (1969) 503–516.
R.E. Machol, “Letter to the Editor”, OR/MS TODAY 3 (4) (1976).
R. Muther, Systematic layout planning, Industrial Education Institute, Boston (1961).
H. Müller-Merbach, Optimale Reinhenfolgen (Springer, Berlin, 1970).
H. Müller-Merbach, “Letter to the Editor”, OR/MS TODAY 3 (4) (1976).
C.E. Nugent, T.E. Vollmann and J. Ruml, “An experimental comparison of techniques for the assignment of facilities to locations”, Operations Research 16 (1968) 150–172.
J.F. Pierce and W.B. Crowston, “Tree-search algorithms for quadratic assignment problems”, Naval Research Logistics Quarterly 18 (1971) 1–36.
M. Scriabin and R.C. Vergin, “Comparison of computer algorithms and visual based methods for plant layout”, Management Science 22 (1975) 172–181.
L. Steinberg, “The backboard wiring problem: a placement algorithm”, SIAM Review 3 (1961) 37–50.
K.-H. Stratmann, “Numerische Untersuchungen uber Quadratische Zuordnungsprobleme”, M.Sc. Thesis, Mathematisches Institut der Universität zu Köln, Köln (1976).
T.E. Vollmann and E.S. Buffa, “The facilities layout problem in perspective”, Management Science 12 (1965) 450–468.
T.E. Vollmann, C.E. Nugent and R.L. Zartler, “A computerized model for office layout”, Journal of Industrial Engineering 19 (1968) 321–329.
G.O. Wesolowsky and R.F. Love, “The optimal location of new facilities using rectangular distances”, Operations Research 19 (1971) 124–130.
G.O. Wesolowsky and R.F. Love, “A nonlinear approximation method for solving a generalized rectangular distance Weber problem”, Management Science 18 (1972) 656–663.
T. Willoughby, “A generative approach to computer planning, a theoretical proposal”, Computer Aided Design (1970) 29–37.
T. Willoughby, “A reasoned approach to the use of computers in building planning”, Notes méthodologiques en Architecture et Urbanisme, No. 2 Centre MMI, Institut de l’Environnement (1973) 89–154.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1978 The Mathematical Programming Society
About this chapter
Cite this chapter
Krarup, J., Pruzan, P.M. (1978). Computer-aided layout design. In: Balinski, M.L., Lemarechal, C. (eds) Mathematical Programming in Use. Mathematical Programming Studies, vol 9. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0120827
Download citation
DOI: https://doi.org/10.1007/BFb0120827
Received:
Revised:
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00795-8
Online ISBN: 978-3-642-00796-5
eBook Packages: Springer Book Archive