The facility layout problem
European Journal of Operational ResearchPublished 1 June 1987
Andrew Kusiak, Sunderesh S. Heragu
Citations603
SJR quartileQ1
SJR score2.24
SNIP2.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Various formulations of the facility layout problem and the algorithms for solving this problem are presented and Twelve heuristic algorithms are compared on the basis of their performance with respect to eight test problems commonly used in the literature.
Abstract
In this paper, the 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.
Keywords
Engineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
Graph Theory with Applications
9,089 Citations1976J. A. Bondy, U. S. R. Murty
Journal of the ACMP-Complete Approximation Problems
1,715 Citations1976Sartaj Sahni, Teofilo F. Gonzalez
For P- complete problems such as traveling salesperson, cycle covers, 0-1 integer programming, multicommodity network flows, quadratic assignment, etc., it is shown that the approximation problem is also P-complete.
Operations ResearchAn Algorithm for the Traveling Salesman Problem
1,049 Citations1963John D. C. Little, Katta G. Murty +2 more
A “branch and bound” algorithm is presented for solving the traveling salesman problem, where the set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching.
Management ScienceA Heuristic Algorithm and Simulation Approach to Relative Location of Facilities
739 Citations1963Gordon C. Armour, Elwood S. Buffa
A computer program governed by an algorithm which determines how relative location patterns should be altered to obtain sequentially the most improved pattern with each change, commands their alteration, evaluates the results of alterations, and identifies the sub-optimum relative location patterns.
Operations ResearchAn Experimental Comparison of Techniques for the Assignment of Facilities to Locations
569 Citations1968Christopher E. Nugent, Thomas E. Vollmann +1 more
The new Biased Sampling procedure is seen to produce the best solutions but at relatively high computational cost, and the Hillier-Connors procedure is especially interesting because it is considerably faster than craft and BiASED Sampling and its solutions are only 2–6 per cent worse than BiasedSampling and only slightly worse than craft.
Journal of the Society for Industrial and Applied MathematicsOptimal and Suboptimal Algorithms for the Quadratic Assignment Problem
441 Citations1962Paul C. Gilmore
European Journal of Operational ResearchQuadratic assignment problems
382 Citations1984Rainer E. Burkard
Operations ResearchMachine Layout Problem in Flexible Manufacturing Systems
311 Citations1988Sunderesh S. Heragu, Andrew Kusiak
Two new construction algorithms are presented to solve the machine layout problem in FMS's and the triangle assignment algorithm TAA is found to give solutions of better quality than any other construction method published.
Journal of the Operational Research SocietyHospital Layout as a Quadratic Assignment Problem
276 Citations1977Alwalid N. Elshafei
This paper presents a heuristic procedure to solve the problem of locating hospital departments so as to minimize the total distance travelled by patients, and comments on the computational experience with the heuristic.
Management ScienceQuadratic Assignment Problem Algorithms and the Location of Indivisible Facilities
230 Citations1966Frederick S. Hillier, Michael M. Connors
European Journal of Operational ResearchAn algorithm for the quadratic assignment problem using Bender's decomposition
171 Citations1978L. Kaufman, F. Broeckx
The mixed integer program obtained by Glover's method is discussed and a solution using Bender's decomposition is proposed.
SIAM ReviewA Review of the Placement and Quadratic Assignment Problems
168 Citations1972Maurice Hanan, Jerome M. Kurtzberg
The placement problem is explored and a survey of algorithms is presented for the attack of it and the associated quadratic assignment problem and known experimental results of the algorithms defined, conclusions and areas for future research are presented.
A I I E TransactionsComputerized Layout Design: A Branch and Bound Approach
163 Citations1975Mokhtar S. Bazaraa
A branch and bound method for optimizing the resulting problem is devised and optimal and suboptimal layouts can be provided to the layout engineer for consideration and modification.
Operations ResearchThe Optimal Assignment of Facilities to Locations by Branch and Bound
163 Citations1966J. William Gavett, Norman V. Plyter
The branch-and-bound technique with modifications is used to give an optimal assignment, in which the sum of the product of distance times traffic intensity for all pairs of facility-location assignments is a minimum.
Management ScienceAn Algorithm for the Quadratic Assignment Problem
152 Citations1970Glenn W. Graves, Andrew B. Whinston
A novel feature of the paper is the development of the statistical properties of the criterion function used in conjunction with a general enumerative procedure to form the main parts of the algorithm.
International Journal of Production ResearchThe facilities layout problem: a multi-goal approach
152 Citations1979Meir J. Rosenblatt
A heuristic algorithm is developed which results in a discrete efficient frontier set, including only 'efficient layouts’, which is presented as a combined quantitative and qualitative approach to the plant layout problem.
Discrete Applied MathematicsOn the quadratic assignment problem
148 Citations1983Alan Frieze, Jacob Yadegar
The relationship between Gilmore–Lawler lower bounds with decomposition for the quadratic assignment problem and a lagrangean relaxation of a particular integer programming formulation is discussed.
Naval Research Logistics QuarterlyBenders' partitioning scheme applied to a new formulation of the quadratic assignment problem
144 Citations1980Mokhtar S. Bazaraa, Hanif D. Sherali
The quadratic objective function is transformed into a linear objective function by introducing a number of new variables and constraints, and the resulting problem is a 0-1 linear integer program with a highly specialized structure.
European Journal of Operational ResearchA heuristic for quadratic Boolean programs with applications to quadratic assignment problems
139 Citations1983Rainer E. Burkard, Tilman Bönniger
Computational tests with quadratic assignment problems (QAP) showed that it finds very good suboptimal solutions in moderate time and behaves computationally stable.
Management ScienceTechniques for Facilities Layout: Deciding which Pairs of Activities Should be Adjacent
128 Citations1983L. R. Foulds
The layout problem is formulates and exact and heuristic methods of solution are reviewed, special emphasis is placed on the newly-emerging graph-theoretic techniques which appear promising.
International Journal of Production ResearchAn applied model for the facilities design problem
122 Citations1976James A. Tompkins, Ruddell Reed
A model which can be used in the design of a facility, where the facilities design includes the selection of the materials handling system and the placement of departments within the facility is described.
International Journal of Production ResearchGraph theoretic heuristics for the plant layout problem
121 Citations1978L. R. Foulds, D. F. Robinson
Naval Research Logistics QuarterlyNumerical investigations on quadratic assignment problems
111 Citations1978Rainer E. Burkard, Karl‐Heinz Stratmann
This paper contains a comparative study of the numerical behavior of different algorithms for solving quadratic assignment problems, and how they can be combined efficiently with the Gaschutz-Ahrens procedure and the perturbation method.
Parallel Branch‐and‐Bound Algorithms
108 Citations2006Teodor Gabriel Crainic, Bertrand Le Cun +1 more
In the beginning of the twenty-first century, large unsolved combinatorial optimization problems have been solved exactly and the scientific progress in Operations Research, in particular regarding the quality of the lower bounds for these problems, brought on these achievements.
Management ScienceThe Facilities Layout Problem in Perspective
108 Citations1966Thomas E. Vollmann, Elwood S. Buffa
Each layout problem is made unique by its particular assumptions, constraints, limitations, and the intrinsic activity of the components; a guide to establishing this uniqueness and to selecting appropriate tool3 for analysis is presented.
Management ScienceComparison of Computer Algorithms and Visual Based Methods for Plant Layout
103 Citations1975Michael Scriabin, Roger C. Vergin
Tests show not only that the computer algorithms do not perform better than selected human subjects in the design of plant layouts, but that the human subjects actually achieve layouts which are stochastically better than those produced by the computer programs.
International Journal of Production ResearchA multigoal heuristic for facilities design problems: MUGHAL
99 Citations1982KEDAR NATH DUTTA, Sadananda Sahu
Journal of the Operational Research SocietyOn the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem
98 Citations1982Mokhtar S. Bazaraa, Hanif D. Sherali
This paper uses the formulation of the quadratic assignment problem as that of minimizing a concave quadRatic function over the assignment polytope as a model for solving conventional cutting plane procedures for solving this problem.
Operations ResearchDISCON: A New Method for the Layout Problem
95 Citations1980Zvi Drezner
The problem is formulated and solved as a nonconvex mathematical programming problem using a procedure termed DISpersion-CONcentration, and the total cost is the sum of weighted distances between all pairs of facilities.
Management ScienceSpacecraft for Multi-Floor Layout Planning
94 Citations1982Roger V. Johnson
The problem definition and solution procedure overcome the problem of severe nonlinearity of inter-department movement times relative to distance, which enter the multi-floor problem because of the indirectness of routing, and because of different movement speeds compared with the single floor case.
Naval Research Logistics QuarterlyTree-search algorithms for quadratic assignment problems
87 Citations1971J.F. Pierce, Wallace B. Crowston
Several types of algorithms for solving quadratic assignment problems are discussed, presenting a unifying framework for some of the existing algorithms, and dcscribing some new algorithms.
Management ScienceFacilities Planning with Graph Theory
86 Citations1970Jouko Seppänen, James M. Moore
Naval Research Logistics QuarterlyA branch‐and‐bound‐based heuristic for solving the quadratic assignment problem
77 Citations1983Mokhtar S. Bazaraa, Ömer Kırca
Using symmetric properties of the problem, the algorithm eliminates 'mirror image' branches, thus reducing the search effort and producing the best known solutions for all well-known problems in the literature.
Operations ResearchFacilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics
76 Citations1985L. R. Foulds, Peter B. Gibbons +1 more
Three graph theoretic heuristics that attempt to determine an optimal planar adjacency graph from a REL chart are described and computational experience suggests that these methods can provide effective solutions to problems of the size frequently encountered in practice by designers.
Management ScienceA Multiple Objective Approach to Space Planning for Academic Facilities
75 Citations1979Larry P. Ritzman, John Bradford +1 more
This paper addresses the office layout problem where existing offices vary considerably as to relevant criteria and yet permanent walls make it impractical to remodel existing spaces.
International Journal of Production ResearchFacilities relative allocation technique (FRAT)
73 Citations1973Tarek M. Khalil
The proposed algorithm, combining features from other well known models, and programmed in Fortran IV is tested against existing methods and shows that the algorithm is efficient, easy to run and is very competitive with other well-known methods.
Management ScienceThe Quadratic Assignment Problem: An Experimental Evaluation of Solution Strategies
69 Citations1981Robin Liggett
Management ScienceModular Allocation Technique (MAT)
64 Citations1970Harry K. Edwards, Billy E. Gillett +1 more
The MAT general algorithm, an example problem and a theorem relating the MAT solution to the optimal solution are given and a computer program has been written that will apply MAT to the allocation problem for a maximum of 40 facilities.
Management ScienceA Cluster-Analytic Approach to Facility Layout
61 Citations1985Michael Scriabin, Roger C. Vergin
A new algorithm, FLAC (Facility Layout by Analysis of Clusters), is described which emulates the visual methods used by industrial engineers in solving facility layout problems and is found to perform well in problems with high as well as low flow dominance.
Journal of the Operational Research SocietyA Strategy for Solving the Plant Layout Problem
60 Citations1976L. R. Foulds, D. F. Robinson
This work considers the problem of laying out the facilities of which a plant is composed, in terms of specifying which facilities are to be adjacent, and seeks to maximise the sum of benefits over all pairs of adjacent facilities.
Computers & Industrial EngineeringFacilities layout—A survey of solution procedures
56 Citations1985Reuven R. Levary, Sylvia Kalchik
Management ScienceThe Efficiency of Computer Algorithms for Plant Layout
54 Citations1972Larry P. Ritzman
This paper presents the results of comparing experimentally the performance of four of the more promising computer algorithms for the plant layout problem, tested with twenty-six test problems.
International Journal of Production ResearchComputer aided facilities design : An international survey
53 Citations1974James M. Moore
It is apparent that computers are being used as design aids although few practitioners are willing to delegate the whole job to a computer at this time.
Management ScienceA Perturbation Scheme to Improve Hillier’s Solution to the Facilities Layout Problem
51 Citations1984Christopher J. Picone, Wilbert E. Wilhelm
A new heuristic is described, the Revised Hillier procedure, for solving the facilities layout problem, which incorporates the effective features of the well-knownHillier procedure in combination with 3-way and 4-way exchanges to extend the neighborhood over which the search for a solution is conducted.
Journal of the Operational Research SocietyA Problem of Assignment with Inter-Related Costs
51 Citations1963A. H. Land
There is a class of assignment problems where the cost function depends on the assignment of pairs of variables and a method of finding the optimum solution by a systematic exploration of a limited part of the solution space is presented by means of a numerical example.
Naval Research Logistics QuarterlyAn exact branch‐and‐bound procedure for the quadratic‐assignment problem
48 Citations1979Mokhtar S. Bazaraa, Alwalid N. Elshafei
An exact branch-and-bound procedure, which is able to produce optimal solutions for problems with twelve facilities or less, is developed and incorporates the concept of stepped fathoming to reduce the effort expended in searching the decision trees.
European Journal of Operational ResearchAn exact algorithm for the general quadratic assignment problem
48 Citations1986Bharat K. Kaku, Gerald L. Thompson
An algorithm that is based on the linearization and decomposition of a general Quadratic Assignment Problem of size n into n2 Linear Assignment Problems of size (n − 1) to calculate a lower bound for the original problem.
Operations ResearchAn Efficient Equipment-Layout Algorithm
46 Citations1974Farrokh Neghabat
This paper treats the problem of locating a given number of interrelated physical facilities in a single-or multi-story building as an optimization model such that the weighted sum of the distances along orthogonal directions is minimized, and describes a constructive heuristic algorithm for the one-dimensional model.
OmegaA heuristic for facilities layout planning
42 Citations1985R. H. Green, Lar Al-Hakim
A new matrix representation of a planar graph and its dual is presented and this is then used to implement a heuristic for facilities layout planning.
International Journal of Production ResearchAn interactive approach to computer aided facility layout
41 Citations1980Claire O’Brien, S. E. Z. Abdel Barr
An interactive approach to construction and improvement procedures which utilizes a refresh graphics terminal (IMLAC) linked to a PRIME 400 computer and a heuristic procedure, S-ZAKY, to develop improved layouts based upon an analysis of materials flow.
OmegaGraph theory and computer aided facilities design
38 Citations1978Allan S. Carrie, James M. Moore +2 more
Four variations of an algorithm based upon graph theory are developed for solving the facilities design problem, which involves locating economic activities on a floor within a building in such a manner to optimize an appropriate measure of effectiveness such as the total cost of materials handling.
Naval Research Logistics QuarterlySolving quadratic assignment problems with rectangular distances and integer programming
34 Citations1976Robert F. Love, Jsun Y. Wong
International Journal of Production ResearchA REVIEW OF PLANT DESIGN TECHNIQUES
32 Citations1970TARIG E. EL-RAYAH, R. H. Hollier
International Journal of Production ResearchOn the use of flow dominance in complexity measures for facility layout problems
30 Citations1985Willy Herroelen, Annick Van Gils
It is shown that flow dominance does not serve its intended purpose and that the complexity rating factors suggested in the literature not only show serious problems with regard to their interpretability, but are largely unusable.
Management ScienceHumans vs. Computer Algorithms for the Plant Layout Problem
30 Citations1980Thomas W. Trybus, Lewis D. Hopkins
International Journal of Production ResearchString processing algorithms for plant layout problems
26 Citations1975Jouko Seppänen, James M. Moore
A problem oriented linear string representation for trees and the concept of grammar are introduced as basic tools for symbolic computation of trees and planar graphs and the need of optimal algorithmic techniques is pointed out.
OmegaAn efficient heuristic procedure for solving the layout design problem
25 Citations1976G. G. Hitchings
By utilizing unique attributes associated with real-life problems and using small incisive modifications it is demonstrated how a heuristic procedure can be significantly improved.
Naval Research Logistics QuarterlySuboptimal algorithms for the quadratic assignment problem
25 Citations1968G. K. Gaschütz, Joachim Ahrens
International Journal of Production ResearchOn the application of computer aids to plant layout
24 Citations1980Lewis Waswa, Trevor Block
The results of an extensive investigation into the performance of both human planners and computer algorithms on a standard set of layout problems are reported.
Management ScienceNote—On the Complexity of Facilities Layout Problems
22 Citations1979Trevor Block
A complexity rating that is a function of the flow dominance and the upper and lower bound to the value of flow dominance is defined for facilities layout problems to provide a better measure of problem complexity than one based on flow dominance alone.
A I I E TransactionsLayout Planning by Computer Simulation
21 Citations1972Klaus Zoller, Kristian Adendorff
The model presented in this paper uses computer simulation to generate and evaluate samples from this population of work centers, with the objective of obtaining some observations from the vicinity of the overall optimum.
International Journal of Production ResearchEvaluation of an application of graph theory to the layout problem
21 Citations1985Amar Hammouche, Dennis B. Webster
A graph theory approach is developed based on research experience and suggestions of Moore, Carrie and Seppanen, to develop a general computer program implementing the procedure and to compare its performance with that of CRAFT, CORELAP and ALDEP.
Management ScienceNote—A Note on “Comparison of Computer Algorithms and Visual Based Methods for Plant Layout” by M. Scriabin and R. C. Vergin
20 Citations1977Trevor Block
This note recommends the use of flow dominance as a measure to determine the choice between computer algorithms and visual based methods for plant layout and shows by an experiment that for plant layouts problems with a flow dominance less than 200% computer algorithms are superior to visual based Methods.
Special Cases of the Quadratic Assignment Problem
18 Citations1976Nicos Christofides, Michael John Gerrard
Journal of the Operational Research SocietyAn Experimental Investigation of Some Heuristic Strategies for Component Placement
15 Citations1976Charles Steven Parker
A construction approach due to Graves and Whinston produced the best results, both when used to generate starting solutions for the improvement methods and when evaluated on its own merit against the improved methods using other starts.
Management ScienceNote—Plant Layout: Computers Versus Humans
12 Citations1977Denis R. Coleman
It is attempted to show that Scriabin's and Vergin's experiments do not provide a useful comparison of computers and humans, and to point out several experimental procedures that would make comparisons of heuristic computer algorithms and humans more valid.
Design StudiesThe patients' view of their domain
12 Citations1988Tun Sing Chen, Henry Sanoff
Reactions to existing and proposed hospital rooms were elicited from staff as well as obstetric, medical, and mental health patients, and varying preferences for privacy and social interaction by patients and nurses.
Management ScienceNote—A Note on Spacecraft for Multi-Floor Layout Planning
9 Citations1984F. Robert Jacobs
This note provides a brief comparison between a three-dimensional layout planning system recently described in Management Science and a similar system developed earlier, using SPACECRAFT for multi-floor layout planning.
Management ScienceNote—Comments on the Complexity Rating Factor for Layout Problems
8 Citations1981R. Gupta, Michael P. Deisenroth
The sensitivities of flow dominance and the rating factor to changes in a single element of the flow matrix are examined and their implications discussed.
…