62
4 Layout of a Single Floor
Let us look more closely at how this formulation of the nonoverlap constraints
works. For example, consider departments i = 1 and j = 2, and suppose that
α 12 = 1. By constraint (4.23), we have that α 21 = 0, β 12 = 0, and β 21 = 0.
Constraints (4.21) become
x 1 +
1
2
w 1 ≤ x 2 −
1
2
w 2 and x 2 +
1
2
w 2 ≤ x 1 −
1
2
w 1 + w F ,
and constraints (4.22) become
y 1 +
1
2
h 1 ≤ y 2 −
1
2
h 2 + h F and y 2 +
1
2
h 2 ≤ y 1 −
1
2
h 1 + h F .
The first constraint requires that the left border of department 2 (with x
coordinate equal to x 2 −
1
2 w 2 ) must lie to the right of the right border of department
1 (with x coordinate equal to x 1 +
1
2 w 1 ). In other words, department 1 is to the
left of 2, or equivalently, 1 precedes 2 in the horizontal dimension, as desired from
the choice of α 12 = 1. Moreover, the other three constraints have the width or
height of the entire facility (w F or h F ) added to their right-hand side. This renders
them inactive because they will be satisfied by any otherwise feasible values of the
variables involved. That is, w F and h F are effectively acting as big-M values; see
Sect. 2.3.3.
An alternative MISOCO representation of the relative positions of pairs of
departments is introduced in the next section.
4.3 Sequence-Pair Formulation
Sequence-pair approaches determine the relative positions of the departments using
the so-called sequence-pair representation. This representation is integrated into a
MISOCO model similar to that in Sect. 4.2 to obtain a formulation of the UA-FLP.
A sequence-pair, denoted Γ + and Γ − , consists of a pair of sequences of the set
of departments. Together, these two sequences encode the relative position of each
pair of departments.
The following definition explains how a sequence-pair defines the relative
positions of departments within a layout.
Definition 4.1 Let (Γ + , Γ − ) be a sequence-pair, and let i and j be two departments
in Γ + , Γ − . The sequence-pair determines the relative horizontal or vertical placement of i and j in a layout as follows:
• if i follows j in both Γ + and Γ − , then i is to the right of j ;
• if i precedes j in both Γ + and Γ − , then i is to the left of j ;
• if i precedes j in Γ + and follows j in Γ − , then i is above j ;
• if i follows j in Γ + and precedes j in Γ − , then i is below j .
4 Layout of a Single Floor
Let us look more closely at how this formulation of the nonoverlap constraints
works. For example, consider departments i = 1 and j = 2, and suppose that
α 12 = 1. By constraint (4.23), we have that α 21 = 0, β 12 = 0, and β 21 = 0.
Constraints (4.21) become
x 1 +
1
2
w 1 ≤ x 2 −
1
2
w 2 and x 2 +
1
2
w 2 ≤ x 1 −
1
2
w 1 + w F ,
and constraints (4.22) become
y 1 +
1
2
h 1 ≤ y 2 −
1
2
h 2 + h F and y 2 +
1
2
h 2 ≤ y 1 −
1
2
h 1 + h F .
The first constraint requires that the left border of department 2 (with x
coordinate equal to x 2 −
1
2 w 2 ) must lie to the right of the right border of department
1 (with x coordinate equal to x 1 +
1
2 w 1 ). In other words, department 1 is to the
left of 2, or equivalently, 1 precedes 2 in the horizontal dimension, as desired from
the choice of α 12 = 1. Moreover, the other three constraints have the width or
height of the entire facility (w F or h F ) added to their right-hand side. This renders
them inactive because they will be satisfied by any otherwise feasible values of the
variables involved. That is, w F and h F are effectively acting as big-M values; see
Sect. 2.3.3.
An alternative MISOCO representation of the relative positions of pairs of
departments is introduced in the next section.
4.3 Sequence-Pair Formulation
Sequence-pair approaches determine the relative positions of the departments using
the so-called sequence-pair representation. This representation is integrated into a
MISOCO model similar to that in Sect. 4.2 to obtain a formulation of the UA-FLP.
A sequence-pair, denoted Γ + and Γ − , consists of a pair of sequences of the set
of departments. Together, these two sequences encode the relative position of each
pair of departments.
The following definition explains how a sequence-pair defines the relative
positions of departments within a layout.
Definition 4.1 Let (Γ + , Γ − ) be a sequence-pair, and let i and j be two departments
in Γ + , Γ − . The sequence-pair determines the relative horizontal or vertical placement of i and j in a layout as follows:
• if i follows j in both Γ + and Γ − , then i is to the right of j ;
• if i precedes j in both Γ + and Γ − , then i is to the left of j ;
• if i precedes j in Γ + and follows j in Γ − , then i is above j ;
• if i follows j in Γ + and precedes j in Γ − , then i is below j .