54
3 Layout on Several Rows
The above relations, plus the triangle inequalities for the distances between every
triplet of departments i, j , and k
d ij + d ik ≥ d jk , d ij + d jk ≥ d ik , d ik + d jk ≥ d ij , 1 ≤ i < j < k ≤ n,
(3.94)
can be used to obtain an SDO formulation for the k-PROP.
In the SDO formulation, the possibility of spaces is handled using the next
theorem. The result makes use of the half-integer grid, which is the set of all values
that are equal to an integer or an integer plus 0.5. For example, 5 and 9.5 are both
half-integer, but 4.3 is not.
Theorem 3.4 If all the department lengths i are integer, then there is always an
optimal solution to the MRFLP on the half-integer grid.
Corollary 3.2 If all the department lengths i are integer, then for each instance
of the MRFLP, we obtain an equivalent instance of the k-PROP by adding spacing
departments of length 0.5 such that the length of each row becomes equal to M :=
n
i=1 i .
We can solve a DRFLP or a MRFLP using the k-PROP SDO-based formulation
by adding enough spacing departments of length 0.5 with all involved connectivities
equal to zero and then applying the SDO approach for k-PROP. Because the number
of spacing departments needed will normally be too large for computation, it is in
practice necessary to reduce this number.
Finally, the restriction that the assignment of departments to rows is fixed can be
handled by using the above approach to find the global optimal solution for each of
the possible assignments (or for a subset of them). This will lead to a global optimal
solution (or global lower bounds) for the DRFLP or the MRFLP.
3.7 References and Further Reading
The relationship between the material handling system and the type of layout is
discussed in Heragu and Kusiak (1988) and Heragu (2008). Another application of
the DRFLP is the arrangement of rooms in buildings, see, e.g., Ahonen et al (2014).
The MILO formulation for the DRFLP in Sect. 3.1.1 was proposed by Amaral (2013). Subsequently, Secchin and Amaral (2019) presented the model in
Sect. 3.1.2, but we have presented the nonoverlap constraint (3.13) instead of
x i + d ij ≤ x j + 2(L − i /2 − j /2)(1 − α ij ), i < j
x i + d ji ≤ x j + 2(L − i /2 − j /2)(1 − α ij ), i > j.
3 Layout on Several Rows
The above relations, plus the triangle inequalities for the distances between every
triplet of departments i, j , and k
d ij + d ik ≥ d jk , d ij + d jk ≥ d ik , d ik + d jk ≥ d ij , 1 ≤ i < j < k ≤ n,
(3.94)
can be used to obtain an SDO formulation for the k-PROP.
In the SDO formulation, the possibility of spaces is handled using the next
theorem. The result makes use of the half-integer grid, which is the set of all values
that are equal to an integer or an integer plus 0.5. For example, 5 and 9.5 are both
half-integer, but 4.3 is not.
Theorem 3.4 If all the department lengths i are integer, then there is always an
optimal solution to the MRFLP on the half-integer grid.
Corollary 3.2 If all the department lengths i are integer, then for each instance
of the MRFLP, we obtain an equivalent instance of the k-PROP by adding spacing
departments of length 0.5 such that the length of each row becomes equal to M :=
n
i=1 i .
We can solve a DRFLP or a MRFLP using the k-PROP SDO-based formulation
by adding enough spacing departments of length 0.5 with all involved connectivities
equal to zero and then applying the SDO approach for k-PROP. Because the number
of spacing departments needed will normally be too large for computation, it is in
practice necessary to reduce this number.
Finally, the restriction that the assignment of departments to rows is fixed can be
handled by using the above approach to find the global optimal solution for each of
the possible assignments (or for a subset of them). This will lead to a global optimal
solution (or global lower bounds) for the DRFLP or the MRFLP.
3.7 References and Further Reading
The relationship between the material handling system and the type of layout is
discussed in Heragu and Kusiak (1988) and Heragu (2008). Another application of
the DRFLP is the arrangement of rooms in buildings, see, e.g., Ahonen et al (2014).
The MILO formulation for the DRFLP in Sect. 3.1.1 was proposed by Amaral (2013). Subsequently, Secchin and Amaral (2019) presented the model in
Sect. 3.1.2, but we have presented the nonoverlap constraint (3.13) instead of
x i + d ij ≤ x j + 2(L − i /2 − j /2)(1 − α ij ), i < j
x i + d ji ≤ x j + 2(L − i /2 − j /2)(1 − α ij ), i > j.