3.2 Multi-Row Facility Layout
41
binary variables to encode their relative positions:
α ij =
1 if i is placed to the left of j in the same row
0 otherwise,
β ij =
1 if i and j are placed in different rows and i is below j
0 otherwise.
Let d x
ij and d
y
ij represent the horizontal and vertical distances between i and j .
Using the above variable definitions, the formulation for the MRFLP is
minimize
1≤i c ij (d
x
ij + d
y
ij )
(3.36)
s.t. d
x
ij ≥ x i − x j , d
x
ij ≥ x j − x i , 1 ≤ i < j ≤ n
(3.37)
d
y
ij ≥ y i − y j , d
y
ij ≥ y j − y i , 1 ≤ i < j ≤ n
(3.38)
x j − x i ≥
1
2
(( i + j ) − L(1 − α ij ), 1 ≤ i < j ≤ n,
(3.39)
x i − x j ≥
1
2
(( i + j ) − L(1 − α ji ), 1 ≤ i < j ≤ n,
(3.40)
y j − y i ≥ d
row
− md
row (1 − β ij ), 1 ≤ i < j ≤ n,
(3.41)
y i − y j ≥ d
row
− md
row (1 − β ji ), 1 ≤ i < j ≤ n,
(3.42)
y i − y j ≤ (1 − α ij − α ji )(m − 1)d
row , 1 ≤ i < j ≤ n,
(3.43)
y j − y i ≤ (1 − α ij − α ji )(m − 1)d
row , 1 ≤ i < j ≤ n,
(3.44)
0 ≤ y i ≤ (m − 1)d
row , 1 ≤ i ≤ n,
(3.45)
1
2
i ≤ x i ≤ L −
1
2
i , 1 ≤ i ≤ n,
(3.46)
α ij + α ji + β ij + β ji = 1, 1 ≤ i < j ≤ n,
(3.47)
α ij + α jk ≤ 1 + α ik , 1 ≤ i, j, k ≤ n, i < j, k = i, j
(3.48)
β ij + β jk ≤ 1 + β ik , 1 ≤ i, j, k ≤ n, i < j, k = i, j
(3.49)
α ij , β ij ∈ {0, 1}, 1 ≤ i, j ≤ n,
(3.50)
where d row is the row width (common to all rows), and as before, n is the number
of departments, m is the maximum number of rows allowed for the layout, i is the
length of department i, and L =
n
i=1 i .
Constraints (3.37)–(3.38) establish the horizontal and vertical distances between
departments using the first linearization approach described in Sect. 2.3.1. Constraints (3.39)–(3.40) prevent any two departments in the same row from overlapping. Constraints (3.41)–(3.42) avoid the overlapping of rows and simultaneously