Int J Adv Manuf Technol (2006) 30: 425–433

DOI 10.1007/s00170-005-0087-9

ORIGINA L ARTI CLE

S. P. Singh . R. R. K. Sharma

A review of different approaches to the facility layout problems

Received: 28 September 2004 / Accepted: 9 March 2005 / Published online: 12 November 2005
# Springer-Verlag London Limited 2005

Abstract Here, an attempt is made to present a state-of- They must be carefully considered in the context of the
the-art review of papers on facility layout problems. This FLP. This paper gives a review of different approaches to
paper aims to deal with the current and future trends of the FLP, viz. formulations, solution methodologies and
research on facility layout problems based on previous re- current as well as emerging trends. This paper aims to
search including formulations, solution methodologies and endorse readers who want to explore facility layout re-
development of various software packages. New develop- search and layout packages; it is an active area in which
ments of various techniques provide a perspective of the nearly 140 papers have been published on the FLP over the
future research in facility layout problems. A trend toward last 20 years. A detailed review of each and every software
multi-objective approaches, developing facility layout soft- package is not carried out here but the references are
ware using meta-heuristics such as simulated annealing provided.
(SA), genetic algorithm (GA) and concurrent engineering The paper is structured as follows: In Section 2 an
to facility layout is observed. overview of the FLP along with the formulations is de-
scribed. Solution methodology is addressed in Section 3.
Keywords Survey of facility layout problems . Current trends and further scope of work are discussed in
Combinatorial optimization . Quadratic assignment Section 4 followed by a conclusion.
problem (QAP) . Mixed integer programming (MIP)

2 Overview of facility layout problem

1 Introduction
The FLP is a well studied combinatorial optimization
Determining the physical organization of a production problem which arises in a variety of problems such as
system is defined to be the facility layout problem (FLP). printed circuit board design; layout design of hospitals,
Where to locate facilities and the efficient design of those schools, and airports; backboard wiring problems; type-
facilities are important and fundamental strategic issues writers; warehouses; hydraulic turbine design; etc. The
facing any manufacturing industry. Tompkins and White focus of this review work is on the facility layout of
[1] estimated that 8% of the United States gross national industrial (manufacturing) plants, which is concerned with
product has been spent on new facilities annually since finding the most efficient arrangement of ‘n’ indivisible
1955, that does not include the modification of existing facilities in ‘n’ locations. Minimizing the material handling
facilities. Francis and White [2] claimed that from 20 to 50 cost is the most considered objective but Mecklenburgh [3]
percent of the total operating expenses in manufacturing and Francis et al. [4] gave qualitative as well as quantitative
are attributed to materials handling costs. Effective facil- objectives for FLP. Reduced material movement [5, 6]
ities planning could reduce these costs by 10 to 30 percent lowers work-in-process levels and throughput times, less
annually. For FLP, the most common objective used in product damage, simplified material control and schedul-
mathematical models is to minimize the materials handling ing, and less overall congestion. Hence, when minimizing
cost, which is a quantitative factor. Qualitative factors such material handling cost, other objectives are achieved
as plant safety, flexibility of layout for future design simultaneously. The output of the FLP is a block layout
changes, noise and aesthetics [2] can also be considered. that specifies the relative location of each department.
Detailed layout of a department can also be obtained later
by specifying aisle structure, and input/output point
locations which may include flow line and machine layout
S. P. Singh (*) . R. R. K. Sharma problems. This paper is a survey of block layout. This
Department of Industrial and Management Engineering, section deals with the description of formulations of FLP.
Indian Institute of Technology Kanpur,
Kanpur, 208016, India In the following sub-sections, Section 2.1 describes
e-mail: sprsingh@[Link] QAP, graph theoretic approach is given in Section 2.2 and
Fax: +91-512-2597553 MIP formulation for FLP is provided in Section 2.3.
426

