TI4101

Perancangan Tata Letak Pabrik

BASIC ALGORITHMS
FOR THE LAYOUT PROBLEM

Laboratorium Sistem Produksi

Prodi. Teknik Industri
@2018
 Tujuan & Prasyarat
 Tujuan Instruksional Umum
 Mahasiswa mampu merancang tata letak fasilitas sistem
manufaktur, yang meliputi mesin, tempat kerja, dan gudang serta
sistem pemindahan material-nya.

 Tujuan khusus
 Mampu menggunakan algoritma yang tepat untuk menyelesaikan
permasalahan tata letak

2
 OUTLINE

 Introduction
 Heuristic Algorithms
 Software for layout modeling
 Layout issues in modern manufacturing systems

3
 INTRODUCTION

 A model itself does not provide a solution to a

problem

 Algorithms or solution techniques have to be

developed to solve a model. An algorithm is a
step-by-step procedure that finds a solution to a
model and hence to the problem, in a finite
number of steps.

 We introduce algorithms that have been

developed for the layout problem
4
 INTRODUCTION

 Algorithms developed can be divided into two

categories:
 Optimal Algorithms (discussed in Ch. 5)
 Heuristic Algorithms

 All optimal algorithms developed suffer from

disadvantages: the memory and computational
time requirements are extremely high increase
exponentially as the problem size increases.

 Hence, there are many more heuristic algorithms

for solving the layout problem 5
 Heuristic Algorithms

 Can be classified into 3 categories:

 Construction Algorithms

 Improvement Algorithms

 Hybrid Algorithms

6
 Construction Algorithms

 MST (Modified Spanning Tree)

 CORELAP

 PLANET

7
 MST ALGORITHM

 Single-row layout problem

 Similar to the spanning tree algorithm (Heragu,

Kusiak, 1988)

8
MST ALGORITHM

9
Contoh Algorithma MST (1)

Input data
 Clearence dij = 2 feet

