Basic Algorithms and Software

for the Layout Problem

Chapter 5
 Algorithms

• Optimal
• Heuristic
 Algorithms
• Construction • Hybrid
– MST – Modified Penalty
– Graph Theoretic Algorithm
Method
• Improvement
– 2-opt
• Greedy
• Steepest Descent
– 3-opt
• Greedy
• Steepest Descent
 MST Algorithm
• Step 1: Given the flow matrix [fij], clearance
matrix [dij] and machine lengths li, compute an
adjacency weight matrix where:
f’ij = (fij)(dij+0.5(li+lj)).
• Step 2: Find the largest element in [f’ij] and
the corresponding i, j. Denote this pair of i, j
as i*, j*. Connect machines i*, j*. Set f’i*j* =f’i *i*
=-infinity
 MST Algorithm
• Step 3: Find the largest element f’i*k,f’j*l in
row i*, j* of matrix If f’i*k*>f’j*l* connect k to i*,
remove row i*, column i* from matrix and set i*
= k. Otherwise, connect l to j*, remove row j*,
column j* from matrix and set j* = l. Set f’i*j* =f’i
*i* =-infinity
• Step 4: Repeat step 3 until all machines are
connected. The sequence of machines
obtained determines the arrangement of
machines.
 Example 1
M 1 2 3 4 5 6

Machine Lengths (in feet)

a 1 - 12 3 6 0 20 20

c 2 12 - 5 5 5 0 10

h 3 3 5 - 10 4 2 16

i 4 6 5 10 - 2 12 20

n 5 0 5 4 2 - 6 10

e 6 20 0 2 12 6 - 10
 Example 1 Solution
M 1 2 3 4 5 6

a 1 - 204 60 132 0 340

c 2 204 - 75 85 60 0

h 3 60 75 - 200 60 30

i 4 132 85 200 - 34 204

n 5 0 60 60 34 - 72

e 6 340 0 30 204 72 -
 Example 1 Solution

5 2 1 6 4 3
 Graph Theoretic Method

• Terminology
– Graph
– Complete graph
– Planar Graph
– Maximal Planar Graph
9

1 2 3

1 2 3

4 5
4 5
6
6
7 8

7 8
 Graph Theoretic Method

• Layout…. • And its dual…

9
1 2 3

1 2 3

4 5
4 5
6
6

7 8
7 8
 Graph Theoretic Method*

Step 1: Identify the department-pair in the flow matrix with the maximum flow. Place
the corresponding nodes in a new PAG and connect them.
Step 2: From the rows corresponding to the connected nodes in the flow matrix,
select the node which is not yet in the PAG and has the largest flows with the
connected nodes.
Step 3: Update PAG by connecting the selected node to those in Step 2. This
forms a triangular face in the PAG.
Step 4: For each column of the flow matrix corresponding to a node not present in
the PAG, examine the sum of flow entries in the rows corresponding to the
nodes of the triangular face selected in step 3. Select the column for which
this sum is the largest. Update PAG by placing the corresponding node
within the selected face and connect it to nodes of the face. This forms three
new triangular faces.
Step 5: Arbitrarily select one of the faces formed and go to Step 4. Repeat Step 5
until all the nodes have been included in the PAG.

* Based on the result that the maximum number of arcs in a planar graph with n nodes 3n-6
 Graph Theoretic Method
1 2 3 4 5 6 7 8 9 10 1 12

1 - 1 0 8 0 2 3 0 0 0 0 0

Do Example 2 2 1 - 0 1 1 1 0 0 0 0 0 0

M 3 0 0 - 0 2 0 0 0 0 0 0 0

a 4 8 1 0 - 0 4 14 11 0 0 0 0

c 5 0 1 2 0 - 1 0 0 0 0 0 0

h 6 2 1 0 4 1 - 3 0 0 3 0 0

i 7 3 0 0 14 0 3 - 5 5 9 8 2

n 8 0 0 0 11 0 0 5 - 8 0 0 0

e 9 0 0 0 0 0 0 5 8 - 0 0 0

10 0 0 0 0 0 3 9 0 0 - 6 0

11 0 0 0 0 0 0 8 0 0 6 - 4

12 0 0 0 0 0 0 2 0 0 0 4 -
 Graph Theoretic Method

Example 2
4 7
14

8 8

8
11 5 11 5
0 9 5

4 7 4 7
14 14
 Graph Theoretic Method

8
Example 2

13

2 3
1 10
5
8
6 9 12

11

4 7
13

2 3
1 10
5

6 9 12

11

4 7
 Graph Theoretic Method

Example 2

2
3

8 6 9

10
11 12
4
7

5
 2-opt algorithm
• Step 1: Let S be the initial solution provided by the
user and z its OFV. Set i=1; j=i+1=2.
• Step 2: Consider the exchange between the
positions of departments i and j in the solution S. If
the exchange results in a solution S’ that has an
OFV z’< z, set z*=z’ and S*=S’. If j < mn, set j=j+1;
otherwise, set i=i+1, j=I+1. If i < mn, repeat step 2;
otherwise, go to step 3.
• Step 3: If S not =S*, set S=S*, z=z*, i=1, j=i+1=2
and go to step 2. Otherwise, return S* as the best
solution to the user. Stop.

• Do Example 3 using SINROW or MULROW

 2-opt algorithm
. . . . . mn

. . .

. . . . . .

. . . . . .

m+1 m+2 . . . .

1 2 . . . m
 Example 3

O 1 2 3 4 1 2 3 4
f 1 - 17 12 11 S 1 - 1 1 2
[fij]= f 2 17 - 12 4 [dij]= i 2 1 - 2 1
i 3 12 12 - 4 t 3 1 2 - 1
c 4 11 4 4 - e 4 2 1 1 -
e
 3-opt algorithm
Step 1: Let S be the initial solution and z its OFV; Set S*=S,
z*=z, i=1; j=i+1; k=j+1.
Step 2: Consider changing the position of department i to that of
j, j to that of k, and k to that of i, simultaneously. If the
resulting solution SN has OFV z’ < z, set z*=z’ and S*=S’.
Step 3: If k < mn, set k = k +1, and repeat step 2. Otherwise, set
j=j+1 and check if j < mn-1.
If j < mn-1, set k=j +1, and repeat step 2. Otherwise, set i = i
+1, j=i+1, k = j +1, and check if i < mn-2.
If i < mn -2, repeat step 2. Otherwise, go to step 4.
Step 4: If S not = S*, set S=S*, z=z*, i=1, j=i+1, k=j+1 and go to
step 2. Otherwise, return S* as the best solution to the user.
Stop.
 Layout Software
- CRAFT

- BLOCPLAN

- PFAST

- FactoryFLOW

- Layout-iQ

- VIP-PLANOPT

- Flowpath Calculator
 CRAFT in Excel
• Do Example 4
 BLOCPLAN
n −1 n

RD
• Adjacency score
ij ij
i =1 j = i +1
n −1 n

R
i =1 j = i +1
ij

n −1 n

• Rel-dist score d R

i =1 j =i +1
ij ij

• R-score = 1- (rel-dis score- lower bound)/(upperbound-

lower bound)
1 if departments i and j are on the same floor and adjacent
Dij 
0 otherwise

Rij numeric value assigned to the relationship code between

departments i and j,
• n total number of departments, and
• dij rectilinear distance between the centers of departments i and j
 BLOCPLAN
• Do Example 5
PFAST
Layout-iQ
VIP-PLANOPT
Flowpath Calculator
 BLOCPLAN
• Re-layout
– CRAFT-M
• Multi-Floor Layout
– BLOCPLAN