28
2 Layout on a Single Row
We again use the variables α from earlier sections: α ij = 1 if department i
is located to the left of department j , and α ij = 0 otherwise. We fix the desired
direction of flow from left to right, so that backward flow is any flow from right to
left. In other words, the flow from i to j is backwards if j is to the left of i, i.e., if
α ji = 1.
Let d b
ij denote the backtracking distance from machine i to machine j , i = j ,
i, j = 1, . . . , n. Note that we always have one of d
b
ij and d
b
ji equal to zero and the
other positive, depending on the relative positions of i and j . Observe also that the
backtracking distance between i and j is exactly the number of positions between
them. We use this observation to express the backtracking distance. First, suppose
that department j is to the left of department i. Then the number of positions
between them can be computed by counting the number of departments to the left
of i and subtracting the number of departments to the left of j . We thus have
d
b
ij =
k =i
α ki −
k =j
α kj .
Similarly, if i is to the left of j , then the backtracking distance is
d
b
ji =
k =j
α kj −
k =i
α ki .
We can express both cases simultaneously as follows:
d
b
ij − d
b
ji =
k =i
α ki −
k =j
α kj
d
b
ij , d
b
ji ≥ 0.
The idea is that depending on the sign of the difference on the right-hand side, one of
d
b
ij and d
b
ji will be positive and the other zero. Naturally, they could both be positive
and have the correct difference between them to equate to the right-hand side, but
this will not happen because of the objective function, which is clearly
min
d b
ij
n
i=1
j =i
f ij d
b
ij .
This minimization will make all the d
b
ij variables as small as possible, so the desired
result is obtained.
The formulation of the MBRLP is thus
minimize
n
i=1
j =i
f ij d
b
ij
(2.77)
s.t. d
b
ji − d
b
ij =
k =i
α ki −
k =j
α kj , 1 ≤ i < j ≤ n,
(2.78)
2 Layout on a Single Row
We again use the variables α from earlier sections: α ij = 1 if department i
is located to the left of department j , and α ij = 0 otherwise. We fix the desired
direction of flow from left to right, so that backward flow is any flow from right to
left. In other words, the flow from i to j is backwards if j is to the left of i, i.e., if
α ji = 1.
Let d b
ij denote the backtracking distance from machine i to machine j , i = j ,
i, j = 1, . . . , n. Note that we always have one of d
b
ij and d
b
ji equal to zero and the
other positive, depending on the relative positions of i and j . Observe also that the
backtracking distance between i and j is exactly the number of positions between
them. We use this observation to express the backtracking distance. First, suppose
that department j is to the left of department i. Then the number of positions
between them can be computed by counting the number of departments to the left
of i and subtracting the number of departments to the left of j . We thus have
d
b
ij =
k =i
α ki −
k =j
α kj .
Similarly, if i is to the left of j , then the backtracking distance is
d
b
ji =
k =j
α kj −
k =i
α ki .
We can express both cases simultaneously as follows:
d
b
ij − d
b
ji =
k =i
α ki −
k =j
α kj
d
b
ij , d
b
ji ≥ 0.
The idea is that depending on the sign of the difference on the right-hand side, one of
d
b
ij and d
b
ji will be positive and the other zero. Naturally, they could both be positive
and have the correct difference between them to equate to the right-hand side, but
this will not happen because of the objective function, which is clearly
min
d b
ij
n
i=1
j =i
f ij d
b
ij .
This minimization will make all the d
b
ij variables as small as possible, so the desired
result is obtained.
The formulation of the MBRLP is thus
minimize
n
i=1
j =i
f ij d
b
ij
(2.77)
s.t. d
b
ji − d
b
ij =
k =i
α ki −
k =j
α kj , 1 ≤ i < j ≤ n,
(2.78)