Facilities Planning and Design

INE 425
Lec 8

1
CHAPTER 7
LAYOUT
 Pairwise Exchange Method
• The majority of layout problems involves the
redesign of an existing facility, which is
typically
Alternative 3 no 2 triggered by the addition of new
machines, changes in product mixes, decisions
related to the contraction and expansion of
storage areas, or a simple realization that the
old layout is no longer adequate for its current
needs.
• Given an existing layout and the problem is to
6Xcome
6X 66 up with an improved layout.
 Pairwise Exchange Method
• We will discuss the layout improvement based on
minimizing the total cost of transporting materials
among all departments in a facility.
Alternative 3 no 2
• We will assume that the distance between
departments is rectilinear and is measured form the
department centroids.
• The pair wise exchange procedure is illustrated
through the following example.
• Consider four department of equal size. The material
flows between department are given in table 1, and
6X 66 existing layout is shown in Figure 1
The
6X
 Pairwise Exchange Method

Alternative 3 no 2

Table 1. Material flow matrix

6X
6X66

Figure 1. Layouts corresponding to each iteration

 Pairwise Exchange Method
• The distance-based objective function value (or “total
cost”) for the existing layout is computed as follows:
• TC1234 3=no
Alternative 10(1)
2 + 15(2) + 20(3) + 10(1) + 5(2) + 5(1) = 125
• The subscript notation indicates the order of the
departments in the initial layout.
• The pairwise exchange method is simply states that for
each iteration, all feasible exchanges in the locations of
department pairs are evaluated and the pair that
results in the largest reduction in total cost is selected.
• Since all departments areas are assumed to be of equal
6X
6X66the feasible exchanges are 1-2, 1-3, 1-4, 2-3, 2-4,
size,
and 3-4.
 Pairwise Exchange Method
• The distance matrix is recomputed each time
an exchange is performed.
Alternative 3 no 2

Table 2 Distance Matrix Based on Existing Layout

• The layout costs resulting from the above
exchanges are
6X
6X66
 Pairwise Exchange Method
1 2 3 4
• 1St

Alternative 3 no 2

• TC2134(1-2) = 10(1) + 15(1) + 20(2) + 10(2) + 5(3) + 5(1) = 105

• TC3214(1-3) = 10(1) + 15(2) + 20(1) + 10(1) + 5(2) + 5(3) = 95
• TC4231(1-4) = 10(2) + 15(1) + 20(3) + 10(1) + 5(1) + 5(2) = 120
• TC1324(2-3) = 10(2) + 15(1) + 20(3) + 10(1) + 5(1) + 5(2) = 120
• TC1432(2-4) = 10(3) + 15(2) + 20(1) + 10(1) + 5(2) + 5(1) = 105
• 6X
6X66
TC1243(3-4) = 10(1) + 15(3) + 20(2) + 10(2) + 5(1) + 5(1) = 125
• Thus, we select pair 1-3 and perform the exchange in the
layout
 Pairwise Exchange Method
3 2 1 4
• 2nd

Alternative 3 no 2

• TC3124(1-2) = 10(1) + 15(1) + 20(2) + 10(1) + 5(1) + 5(3) = 95

• TC1234(1-3) = 10(1) + 15(2) + 20(3) + 10(1) + 5(2) + 5(1) = 125
• TC3241(1-4) = 10(2) + 15(3) + 20(1) + 10(1) + 5(1) + 5(2) = 110
• TC2314(2-3) = 10(2) + 15(1) + 20(1) + 10(1) + 5(3) + 5(2) = 90
• TC3412(2-4) = 10(1) + 15(2) + 20(1) + 10(3) + 5(2) + 5(2) = 105
• 6X
6X66
TC4213(3-4) = 10(1) + 15(1) + 20(2) + 10(2) + 5(1) + 5(3) = 105
• The pair 2-3 selected with a total cost value of 90
 Pairwise Exchange Method
2 3 1 4
• 3rd

Alternative 3 no 2

• TC1324( 1-2) = 10(2) + 15(1) + 20(3) + 10(1) + 5(3) + 5(1) = 120

