76
5 Extensions and Related Problems
The QAP can be expressed as a quadratic binary optimization problem. We define
the binary variables
x ip =
1 if department i is assigned to location p,
0 otherwise.
Using these variables, the formulation of the QAP is as follows:
minimize
n
i=1
n
j =1
n
p=1
n
q=1
c ij d
pq x ip x jq
(5.2)
s.t.
n
p=1
x ip = 1, 1 ≤ i ≤ n
(5.3)
n
i=1
x ip = 1, 1 ≤ p ≤ n
(5.4)
x ip ∈ {0, 1}, 1 ≤ i, p ≤ n.
(5.5)
In the objective function, if department i is assigned to location p and department
j is assigned to location q, then the product of c ij and d
pq is counted towards the
total cost of the layout.
Constraints (5.3) ensure that each department is assigned to exactly one location,
and constraints (5.4) ensure that precisely one department is assigned to each
location. Constraints (5.3) and (5.4) together define an assignment of departments
to locations. The assignment problem (5.2)–(5.5) is called quadratic because the
objective function is quadratic in the variables x.
The QAP is well known for being computationally demanding. In general, it is
challenging to solve a QAP with more than 30 departments to global optimality.
5.2 Re-Layout Problems
Re-layout refers to the process of making changes to an existing facility layout by
relocating a certain number of departments to new locations, with possible changes
to their area requirements, their aspect ratio requirements, or the bounds on their
dimensions. For example, in the manufacturing context, the purpose of re-layout is
to improve the workflow and, hence, the productivity of the facility, after changes
to the product mix and/or the manufacturing processes themselves. Re-layout for
a single floor has received the most attention, but re-layout applies to all types of
layout problems.
One of the key features of re-layout is that it is constrained by some of the
features of the existing layout, in particular the fact that certain departments (often
5 Extensions and Related Problems
The QAP can be expressed as a quadratic binary optimization problem. We define
the binary variables
x ip =
1 if department i is assigned to location p,
0 otherwise.
Using these variables, the formulation of the QAP is as follows:
minimize
n
i=1
n
j =1
n
p=1
n
q=1
c ij d
pq x ip x jq
(5.2)
s.t.
n
p=1
x ip = 1, 1 ≤ i ≤ n
(5.3)
n
i=1
x ip = 1, 1 ≤ p ≤ n
(5.4)
x ip ∈ {0, 1}, 1 ≤ i, p ≤ n.
(5.5)
In the objective function, if department i is assigned to location p and department
j is assigned to location q, then the product of c ij and d
pq is counted towards the
total cost of the layout.
Constraints (5.3) ensure that each department is assigned to exactly one location,
and constraints (5.4) ensure that precisely one department is assigned to each
location. Constraints (5.3) and (5.4) together define an assignment of departments
to locations. The assignment problem (5.2)–(5.5) is called quadratic because the
objective function is quadratic in the variables x.
The QAP is well known for being computationally demanding. In general, it is
challenging to solve a QAP with more than 30 departments to global optimality.
5.2 Re-Layout Problems
Re-layout refers to the process of making changes to an existing facility layout by
relocating a certain number of departments to new locations, with possible changes
to their area requirements, their aspect ratio requirements, or the bounds on their
dimensions. For example, in the manufacturing context, the purpose of re-layout is
to improve the workflow and, hence, the productivity of the facility, after changes
to the product mix and/or the manufacturing processes themselves. Re-layout for
a single floor has received the most attention, but re-layout applies to all types of
layout problems.
One of the key features of re-layout is that it is constrained by some of the
features of the existing layout, in particular the fact that certain departments (often