3.1 Double-Row Facility Layout
35
centres with respect to a fixed origin. Without loss of generality, we place the
corridor along the x-axis, with the origin at the left end of the corridor.
3.1.1 Initial Mixed-Integer Linear Optimization Model
We consider again the binary variables α ij , 1 ≤ i, j ≤ n, used in Chap. 2, but
we change their definition. Specifically, we extend them to represent not only
the relative position of departments i and j but also whether or not these two
departments are in the same row. The definition of the α ij is therefore as follows:
α ij =
⎧
⎨
⎩
1, if department i is to the left of department j
and both i and j are in the same row;
0, otherwise.
Note that α ij = 0 whenever i and j are not in the same row and also when they are
in the same row but i is to the right of j .
We naturally need constraints to ensure that the values assigned to the variables
α ij are consistent. The first two sets of constraints discussed below are analogous to
the models for single row, and the third and fourth cover situations that cannot occur
in the SRFLP. First, we cannot simultaneously have i to the left of j and j to the
left of i (whether or not they are in the same row). Hence, we have the constraints
α ij + α ji ≤ 1, 1 ≤ i < j ≤ n.
(3.1)
Second, we need transitivity constraints with respect to row assignments. Specifically, we need to ensure that if departments i and k are in the same row and k and j
are in the same row, then i and j are also in the same row. We model this transitivity
requirement via the constraints
α ik + α ki + α jk + α kj − α ij − α ji ≤ 1, 1 ≤ i, j, k ≤ n, i < j, k = i, j. (3.2)
These constraints work as follows. If i and j are in the same row, then α ik +α ki = 1.
Similarly, if k and j are in the same row, then α jk + α kj = 1. Whenever both of
these hold, constraint (3.2) takes the form
1 ≥ α ik + α ki + α jk + α kj − α ij − α ji = 1 + 1 − (α ij + α ji ),
which implies that α ij + α ji ≥ 1 must hold, i.e., i and j must be in the same row.
Third, we need constraints to prevent the (impossible) situation where k is to the
left of j , j is to the left of i, and i is to the left of k. These so-called three-cycle
constraints are as follows:
α ik + α ji + α kj − α ki − α ij − α jk ≤ 1, 1 ≤ i, j, k ≤ n, i, k < j, k = i.
(3.3)
35
centres with respect to a fixed origin. Without loss of generality, we place the
corridor along the x-axis, with the origin at the left end of the corridor.
3.1.1 Initial Mixed-Integer Linear Optimization Model
We consider again the binary variables α ij , 1 ≤ i, j ≤ n, used in Chap. 2, but
we change their definition. Specifically, we extend them to represent not only
the relative position of departments i and j but also whether or not these two
departments are in the same row. The definition of the α ij is therefore as follows:
α ij =
⎧
⎨
⎩
1, if department i is to the left of department j
and both i and j are in the same row;
0, otherwise.
Note that α ij = 0 whenever i and j are not in the same row and also when they are
in the same row but i is to the right of j .
We naturally need constraints to ensure that the values assigned to the variables
α ij are consistent. The first two sets of constraints discussed below are analogous to
the models for single row, and the third and fourth cover situations that cannot occur
in the SRFLP. First, we cannot simultaneously have i to the left of j and j to the
left of i (whether or not they are in the same row). Hence, we have the constraints
α ij + α ji ≤ 1, 1 ≤ i < j ≤ n.
(3.1)
Second, we need transitivity constraints with respect to row assignments. Specifically, we need to ensure that if departments i and k are in the same row and k and j
are in the same row, then i and j are also in the same row. We model this transitivity
requirement via the constraints
α ik + α ki + α jk + α kj − α ij − α ji ≤ 1, 1 ≤ i, j, k ≤ n, i < j, k = i, j. (3.2)
These constraints work as follows. If i and j are in the same row, then α ik +α ki = 1.
Similarly, if k and j are in the same row, then α jk + α kj = 1. Whenever both of
these hold, constraint (3.2) takes the form
1 ≥ α ik + α ki + α jk + α kj − α ij − α ji = 1 + 1 − (α ij + α ji ),
which implies that α ij + α ji ≥ 1 must hold, i.e., i and j must be in the same row.
Third, we need constraints to prevent the (impossible) situation where k is to the
left of j , j is to the left of i, and i is to the left of k. These so-called three-cycle
constraints are as follows:
α ik + α ji + α kj − α ki − α ij − α jk ≤ 1, 1 ≤ i, j, k ≤ n, i, k < j, k = i.
(3.3)