• TC2134( 1-3.) = 10(1) + 15(1) + 20(2) + 10(2) + 5(3) + 5(1) = 105
• TC2341(l-4) = 10(3) + 15(2) + 20(1) + 10(1) + 5(2) 4- 5(1) = 105
• TC3214(2-3) = 10(1) + 15(2) + 20(1) + 10(1) + 5(2) + 5(3) = 95
• TC4312(2-4) = 10(1) + 15(1) + 20(2) + 10(2) + 5(3) + 5(1) = 105
• TC2413(3-4) = 10(2) + 15(1) + 20(1) + 10(3) + 5(1) + 5(2) = 100
• Since
6X66the lowest total cost for this iteration, 95, is worse than
6X
the total cost value of 90 in the second iteration, then the
procedure is terminated. Thus, the final layout arrangement is
2-3-1-4.
 Graph-Based Construction Method
• The graph-based method is a construction-type
layout algorithm; it has its roots in graph theory.
• It is 3often
Alternative no 2 used with an adjacency-based objective.
The recognition of the usefulness of graph theory as
a mathematical tool in the solution of facilities
planning problems dates back to the late 1960s and
early 1970s .
• Graph theory methods have similarities with the SLP
method developed by Muther

6X
6X66
 Graph-Based Construction Method
• Consider the block layout shown in Figure 2a . We
first construct an adjacency graph, where each node
represents a department, with a connecting arc
Alternative 3 no 2
between two nodes indicating that two departments
share a common border.

6X
6X66
(a) (b)
Figure 2 Adjacency graphs for alternative block layouts
 Graph-Based Construction Method
• A similar graph is constructed for the alternative
block layout shown in Figure 2b
• Which
Alternative 3 noblock
2 plan layout is better? We can score
each block plan layout by summing the numerical
weights assigned to each arc. On this basis, block
plan layout (2b ) is better than block plan
layout(2a)with scores 71 and 63, respectively. Thus,
finding a maximally weighted block plan layout is
equivalent to obtaining an adjacency graph with the
maximum sum of arc weights.
6X
6X66
 Graph-Based Construction Method
• We observe that the two graphs shown in Figure 2
are subgraphs of the graph shown in Figure 3b, which
is derived from the relationship chart in Figure 3a.
Alternative 3 no 2

6X
6X66

Figure 3 Relationship chart and relationship diagram

 Graph-Based Construction Method
• Before we describe a method for determining
adjacency graphs, we first make the following
observations:
Alternative 3 no 2
(a) The score does not account for distance, nor does it account
for relationships other than those between adjacent
departments.
(b) Dimensional specifications of departments are not
considered; the length of common boundaries between
adjacent departments are also not considered.
(c) The arcs do not intersect; this property of graphs is called
planarity. We note that the relationship diagram is usually a
6Xnonplanar graph.
6X66
(d) The score is very sensitive to the assignment of numerical
weights in the relationship chart.
 Graph-Based Construction Method Procedure
• There are two strategies, we can follow in developing a
maximally weighted planar adjacency graph.
• One way is to start with the relationship diagram and
Alternative 3 no 2
selectively prune connecting arcs while making sure that
the final graph is planar.
• A second approach is to iteratively construct an
adjacency graph via a node insertion algorithm while
retaining planarity at all times. A heuristic procedure is
described below:
• Step 1: From the relationship chart in figure 3a, select the
department pair with the largest weight. Thus
6X
6X 66
departments 3 and 4 are selected to enter the graph.
 Graph-Based Construction Method

Alternative 3 no 2

6X
6X66
 Graph-Based Construction Method Procedure
• Step 2: Select the third department to enter. The third
department is selected based on the sum of the weights
with respect to the departments 3 and 4. From figure 4a
Alternative 3 no 2 2 is chose with a value of 25.
department
• Step 3: The fourth department to enter by evaluating the
value of adding one of the unassigned departments
represented by a node on a face of the graph. A face of a
graph is a bounded region of a graph. The value of adding
departments 1 and 5 are 27 and 9, respectively.
Department 1 is selected and placed inside the region 2-
3-4, as shown in figure 4b.
6X
6X66
 Graph-Based Construction Method
