52
3 Layout on Several Rows
3.5.3 Parallel Row Ordering Problem
The parallel row ordering problem (PROP) is a version of the CAP in which, in
addition, the assignment of departments to rows is given. Let m be the number of
departments and N 1 and N 2 be a partition of the set of departments {1, 2, . . . , m},
i.e., N = N 1 ∪ N 2 and N 1 ∩ N 2 = ∅ so that the sets N 1 and N 2 represent an
assignment of the departments to the two rows. To obtain a formulation for the
PROP, it suffices to add the following constraints to the CAP (3.81)–(3.86):
α ij = α ji = 0, i ∈ N 1 , j ∈ N 2
α ij + α ji = 1, i,j ∈ N 1 or i, j ∈ N 2 .
3.5.4 k-Parallel Row Ordering Problem
The k-parallel row ordering problem (k-PROP) is the generalization of the PROP
(where k = 2) to three or more rows. As for the PROP, the assignment of
departments to rows is given, and solutions to the k-PROP must satisfy the
conditions of the k-CAP (no space between adjacent departments; leftmost point
of every row at origin).
The MILO formulation described here is a modification of the model presented
in Sect. 3.3 for the FR-MRFLP. We use the notation of Sect. 3.3, so that R =
{1, 2, . . . , m} denotes the set of rows and N r the set of departments assigned to
row r ∈ R. We also use the dummy departments n + 1 and n + 2 to be placed at the
left and right boundaries, respectively, of the layout, and n+1 = n+2 = 0, as well
as c ij = 0 if i ∈ {n + 1, n + 2} or j ∈ {n + 1, n + 2}. Also as before, we extend the
set N r to include the dummy departments: ˜
N r = N r ∪ {n + 1, n + 2}.
The modifications made here to the MILO model from Sect. 3.3 guarantee the
two k-CAP conditions. Specifically, we change the constraints defining the distance
variables. The new model is
minimize
i,j ∈N
i
(3.89)
s.t. (3.52) − (3.60), (3.65)
d ij =
k∈N r
k =i,j
k β ij k +
i + j
2
, r ∈ R, i, j ∈ N r ∪ {n + 1}, i < j,
(3.90)
d ij ≥ 0, i,j ∈ N ∪ {n + 1}, i < j.
(3.91)
3 Layout on Several Rows
3.5.3 Parallel Row Ordering Problem
The parallel row ordering problem (PROP) is a version of the CAP in which, in
addition, the assignment of departments to rows is given. Let m be the number of
departments and N 1 and N 2 be a partition of the set of departments {1, 2, . . . , m},
i.e., N = N 1 ∪ N 2 and N 1 ∩ N 2 = ∅ so that the sets N 1 and N 2 represent an
assignment of the departments to the two rows. To obtain a formulation for the
PROP, it suffices to add the following constraints to the CAP (3.81)–(3.86):
α ij = α ji = 0, i ∈ N 1 , j ∈ N 2
α ij + α ji = 1, i,j ∈ N 1 or i, j ∈ N 2 .
3.5.4 k-Parallel Row Ordering Problem
The k-parallel row ordering problem (k-PROP) is the generalization of the PROP
(where k = 2) to three or more rows. As for the PROP, the assignment of
departments to rows is given, and solutions to the k-PROP must satisfy the
conditions of the k-CAP (no space between adjacent departments; leftmost point
of every row at origin).
The MILO formulation described here is a modification of the model presented
in Sect. 3.3 for the FR-MRFLP. We use the notation of Sect. 3.3, so that R =
{1, 2, . . . , m} denotes the set of rows and N r the set of departments assigned to
row r ∈ R. We also use the dummy departments n + 1 and n + 2 to be placed at the
left and right boundaries, respectively, of the layout, and n+1 = n+2 = 0, as well
as c ij = 0 if i ∈ {n + 1, n + 2} or j ∈ {n + 1, n + 2}. Also as before, we extend the
set N r to include the dummy departments: ˜
N r = N r ∪ {n + 1, n + 2}.
The modifications made here to the MILO model from Sect. 3.3 guarantee the
two k-CAP conditions. Specifically, we change the constraints defining the distance
variables. The new model is
minimize
i,j ∈N
i
(3.89)
s.t. (3.52) − (3.60), (3.65)
d ij =
k∈N r
k =i,j
k β ij k +
i + j
2
, r ∈ R, i, j ∈ N r ∪ {n + 1}, i < j,
(3.90)
d ij ≥ 0, i,j ∈ N ∪ {n + 1}, i < j.
(3.91)