3.3 Fixed-Row Multi-Row Facility Layout
45
The MILO model is
minimize
i,j ∈N
i
(3.51)
s.t. β ij k + β ikj + β jki = 1, r ∈ R, i, j, k ∈ ˜
N r , i < j < k,
(3.52)
β ij h + β ikh − β jkh ≥ 0, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.53)
β ij h − β ikh + β jkh ≥ 0, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.54)
− β ij h + β ikh + β jkh ≥ 0, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.55)
β ij h + β ikh + β jkh ≤ 2, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.56)
β n+1,n+2,i = 1, i ∈ N,
(3.57)
β ij,n+1 = 0, r ∈ R, i, j, ∈ N r ∪ {n + 2}, i < j,
(3.58)
β ij,n+2 = 0, r ∈ R, i, j, ∈ N r ∪ {n + 1}, i < j,
(3.59)
β j,n+1,i = β i,n+2,j , r ∈ R, i, j ∈ N r , i = j,
(3.60)
d j,n+1 − d i,n+1 ≥
i + j
2
+ L (β j,n+1,i − 1), r ∈ R, i, j ∈ N r , i = j,
(3.61)
d ij ≥ d i,n+1 − d j,n+1 , i,j ∈ N, i < j,
(3.62)
d ij ≥ d j,n+1 − d i,n+1 , i,j ∈ N, i < j,
(3.63)
d i,n+1 ≥ i /2, i ∈ N,
(3.64)
β ij k ∈ {0, 1}, r ∈ R, i, j, k ∈ N r ∪ {n + 1, n + 2}, i < j,
(3.65)
where L =
n
i=1 i .
Constraints (3.52)–(3.56) are exactly the same as constraints (2.27)–(2.31) in
Sect. 2.4, and we refer the reader to that section for an explanation of their meaning.
Constraints (3.57)–(3.60) ensure that in each row, all the departments lie between
the dummy departments n+1 and n+2. Constraints (3.57) say that every department
must be placed between the dummy departments n + 1 and n + 2. Constraints (3.58)
and (3.59) prevent the dummy departments from being placed between any other
two departments. Constraints (3.60) say that i is between j and n + 1 if and only if
j is between i and n + 2.
Constraints (3.61) give the distance between each pair of departments in the same
row: if i is between j and n + 1, then β j,n+1,i = 1, which implies d j,n+1 − d i,n+1 ≥
i + j . These constraints prevent any two departments, placed in the same row,
from overlapping.
45
The MILO model is
minimize
i,j ∈N
i
(3.51)
s.t. β ij k + β ikj + β jki = 1, r ∈ R, i, j, k ∈ ˜
N r , i < j < k,
(3.52)
β ij h + β ikh − β jkh ≥ 0, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.53)
β ij h − β ikh + β jkh ≥ 0, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.54)
− β ij h + β ikh + β jkh ≥ 0, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.55)
β ij h + β ikh + β jkh ≤ 2, r ∈ R, i, j, k, h ∈ ˜
N r , h = i, j, k, i < j < k,
(3.56)
β n+1,n+2,i = 1, i ∈ N,
(3.57)
β ij,n+1 = 0, r ∈ R, i, j, ∈ N r ∪ {n + 2}, i < j,
(3.58)
β ij,n+2 = 0, r ∈ R, i, j, ∈ N r ∪ {n + 1}, i < j,
(3.59)
β j,n+1,i = β i,n+2,j , r ∈ R, i, j ∈ N r , i = j,
(3.60)
d j,n+1 − d i,n+1 ≥
i + j
2
+ L (β j,n+1,i − 1), r ∈ R, i, j ∈ N r , i = j,
(3.61)
d ij ≥ d i,n+1 − d j,n+1 , i,j ∈ N, i < j,
(3.62)
d ij ≥ d j,n+1 − d i,n+1 , i,j ∈ N, i < j,
(3.63)
d i,n+1 ≥ i /2, i ∈ N,
(3.64)
β ij k ∈ {0, 1}, r ∈ R, i, j, k ∈ N r ∪ {n + 1, n + 2}, i < j,
(3.65)
where L =
n
i=1 i .
Constraints (3.52)–(3.56) are exactly the same as constraints (2.27)–(2.31) in
Sect. 2.4, and we refer the reader to that section for an explanation of their meaning.
Constraints (3.57)–(3.60) ensure that in each row, all the departments lie between
the dummy departments n+1 and n+2. Constraints (3.57) say that every department
must be placed between the dummy departments n + 1 and n + 2. Constraints (3.58)
and (3.59) prevent the dummy departments from being placed between any other
two departments. Constraints (3.60) say that i is between j and n + 1 if and only if
j is between i and n + 2.
Constraints (3.61) give the distance between each pair of departments in the same
row: if i is between j and n + 1, then β j,n+1,i = 1, which implies d j,n+1 − d i,n+1 ≥
i + j . These constraints prevent any two departments, placed in the same row,
from overlapping.