38
3 Layout on Several Rows
β ij k ≤ α jk + α kj , 1 ≤ i < j ≤ n, k = i, j,
(3.20)
α ij , β ij k ∈ {0, 1}, 1 ≤ i = j ≤ n, k = i, j,
(3.21)
i
2
≤ x i ≤ L −
i
2
, 1 ≤ i ≤ n.
(3.22)
The new constraints (3.16)–(3.20) determine the values of the variables β ij k for
each feasible assignment to the variables α ij , α ik , α jk , α ji , α ki , and α kj . Specifically, whenever k is between i and j , then constraints (3.16) and (3.17) enforce
β ij k = 1. Alternatively, if one of {i, j, k} is in a different row, constraints (3.18)–
(3.20) ensure that β ij k = 0.
3.2 Multi-Row Facility Layout
An instance of the multi-row facility layout problem (MRFLP) has a given number
of rows to which the departments can be assigned. The departments all have the
same height (equal to the row height), the distances between adjacent rows are equal,
and departments can in general be assigned to any row. While from a mathematical
point of view, the MRFLP is a natural extension of single-row or double-row layout,
from an industrial engineering perspective, layout on three or more rows is a more
challenging problem.
The matter of measuring the rectilinear distance between the centres of two
departments takes on a greater importance when considering layouts on three or
more rows. When two departments are assigned to different rows separated by at
least one other row, clearly a component of this distance arises from the separation
between the rows. This is not the case for one- and two-row versions of layout,
where only the horizontal component of the distance matters.
The MRFLP captures the basic structure of applications where the departments
are to be arranged in well-defined rows because the separation between the rows is
prespecified. It is thus a problem that is discrete in one dimension (between rows)
and continuous in the other dimension (within rows).
We first introduce a straightforward nonlinear model as an extension of the
single-row layout model (2.3)–(2.5):
minimize
n−1
i=1
n
j =i+1
c ij (|x i − x j | + |y i − y j |)
(3.23)
s.t. |x i − x j | ≥
1
2
(( i + j ) − L(1 − α ij ), 1 ≤ i < j ≤ n,
(3.24)
|y i − y j | ≥
1
2
(w i + w j ) − Lα ij , 1 ≤ i < j ≤ n,
(3.25)
α ij ∈ {0, 1}, 1 ≤ i < j ≤ n,
(3.26)
3 Layout on Several Rows
β ij k ≤ α jk + α kj , 1 ≤ i < j ≤ n, k = i, j,
(3.20)
α ij , β ij k ∈ {0, 1}, 1 ≤ i = j ≤ n, k = i, j,
(3.21)
i
2
≤ x i ≤ L −
i
2
, 1 ≤ i ≤ n.
(3.22)
The new constraints (3.16)–(3.20) determine the values of the variables β ij k for
each feasible assignment to the variables α ij , α ik , α jk , α ji , α ki , and α kj . Specifically, whenever k is between i and j , then constraints (3.16) and (3.17) enforce
β ij k = 1. Alternatively, if one of {i, j, k} is in a different row, constraints (3.18)–
(3.20) ensure that β ij k = 0.
3.2 Multi-Row Facility Layout
An instance of the multi-row facility layout problem (MRFLP) has a given number
of rows to which the departments can be assigned. The departments all have the
same height (equal to the row height), the distances between adjacent rows are equal,
and departments can in general be assigned to any row. While from a mathematical
point of view, the MRFLP is a natural extension of single-row or double-row layout,
from an industrial engineering perspective, layout on three or more rows is a more
challenging problem.
The matter of measuring the rectilinear distance between the centres of two
departments takes on a greater importance when considering layouts on three or
more rows. When two departments are assigned to different rows separated by at
least one other row, clearly a component of this distance arises from the separation
between the rows. This is not the case for one- and two-row versions of layout,
where only the horizontal component of the distance matters.
The MRFLP captures the basic structure of applications where the departments
are to be arranged in well-defined rows because the separation between the rows is
prespecified. It is thus a problem that is discrete in one dimension (between rows)
and continuous in the other dimension (within rows).
We first introduce a straightforward nonlinear model as an extension of the
single-row layout model (2.3)–(2.5):
minimize
n−1
i=1
n
j =i+1
c ij (|x i − x j | + |y i − y j |)
(3.23)
s.t. |x i − x j | ≥
1
2
(( i + j ) − L(1 − α ij ), 1 ≤ i < j ≤ n,
(3.24)
|y i − y j | ≥
1
2
(w i + w j ) − Lα ij , 1 ≤ i < j ≤ n,
(3.25)
α ij ∈ {0, 1}, 1 ≤ i < j ≤ n,
(3.26)