Seminar Nasional IENACO-2014
ISSN: 2337-4349
PENJADWALAN PRODUK PAINTED DI PT. X DENGAN ALGORITMA BRANCH AND BOUND UNTUK MEMINIMASI MEAN FLOW TIME Lely Herlina1*, Ary Kurniati2, Bobby Kurniawan3 1,2,3
Jurusan Teknik Industri, Fakultas Teknik, Universitas Sultan Ageng Tirtayasa Jl. Jend. Sudirman Km3, Cilegon Banten * Email:
[email protected]
Abstrak PT. X adalah perusahaan manufaktur yang bergerak pada pelapisan metal (ZINCALUME®) dan pelapisan cat (COLORBOND®). Pembuatan kedua produk tersebut melewati plan produksi yang dinamakan Metal Coating Line 2 (MCL 2). Produk pelapisan cat atau painted paling banyak dipesan oleh konsumen khususnya di MCL 2, sehingga dibutuhkan waktu pengerjaan produk yang cepat dengan cara menjadwalkan produk secara tepat. Metode penelitian yang digunakan untuk menjadwalkan produk painted adalah algoritma branch and bound. Penelitian dilakukan dengan tujuan untuk meminimasi mean flow time pada MCL 2. Usulan penjadwalan dengan algoritma branch and bound ini akan dibandingkan dengan penjadwalan eksisiting di perusahaan. Penjadwalan eksisting pada perusahaan yaitu FCFS (First Come First Served) dimana order yang datang terlebih dahulu, akan diproses pada plan produksi. Penjadwalan ini menggunakan sistem batch. Pembagian batch berdasarkan dimensi dari produk painted, yaitu batch pertama dengan dimensi 0,20 x 914mm dan batch kedua dengan dimensi 0,25 x 914mm. Berdasarkan pengolahan data diperoleh nilai mean flow time untuk batch 0,20 x 914mm menggunakan algoritma branch and bound adalah 18,42 jam sedangkan nilai mean flow time pada kondisi eksisting 43,23 jam. Untuk batch 0,25 x 914mm, nilai mean flow time pada algoritma branch and bound adalah 147,13 jam sementara nilai mean flow time pada kondisi eksisting 182,76 jam. Penurunan mean flow time antara kondisi eksiting dengan menggunakan algoritma branch and bound pada batch 0,20 x 914 mm dan 0,25 x 914 mm sebesar 57% dan 19%. Kata kunci: Algoritma Branch And Bound, Batch, FCFS (First Come First Served), Mean Flow Time
1.
PENDAHULUAN PT. X adalah perusahaan manufaktur yang bergerak di bidang pelapisan metal (ZINCALUME®) dan pelapisan cat (COLORBOND®). Produk utama pelapisan metal (ZINCALUME®) dinamakan produk bare sedangkan untuk produk pelapisan cat (COLORBOND®) disebut produk painted. Pembuatan kedua produk dilakukan pada Metalic Coating Line (MCL) 2 yang merupakan line baru di PT.X. Penelitian difokuskan pada produk painted karena produk ini lebih banyak dipesan oleh konsumen sehingga dibutuhkan waktu pengerjaan produk yang cepat dengan cara menjadwalkan produk secara tepat. Penjadwalan (scheduling) menurut Kenneth R.Baker (2008) yaitu proses pengalokasian sumber untuk memilih sekumpulan tugas dalam jangka waktu tertentu. Pengertian ini mengandung arti bahwa penjadwalan merupakan sebuah fungsi pengambilan keputusan, yaitu menentukan jadwal yang paling tepat. Pengambilan keputusan ini bertujuan untuk mencapai keinginan konsumen dan target produksi yang diinginkan oleh perusahaan. Algoritma penjadwalan yang diusulkan untuk menjadwalkan produk painted adalah algoritma Branch & Bound. Pada algoritma Branch and Bound, terdapat tiga buah bagian utama, yaitu : ekspresi batas bawah (Lower Bound (LB)), strategi pencarian dan pencabangan (branching). Di dalam prosedur ini, suatu masalah dipecah menjadi beberapa sub masalah yang merepresentasikan pembagian kerja secara parsial. Simpul-simpul terus bercabang sampai diperoleh solusi lengkap (Sutanto,2004). Tujuan penelitian ini adalah membuat mekanisme penjadwalan baru pada produk painted di MCL 2 dengan menggunakan algoritma Branch & Bound untuk meminimasi mean flow time.
428
Seminar Nasional IENACO-2014
ISSN: 2337-4349
2.
METODOLOGI Tahapan penelitian yang akan dilakukan untuk membuat variasi jadwal yang baru dengan menggunakan algoritma Bracnch and Bound untuk meminimasi mean flow time, sebagai berikut : Tahap pertama yang dilakukan adalah perhitungan penjadwalan eksisting pada perusahaan. Metode penjadwalan eksisting di perusahaan menggunakan aturan first come first serve. Kemudian membagi produk painted menjadi dua batch yaitu batch pertama berdimensi 0,20 x 914mm dan batch kedua mempunyai dimensi 0,25 x 914 mm, dan dilakukan perhitungan mean flow time pada masing-masing batch. Tahap kedua adalah menentukan jadwal inisial untuk masing-masing batch sebagai dasar perhitungan algoritma Branch and Bound. Tahap ketiga adalah perhitungan penjadwalan dengan algoritma Branch and Bound. Langkah-langkah algoritma branch and bound sebagai berikut:
Mulai
Inisiasikan solusi awal dengan : i= Vo= 0 ; Jo=Ro= { J1,... Jn } dimana urutan job Ro diatur dengan SPT pada mesin
Buat percabangan X1 = 1 untuk masing-masing job i
Hitung lower bound (batas bawah) (fL)
Menentukan Titik Aktif
Buat pencabangan pada titik aktif
Hitung batas bawah ( fL)
Menentukan solusi jalur
Selesai
Gambar 1. Langkah-langkah Algoritma Branch and Bound Tahap keempat adalah membandingkan nilai mean flow time pada kondisi eksisting dengan penjadwalan menggunakan algoritma Branch & Bound untuk masing-masing batch.
429
Seminar Nasional IENACO-2014
3.
ISSN: 2337-4349
HASIL DAN PEMBAHASAN Data yang digunakan untuk pengolahan data terdapat pada Tabel 1. Tabel 1. Data Job (jam) Job 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
Item Description 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Carita DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR 0.20 x 914mm Gemilang SS AZ100 G300 Steel Biru Bromo DB NIR 0.20 x 914mm Gemilang SS AZ100 G300 Stl Hijau Borneo DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Hijau Borneo DB NIR 0.20 x 914mm Gemilang SS AZ100 G300 Stl Merah Merapi DB NIR 0.20 x 914mm Gemilang SS AZ100 G300 Stl Merah Carita DB NIR 0.20 x 914mm Gemilang SS AZ100 G300 Stl Hijau Borneo DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR 0.20 x 914mm Gemilang AZ100 G300 Steel Merah Carita DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Biru Bromo DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Carita DB NIR 0.20 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR 0.20 x 914mm Gemilang AZ100 G300 Steel Merah Carita DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Biru Bromo DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Carita DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR 0.20 x 914mm Gemilang AZ100 G300 Steel Hijau Borneo DB NIR 0.20 x 914mm Gemilang AZ100 G300 Steel Biru Bromo DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Biru Bromo DB NIR 0.25 x 914mm Gemilang AZ100 G300 Steel Merah Merapi DB NIR
Grade G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300 G300
Spesifikasi Quantity (ton) Thick Widthness 0,25 914 353,62 0,25 914 111,985 0,2 914 89,66 0,2 914 88,53 0,25 914 111,985 0,25 914 108,56 0,2 914 127,25 0,2 914 64,23 0,2 914 88,53 0,25 914 111,985 0,2 914 18,58 0,25 914 156,46 0,25 914 454,48 0,2 914 17,65 0,2 914 18,58 0,25 914 156,46 0,25 914 162,30 0,25 914 100,86 0,25 914 183,79 0,2 914 17,33 0,2 914 16,79 0,25 914 126,06 0,25 914 162,30
Standard Runtime
Setup
Total Time
25,03 14,30 7,59 8,11 14,30 7,29 9,12 5,08 8,11 14,30 1,79 16,45 33,03 0,89 1,79 16,45 25,58 8,00 14,30 0,89 0,89 11,05 25,58
0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0 0,5
25,53 14,80 8,09 8,61 14,80 7,79 9,62 5,58 8,61 14,80 2,29 16,95 33,53 1,39 2,29 16,95 26,08 8,50 14,80 1,39 1,39 11,05 26,08
Tahap awal pengolahan data yaitu melakukan perhitungan penjadwalan eksisiting dengan aturan FCFS. Produk dibagi menjadi dua batch yaitu batch berdimensi 0,20x914 mm dan 0,25 x 914 mm. Batch 0,20 x 914 mm terdiri dari 10 job dan batch 0,25 x 914 mm terdiri dari 13 job. Nilai mean flow time yang didapatkan pada batch 0,20 x 914 mm adalah 43,23 jam dengan urutan job yaitu job 3- job 4- job 7- job 8- job 9- job 11- job 14- job 15- job 20- job 21. Untuk batch 0,25 x 914 mm nilai mean flow time adalah 182,76 jam dengan urutan job yaitu job 1- job 2- job 5- job 6- job 10- job 12 -job 13-job 16- job 17- job 18- job 19 -job 22-job 23. Tahap berikutnya adalah menentukan jadwal inisial untuk batch 0,20 x 914 mm dan 0,25 x 914 mm dengan menggunakan aturan SPT (Short Processing Time). Nilai mean flow time berdasarkan SPT adalah 18,42 jam untuk batch 0,20 x 914 mm dengan urutan jadwalnya yaitu job 14- job 20- job 21- job 11- job 15 – job 8- job 3 –job 4- job 9- job 7. Sementara nilai mean flow time pada batch 0,25 x 914 mm yaitu 148,45 jam dengan urutan job nya yaitu job 6- job 20- job 21job 11- job 15 – job 8- job 3 –job 4- job 9- job 7. Setelah jadwal inisial diperoleh, langkah selanjutnya adalah melakukan penjadwalan dengan algoritma branch and bound. Pencabangan pertama untuk batch 0,20 x 914 mm terlihat pada gambar 2. P(o) (0)
P(14) 1,39
P(20) 1,39
P(21) 1,39
P(11) 2,29
P(8) 5,58 P(15) 2,29
P(3) 8,09
P(4) 8,61
P(9) 8,61
P(7) 9,62
Gambar 2. Percabangan Pertama untuk batch 0,20 x 914 mm Langkah berikutnya yaitu menentukan lower bound (batas bawah) . Lower Bound pada batch 0,20 x 914 mm dapat dilihat pada Gambar 3. P(o) (0)
P(14) 1,39
P(20) 1,39
P(21) 1,39
P(11) 2,29
P(8) 5,58 P(15) 2,29
430
P(3) 8,09
P(4) 8,61
P(9) 8,61
P(7) 9,62
Seminar Nasional IENACO-2014
ISSN: 2337-4349
Gambar 3. Lower Bound Pada Percabangan Pertama untuk batch 0,20 x 914 mm Dan didapatkan node yang dipilih sebagai lower bound (batas bawah) yaitu node dengan P (14), P(20) dan P(21) dengan masing-masing job ke 14, 20 dan 21. Yang kemudian dilanjutkan dengan pembuatan node baru yang dicabangkan pada node yang telah dipilih. Struktur algoritma Branch and Bound untuk batch 0,20 x 914 mm, ditunjukan pada Gambar 4. Vo (0) P(21) 1,39
P(20) 1,39
P(14) 1,39
P(14,15) P(14,8) P(14,3) 4,43 7,72 10,23
P(14,21) 3,53
P(14,4) P(14,9) 10,75 10,75
P(14,7) 11,76
P(20,14) 3,53
P(20,9) 10,75
P(14,11) 4,43
P(20,11) 4,43 P(20,21) P(20,15) 3,53 N1 7,72
P(20,4) 10,75
P(11) 2,29
P(21,11) 4,43
P(21,14) 3,53
P(20,8) 7,72
P(20,3) 7,72
P(20,9) 10,75
P(20,7) 11,76
N2
P(21,20) 3,53
P(21,8) 7,72
P(21,15) 4,43
P(21,3) 8,94
P(21,4) 10,75 P(21,9) 10,75
P(8) 5,58
P(4) 8,61
P(3) 8,09
P(15) 2,29
P(9) 8,61
P(7) 9,62
P(21,7) 11,76
N3
P(14,20) 3,53
P(14,20,11) 6,57 P(14,20,15) P(14,20,8) P(14,20,3) P(14,20,4) 6,57 9,86 12,37 11,64
P(14,20,21) 5,67
5
P(14,20,9) P(14,20,17) 11,64 13,91
P(14,21,20) P(14,21,11) P(14,21,15) 5,67 6,57 6,57
P(14,21,8) 9,86
P(14,21,3) 11,12
P(14,21,9) 12,89
P(14,20,21,4) P(14,20,21,9) P(14,20,21,7) 15,03 15,03 16,04
P(20,14,21) P(20,14,11) P(20,14,15) P(20,14,8) P(20,14,3) 5,67 6,57 9,86 12,37 6,57
P(14,21,7) 13,9
7
P(14,20,21,11) P(14,20,21,15) P(14,20,21,8) P(14,20,21,3) 8,71 8,71 12 14,51
P(20,14,21,11) P(20,14,21,15) P(20,14,21,8) P(20,14,21,3) 8,71 8,71 12 14,51 P(14,21,20,11) P(14,21,20,15) P(14,21,20,8) P(14,21,20,3) 8,71 8,71 12 14,51
P(14,21,20,4) P(14,21,20,7) P(14,21,20,9) 15,03 16,04 15,03
N5
N4
P(14,21,4) 12,89
N8
N7
N6 P(20,21) 3,53
P(20,14,4) 12,89
P(20,14,9) 12,89
P(20,14,7) 13,9
P(20,14,21,4) P(20,14,21,9) P(20,14,21,7) 15,03 15,03 16,04
N9
P(21,20) 3,53
P(21,14) 3,53
N3
N1 P(20,21,14) P(20,21,11) P(20,21,15) 5,67 6,57 6,57
P(20,21,8) 9,86
P(20,21,3) 11,12
P(20,21,4) 12,89
P(20,21,9) 12,89
P(21,20,14) P(21,20,11) P(21,20,15) 5,67 6,57 6,57
N2
P(20,21,7) 13,9
P(21,14,20) P(21,14,11) P(21,14,15) 5,67 6,57 6,57
P(20,21,14,11) P(20,21,14,15) P(20,21,14,8) P(20,21,14,3) 8,71 8,71 12 14,51
P(21,14,3) 11,12
P(21,14,4) 12,89
P(21,14,9) 12,89
P(21,20,8) 9,86
P(21,20,3) 12,37
P(21,20,14,11) P(21,20,14,15) P(21,20,14,8) P(21,20,14,3) 8,71 8,71 12 14,51 P(21,14,20,11) P(21,14,20,15) P(21,14,20,8) P(21,14,20,3) 8,71 8,71 12 14,51
P(21,20,4) 12,89
P(21,20,9) 12,89
P(21,20,7) 13,9
P(21,14,7) 13,9
P(20,21,14,4) P(20,21,14,9) P(20,21,14,7) 15,03 15,03 16,04
N11
N10
P(21,14,8) 9,86
P(21,14,20,4) P(21,14,20,9) P(21,14,20,7) 15,03 15,03 16,04
P(21,20,14,4) P(21,20,14,9) P(21,20,14,7) 15,03 15,03 16,04
N15
N14
.
N13
N12
Gambar 4. Struktur Branch and Bound untuk batch 0,20 x 914 mm Dan untuk batch 0,20 x 914 mm didapatkan nilai mean flow time terkecil yaitu 18,42 jam dengan sequencing yaitu job 14-20-21-11-15-8-3-4-9-7. Sementara struktur Branch and Bound pada batch 0,25 x 914 mm, ditunjukkan pada Gambar 6. Vo (0)
P(18) 8,50
P(6) 7,79
P(22) 11,55 P(2,6) 23,34
P(6,22) 20,09
P(6,5) 23,34
P(6,10) 23,34
P(6,19) P(6,12) 23,34 25,49
P(6,16) 25,49 P(6,1) P(6,17) 34,07 23,34 P(6,23) 23,34
P(6,2) 23,34
P(10) 14,3
P(2) 14,80
P(5) 14,3
P(19) 14,3
P(16) 16,95
P(12) 16,95
P(1) 25,53
P(17) 26,08
P(13) 33,53
P(23) 26,08
P(6,13) 23,34
P(6,18) 17,04
P(6,18,22) 32,59
P(6,18,22) 29,34
P(6,18,5) 32,59
P(6,18,10) P(6,18,19) P(6,18,12) 32,59 32,59 34,74
P(6,18,16) 34,75
P(6,18,17) 43,87
P(6,18,1) 43,32
P(6,18,22,1) 55,62 P(6,18,22,2) 44,89
P(6,18,22,5) P(6,18,22,10) 44,89 44,89
P(6,18,22,19) 44,89
N1
N2
P(6,18,22,2,5) 59,19
P(6,18,22,2,10) 59,19
P(6,18,22,2,19) 59,19
P(6,18,22,12) 46,54
P(6,18,22,2) 62,59
P(6,18,22,16) 46,54
P(6,18,22,216) 62,59
P(6,18,23) 43,07
P(6,18,22,17) 56,17
P(6,18,22,2,1) 71,17
P(6,18,13) 17,04
P(6,18,22,23) 56,17
P(6,18,22,2,17) 70,47
P(6,18,22,13) 663,62
P(6,18,22,2,23) 70,47
P(6,18,22,2,13) 79,17
P(6,18,22,2,2,5) 59,19
N3
P(6,18,22,2,5,10) 73,49 N24
P(6,18,22,2,5,19) 73,49
P(6,18,22,2,5,12) 76,89
N4
P(6,18,22,2,5,16) 76,89
P(6,18,22,2,5,1) 85,47
P(6,18,22,2,5,17) 84,27
P(6,18,22,2,5,23) 84,27
P(6,18,22,2,5,13) 93,47
P(6,18,22,2,10,5) 73,49 N26
N25
P(6,18,22,2,10) 59,19
N5
P(6,18,22,2,10,19) 73,49
P(6,18,22,2,19) 59,19
P(6,18,22,2,12) 62,59
P(6,18,22,2,16) 62,59
P(6,18,22,2,1) 71,17
P(6,18,22,2,17) 70,47
P(6,18,22,2,23) 70,47
N6
P(6,18,22,2,10,12) 76,49
P(6,18,22,2,10,16) 76,49
P(6,18,22,2,10,1) 85,47
P(6,18,22,2,10,17) 76,49
P(6,18,22,2,10,23) 84,27
N27
Gambar 5. Struktur Branch and Bound untuk batch 0,25 x 914 mm
431
P(6,18,22,2,10,13) 93,47
.
Seminar Nasional IENACO-2014
ISSN: 2337-4349
Perhitungan algoritma Branch and Bound untuk batch 0,25 x 914 mm menghasilkan nilai mean flow time terkecil yaitu 147,13 jam dengan sequencing yang dihasilkan job 6-18-2-22-5-1019-16-12-1-23-17-13. Berdasarkan perhitungan yang telah dilakukan, untuk batch 0,20 x 914 mm, nilai mean flow time pada jadwal inisial dengan menggunakan aturan SPT dan jadwal yang dihasilkan oleh agoritma branch and bound sama yaitu 18,42 jam dengan urutan job yang berbeda yaitu 14-20-21-11-15-83-4-9-7 dan 14-21-20-11-15-8-3-4-9-7. Sementara untuk hasil perhitungan pada batch 0,25 x 914 mm, mean flow time berdasarkan algoritma branch and bound adalah 147,13 jam dengan urutan job 6-18-2-22-5-10-19-16-12-1-23-17-13. 4.
KESIMPULAN Penjadwalan produk painted di MCL 2 dengan menggunakan algoritma branch and bound menghasilkan nilai mean flow time sebesar 18,42 jam untuk batch 0,20 x 914mm. Sementara untuk batch 0,25 x 914 mm, didapatkan nilai mean flow time sebesar 147,13 jam. Sehingga penurunan dari kondisi eksisting yaitu 57 % pada batch 0,20 x 914mm dan 19 % pada batch 0,25 x 914. DAFTAR PUSTAKA Baker, K. R. 2008. Element of Sequencing dan Scheduling. John Wiley dan Sons Inc. New York. Berlianty, I., et. al. 2010. Teknik- Teknik Optimasi Heuristik. Graha Ilmu. Yogyakarta. Brucker, P. 2007. Scheduling Algoritms Fifth Edition. Springer-Verlag Berlin Heidelberg. Germany. Pinedo, M., 2008. Scheduling Theory, Algorithms, and System Thirt Edition. Springer. New York. Sutanto,G . 2000. Algoritma Branch And Bound Dan Algoritma Genetika Untuk Penjadwalan Flowshop Dengan Fungsi Tujuan Ganda. Skripsi Jurusan Teknik Industri Fakultas Teknik Universitas Kristen Petra : Surabaya. Sutanto, J., et. al. 2004. Algoritma Brach and Bound untuk Masalah Penjadwalan pada Mesin Paralel. Jurnal Teknik Informatika. Laboratorium Ilmu dan Rekayasa Komputasi. Departemen Teknik Informatika : ITB
432
