36
3 Layout on Several Rows
Note that if all three terms are equal to 1, then this inequality requires (at least) one
of the other terms to be equal to 1 as well, but this contradicts (3.1).
Fourth, we require that for every triple i, j, k of departments, at least two must
be in the same row. We model this via the constraints
α ij + α ik + α jk + α ji + α ki + α kj ≥ 1, {i, j, k} ⊂ {1, . . . , n}.
(3.4)
These constraints ensure that no more than two rows are used, as required by the
DRFLP.
We also introduce the continuous variables x i , 1 ≤ i ≤ n, and d ij , 1 ≤ i < j ≤
n, with x i representing the position of the centre of department i along the corridor
and d ij representing the distance between the centres of i and j measured along the
corridor. These quantities are the same as those in Chap. 2 for the SRFLP.
Using the variables and constraints described above, we can write an initial
mixed-integer linear formulation of the DRFLP as follows:
minimize
n−1
i=1
n
j =i+1
c ij d ij
(3.5)
s.t. d ij ≥ x i − x j , d ij ≥ x j − x i , 1 ≤ i < j ≤ n,
(3.6)
x i +
i + j
2
≤ x j + L(1 − α ij ), 1 ≤ i = j ≤ n,
(3.7)
d ij −
i + j
2
α ij −
i + j
2
α ji ≥ 0, 1 ≤ i < j ≤ n,
(3.8)
(3.1), (3.2), (3.3), (3.4),
α ij ∈ {0, 1}, 1 ≤ i = j ≤ n,
(3.9)
i
2
≤ x i ≤ L −
i
2
, 1 ≤ i ≤ n,
(3.10)
where L =
n
i=1 i . In this formulation, constraints (3.6) give the centre-tocentre distance between each pair of departments using the same approach as for
the SRFLP. Also similarly to the SRFLP, constraints (3.7) ensure that departments
assigned to the same row do not overlap. Constraints (3.8) ensure that if department
i is placed in the same row as department j , then the distance between their centres
is at least (( i + j )/2. Constraints (3.9) require the α ij variables to be binary, and
constraints (3.10) are the same bounds on the x variables as those used for the
SRFLP.