64
4 Layout of a Single Floor
Fig. 4.4 Values of (α ij , β ij )
for a sequence-pair and
possible locations for j with
respect to i
i
(0, 0)
i
(0, 1)
i
(1, 0)
i
(1, 1)
The sequence-pair-based MISOCO formulation for the UA-FLP is as follows:
minimize
1≤i c ij (d
x
ij + d
y
ij )
s.t. (4.13) − (4.20)
α ij + α ji = 1, 1 ≤ i < j ≤ n
β ij + β ji = 1, 1 ≤ i < j ≤ n
(4.25)
α ik + α kj − α ij ≤ 1, 1 ≤ i < j ≤ n
β ik + β kj − β ij ≤ 1, 1 ≤ i < j ≤ n
(4.26)
x i +
1
2 w i ≤ x j −
1
2 w j + w F (2 − α ij − β ij ), 1 ≤ i, j ≤ n, i = j
y i +
1
2 h i ≤ y j −
1
2 h j + h F (1 + α ij − β ij ), 1 ≤ i, j ≤ n, i = j
(4.27)
α ij , β ij ∈ {0, 1}, 1 ≤ i, j ≤ n.
(4.28)
Constraints (4.25) ensure that every department appears exactly once in each
sequence, and constraints (4.26) are transitivity constraints that must hold for
each of the two sequences. Together these constraints ensure that the binary
variables represent valid sequences. Constraints (4.27) express the nonoverlapping
requirement in terms of the binary variables (and hence of the sequence-pair).