80
5 Extensions and Related Problems
d
h
ij includes the use of an elevator. Otherwise, Z ij = 1 so this constraint becomes
inactive and d h
ij is found by constraint (5.12). Constraints (5.14), (5.15), (5.16), and
(5.17) were discussed in Sect. 4.1.
Constraints (5.18)–(5.21) prevent the overlapping of departments and elevators
on the same floor. To see how these constraints operate, suppose first that Z ij = 0.
This means that departments i and j are on different floors, and therefore we do
not want to enforce a nonoverlap constraint between them. Observe that because
Z ij = 0, for the four possible assignments of binary values to X ij and Y ij , we have
(1 − Z ij + X ij + Y ij ) = 1 + X ij + Y ij > 0,
(2 − Z ij − X ij + Y ij ) = 2 − X ij + Y ij > 0,
(2 − Z ij + X ij − Y ij ) = 2 + X ij − Y ij > 0,
(3 − Z ij − X ij − Y ij ) = 3 − X ij − Y ij > 0.
Therefore, the right-hand side of constraints (5.18)–(5.21) will always be inactive.
Alternatively, if Z ij = 1, then departments i and j are on the same floor, and
therefore we must enforce one of the four nonoverlap constraints. Because Z ij = 1,
for any assignment of binary values to X ij and Y ij , we have
(1 − Z ij + X ij + Y ij ) = X ij + Y ij , which will equal 0 only if X ij = 0 and Y ij = 0;
(2 − Z ij − X ij + Y ij ) = 1 − X ij + Y ij , which will equal 0 only if X ij = 1 and Y ij = 0;
(2 − Z ij + X ij − Y ij ) = 1 + X ij − Y ij , which will equal 0 only if X ij = 0 and Y ij = 1;
(3 − Z ij − X ij − Y ij ) = 2 − X ij − Y ij , which will equal 0 only if X ij = 1 and Y ij = 1.
Therefore, depending on the specific values of X ij and Y ij , precisely one of
the right-hand sides of constraints (5.18)–(5.21) will equal 0, which makes that
constraint active and ensures that the two departments do not overlap.
Finally, constraints (5.22) and (5.23) ensure that each elevator covers all the
floors and every pair of elevators shares the same floor.
5.3.2 Two-Stage Approach for the MF-FLP
Another way to tackle the MF-FLP is to first allocate the departments to floors while
minimizing the vertical interaction costs, and then optimize the layout of the floors
independently as multiple instances of single-floor layout. This is essentially a twostage approach, akin to those presented in Sect. 4.4 for single-floor layout.
The assignment of departments to floors can be done using a quadratic semiassignment problem (QSAP). This is a version of the QAP in which each department
must be assigned to exactly one floor, but more than one department can be assigned
5 Extensions and Related Problems
d
h
ij includes the use of an elevator. Otherwise, Z ij = 1 so this constraint becomes
inactive and d h
ij is found by constraint (5.12). Constraints (5.14), (5.15), (5.16), and
(5.17) were discussed in Sect. 4.1.
Constraints (5.18)–(5.21) prevent the overlapping of departments and elevators
on the same floor. To see how these constraints operate, suppose first that Z ij = 0.
This means that departments i and j are on different floors, and therefore we do
not want to enforce a nonoverlap constraint between them. Observe that because
Z ij = 0, for the four possible assignments of binary values to X ij and Y ij , we have
(1 − Z ij + X ij + Y ij ) = 1 + X ij + Y ij > 0,
(2 − Z ij − X ij + Y ij ) = 2 − X ij + Y ij > 0,
(2 − Z ij + X ij − Y ij ) = 2 + X ij − Y ij > 0,
(3 − Z ij − X ij − Y ij ) = 3 − X ij − Y ij > 0.
Therefore, the right-hand side of constraints (5.18)–(5.21) will always be inactive.
Alternatively, if Z ij = 1, then departments i and j are on the same floor, and
therefore we must enforce one of the four nonoverlap constraints. Because Z ij = 1,
for any assignment of binary values to X ij and Y ij , we have
(1 − Z ij + X ij + Y ij ) = X ij + Y ij , which will equal 0 only if X ij = 0 and Y ij = 0;
(2 − Z ij − X ij + Y ij ) = 1 − X ij + Y ij , which will equal 0 only if X ij = 1 and Y ij = 0;
(2 − Z ij + X ij − Y ij ) = 1 + X ij − Y ij , which will equal 0 only if X ij = 0 and Y ij = 1;
(3 − Z ij − X ij − Y ij ) = 2 − X ij − Y ij , which will equal 0 only if X ij = 1 and Y ij = 1.
Therefore, depending on the specific values of X ij and Y ij , precisely one of
the right-hand sides of constraints (5.18)–(5.21) will equal 0, which makes that
constraint active and ensures that the two departments do not overlap.
Finally, constraints (5.22) and (5.23) ensure that each elevator covers all the
floors and every pair of elevators shares the same floor.
5.3.2 Two-Stage Approach for the MF-FLP
Another way to tackle the MF-FLP is to first allocate the departments to floors while
minimizing the vertical interaction costs, and then optimize the layout of the floors
independently as multiple instances of single-floor layout. This is essentially a twostage approach, akin to those presented in Sect. 4.4 for single-floor layout.
The assignment of departments to floors can be done using a quadratic semiassignment problem (QSAP). This is a version of the QAP in which each department
must be assigned to exactly one floor, but more than one department can be assigned