Step 1
f’ij= fij (dij + ½ (li + lj)

f’12= 12 (2+ ½ (20+10)

= 204
10
Contoh Algorithma MST (2)

11
 CORELAP

 First construction algorithm, developed by Lee

and Moore (1967)

 It converts qualitative input data (obtained from

ARC) into quantitative data

 CORELAP calculates the Total Closeness Rating

(TCR) for each facility

 Facility with the highest TCR is selected and

placed in the centre of the layout
12
 CORELAP

 If two or more facilities share the highest TCR,

select one with the highest area (if there is still a
tie, select the first such facility).

 Selection of the second facility depends on the

interaction with the permanent facility (placed in
the layout).

 The temporary facility (unselected facility) with

highest adjacency relationship (A, E, I, etc.) with
the permanent facility is selected
13
 CORELAP

 The third and subsequent facilities are selected

on the basis of their relationship with the
permanent facilities.

 The entering facility is placed in the location that

maximizes the PR (placement rating) –For an
example, see Fig. 6.1

14
CORELAP

15
EXAMPLE 2: [ADJACENCY REL]

16
CORELAP

17
 Improvement Algorithms

 2-OPT and 3-OPT

 CRAFT

 SA-CRAFT (Mulyono dan Iskandar, 1994)

18
2-Opt Algorithm

19
Facilities and Sites

20
Example:[2-Opt Algorithm]

21
SOLUTION

22
SOLUTION

23
SOLUTION

24
3-Opt Algorithm

25
 CRAFT
 Computerized Relative Allocation of Facility Technique
(Armour and Buffa, 1963)

 Up till now, It is still popular and widely used in practice

 CRAFT requires the input data:

 Dimension of the building
 Dimension of facilities
 Flow of material and cost per unit load per unit distance
 An initial layout
 Restriction on location of facilities (fixed facilities)

26
 CRAFT

 Given the initial layout, CRAFT computes the

distance between centres of each pair facility
and determine the cost of the initial layout.

 CRAFT considers exchanging the location of

certain pair of facilities

 The facility pairs considered either have the

same area or are adjacent (See Fig. 6.13)

27
CRAFT:[Estimated Cost]

28
 CRAFT

 Each iteration, CRAFT can examine a maximum

n(n-1) possible exchanges, (n=#of facilities)

 The location exchange that result in the greatest

estimated cost reduction is made

 The algorithm is stopped if no two-way

exchange results in a lower cost.

29
 CRAFT:[Exchange facilities]

 CRAFT is also capable of performing:

 Three way exchanges

 Two-way exchanges followed by three way

exchanges

 Three way exchanges followed by two-way

exchanges

30
 CRAFT

 The original version was capable of handling

only 40 facilities (Please check the capability of
CRAFT in the QSB).

 In general, better the starting solution, the better

the final solution.

 This is true with CRAFT also.

31
Example: [CRAFT]

32
Example: [CRAFT]

33
Data Input
CRAFT

34
OUTPUT: [CRAFT]

35
OUTPUT: [CRAFT]

36
OUTPUT: [CRAFT]

37
OUTPUT: [CRAFT]

38
OUTPUT: [CRAFT]

39
OUTPUT: [CRAFT]

40
OUTPUT: [CRAFT]

41
 Hybrid Algorithms

 All improvement algorithms require an initial

layout
 The better the starting solution, the better the
final solution
 A hybrid algorithm uses a construction algorithm
to produce an initial layout and then improve it by
an improvement algorithm.
 BLOCPLAN is a hybrid algorithm.
 R-MAT (Iskandar, 1985)

42
 BLOCPLAN

 Can develop a single-story or multi-story layout

 Can handle quantitative or qualitative data
 Can handle a maximum of 18 facilities
 Three ways of providing flow data:
 ARC
 From-To-Chart
 Product-Routing data
 BLOCPLAN converts flow matrix into an
equivalent relationship chart by dividing the
maximum flow element by 5 (See Table 6.2).
 Then rel chart is used to develop a layout
43
TABLE 6.2

44
 BLOCPLAN

 BLOCPLAN can develop a layout:

 Randomly using a construction algorithm;
 Using an embedded improvement algorithm; or
 Using an automatic search algorithm
 The improvement algorithm executes an
exchange and calculates the adjacency score
and the rel-dist score of the new layout.

45
Adjacency score and Rel-Dist score

46
 BLOCPLAN

 The Criterion used is R-score

 R-score=1 – (rel-dist score-LB)/(UB-LB)
 UB: Upper Bound LB: Lower Bound
 R-score =1 means that the solution is optimal
 Hence, BLOCPLAN is trying to develop the
layout with R-score being close to one.

47
 Software for layout modelling

 CORELAP
 CRAFT
 BLOCPLAN
 FactoryCAD
 FactoryPLAN
 FactoryFLOW
 (See more in IE Solutions magazine, August
1995)

48
 Layout issues
in modern manufacturing systems
 The layout problem discussed has been based on three
assumptions:
 The layout problem is two-dimensional
 Information on future manufacturing activities is known at the time
facility design decisions are made
 The product mix and volume remain fairly constant

 These may have been justified in traditional

manufacturing systems but they no longer hold in modern
systems

49
 Layout Issues in modern
manufacturing systems
 A stable business environment –the traditional
manufacturing systems
 A high level of volatility and uncertainty in the current
industrial climate
 Effective lifetime of a layout is two years (Nicol and
Hollier, 1983)
 The lifetime has decreased further say to one year or less
in the past decade
 Due to the high rate of technological innovations as well
as the frequent changes in product design and functional
demanded by customers
 Re-layout will become more common that layout of new
facilities in the future systems (the Dynamic layout
problem) 50
 Layout issues

 The layout problem is two-dimensional (This is

hold for a manufacturing system)

 It does not apply in an office layout problem –

where facilities are usually located in several
floors

 Manufacturing systems in the future may have to

deal with three-dimensional layout problems –
land prices become to high; building a new plant
costs ten times more than refurbishing an
existing one 51
 Layout issues

 Hence, the manufacturer needs to consider

expansion in vertical dimension –transforming a
2-D layout problem into a 3-D layout one.

 The distance between facilities situated in

different floors may be nonlinear.

 Many algorithms are available the multifloor

problem (e.g. BLOCPLAN, SPACECRAFT,
CRAFT 3-D, MULTIPLE)

52