3.4 Multi-Row Facility Layout with Departments of Equal Length
49
ξ jk + β ikj + β ij k + β jki ≤ 1, i < k < j,
(3.76)
ξ ij + ξ jk − ξ ik ≤ 1, i < j, k = i, j,
(3.77)
j =i
ξ ij = m − 1, 1 ≤ i ≤ n,
(3.78)
n
i=1
n
k=i+1
n
j =1
j =i,k
β ij k = m
3
C
3
,
(3.79)
β ij k , ξ ij ∈ {0, 1}, 1 ≤ i < j ≤ n, k = i, j
(3.80)
where, as above, C is the number of columns fixed according to Theorem 3.3, and
m is the number of rows.
The objective function (3.66) expresses the distance between i and j by counting
the number of departments between i and j . Because it counts all the departments
between i and j over all rows, this total must be divided by m. Furthermore, if i and
j are not in the same column (ξ ij = 0), then it increases the distance by 1 (which is
half of the sum of the lengths of i and j ).
Constraints (3.67) ensure that, for every choice of three distinct departments i,
j , and k, department h cannot simultaneously lie between i and j , between i and k,
and between j and k.
Constraints (3.68)–(3.73) require a form of consistency, namely that for every
choice of three distinct departments i, j , and k, if department h lies between
departments i and j , then also h lies between i and k, or between j and k, or in
the same column as k (which also implies that k lies between i and j ).
Constraints (3.74)–(3.76) state that if two departments out of three are in the
same column, then none of them is between the other two. Simultaneously, if one of
the three departments is between the other two, then no two of them are in the same
column. Constraints (3.77) are transitivity constraints. Constraints (3.78) say that
each department shares its column with m − 1 other departments. Finally, constraint
(3.79) counts the number of betweenness variables that must equal 1. The idea is
that for each of the
C
3
subsets of three columns, there are m 3 ways to choose one
department from each column, and these are the only choices for which the variable
β ij k equals 1.
This formulation can be specialized for the double-row case. For the objective
function, we set m = 2. Constraints (3.67)–(3.73) are still valid, and constraints
(3.74)–(3.76) can be strengthened to
ξ ij + ξ ik + ξ jk + β ij k + β ikj + β jki = 1, i < k < j.
Constraints (3.77) are not changed, and for constraints (3.78) and (3.79), we set
m = 2.
49
ξ jk + β ikj + β ij k + β jki ≤ 1, i < k < j,
(3.76)
ξ ij + ξ jk − ξ ik ≤ 1, i < j, k = i, j,
(3.77)
j =i
ξ ij = m − 1, 1 ≤ i ≤ n,
(3.78)
n
i=1
n
k=i+1
n
j =1
j =i,k
β ij k = m
3
C
3
,
(3.79)
β ij k , ξ ij ∈ {0, 1}, 1 ≤ i < j ≤ n, k = i, j
(3.80)
where, as above, C is the number of columns fixed according to Theorem 3.3, and
m is the number of rows.
The objective function (3.66) expresses the distance between i and j by counting
the number of departments between i and j . Because it counts all the departments
between i and j over all rows, this total must be divided by m. Furthermore, if i and
j are not in the same column (ξ ij = 0), then it increases the distance by 1 (which is
half of the sum of the lengths of i and j ).
Constraints (3.67) ensure that, for every choice of three distinct departments i,
j , and k, department h cannot simultaneously lie between i and j , between i and k,
and between j and k.
Constraints (3.68)–(3.73) require a form of consistency, namely that for every
choice of three distinct departments i, j , and k, if department h lies between
departments i and j , then also h lies between i and k, or between j and k, or in
the same column as k (which also implies that k lies between i and j ).
Constraints (3.74)–(3.76) state that if two departments out of three are in the
same column, then none of them is between the other two. Simultaneously, if one of
the three departments is between the other two, then no two of them are in the same
column. Constraints (3.77) are transitivity constraints. Constraints (3.78) say that
each department shares its column with m − 1 other departments. Finally, constraint
(3.79) counts the number of betweenness variables that must equal 1. The idea is
that for each of the
C
3
subsets of three columns, there are m 3 ways to choose one
department from each column, and these are the only choices for which the variable
β ij k equals 1.
This formulation can be specialized for the double-row case. For the objective
function, we set m = 2. Constraints (3.67)–(3.73) are still valid, and constraints
(3.74)–(3.76) can be strengthened to
ξ ij + ξ ik + ξ jk + β ij k + β ikj + β jki = 1, i < k < j.
Constraints (3.77) are not changed, and for constraints (3.78) and (3.79), we set
m = 2.