5.3 Layout on Several Floors
81
to each floor. The QSAP formulation is as follows:
minimize
n
i=1
n
j =i+1
p
k=1
p
l=1
c ij D kl z ik z jl
(5.26)
s.t.
p
k=1
z ik = 1, 1 ≤ i ≤ n
(5.27)
n
i=1
A i z ik ≤ w F h F , 1 ≤ k ≤ p
(5.28)
z ik ∈ {0, 1}, 1 ≤ i ≤ n, 1 ≤ k ≤ p.
(5.29)
The variable z ik equals 1 if department i is assigned to floor k, and 0 otherwise. Here
D kl is not a variable, but a parameter prespecified via D kl = δ|k − l|. The distance
between departments i and j is given by D kl z ik z jl . This quantity is set to D kl if i
and j are assigned to floors k and l, respectively, and zero otherwise. Constraints
(5.27) assign each department to exactly one floor. Constraints (5.28) ensure that the
departments assigned to each floor fit into that floor.
One limitation of this formulation is that the distance is assumed to be measured
vertically through floors, which may be problematic in practical applications. An
alternative is a MILO formulation. Let the variables d v
ij represent the vertical
distance between each pair i, j of departments, and consider the following MILO
model:
minimize
1≤i c ij d
v
ij
(5.30)
s.t.
p
k=1
z ik = 1, 1 ≤ i ≤ n
(5.31)
d
v
ij ≥ δ
p
k=1
k(z ik − z jk ), 1 ≤ i < j ≤ n
(5.32)
d
v
ij ≥ δ
p
k=1
k(z jk − z ik ), 1 ≤ i < j ≤ n
(5.33)
n
i=1
A i z ik ≤ w F h F , 1 ≤ k ≤ p
(5.34)
z ik ∈ {0, 1}, 1 ≤ i ≤ n, 1 ≤ k ≤ p.
(5.35)