44
3 Layout on Several Rows
Recall the three tasks (stated at the beginning of this chapter) that arise for an
instance of MRFLP:
1. assign each department to exactly one of the rows;
2. express mathematically the weighted centre-to-centre distance between pairs of
departments (which may or may not be in the same row);
3. account for the possibility of empty space between departments in the same row.
The idea is to have simpler models that do not perform all these tasks but can be
used as part of an overall strategy for the MRFLP.
A successful example of such an approach is as follows. Suppose that the
assignment of departments to rows (the first task above) is known, and set up a
model that optimizes the layout for that given assignment. Then by enumerating all
possible assignments of departments to rows and optimizing the layout for each of
the assignments, one can solve the MRFLP. Naturally, if the enumeration is done by
brute force, then there will be no gain in efficiency compared to the MILO models
above. However, if we enumerate the assignments in a clever way, then we obtain a
more efficient way to solve the MRFLP.
The remaining sections of this chapter consider special cases of the MRFLP,
some of which have been used in such alternative approaches.
3.3 Fixed-Row Multi-Row Facility Layout
In this section we consider the special case of fixed-row MRFLP, abbreviated FRMRFLP. The FR-MRFLP is the variant of MRFLP in which the assignment of
departments to rows is fixed and given as input. Thus, the optimization does not
need to assign each department to a row.
To model the FR-MRFLP, we assume that we are given as input the set R =
{1, 2, . . . , m} of rows for the layout and a description of the row assignments in the
form of sets N r , r ∈ R, of the departments assigned to row r.
For the MILO model below, we introduce two dummy departments n + 1 and
n + 2 to be placed at the left and right ends, respectively, of the layout. These
dummy departments have zero lengths, i.e., n+1 = n+2 = 0, and they do not
contribute any cost to the objective function, so we set c ij = 0 if i ∈ {n + 1, n + 2}
or j ∈ {n + 1, n + 2}. Each department set N r is extended to include the dummy
departments, with the notation ˜
N r = N r ∪ {n + 1, n + 2}.
The MILO model presented, unlike those in Sects. 3.2.1 and 3.2.2, does not use
continuous variables for the position of the departments within rows. Instead it is
built on the betweenness model from Sect. 2.4. Therefore, we recall the betweenness
variables defined in Sect. 2.4 for any three distinct departments i, j , and k:
β ij k =
1, if department k lies between departments i and j,
0, otherwise.
3 Layout on Several Rows
Recall the three tasks (stated at the beginning of this chapter) that arise for an
instance of MRFLP:
1. assign each department to exactly one of the rows;
2. express mathematically the weighted centre-to-centre distance between pairs of
departments (which may or may not be in the same row);
3. account for the possibility of empty space between departments in the same row.
The idea is to have simpler models that do not perform all these tasks but can be
used as part of an overall strategy for the MRFLP.
A successful example of such an approach is as follows. Suppose that the
assignment of departments to rows (the first task above) is known, and set up a
model that optimizes the layout for that given assignment. Then by enumerating all
possible assignments of departments to rows and optimizing the layout for each of
the assignments, one can solve the MRFLP. Naturally, if the enumeration is done by
brute force, then there will be no gain in efficiency compared to the MILO models
above. However, if we enumerate the assignments in a clever way, then we obtain a
more efficient way to solve the MRFLP.
The remaining sections of this chapter consider special cases of the MRFLP,
some of which have been used in such alternative approaches.
3.3 Fixed-Row Multi-Row Facility Layout
In this section we consider the special case of fixed-row MRFLP, abbreviated FRMRFLP. The FR-MRFLP is the variant of MRFLP in which the assignment of
departments to rows is fixed and given as input. Thus, the optimization does not
need to assign each department to a row.
To model the FR-MRFLP, we assume that we are given as input the set R =
{1, 2, . . . , m} of rows for the layout and a description of the row assignments in the
form of sets N r , r ∈ R, of the departments assigned to row r.
For the MILO model below, we introduce two dummy departments n + 1 and
n + 2 to be placed at the left and right ends, respectively, of the layout. These
dummy departments have zero lengths, i.e., n+1 = n+2 = 0, and they do not
contribute any cost to the objective function, so we set c ij = 0 if i ∈ {n + 1, n + 2}
or j ∈ {n + 1, n + 2}. Each department set N r is extended to include the dummy
departments, with the notation ˜
N r = N r ∪ {n + 1, n + 2}.
The MILO model presented, unlike those in Sects. 3.2.1 and 3.2.2, does not use
continuous variables for the position of the departments within rows. Instead it is
built on the betweenness model from Sect. 2.4. Therefore, we recall the betweenness
variables defined in Sect. 2.4 for any three distinct departments i, j , and k:
β ij k =
1, if department k lies between departments i and j,
0, otherwise.