2.1 QAP model 21]. A review of the results of graph theoretic approaches
can be found in Foulds [17] and Hassan and Hogg [16].
FLP has been generally formulated as a QAP introduced by
Koopmans and Beckman [7] which is NP-complete [8–10]
and one of the frequently used formulations to resolve FLP. 2.3 MIP model
Consequently, even a powerful computer cannot handle a
large instance of the problem. The objective can be to either MIP has received some attention as a way of modeling the
minimize time, cost, traveling distance, and/or flows. Con- FLP. Montreuil [22] first formulated FLP as MIP where a
sequently, various heuristics have been proposed thus far to distance-based objective was used in a continuous layout
solve large instances of QAP and a review of these heuristic representation that was an extension of the discrete QAP.
is given in Section 3.2. Equivalent linear integer formula- Hegaru and Kusiak [23] developed a specialized case of
tions and heuristics have developed for solving the QAP this MIP. Lacksonen [24] proposed a two-step algorithm
but they are limited to particular problems [11–13]. Lawler for solving the FLP while assuming variable area which
[14] and Christofides et al. [15] demonstrated the equiv- can solve a general dynamic facility layout with varying
alence of the QAP problem to a linear assignment problem departmental areas assuming that all are rectangular.
with certain additional constraints. The following formu- Lacksonen [25] then extended the proposed model to
lation is adopted from Koopmans and Beckman [7]. deal with unequal areas and rearrangement costs. However,
the model could only be optimally solved for small prob-
n X
X n X
n X
n
lems. Kim and Kim [26] considered the problem of
MinTF ¼ 1=2
Fik
Djl
Xij
Xkl (1) locating input and output (I/O) points of each department
i¼1 j¼1 k¼1 l¼1 for a given block layout with the objective of minimizing
i6¼k j6¼l
the total transportation distance. A new branch-and-bound
algorithm was proposed that seems to perform efficiently
X
n even for large-size problems. However, the simultaneous
Xij ¼ 1 for all i ¼ 1:::n (2) solution of the block problem and the I/O points layouts
j¼1 has not yet been solved. Barbosa-Povoa et al. [27] pro-
posed a mathematical programming approach for the gen-
eralized facilities detailed layout problem.
X
n A detailed MIP for FLP can be found in Montreuil [22].
Xij ¼ 1 for all j ¼ 1:::n (3) Although this MIP approach holds much promise, cur-
i¼1
rently only FLP of size six or less [18] are optimally
solvable. The objective is based on flow time rectilinear
Xij=1 if facility “i” is located/assigned to location “j”. distance between centroid of two departments.
Xij=0 if facility “i” is not located/assigned to location “j”.
Fik is the flow between two facilities i and k.
Djl is the distance between two locations j and l. 3 Solution methodology
Constraint 1 (Eq. 1) is a restriction that only one facility
can be located at one location, and constraint 2 (Eq. 2) In this section various solution methodologies, e.g. exact
ensures that each location can only be assigned to one procedures, heuristics and meta-heuristics available to
facility. The objective is to minimize the total flow among solve facility layout problems optimally or near to optimal,
facilities i=1 to n and k=1 to n. As all indices are summed are discussed in detail. Exact procedures that can give
from 1 to n, each assignment will be counted twice; hence optimal solutions to facility layout problems are discussed
the need to multiply by 1/2. in Section 3.1. Section 3.2 briefly describes heuristic meth-
ods used to solve facility layout problems. Meta-heuristics
available to solve facility layout problems are given is
2.2 Graph theory model Section 3.3. Section 3.4 is devoted to artificial intelligence
approaches applied to solve the facility layout problems.
In the graph theoretic approaches each department or ma-
chine (ignoring the area and shape of the departments at the
beginning) is defined as a node within a graph network. 3.1 Exact procedure
These rely on a predefined desirable adjacency of each pair
of facilities [16, 17]. In other words, it can be said that in Branch and bound methods are used to find an optimum
graph theoretic approaches, it is assumed that the desirabil- solution of quadratic assignment formulated FLP because
ity of locating each pair of facilities adjacent to each other QAP involves only binary variables. Only optimal solu-
is known. Like QAP approaches, unequal area problems of tions up to a problem size of 16 are reported in literature.
even small size cannot be solved optimally [18]. Various pa- Beyond n=16 it becomes intractable for a computer to
pers have been published on this subject where different mod- solve it and, consequently, even a powerful computer can-
els and algorithms’ characteristics have been explored [19– not handle a large instance of the problem.
 427

3.2 Heuristics Table 1 List of facility layout packages [33, 35]

[Link] References Name of package
A comprehensive investigation of the FLP literature
includes examining heuristics. Heuristic algorithms can 1 Dr. Gordan Armour CRAFT
be classified as construction type algorithms where a 2 Seehof and Evans ALDEP
solution is constructed from scratch and improvement type 3 Dr. Moore James CORELAP
algorithms where an initial solution is improved. Con- 4 Michael P. Deisenroth PLANET
struction based methods are considered to be the simplest 5 Teichholz Eric COMP2
and oldest heuristic approaches to solve the QAP from a 6 Kaiman Lee COMPROPLAN COMSBUL
conceptual and implementation point of view, but the 7 Robert C. Lee CORELAP8
quality of solutions produced by the construction method is 8 Robert Dhillon DOMINO
generally not satisfactory. Improvement based methods 9 Teichholz Eric GRASP
start with a feasible solution and try to improve it by inter- 10 Dr. Johnson T.E. IMAGE
changes of single assignments. Improvement methods can 11 Dr. Warnecke KONUVER
easily be combined with construction methods. CRAFT 12 Dr. Warnecke LAYADAPT
[28] is a popular improvement algorithm that uses pair- 13 Raimo Matto LAYOPT
wise interchange. A survey of a few well known heuristics 14 John S. Gero LAYOUT
which are popular as layout software are provided in 15 Dr. Love R.F. LOVE*
Table 1 along with the algorithm used. These heuristics are 16 Dr. Warnecke MUSTLAP2
classified as adjacency and distance based algorithms. For 17 Dr. Vollman Thomas OFFICE
instance, MATCH [29] and SPIRAL [30] are adjacency
18 McRoberts K. PLAN
based while CRAFT [28], SHAPE [31], LOGIC [32],
19 Anderson David PREP
MULTIPLE [33], and FLEX-BAY [34] are distance based
20 Moucka Jan RG and RR
algorithms (descriptions are not provided but interested
21 Dr. Ritzman L.P. RITZMAN*
readers can refer to the cited papers).
22 Dr. Warnecke SISTLAPM
The difference between these two algorithms lies in the
objective function. The objective function for adjacency 23 Prof. Spillers SUMI
based algorithms is given as 24 Hitchings G. Terminal Sampling Procedure
25 Johnson [36] SPACECRAFT
XX
 26 Tompkins and Reed [37] COFAD
max rij xij (4)
i j
27 Hassan, Hogg SHAPE
and Smith [31]
28 Banerjee et al. [38] QLAARP
where xij is 1 if department ‘i’ is adjacent to department ‘j’
29 Tam [39] LOGIC
and else 0. The basic principle behind this objective
30 Bozer, Meller, MULTIPLE
function is that the material handling cost is significantly
and Erlebacher [33]
reduced if the two departments have adjacent boundaries.
31 Tate and Smith [34] FLEX-BAY
The objective function of distance based algorithms is
given as 32 Foulds and Robinson [40] DA (Adjacency Based)
33 Montreuil, Ratliff MATCH (Adjacency Based)
n X
X n X
n X
n and Goetschalckx [29]
MinðTCÞ ¼ 1=2
Cik
Djl
Xij
Xkl 34 Goetschalckx [30] SPIRAL (Adjacency Based)
i¼1 j¼1 k¼1 l¼1 35 Balkrishnan et al. [41] FACOPT
i6¼k j6¼l
* Indicates that the names of packages are based on author’s name
(5)

The underlying philosophy behind this objective func- Where, CikH and DjlH stand for horizontal material
tion is that the distance increases the total cost of traveling. handling cost and horizontal distance, respectively. The
Cik can be replaced by Fik depending on the objective. same meanings are applicable for CikV and DjlV but in
Equation 6 is used as an objective function when the vertical directions.
facility layout is designed for multi-floor.
X
n X
n X
n X
n
 3.3 Meta-heuristics
min CikH
DjlH þ CikV
DjlV
Xij
Xkl
i¼1 j¼1 k¼1 l¼1 Various meta-heuristics such as SA, GA, and ant colony are
i6¼k j6¼l
currently used to approximate the solution of very large
(6) FLP. The SA technique originates from the theory of
statistical mechanics and is based upon the analogy be-
tween the annealing of solids and solving optimization
problems. Burkard and Rendl [42] derived SA for QAP. A
428
Table 2 Survey of SA based S. No. Reference Year QAP MIP Heuristic
FLP papers
1 Kirkpatrick et al. [46] 1983 √ Simulated annealing
2 Burkard and Rendl [42] 1984 √ Simulated annealing
3 Wilhelm and Ward [47] 1987 √ Simulated annealing
4 Kaku and Thomson [48] 1986 √ Simulated annealing
5 Connolly [49] 1990 √ Simulated annealing
6 Laursen [10] 1993 √ Simulated annealing
7 Tam [32] 1992 √ Simulated annealing
8 Heragu and Alfa [50] 1992 √ Simulated annealing
9 Kouvelis et al. [51] 1992 √ Simulated annealing
10 Jajodia et al. [52] 1992 √ Simulated annealing
11 Shang [53] 1993 √ SA and AHP
12 Souilah [54] 1995 √ Simulated annealing
13 Peng et al. [55] 1996 √ Simulated annealing
14 Meller and Bozer [56] 1996 √ Simulated annealing
15 Azadivar and Wang [57] 2000 √ Simulated annealing
16 Baykasoglu and Gindy [58] 2001 √ Simulated annealing
17 Misevicius [59] 2003 √ Simulated annealing
18 Balakrishnan et al. [41] 2003 √ √ SA and GA

most recent survey of SA based facility layout papers is applied TS to solve FLP. The method is still actively re-
tabulated in Table 2. searched, and is continuing to evolve and improve.
GA gained more attention during the last decade than Recently, a few papers have appeared where an ant
any other evolutionary computation algorithms; it utilizes a colony algorithm has been attempted to solve large FLP.
binary coding of individuals as fixed-length strings over Talbi et al. [45] applied ant colony to solve QAP.
the alphabet {0, 1}. GA iteratively search the global opti-
mum, without exhausting the solution space, in a parallel
process starting from a small set of feasible solutions 3.4 Other approaches
(population) and generating the new solutions in some
random fashion. Performance of GA is problem dependent Other approaches which are also currently applied to FLP
because the parameter setting and representation scheme are neural network, fuzzy logic and expert system.
depends on the nature of the problem. Tavakkoli- Tsuchiya et al. [72] had proposed near-optimum parallel
Moghaddam and Shayan [43] analyzed the suitability of algorithm for solving the QAP using two-dimensional
genetic operator for solving FLP. Table 3 provides recent maximum neural network for an N-FLP. Knowledge based
papers on GA based FLP. expert system has also been applied by Malakooti and
Tabu search (TS) is an iterative procedure designed to Tsurushima [73], Abdou and Dutta [74], Heragu and
solve optimization problems. Helm and Hadley [44] Kusiak [75] and Sirinavakul and Thajchayapong [76] to

Table 3 Survey of GA based S. No. Reference Year QAP MIP Heuristic

FLP papers
1 Tam [39] 1992 √ Genetic algorithm
2 Banerjee and Zhou [60] 1995 √ Genetic search
3 Tate and Smith [34] 1995 √ GA
4 Kochhar and Heragu [61] 1998 √ √ Extension of GA
5 Islier [62] 1998 GA
6 Rajshekaran et al. [63] 1998 √ √ GA
7 Mak et al. [64] 1998 √ GA
8 Mckendall et al. [65] 1999 √ √ GA nested approach
9 Kochhar and Heragu [66] 1999 √ GA
10 Gau and Meller [67] 1999 √ √ GA
11 Azadivar and Wang [57] 2000 √ GA and simulation algorithm
12 Al-Hakim [68] 2000 GA
13 Ahuja [69] 2000 √ Genetic algorithm
14 Wu and Appleton [70] 2002 √ GA
15 Lee, Han and Roh [71] 2003 √ GA, Dijkstra algorithm
16 Balakrishnan et al. [41] 2003 √ √ GA and SA
 429
Table 4 Survey of Papers S. Reference Year QAP MIP Heuristic Techniques
where other approaches are ap-
plied to solve FLP No.

1 Dutta and Sahu [78] 1982 √ √

2 Murtagh et al. [79] 1982 √ √
3 Foulds [80] 1983 √ Graph theory
4 Herroelen and Vangils [81] 1985 Flow dominance theory
5 Fortenberry and Fox [82] 1985 √ Pair-wise exchange
6 Hammouche and Webster 1985 Graph theory (theoritical approach)
[83]
7 Foulds and Giffin [84] 1985 √ Graph theory
8 Green and Al_Hakim [85] 1985 √ √
9 Rosenblatt [86] 1986 √ Dynamic programming
10 Kaku and Thomson [48] 1986 √ Simulated annealing
11 Hassan et al. [31] 1986 √ √ Construction
12 Foulds et al. [87] 1986 √ Graph theory
13 Grobelny [88] 1987 √ Fuzzy approach
14 Evans et al. [89] 1987 √ Fuzzy set theory
15 Urban [90] 1987 √ √
16 Rosenblatt and Lee [91] 1987 √ √
17 Jacobs [92] 1987 √ Graph theory
18 Montreuil et al. [29] 1987 Graph theory
19 Hassan and Hogg [16] 1987 Graph theory
20 Grobelny [93] 1988 √ Fuzzy approach
21 Kaku et al. [94] 1988 √ √
22 Kumar et al. [77] 1988 Expert system, pattern recognition
23 Smith and Macleod [95] 1988 √ L. R. and B and B
24 Malakooti and Tsurushima 1989 Expert system, rule based
[73]
25 Malakooti [96] 1989 √ √
26 Heragu and Kusiak [97] 1988 √ √
27 Heragu and Kusiak [75] 1990 √ Knowledge approach
28 Abdou and Dutta [74] 1990 Expert system
29 Houshyar and McGinis [98] 1990 √ √ Cut approach
30 Al-Hakim [99] 1991 Graph theory
31 Heragu and Kusiak [23] 1991 √ √ Unconstrained opt.
32 Kaku et al. [100] 1991 √ √
33 Hassan and Hogg [101] 1991 √ Graph theory
34 Logendran [102] 1991 √ √
35 Burkard et al. [103] 1991 √ QAP_LIB
36 Camp et al. [104] 1992 √ √ Penalty function
37 Leung [105] 1992 √ Graph theory
38 Kaku and Rachamadya [106] 1992 √ √
39 Rosenblatt and Golany [107] 1992 √ √
40 Goetschalckx [30] 1992 √ √ Graph theory
41 Harmonosky and Tothero 1992 √ √ Pairwise, construction
[108]
42 Askin and Mitwasi [109] 1992 √ √
43 Balakrishnan et al. [110] 1992 √ √
44 Al-Hakim [111] 1992 Grapht theory
45 Lacksonan and Enscore 1993 √ B and B, cutting plane, D.P.
[112]
46 White [113] 1993 √ Branch and bound; convex
programming
47 Yaman et al. [114] 1993 √ √
48 Das [115] 1993 √ √
49 Raoot and Rakshit [116] 1991 √ Fuzzy based
430
Table 4 (continued) S. Reference Year QAP MIP Heuristic Techniques
No.

50 Raoot and Rakshit [117] 1994 √ Fuzzy based

51 Urban [118] 1993 √ √
52 Montreuil et al. [119] 1993 √ Graph theory, LP
53 Bozer et al. [33] 1994 √
54 Boswell [120] 1994 √ Graph theory based
55 Sirinaovakul [76] 1994 √ Knowledge based expert
56 Langevin et al. [121] 1994 √ √
57 Trethway and Footle [122] 1994 √
58 White [123] 1996 √ Lagrangian relaxation
59 Badiru and Arif [124] 1996 Fuzzy theory
60 Chiang and Kouvelis [125] 1996 √ Tabu Search
61 Watson and Giffin [21] 1997 √ Vertex splitting algo.
62 Meller [126] 1997 √ √
63 Lacksonan [25] 1997 √ √ Branch and bound
64 Bozer and Meller [127] 1997 √
65 Sarker et al. [13] 1998 √ √
Zetu et al. [128] 1998 Virtual reality(Theoritical approach)
66 Urban [129] 1998 √ Dynammic programming
67 Chan and Sha [130] 1999 √ √
68 Smith and Helm [131] 1999 Virtual reality (Theoritical approach)
69 Dweiri [132] 1999 Fuzzy based
70 Helm and Hadley [44] 2000 √ √ Tabu-search based
71 Knowles and Corne [133] 2002 √ Multi-obj. approach
72 Kim and Kim [134] 2000 √ √
73 Barbosa-Povoa et al. [27] 2001 √ √
74 Al-Hakim [135] 2001 Maximally planer graph
75 Wang and Sarker [136] 2002 √ √
76 Chan, Chan and Ip [137] 2002 √ √
77 Diponegoro and Sarker [138] 2003 √ √
78 Castillo and Peters [139] 2003 √ √ Extended distance based

tackle various issues related to FLP such as multi-

objective, the issue of optimizing material handling
equipment, etc. Kumar et al. [77] applied expert system
to handle qualitative constraints via a symbolic manipula- Facility Layout
tion structure. A survey of papers where these methodol-
ogies have been applied to solve FLP is given in Table 4.

4 Current trends and future scope of work Static (or Dynamic) Layout

This section addresses the issues related to current trends in

Models

the area of FLP and also future research directions. Section

4.1 deals with the currents trends in facility layout followed
by future scope of work.
QIP, MIP, GRAPH THEORY

4.1 Current trends

A summary of current trends during the last two decades is

reviewed here where more than 100 papers are classified as Solution Methodologies to
per the facility classification scheme shown in Fig. 1. solve FLP
Papers in various tables are given in chronological order
along with the solution methodology and formulation used Fig. 1 Classification scheme of facility layout problems
 431

to model FLP that helps to provide a clear understanding of 6. Fu MC, Kaku BK (1997) Minimizing work-in-process and
various aspects of FLP. material handling in the facilities layout problem. IIE Trans
29:29–36
7. Koopmans TC, Beckman M (1957) Assignment problems and
the location of economic activities. Econometrica 25:53–76
4.2 Future scope of work 8. Garey MR, Johnson DS (1979) Computers and intractability: a
guide to the theory of NP-completeness. WH Freemen, New
York
By observing all tables it has been found that research on 9. Kusiak A, Heragu S (1987) The facility layout problem. Eur J
the FLP is not converging but is somewhat diverging. Now, Oper Res 29:229–251
AI can be used apart from developing heuristic to solve 10. Laursen PS (1993) Simulated annealing for the QAP-optimal
large sized FLPs; and more investigation into the multi- tradeoff between simulation time and solution quality. Eur J
objective function rather than single objective function is Oper Res 69:238–243
11. Sarker BR, Yu J (1994) A two-phase procedure for duplicating
required in order to include more relevant layout criteria. bottleneck machines in linear layout, cellular manufacturing
Every two years the Material Handling Institute of system. Int J Prod Res 32(9):2049–2066
America [18], along with other sponsoring industries and 12. Kouvelis P, Chiang W, Yu G (1995) Optimal algorithms for row
government agencies, organizes consortium on material layout problems in automated manufacturing systems. IIE
Trans 27(1):99–104
handling research where researchers are asked to present 13. Sarker BR, Wilhelm WE, Hogg GL (1998) One-dimensional
their research. It is found that there is a lack of application machine layout problems in a multi-product flow line with
of concurrent engineering in FLP with respect to the choice equidistant layouts. Eur J Oper Res 105(3):401–426
of the material handling system which in turn shows that 14. Lawler EL (1962) The quadratic assignment problem. Manage
Sci 9(4):586–599
the current facility layout design is irrespective to the 15. Christofides N, Mingozzi A, Toth P (1980) Contributions to the
choice of material handling system. It has been concluded quadratic assignment problem. Eur J Oper Res 18(4):243–247
that the same facility layout design may not be appropriate 16. Hassan MMD, Hogg GL (1987) A review of graph theory
for all periods since the demand can never remain the same. applications to the facilities layout problem. Omega 15:291–
Hence, research should be towards a stochastic facility 300
17. Foulds LR (1991) Graph theory and applications. Springer,
layout rather than a static one. Berlin Heidelberg New York
There is emerging research into applying meta-heuristic 18. Meller RD, Gau KY (1996) The facility layout problem: recent
such as SA, GA and tabu search to solve large FLP. But, the and emerging trends and perspectives. J Manuf Syst 15:351–
final result depends on the initial solution (or population) 366
19. Boswell SG (1992) TESSA a new greedy algorithm for
taken. Therefore, more research is required to develop facilities layout planning. Int J Prod Res 30:1957–1968
good heuristic to generate good initial feasible solutions. 20. Kim JY, Kim YD (1995) Graph theoretic heuristics for unequal-
sized facility layout problems. Omega 23:391–401
21. Watson KK, Giffin JW (1997) The vertex splitting algorithm
for facilities layout. Int J Prod Res 35:2477–2492
5 Conclusion 22. Montreuil B (1990) A modeling framework for integrating
layout design and flow network design. In: Proceedings of the
The trends of facility layout research over the past two material handling research colloquium, Hebron, KY, pp 43–58
decades are presented in this paper. Recent facility layout 23. Heragu S, Kusiak A (1991) Efficient models for the facility
papers are identified and summarized along with the layout problems. Eur J Oper Res 53:1–13
24. Lacksonen TA (1994) Static and dynamic facility layout
solution methodology used. Various algorithms as well as problems with varying areas. J Oper Res Soc 45:59–69
computerized facility layout software are addressed. A 25. Lacksonen TA (1997) Pre-processing for static and dynamic
further scope of work that is needed in the facility layout facility layout problems. Int J Prod Res 35:1095–1106
area is also suggested. 26. Kim JY, Kim YD (1999) A branch-and-bound algorithm for
locating input and output points of departments on the block
layout. J Oper Res Soc 50:517–525
Acknowledgements The communicating author wishes to express 27. Barbosa-Povoa AP, Mateus R, Novais AQ (2001) Optimal two
his sincere thanks to Prof. B.J. Davies and anonymous referees for dimensional layout of industrial facilities. Int J Prod Res 39
their constructive suggestions which has led to considerable (12):2567–2593
improvement in the quality of this manuscript. 28. Armour GC, Buffa ES (1963) A heuristic algorithm and
simulation approach to relative allocation of facilities. Manage
Sci 9:294–309
29. Montreuil B, Ratliff HD, Goetschalckx M (1987) Matching
References based interactive facility layout. IIE Trans 19(3):271–279
30. Goetschalckx M (1992) An interactive layout heuristic based
1. Tompkins JA, White JA (1984) Facilities planning. Wiley, New on hexagonal adjacency graphs. Eur J Oper Res 63:304–321
York 31. Hassan MMD, Hogg GL, Smith DR (1986) SHAPE: a
2. Francis RL, White JA (1974) Facility layout and location: an construction algorithm for area placement evaluation. Int J
analytical approach. Prentice Hall, Englewood Cliffs, NJ Prod Res 24(5):1283–1295
3. Mecklenburgh JC (1985) Process plant layout. Longman, New 32. Tam KY (1992) A simulated annealing algorithm for allocating
York space to manufacturing cells. Int J Prod Res 30:63–87
4. Francis RL, McGinnis LF, White JA (1992) Facility layout and 33. Bozer YA, Meller RD, Erlebacher S J (1994) An improvement-
layout: an analytical approach. Prentice Hall, Englewood Cliffs, type layout algorithm for single and multiple-floor facilities.
NJ Manage Sci 40(7):918–932
5. Askin RG, Standridge CR (1993) Modeling and analysis of 34. Tate DM, Smith AE (1995) A genetic approach to the quadratic
manufacturing systems. Wiley, New York assignment problem. Comput Oper Res 22:73–83
432
35. Moore JM (1974) Computer aided facilities design: an in- 63. Rajasekharan M, Peters BA, Yang T (1998) A genetic
ternational survey. Int J Prod Res 12(1):21–44 algorithm for facility layout design in flexible manufacturing
36. Johnson FR (1982) SPACECRAFT for multi-floor layout systems. Int J Prod Res 36(1):95–110
planning. Manage Sci 28(4):407–417 64. Mak KL, Wong YS, Chan FTS (1998) A genetic algorithm for
37. Tompkins JA, Reed Jr R (1976) An applied model for the facility layout problems. Comput Intg Manuf 11:113–127
facilities design problem. Int J Prod Res 14(5):583–595 65. McKendall AR, Noble JS, Klein CM (1999) Facility layout of
38. Banerjee P, Montreuil B, Moodie CL, Kashyap RL (1992) A irregular-shaped departments using a nested approach. Int J
modeling of interactive facilities layout designer reasoning Prod Res 37(13):2895–2914
using qualitative patterns. Int J Prod Res 30(3):433–453 66. Kochhar JS, Heragu SS (1999) Facility layout design in a
39. Tam KY (1992) Genetic algorithms, function optimization, and changing environment. Int J Prod Res 37(11):2429–2446
facility layout design. Eur J Oper Res 63:322–346 67. Gau KY, Meller RD (1999) An iterative facility layout
40. Foulds LR, Robinson DF (1978) Graph theoretic heuristics for algorithm. Int J Prod Res 37(16):3739–3758
the plant layout problem. Int J Prod Res 16(1):27–37 68. Al-Hakim LA (2000) On solving facility layout problems using
41. Balakrishnan J, Cheng CH, Wong KF (2003) FACOPT: a user genetic algorithms. Int J Prod Res 38(11):2573–2582
friendly facility layout optimization system. Comput Oper Res 69. Ahuja RK, Orlin JB, Tiwari A (2000) A greedy genetic algo-
30(11):1625–1641 rithm for the quadratic assignment problem. Comput Oper Res
42. Burkard RE, Rend F (1984) A thermodynamically motivated 27:917–934
simulation procedure for combinatorial optimization problems. 70. Wu Y, Appleton E (2002) The optimization of block layout and
Eur J Oper Res 17:169–174 aisle structure by a genetic algorithm. Comput Ind Eng 41:371–
43. Tavakkoli-Moghaddain R, Shanyan E (1998) Facilities layout 387
design by genetic algorithms. Comput Ind Eng 35(3/4):527– 71. Lee KY, Han SN, Roh M (2003) An improved genetic algo-
530 rithm for facility layout problems having inner structure walls
44. Helm SA, Hadley SW (2000) Tabu search based heuristics for and passages. Comput Oper Res 30:117–138
multi floor facility layout. Int J Prod Res 38(2):365–383 72. Tsuchiya K, Bharitkar S, Takefuji Y (1996) A neural network
45. Talbi EG, Roux O, Fonlupt C, Robillard D (2001) Parallel ant approach to facility layout problems. Eur J Oper Res 89:556–
colonies for quadratic assignment pronlem. Future Generation 563
Comput Syst 17:441–449 73. Malakooti B, Tsurushima A (1989) An expert system using
46. Kirkpatrick S, Gelatt Jr CD, Vecchi MP (1983) Optimisation by priorities for solving multiple-criteria facility layout problems.
simulated annealing. Sci 220(4598):671–680 Int J Prod Res 27(5):793–808
47. Wilhelm MR, Ward TL (1987) Solving quadratic assignment 74. Abdou G, Dutta SP (1990) An integrated approach to facilities
problems by simulated annealing. IIE Trans 19:107–119 layout using expert systems. Int J Prod Res 28(4):685–708
48. Kaku BK, Thompson GL (1986) An exact algorithm for the 75. Heragu SS, Kusiak A (1990) Machine layout: an optimization
general quadratic assignment problem. Eur J Oper Res 23 and knowledge based approach. Int J Prod Res 28(4):615–635
(3):382–390 76. Sirinaovakul B, Thajchayapong P (1994) A knowledge base to
49. Connolly DT (1990) An improved annealing scheme for the assist a heuristic search approach to facility layout. Int J Prod
QAP. Eur J Oper Res 46:93–100 Res 32(1):141–160
50. Heragu SS, Alfa AS (1992) Experimental analysis of simulated 77. Kumar SRT, Kashyap RL, Moodie CL (1988) Application of
annealing based algorithms for the layout problem. Eur J Oper expert systems and pattern recognition methodologies to
Res 57:190–223 facilities layout planning. Int J Prod Res 26(5):905–930
51. Kouvelis P, Kuruwarwala AA, Gutierrez GJ (1992) Algorithms 78. Dutta KN, Sahu S (1982) A multigoal heuristic for facilities
for robust single and multiple period layout planning for design problems: MUGHAL. Int J Prod Res 20(2):147–154
manufacturing systems. Eur J Oper Res 63:287–303 79. Murtagh BA, Jefferson TR, Sornprasit V (1982) A heuristic
52. Jajodia S, Minis I, Harhalakis G, Proth J M (1992) CLASS: procedure for solving the quadratic assignment problem. Eur J
computerized layout solutions using simulated annealing. Int J Oper Res 9:71–76
Prod Res 30(1):95–108 80. Foulds LR (1983) Techniques for facilities layout: deciding
53. Shang JS (1993) Multi-criteria facility layout problem: an in- which pairs of activities should be adjacent. Manege Sci 9
tegrated approach. Eur J Oper Res 66:291–304 (12):1414–1416
54. Souilah A (1995) Theory and methodology: simulated anneal- 81. Herroelen W, Vangils A (1985) On the use of flow dominance
ing for manufacturing systems layout design. Eur J Oper Res in complexity measure for facility layout problems. Int J Prod
82:592–614 Res 23(1):97–108
55. Peng T, Huanchen W, Dongme Z (1996) Simulated annealing 82. Fortenberry JC, Cox JF (1985) Multiple criteria approach to the
for the quadratic assignment problem: a further study. Comput facilities layout problem. Int J Prod Res 23(4):773–782
Ind Eng 31(3/4):925–928 83. Hammouche A, Webster D (1985) Evaluation of an application
56. Meller RD, Bozer YA (1996) A new simulated annealing of graph theory to the layout problem. Int J Prod Res 23
algorithm for the facility layout problem. Int J Prod Res (5):987–1000
34:1675–1692 84. Foulds LR, Giffin JW (1985) A graph-theoretic heuristic for
57. Azadivar F, Wang JJ (2000) Facility layout optimization using minimizing total transportation cost in facilities layout. Int J
simulation and genetic algorithms. Int J Prod Res 38(17):4369– Prod Res 23:1247–1257
4383 85. Green LH, Al-Hakim LA (1985) A heuristic for facility layout
58. Baykasoglu A, Gindy NNZ (2001) A simulated annealing planning. Omega 13:469–474
algorithm for dynamic plant layout. Comput Oper Res 28:1403– 86. Rosenblatt MJ (1986) The dynamics of plant layout. Manege
1426 Sci 32(1):76–86
59. Misevicius A (2003) A modified simulated annealing algorithm 87. Foulds LR, Giffin JW, Cameron DC (1986) Drawing a block
for quadratic assignment problem. Informatica 14(4):497–514 plan with graph theory and a microcomputer. Comput Ind Eng
60. Banerjee P, Zhou Y (1995) Facility layout design optimization 10:109–116
with single loop material flow path configuration. Int J Prod 88. Grobelny J (1987) On one possible ‘fuzzy’ approach to
Res 33(1):183–203 facilities layout problems. Int J Prod Res 25:1123–1141
61. Kochhar JS, Heragu SS (1998) MULTI-HOPE: a tool for 89. Evan GW, Wilhelm MR, Karwowski W (1987) A layout design
multiple floor layout problems. Int J Prod Res 38(12):3421– heuristic employing the theory of fuzzy sets. Int J Prod Res 25
3435 (10):1431–1450
62. Islier AA (1998) A genetic algorithm approach for multiple 90. Urban TL (1987) A multiple criteria model for the facilities
criteria facility layout design. Int J Prod Res 36(6):1549–1569 layout problem. Int J Prod Res 25(12):1805–1812
 433
91. Rosenblatt MJ, Lee HL (1987) A robustness approach to 115. Das S (1993) A facility layout method for flexible manufactur-
facilities design. Int J Prod Res 25:479–486 ing systems. Int J Prod Res 31(2):279–297
92. Jacobs FR (1987) A layout planning system with multiple 116. Raoot AD, Rakshit A (1991) A fuzzy approach to facilities
criteria and a variable domain representation. Manage Sci layout planning. Int J Prod Res 29(4):835–857
33:1020–1034 117. Raoot AD, Rakshit A (1994) A fuzzy heuristic for the
93. Grobelny J (1988) The ‘linguistic pattern’ method for a quadratic assignment formulation to the facility layout
workstation layout analysis. Int J Prod Res 26:1779–1798 problem. Int J Prod Res 32(3):563–581
94. Kaku BK, Thompson GL, Baybars I (1988) A heuristic 118. Urban TL (1993) A heuristic for the dynamic facility layout
method for the multi-story layout problem. Eur J Oper Res problem. IIE Trans 25(4):57–63
37:384–397 119. Montreuil B, Venkatadri U, Ratliff HD (1993) Generating a
95. Smith JM, MacleodI R (1988) A relaxed assignment algorithm layout from a design skeleton. IIE Trans 25(1):3–15
for the quadratic assignment problem. INFORMS 26(3):170– 120. Boswell SG (1994) A reply to ‘a note on similarity of a new
190 greedy heuristic for facility layout by graph theory to an
96. Malakooti B (1989) Multiple objective facility layout: a heu- existing approach'. Int J Prod Res 32(1):235–240
ristic to generate efficient alternatives. Int J Prod Res 27(7): 121. Langevin A, Montreuil B, Riopel D (1994) Spine layout
1225–1238 design. Int J Prod Res 32(2):429–442
97. Heragu SS, Kusiak A (1988) Machine layout problems in 122. Tretheway SJ, Foote BL (1994) Automatic computation and
flexible manufacturing systems. Oper Res 36(2):258–268 drawing of facility layout with logical aisle structures. Int J
98. Houshyar A, McGinnis LF (1990) A heuristic for assigning Prod Res 32(7):1545–1555
facilities to locations to minimize WIP travel distance in a 123. White DJ (1996) A lagrangean relaxation approach for a
linear facility. Int J Prod Res 28(8):1485–1498 turbine design quadratic assignment problem. J Oper Res Soc
99. Al-Hakim LA (1991) Two graph theoretic procedures for an 47:766–775
improved solution to the facilities layout problem. Int J Prod 124. Badiru AB, Arif A (1996) FLEXPERT: facility layout expert
Res 29(8):1701–1718 system using fuzzy linguistic relationship codes. IIE Trans
100. Kaku BK, Thompson GL, Morton TE (1991) A hybrid heuristic 28:295–308
for the facilities layout problems. Comput Oper Res 18(3):241– 125. Chiang WC, Kouvelis P (1996) An improved tabu search
253 heuristic for solving facility layout design problems. Int J Prod
101. Hassan MMD, Hogg GL (1991) On constructing a block Res 34:2565–2586
layout by graph theory. Int J Prod Res 29(6):1263–1278 126. Urban TL (1998) Solution procedures for dynamic facility
102. Logendran R (1991) Impact of sequence of operations and layout problem. Annals Oper Res 76:323–342
layout of cells in cellular manufacturing. Int J Prod Res 29 127. Meller RD (1997) The multi-bay manufacturing facility layout
(2):375–390 problem. Int J Prod Res 35(5):1229–1237
103. Burkard RE, Kafish S, Rend F (1991) QAPLIB- a quadratic 128. Zetu D, Prashant B, Schneider P (1998) Data input model for
assignment problem library. Eur J Oper Res 55:115–119 virtual reality-aided facility layout. IIE Trans 30(7):597–620
104. Camp DJV, Carter MW, Vannelli A (1992) A nonlinear 129. Bozer YA, Meller RD (1997) A reexamination of distance-
optimization approach for solving facility layout problems. Eur based facility layout problem. IIE Trans 29(7):549–560
J Oper Res 57:174–189 130. Chen CW, Sha DY (1999) A design approach to the multi-
105. Leung J (1992) A graph theoretic heuristic for designing loop- objective facility layout problem. Int J Prod Res 37(5):1175–
layout manufacturing systems. Eur J Oper Res 57:243–252 1196
106. Kaku K, Rachamadugu R (1992) Layout design for flexible 131. Smith RP, Helm JA (1999) Virtual facility layout design: the
manufacturing systems. Eur J Oper Res 57:224–230 value of an iterative three-dimensional representation. Int J
107. Rosenblatt MJ, Golany B (1992) A distance assignment Prod Res 37(17):3941–3957
approach to the facility layout problem. Eur J Oper Res 132. Dweiri F (1999) Fuzzy development of crisp activity relation-
57:253–270 ship charts for facilities layout. Comput Ind Eng 36(1):1–16
108. Harmonosky CM, Tothero GK (1992) A multi-factor plant 133. Knowles JD, Corne DW (2002) Towards landscape analysis to
layout methodology. Int J Prod Res 30:1773–1789 inform the design of a hybrid local for the multi-objective
109. Askin RG, Mitwasi MG (1992) Integrating facility layout with quadratic assignment problem. Hybrid Intell Syst 271–279
process selection and capacity planning. Eur J Oper Res 134. Kim JY, Kim YD (2000) Layout planning for facilities with
57:162–173 fixed shapes and input and output points. Int J Prod Res 38
110. Balakrishnan J, Jacobs FR, Venkataramanan MA (1992) (18):4635–4653
Solutions for the constrained dynamic facility layout problem. 135. Al-Hakim LA (2001) A note on efficient facility layout
Eur J Oper Res 57:280–286 planning in a maximally planar graph model. Int J Prod Res 39
111. Al-Hakim LA (1992) A modified procedure for converting a (7):1549–1555
dual graph to a blok layout. Int J Prod Res 30(10):2467–2476 136. Wang S, Sarker BR (2002) Locating cells with bottleneck
112. Lacksonen TA, Enscore EE (1993) Quadratic assignment machines in cellular manufacturing systems. Int J Prod Res 40
algorithms for the dynamic layout problem. Int J Prod Res 31 (2):403–424
(3):503–517 137. Chan WM, Chan CY, Ip WH (2002) A heuristic algorithm for
113. White DJ (1993) A convex form of the quadratic assignment machine assignment in cellular layout. Comput Ind Eng
problem. Eur J Oper Res 65:407–416 44:49–73
114. Yaman R, Gethin DT, Clarke MJ (1993) An effective sorting 138. Diponegoro A, Sarker BR (2003) Machine assignment in a
method for facility layout construction. Int J Prod Res 31 nonlinear multi-product flowline. J Oper Res Soc 54(5):472–489
(2):413–427 139. Castillo I, Peters BA (2003) An extended distance based
facility layout problem. Int J Prod Res 41(11):2451–2479