Chapter 5
Extensions and Related Problems
In this chapter, we introduce the quadratic assignment problem, a well-known
special case of facility layout. We also briefly discuss the extensions of facility
layout to re-layout, multi-floor layout, and dynamic versions of facility layout.
5.1 Quadratic Assignment Problem
The quadratic assignment problem (QAP) is a combinatorial optimization problem
that dates back to 1957. It was developed as a mathematical model to assign
economic activities to locations in an optimal way. Since then, it has been used
in a wide variety of contexts, including facility layout.
To formulate facility layout as a QAP, we assume that we have n departments
to assign to n locations and that any department can be assigned to any location.
Because the locations are given and fixed, we also assume that the distance
between every pair of locations is known. Let d
pq denote the distance between
locations p and q, for 1 ≤ p, q ≤ n. Assuming that we are also given nonnegative pairwise connectivities c ij between departments i and j , then the cost of
simultaneously assigning department i to location p and department j to location q
is equal to c ij d
pq . Under these assumptions, the QAP seeks the permutation of the
departments that minimizes the total weighted distance travelled, and analogously
to formulation (2.6) for the SRFLP, it can be formulated as
min
π∈Π n
n
i=1
n
j =1
c ij d
π(i)π(j) ,
(5.1)
where Π n is the set of all permutations π of {1, 2, . . . , n} and π(i) is the location
assigned to department i by permutation π.
© Springer Nature Switzerland AG 2021
M. F. Anjos, M. V. C. Vieira, Facility Layout, EURO Advanced Tutorials
on Operational Research, https://doi.org/10.1007/978-3-030-70990-7_5
75
Extensions and Related Problems
In this chapter, we introduce the quadratic assignment problem, a well-known
special case of facility layout. We also briefly discuss the extensions of facility
layout to re-layout, multi-floor layout, and dynamic versions of facility layout.
5.1 Quadratic Assignment Problem
The quadratic assignment problem (QAP) is a combinatorial optimization problem
that dates back to 1957. It was developed as a mathematical model to assign
economic activities to locations in an optimal way. Since then, it has been used
in a wide variety of contexts, including facility layout.
To formulate facility layout as a QAP, we assume that we have n departments
to assign to n locations and that any department can be assigned to any location.
Because the locations are given and fixed, we also assume that the distance
between every pair of locations is known. Let d
pq denote the distance between
locations p and q, for 1 ≤ p, q ≤ n. Assuming that we are also given nonnegative pairwise connectivities c ij between departments i and j , then the cost of
simultaneously assigning department i to location p and department j to location q
is equal to c ij d
pq . Under these assumptions, the QAP seeks the permutation of the
departments that minimizes the total weighted distance travelled, and analogously
to formulation (2.6) for the SRFLP, it can be formulated as
min
π∈Π n
n
i=1
n
j =1
c ij d
π(i)π(j) ,
(5.1)
where Π n is the set of all permutations π of {1, 2, . . . , n} and π(i) is the location
assigned to department i by permutation π.
© Springer Nature Switzerland AG 2021
M. F. Anjos, M. V. C. Vieira, Facility Layout, EURO Advanced Tutorials
on Operational Research, https://doi.org/10.1007/978-3-030-70990-7_5
75