3.5 Additional Special Cases of Multi-Row Facility Layout
51
The CAP can be formulated in a similar way to the DRFLP. The formulation that
we give below is based on the formulation of the DRFLP in Sect. 3.1.1.
minimize
n−1
i=1
n
j =i+1
c ij d ij
(3.81)
s.t. d ij ≥ x i − x j , d ij ≥ x j − x i , 1 ≤ i < j ≤ n,
(3.82)
x i =
i
2
+
k =i
k α ki , 1 ≤ i ≤ n,
(3.83)
d ij −
i + j
2
α ij −
i + j
2
α ji ≥ 0, 1 ≤ i < j ≤ n
(3.84)
(3.1) − (3.4)
α ij ∈ {0, 1}, 1 ≤ i = j ≤ n,
(3.85)
i
2
≤ x i ≤ L − i , 1 ≤ i ≤ n.
(3.86)
The main difference is the way of expressing the position of each department within
its row, because for the CAP, the position x i of department i is exactly equal to
the sum of the lengths of the preceding departments (see constraints (3.83)). The
formulation can be simplified by using (3.83) to substitute for x i and x j in (3.82)
and (3.86). We can then omit constraints (3.83) and (3.84), and the distances are
computed by the new form of constraints (3.82):
d ij ≥
i − j
2
+
k =i
k α ki −
k =j
k α kj , 1 ≤ i < j ≤ n,
(3.87)
d ij ≥
j − i
2
+
k =j
k α kj −
k =i
k α ki , 1 ≤ i < j ≤ n.
(3.88)
3.5.2 k-Corridor Allocation Problem
The k-corridor allocation problem (k-CAP) is the generalization of the CAP (where
k = 2) to three or more rows. It is also known as the space-free multi-row facility
layout problem (SF-MRFLP). Solutions to the k-CAP must satisfy the conditions
of the CAP (no space between adjacent departments; leftmost point of every row at
origin). The k-CAP can be approached by solving an instance of the k-PROP (see
Sect. 3.5.4) for every possible assignment of departments to rows. However, this
strategy can solve only small instances.