•

Alternative 3 no 2

6X
6X66

Figure 4 Steps of the graph-based procedure

 Graph-Based Construction Method Procedure
• Step 4: Department 5 can be inserted on faces 1-2-3,
1-2-4, 1-3-4, and 2-3-4. Inserting 5 on faces 1-2-4 and
2-3-4 yields identical values of 9. We select arbitrarily
Alternative 3 no 2
1-2-4. the final adjacency graph is given in figure 4c.
This solution is optimal with a total sum of arc
weights equal to 81.
• Step 5: A block layout based on the final adjacency
graph is shown in figure 5. The manner by which we
constructed the block layout is analogous to the SLP
method.
6X
6X66
 Graph-Based Construction Method
•

Alternative 3 no 2

6X
6X66
Figure 5 Block layout from the final adjacency graph.
 CHAPTER 8
COMPUTER ASIDED LAYOUT
 Computer Aided Layout
• Enhance productivity & Quality of Solution
• Can not Replace human Judgment
• Types3 of
Alternative no Algorithms
2
– Type of Input Data
• Qualitative Data- REL Chart
• Quantitative Data – F-T chart (from-to chart, flow-between)
– Objectives:
• Minimizing the sum of flow times distance (Distance-Based
Approach)
• Maximizing an adjacency score (Adjacency-Based
6X
6X66Approach)
 Computer Aided Layout
Distance-based Algorithms
• Objective function Minimize flow * distance
– Called
Alternative 3 noa2“distance-based” objective
– Distance is measured rectilinearly from the department
centroid
– Input is a from-to chart

(1)
fij = amount of flow (or, number of trips or unit loads) between
departments i and j
6X Cij = cost of moving a unit load between departments i and j
6
6X 6
dij = distance between departments i and j
 Computer Aided Layout
Adjacency-based Algorithms
• Objective function Maximize adjacency
Input
Alternative is an
3 no 2 activity relationship chart
Sum of all adjacent relationship values
Easy to use and intuitive
But disregards distance between non-adjacent departments
Means you can generate layouts with similar scores but
vastly different travel distances
(2)

•6XXij6=6 1 if department s i and j are adjacent

6X
• Xij = 0, otherwise
• fij = amount of flow number between i and j
 Computer Aided Layout
• Normalized adjacency score Or Efficiency Rating can
be calculated using this equation
Alternative 3 no 2

• Note that the normalized adjacency score (which is also

known as the efficiency rating) is obtained simply by dividing
the adjacency score obtained from Equation (1) by the total
flow in the facility.
• As a result, the normalized adjacency score is always between
6X 66 and 1. If the normalized adjacency score is equal to 1, it
zero
6X
implies that all department pairs with positive flow between
them are adjacent in the layout.
 Classification of Algorithms Layout
Representation Format
Layout representation format
– Discrete
• The3area
Alternative no 2 of each department is rounded off to the nearest integer
number of grids.
• A smaller grid size yields a finer resolution and gives more flexibility in
department shapes, but
• Results in a larger number of grids which complicates computations.
– Continuous
• Does not use a grid
• More flexible but more difficult to use
• Usually limited to rectangular building and departments

6X
6X66

Discrete Continuous
 Examples of Split and Unsplit departments

Alternative 3 no 2

6X
6X66
Figure 6 Examples of split and unsplit departments
 Classification of Algorithms
 Construction-based
– Develop ‘from scratch' and progressively build layout
– Example
Alternative 3 no 2
• ALDEP (Automated Layout Design Program)
• CORELAP (Computerized Relationship Layout Planning)
 Improvement-based
– Start with an initial layout and try to improve it
through incremental changes
– Example
6X • Pair-wise exchange (TWOWAYX)
6
6X 6
• CRAFT (Computerized Relative Allocation of Facilities
Technique)
 CRAFT
• First computer-aided layout algorithm (1963)
• The input data is represented in the form of a From-
To chart,
Alternative 3 no 2 or qualitative data.
• The main objective behind CRAFT is to minimize total
transportation cost:

