PENGEMBANGAN ALGORITMA ANT COLONY OPTIMIZATION UNTUK MENYELESAIKAN PERMASALAHAN LAYOUT Risang Galih Bhaktiaji 2506 100 105
Dosen pembimbing: Arief Rahman S.T., M.Sc.
pendahuluan PROCESS
PRODUCT
GT
Minimasi material handling
ABS MODEL
GRAPHTHEORY
METAHEURISTIK
GA, CROSS ENTROPY, ACO, PSO, DLL
PENDAHULUAN Menentukan susunan mesin pada shop floor dengan konstrain dimensi shop flor
to solve
Salah satu metode terbaik untuk menyelesaikan QAP (Stuzle and Dorigo, 1999)
LAYOUT PROBLEM
GT Layout / CMS Dewi Pratiwi, 2009
pendahuluan • Rumusan Masalah “Pengembangan algoritma ACO untuk perancangan ulang tata letak fasilitas untuk mengurangi total jarak perpindahan part antar fasilitas pada kasus pembentukan cellular manufacturing system di lantai produksi PT Alstom.”
• Tujuan Penelitian 1. 2. 3.
Mengembangkan algoritma ACO untuk kasus penyusunan layout. Mengimplentasikan metode ACO untuk penyelesaian problem layout pada suatu program komputer. Menganalisa performansi algoritma ACO terhadap algoritma GA.
Tinjauan pustaka LAYOUT
Fungsi Tujuan 𝑐𝑖𝑗 𝑑𝑖𝑗 𝑓𝑖𝑗 𝑖
(minimum material handling cost)
𝑗
GT LAYOUT / CMS
MENGELOMPOKKAN MESIN BERDASARKAN PART FAMILIES
Model matematis • Min
𝑗 𝑐𝑖𝑗 𝑑𝑖𝑗 𝑓𝑖𝑗
𝑖
Subject to •
𝑖 𝑖=1
𝑗 𝑗=1 𝑑𝑖𝑗
•
𝐶 𝑙=1 𝑥𝑖𝑙
•
𝐶 𝑖=1 𝑥𝑖𝑙
,
,
≤𝐶
Fungsi tujuan meminimasi material handling cost Ukuran mesin tidak boleh melebihi ukuran shopfloor
𝑙 = 1,2, … , 𝐶
Satu lokasi hanya diisi satu mesin
𝑙 = 1,2, … , 𝐶
Satu mesin menempati satu lokasi
Ant colony optimization Berdasarkan perilaku semut ketika berjalan dari sarangnya untuk mencari makanan Semut k dari node i akan menuju ke node j dengan probabilitas Pembentukan rute
(i, j ) (i, j ) , ( i , u ) ( i , u ) pk (i, j ) uM k 0
if j M k others
Evaluasi rute
Update feromon
N
i , j (1 ) i , j ik, j k 1
Aco untuk layout
ηij ηij=1/dij
visibilitas
Agar tiap mesin punya peluang untuk didekatkan
ηij=1/fij+1
ACO for TSP
ACO for Layout
dij = jarak antar kota i & j
fij = frekuensi antar mesin i & j
Critical review • Layout 1. Algoritma Genetika (Pratiwi 2009) 2. Algoritma Corelap, Planar Graph, dan 2-OPT (Sholikhin 2009) 3. Manufaktur Sellular (Fitriasari 2008) • ACO 1. ACO for inter-cell (Solimanpur 2002) 2. ACO for machine–part cell formation (Xiangyong 2010) 3. ACO for TSP (Dorigo 1997) 4. ACO for CLRP (Rogam 2010)
ACO untuk Layout dengan Batasan Ukuran Fasilitas
Metodologi penelitian START
Pengembangan Algoritma ACO untuk Problem Layout
Validasi Model
Algoritm a Valid?
A
Metodologi penelitian A
Eksperimen
Bandingkan dengan Metode Lain
Analisis & Interpretasi Kesimpulan & Saran
FINISH
CONTOH SOAL Nama Part Part 1 Part 2 Part 3 Part 4 Part 5
1 2 3 4 2
Urutan Mesin 2 3 4 3 4 4 1 2 3 2 1 3 2
Matriks frekuensi antar mesin 1 2 3 4
1 2 3 4 0 35 0 20 35 0 100 0 0 100 0 45 20 0 45 0
3
Frekuensi 10 15 20 5 25
Mesin Ukuran 1 3x3 2 4x4 3 2x2 4 5x5 Shop Floor 10x10
Dengan enumerasi No
Rute
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1234 1243 1342 1324 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321
Total Biaya 1155 885 1105 980 890 1835 1495 1225 1170 1170 1225 1255 1210 1135 1055 1025 1445 1165 1120 1005 1375 1605 1505 1505
Hasil optimal
1 1 1
1 1 1
1 1 1
4 4 4 4 4
4 4 4 4 4
4 4 4 4 4
2 2 2 2 4 4 4 4 4
2 2 2 2 4 4 4 4 4
2 2 2 2 3 3
2 2 2 2 3 3
Penataan mesin dalam shopfloor
Dengan aco 1. Inisialisasi
Initial Parameter
α:1
Parameter kontrol feromon
β:3
Parameter kontrol visibilitas
ρ : 0.5
Feromon awal
0.01 0.01 0.01 0.01 0.01 0.01
Koefisien penguapan
0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01 0.01
0.01 0.01 0.01 0.01
Visibilitas ( ij f ij 1 )
0.01 0.01 0.01 0.01
0.01 0.01 0.01 0.01
0.01 0.01 0.01 0.01
0 0,77 0,07 0,47 η = 0,77 0 2,07 0,07 0,07 2,07 0 0,97 0,47 0,07 0,97 0
Dengan aco 2. Pembentukan Urutan Mesin 1. Dimulai dari mesin yang dipilih secara random 2. Pemilihan mesin berikutnya menggunakan probabilitas (i, j) (i, j) / (i, u) (i, u) , if j M k p k (i, j ) uM k 0, others
Perpindahan dari node-2
Perpindahan dari node-3 i,j 3-1 3-2 3-3 3-4
pij
p cumulative
random
0,000001 0,916484 0 0,083515
0,000001 0,916485355 0,916485355 1
0,419598
Urutan yang terbentuk
i,j 2-1 2-2 2-3 2-4
pij 1 0 0 0
p cumulative 1 1 1 1
random 0,923794
Perpindahan dari node-1
3-2-1-4
i,j 1-1 1-2 1-3 1-4
pij 0 0 0 1
p cumulative random 0 0 0,428578 0 1
DENGAN ACO 3. Evaluasi Urutan Mesin
3-2-1-4
Total biaya = 1055
3 3
3 3
4 4 4 4 4
4 4 4 4 4
2 2 2 2 4 4 4 4 4
2 2 2 2 4 4 4 4 4
2 2 2 2 4 4 4 4 4
2 2 2 2
1 1 1
1 1 1
1 1 1
DENGAN ACO 4. Update feromon N
i , j (1 ) i , j k 1
k i, j
𝑘
ρ : 0.5 Rute ant k: 3 – 2 – 1 – 4
τ=
0.0500 0,05 0.0700 0,059479 0.0545 0,05 0.0582 0,059479
𝑄
∆𝜏𝑖,𝑗 = 𝑓 = 10/1055 = 0,0094
0.0700 0.05450,05 0.0582 0,059479 0,059479 0.0500 0.1613 0,05 0.0669 0,059478673 0,05 0.0669 0.05000,05 0.0669 0,059479 0,05 0.1613 0.0669 0.0500 0,05 0,05 0,05
𝑘
k urutan mesin nilai solusi semut 1 3-2-1-4 1055 semut 2 1-2-3-4 1155 semut 3 4-3-2-1 1505 semut 4 2-4-3-1 1505 1-3-2-4 980 semut 5 1-2-4-3 885 semut 6 3-1-4-2 1135 semut 7 3-4-2-1 1165 semut 8 4-1-2-3 1120 semut 9 4-2-3-1 1605 semut 10
DENGAN ACO 5. Kriteria Pemberhentian Iterasi maksimum 6. Hasil paling optimal
Solusi Terbaik Dua Iterasi Iterasi 1 2
Urutan mesin 1-2-4-3 1-2-4-3
Total Biaya MH 885 885
Eksperimen dan analisis Urutan Proses beserta Volume, Batch dan Frekuensinya CM
Part
CM 1
Part 1
10
Part 2
10
Part 3
9
Part 5
CM 2
Urutan Mesin
Volume
Batch
166
1
166
332
9
37
1
1044
15
70
2
3
16
4
4
Part 7
1
4
6
5376
80
68
Part 8
2
7
4
996
30
34
Part 12
10
1
264
1
264
Part 15
2
5
72
2
36
Part 17
10
10
1
10
Part 20
2
8
5
200
13
16
Part 23
2
1
3
576
144
4
Part 24
2
1
192
96
2
Part 4
15
19
1028
11
94
Part 6
16
720
90
8
Part 9
16
18
996
30
34
Part 10
16
18
2988
498
6
Part 11
16
22
18
377
42
9
Part 13
17
21
13
154
1
154
Part 14
15
13
36
1
36
Part 16
17
12
14
412
13
32
Part 18
17
21
13
20
12
1
12
Part 19
15
17
19
13
10
1
10
Part 21
15
12
14
19
130
15
9
Part 22
16
18
13
23
8
8
1
6
11 1
10
13
20
23
23
Sumber: Dewi Pratiwi, 2009
Frekuensi
Eksperimen dan analisis Dimensi Mesin CM
Nama Mesin
No. Mesin
Panjang
Lebar
1
Manual Drilling Machine
1
4
8
CNC Burning Cutting
2
5
15
CNC Lathe Machine
3
2
5
Plate Bending Roll
4
6
12
Layout Marking
5
1
1
Hydrostatic Testing
6
14
27
Cleaning before Harp Asy
7
13
14
Grinding after CNC BC
8
1
1
Band Saw
9
1
2
Heat Treatment Slot Furnace Low Temp Lathe Machine
10
5
5
11
2
3
Pipe Bender 3"4"
12
3
6
Lathe Machine
13
5
3
Pneum Scarfing Machine
14
2
2
Bug-O Prog Saddle & Elbow Cutter Shearing Machine
15
2
10
16
5
9
Band Saw
17
5
2
Press Break
18
5
8
Heat Treatment Slot Furnace Low Temp CNC Drilling Machine
19
5
5
20
10
17
Con-O Press
21
2
10
Iron Worker
22
2
7
Manual Drilling Machine
23
4
4
2
Sumber: Dewi Pratiwi, 2009
Ukuran Shopfloor CM 1 2
Ukuran 26 x 51 17 x 41
EKSPERIMEN DAN ANALISIS f=36 f=280 • CM1 Urutan mesin : 7 4 2 5 11 8 3 1 10 6 9 f=166 Total biaya MH = 9.028 7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
7 7 7 7 7 7 7 7 7 7 7 7 7 7
4 4 4 4 4 4 4 4 4 4 4 4
11 11 11 11 11 11
8
3 3 3 3 3
3 3 3 3 3
1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
10 10 10 10 10
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
10 10 10 10 10
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
4 4 4 4 4 4 4 4 4 4 4 4
9 9
4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
5
Frekuensi antar mesin 1 2 3 4 5 6 7 8 9 10 11
1 2 0 6 6 0 4 4 68 0 16 36 0 0 0 34 0 16 70 0 280 0 0 0
3 4 5 6 7 8 9 10 11 4 68 16 0 0 0 70 280 0 4 0 36 0 34 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 68 34 0 0 0 0 0 0 0 0 0 16 0 0 36 0 68 0 0 0 0 0 166 0 0 34 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 166 0 0 0 0 0 0 0 36 0 0 0 0 0 0
EKSPERIMEN DAN ANALISIS f=166 f=166 • CM2 Urutan mesin : 9 12 4 5 7 11 3 1 6 10 2 8 f=166 Total biaya MH = 9.598,5
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 6 6
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 6 6
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 6 6
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 5 5 5 5 5 5 5 5 6 6
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 5 7 7 5 7 7 5 7 7 5 7 7 5 7 7 5 7 7 5 7 7 5 5 6 10 10 6 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 7 7 7 7 7 7 7
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 7 7 7 7 7 7 7
9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 7 7 7 7 7 7 7
12 12 12 12
12 12 12 12
12 12 12 12
12 12 12 12
4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4
11 11 11 11 11 11 11
11 11 11 11 11 11 11
3 3
3 3
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
2 2 2
2 2 2
2 2 2
2 2 2
2 2 2
8 8 8 8 8
8 8 8 8 8
8 8 8 8 8
8 8 8 8 8
8 8 8 8 8
Frekuensi antar mesin 1 2 3 4 5 6 7 8 9 10 11 12
1 0 0 41 9 0 32 0 0 0 0 0 0
2 3 4 5 6 7 8 9 10 11 12 0 41 9 0 32 0 0 0 0 0 0 0 0 36 0 0 1 10 166 166 0 1 0 0 0 0 0 0 9 0 0 0 0 36 0 0 0 10 0 94 0 0 0 0 0 0 0 0 0 41 0 0 0 9 0 0 0 10 0 0 0 0 0 166 0 0 1 0 0 41 0 0 0 0 0 9 0 10 9 94 0 0 0 0 0 0 0 0 166 0 0 0 0 0 0 0 0 0 166 166 0 0 0 166 0 0 0 0 0 0 0 0 0 9 0 9 0 0 0 0 0 1 0 0 0 0 0 0 166 0 0 0
EKSPERIMEN DAN ANALISIS hubungan jumlah ITERASI dengan pencapaian hasil optimal
• CM1 JUMLAH ITERASI
REPLIKASI KE-
250
26
500
3
1000
6
5000
19
Jumlah Replikasi
26
19
6 3
• CM2
250
JUMLAH ITERASI
REPLIKASI KE-
250
26
500
3
1000
6
5000
19
Jumlah Replikasi
Dipengaruhi oleh solusi yang terbentuk di iterasi awal dan bilangan random untuk memilih node pertama
500 1000 Jumlah Iterasi
5000
13 10 9
250
500 1000 Jumlah Iterasi
5000
EKSPERIMEN DAN ANALISIS PERBANDINGAN GA DAN ACO Perbandingan Hasil GA dan ACO
CM 1 2
Total Biaya GA ACO 11.047 9.028 15.076 9.598,5
GAP 18,3% 36,2%
Kemungkinan penyebab: 1. Kurangnya populasi awal yang dibangkitkan sehingga solusi kurang bervariasi untuk kemudian dilakukan cross over dan mutasi 2. Kurangnya jumlah replikasi
Kesimpulan
1. Modifikasi ACO untuk penyelesaian layout adalah dengan mengubah rumus visibilitas menjadi berdasarkan frekuensi dan biaya perpindahan per satuan jarak dengan rumus ηij= ( fij*cij+1). 2. Algoritma Ant Colony Optimization terbukti dapat digunakan untuk menyelesaikan permasalahan penyusunan layout yang memiliki batasan ukuran shopfloor tertentu. 3. ACO mampu memberikan hasil yang lebih baik dibandingkan dengan GA pada kedua sel manufaktur yang menjadi objek penelitian. Pada sel manufaktur 1 terjadi perbaikan sebesar 18,3%, sedangkan pada sel manufaktur 2 terjadi perbaikan sebesar 36,2%.
4. Jumlah iterasi tidak menunjukkan pengaruh pada jumlah replikasi yang harus dilakukan untuk mendapatkan hasil yang optimal.
saran 1. Digunakan set data dengan ukuran yang lebih bervariatif dan lebih besar untuk menguji algoritma ACO agar hasil uji performansinya lebih valid. 2. ACO dapat digabungkan dengan algoritma lain untuk membentuk algoritma hybrid. Penggabungan dengan algoritma lain diharapkan mampu menghasilkan solusi yang lebih baik dan dapat membangkitkan urutan yang lebih random sehingga hasil lebih banyak.
Daftar pustaka 1.
2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Aribowo, N. (2008), Perancangan Ulang Tata Letak Fasilitas Produksi dengan Menggunakan Algoritma CORELAP, Algoritma 2-OPT, dan Algoritma PLANAR GRAPH untuk Meminimasi Biaya Material handling (Studi Kasus di PT. Swadaya-Gresik,. Laporan Tugas Akhir Teknik Industri - ITS. Benjaafar, S. (2000), “Design of Flexible Plant Layout”, IIE Trans vol.32 (4), hal 309-322. Dorigo, M. and L. M. Gambardella. (1997), "Ant colonies for the travelling salesman problem", Biosystems 43(2): 73-81. Fitriasari, I. (2008), Perancangan Ulang Tata Letak Fasilitas Produksi dengan Pendekatan Manufaktur Seluller, Laporan Tugas Akhir Teknik Industri - ITS. Heragu, S. (1997), Facilities Design, Boston: WS Publishing Company. Heragu, S. (2006), Facilities Design Second Edition, Lincoln: iUniverse, Inc. Prasetyawan, Y. (2006), “Perbaikan Tata Letak Lini Produksi O-5 in XYZ Ltd”, Seminar Nasional Mesin dan Industri, Universitas Tarumanegara, Jakarta. Pratiwi, D. (2009), Perancangan Ulang Tata Letak Fasilitas Produksi Dengan Pendekatan Hybrid Layout Pada PT. Alstom Power Energy System Indonesia, Laporan Tugas Akhir Teknik Industri - ITS. Santosa, B., Willy, P. (2011), Metoda Heuristik Konsep dan Implementasi, Surabaya: Guna Widya. Sholikhin. (2009), Desain Relayout dengan Menggunakan Algoritma Corelap, Planar Graph, dan 2OPT untuk Meningkatkan Performansi Perusahaan (Studi Kasus: PT Djitoe Indonesia Tobacco Coy), Laporan Tugas Akhir Teknik Industri - ITS. Solimanpur, M., Vrat, P., Shankar, R. (2004), “Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing layout problem in cellular manufacturing”, European Journal of Operation Research vol.157, hal. 592-606. Tompkins, J. A., White, J. A., Bozer, Y. A., & Tanchoco, J. M. (2003), Facilities Planning Third Edition, New York: Jhon Wiley & Sons, Inc. Wignjosoebroto, S. (2003), Tata Letak Pabrik dan Pemindahan Bahan Edisi Ketiga, Surabaya: Guna Widya. Xiangyong, Li., Baki, M. F., Aneja, Y. P. (2010), “An ant colony optimization metaheuristic for machine– part cell formation problems”, Computers & Operation Research vol.37, hal. 2071-2081.
