3.4 Multi-Row Facility Layout with Departments of Equal Length
47
Specifically, we have the following result.
Theorem 3.2 There is always an optimal solution to the MREFLP on the integer
grid.
Theorem 3.2 is especially interesting because it allows us to make specific
statements about the empty spaces that can occur between departments in the same
row, which is the last of the three tasks stated at the beginning of this chapter.
In particular, it implies that all the spaces between departments will have integer
lengths.
Moreover, with a careful and detailed analysis, it is possible to make specific
statements about the minimum number of columns required to obtain at least one
optimal layout for the MREFLP. First, we make the following assumptions, where
n is the number of departments, and m is the number of rows available for the
layout.
Assumption 1 Columns containing only spaces can be deleted.
Assumption 2 If two nonempty neighbouring columns together contain no more
than m departments, then all the corresponding departments can be
assigned to the left column, and the right column can be deleted.
Assumption 3 If n > 2m and the first and third columns contain in total at
most m departments, then all the corresponding departments can
be assigned to the third column, and the first column can be deleted.
More generally, this holds for columns k − 2 and k such that each
column with index at most k contains at least one department.
Under these assumptions, the following theorem can be proved.
Theorem 3.3 The minimum number of columns sufficient to preserve at least one
optimal layout for an instance with n departments is
1. equal to 1 if n ≤ m and equal to 2 if m < n <
3
2 m +
3
2 ;
2. equal to
2n
3
− 1 for the DREFLP with n ≥ 9;
3. equal to
2n
m+1
for the MREFLP with an odd number of rows m; and
4. equal to or at most 2t + 1 for the MREFLP with an even number of rows m and
n ∈ {
m
2 + 2 + (m + 1)(t − 1), . . . ,
m
2 + 1 + (m + 1)t} for some t ∈ N.
This means that we can compute in advance the number of columns required to
obtain an optimal solution. We call this number C. Knowing C and knowing that
we have n departments, we can fill up the C columns and m rows with spacing
departments, i.e., departments of length 1 and with all pairwise connectivities
involving them equal to 0. This means that there is no need for models to explicitly
consider the issue of empty spaces between departments in the same row, as all the
necessary spaces will be occupied by the spacing departments in an optimal way.
47
Specifically, we have the following result.
Theorem 3.2 There is always an optimal solution to the MREFLP on the integer
grid.
Theorem 3.2 is especially interesting because it allows us to make specific
statements about the empty spaces that can occur between departments in the same
row, which is the last of the three tasks stated at the beginning of this chapter.
In particular, it implies that all the spaces between departments will have integer
lengths.
Moreover, with a careful and detailed analysis, it is possible to make specific
statements about the minimum number of columns required to obtain at least one
optimal layout for the MREFLP. First, we make the following assumptions, where
n is the number of departments, and m is the number of rows available for the
layout.
Assumption 1 Columns containing only spaces can be deleted.
Assumption 2 If two nonempty neighbouring columns together contain no more
than m departments, then all the corresponding departments can be
assigned to the left column, and the right column can be deleted.
Assumption 3 If n > 2m and the first and third columns contain in total at
most m departments, then all the corresponding departments can
be assigned to the third column, and the first column can be deleted.
More generally, this holds for columns k − 2 and k such that each
column with index at most k contains at least one department.
Under these assumptions, the following theorem can be proved.
Theorem 3.3 The minimum number of columns sufficient to preserve at least one
optimal layout for an instance with n departments is
1. equal to 1 if n ≤ m and equal to 2 if m < n <
3
2 m +
3
2 ;
2. equal to
2n
3
− 1 for the DREFLP with n ≥ 9;
3. equal to
2n
m+1
for the MREFLP with an odd number of rows m; and
4. equal to or at most 2t + 1 for the MREFLP with an even number of rows m and
n ∈ {
m
2 + 2 + (m + 1)(t − 1), . . . ,
m
2 + 1 + (m + 1)t} for some t ∈ N.
This means that we can compute in advance the number of columns required to
obtain an optimal solution. We call this number C. Knowing C and knowing that
we have n departments, we can fill up the C columns and m rows with spacing
departments, i.e., departments of length 1 and with all pairwise connectivities
involving them equal to 0. This means that there is no need for models to explicitly
consider the issue of empty spaces between departments in the same row, as all the
necessary spaces will be occupied by the spacing departments in an optimal way.