• Improvement-type layout algorithm

6X
6X66
 CRAFT Steps
1. Calculate centroid of each department and rectilinear
distance between pairs of departments centroids (stored in a
distance matrix).
Alternative 3 no 2
2. Find the cost of the initial layout by multiplying the
– From-To (flow) chart,
– unit cost matrix, and
– From-To (distance) matrix
3. Improve the layout by performing all-possible two or three
way Exchanges way
– At each iteration, CRAFT selects the interchange that
results in the maximum reduction in transportation costs
6X–6These interchanges are continued until no further
reduction is possible
 CRAFT Steps
Given initial layout

Alternative 3 no 2 Calculate centroid

6XGiven
6 load Dept.
 CRAFT Steps
Or calculate from to chart distance as

Alternative 3 no 2

6X 6 Calculate the total distance .

The pair wise exchange A-B, A-C, A-D, and so on
Here we exchange D-E
 CRAFT Steps
D-E

Alternative 3 no 2

6X 6
 CRAFT Steps
C-D

Alternative 3 no 2

6X 6
 CRAFT Steps
B-C

Alternative 3 no 2

The score is
increase
We select
the previous layout
6X 6
 Example (page 334)
• Consider a manufacturing facility with seven departments. The
department names, their areas, and the from-to chart are shown
in Table 3. We assume that all the cij values are set equal to 1.
Alternative 3 no 2Table 3 Departmental Data and From-To Chart

6X
6X66
 From-To (distance) matrix
A B C D E F G H

A - 6 5.5 6.75 12.5 15 9.75 13.5

Alternative 3 no 2
B - 5.5 5.5 11.5 14 14.75 12.5

C - 6.25 7 9.5 9.25 8

D - 12.25 8.75 15.5 7.75

E - 3.5 3.25 8

F - 6.75 4.5

G - 11.25
6X
6X66
H -
 CRAFT
• Initial CRAFT layout and department centroids for
Example ( z = 2974 X 20 = 59,480 units).
Alternative 3 no 2

6X
6X66
 CRAFT
• Intermediate CRAFT layout obtained after
exchanging departments E and F (z = 2953 X 20 =
59,060 units).
Alternative 3 no 2

6X
6X66
 CRAFT
• Final CRAFT layout (z = 2833-50 X 20 = 56,670 units).

Alternative 3 no 2

6X
6X66
 BLOCPLAN
• Like MicroCRAFT, arranges departments in bands
• Uses a relationship chart as well as a from-to chart
– Can be used only one at a time
Alternative 3 no 2
• Objective function: Measures layout “cost” using
– distance based, or
– adjacency-based, or
– REL-DIST
• Number of bands determined by the program
– Usually two or three bands
• Band widths may vary
• Departments contained in only one band
– departments are rectangular
6X 6
• Uses continuous layout representation
• Can do both construction and improvement
 CORELAP
• Computerized Relationship Layout Planning
• Construction algorithm
• Inputs
– Relationship
Alternative 3 no 2 chart
– Number of departments
– Area of each department
– Weight of REL chart entries
• Calculates a total closeness rating (TCR) from the relationship chart
• Department with highest TCR is placed in the center
• Tie-breaker is area size
• Next department chosen by the relationship with first department
– Start with A relationships
– If no A’s, then E’s, I’s, etc.
• Calculate the placement rating
6X 6 on relationship weights
– Based
– Sum of weights of adjacent departments
– Tie breaker is boundary length
 CORELAP
Example
Use CORELAP to determine the layout for the given relationship
TCR
Alternative 3 no 2

Select 6X 6
the greater TCR
Select the Department 3, then select the department with the high relation with Dept. 3
We find Dept. 2, then select the Department with high relation with Dept. 3, 2
We select Dept. 4
 CORELAP
The layout is

Alternative 3 no 2

The total block required is 35

use 5x7 block area
6X 6
 • Also,Refer to illustrated example on lec 8
that solved by TCR (CORELAP) approach
Alternative 3 no 2

• Read the solved examples on pages (334-

358)

6X 6
Thank you