PENGGUNAAN ALGORITMA GENETIKA PADA PENJADWALAN PRODUKSI DI PT DNP INDONESIA PULO GADUNG Suriadi AS, Ulil Hamida, N. Anna Irvani STMI Jakarta, Kementerian Perindustrian RI ABSTRAK Permasalahan yang terjadi di PT DNP Indonesia adalah seringnya terjadi keterlambatan penyelesaian pesanan. Keterlambatan ini disebabkan oleh penjadwalan produksi di perusahaan. Saat ini perusahaan menggunakan penjadwalan FCFS. Penjadwalan dengan FCFS berarti bahwa job yang datang diproses sesuai dengan job mana yang datang terlebih dahulu. Dengan metode FCFS, job yang datang terlebih dahulu diproses terlebih dahulu, dan job yang terakhir datang, diproses setelah job yang lebih dulu datang selesai. Padahal bisa jadi job yang datang terlebih dahulu memiliki batas waktu yang lebih lama dibandingkan job yang datang terakhir. Oleh karena itu digunakan metode algoritma genetika untuk melakukan perbaikan penjadwalan agar tidak terjadi keterlambatan lagi. Berdasarkan penelitian yang telah dilakukan, penjadwalan dengan algoritma genetika menghasilkan performansi yang lebih baik dibandingkan dengan metode FCFS, metode penjadwalan yang dibuat dengan menggunakan algoritma genetika mendapatkan hasil penjadwalan yang optimal. Ini terlihat dari waktu penyelesaian seluruh pengerjaan pesanan dan rata-rata waktu yang digunakan oleh tiap job pada lantai produksi mengalami penghematan waktu masing-masing sebesar 7,25 % dan 18,4 %. Penghematan waktu tersebut akhirnya berdampak pada pengurangan keterlambatan pesanan. Kata kunci: penjadwalan produksi, FCFS, algoritma genetika.
1. PENDAHULUAN PT DNP Indonesia sebagai sebuah perusahaan kemasan fleksibel (flexible packaging) yang menghasilkan produk bervariasi berupa kemasan makanan dan minuman, kemasan pewangi, dan lain sebagainya sesuai dengan permintaan konsumen yang bersifat MTO (make to order). Tahapan proses produksi perusahaan tersebut melalui gravure printing, rewind, lamination, finishing dan packing dengan menggunakan plastic film dan aluminium foil sebagai bahan baku, serta bahan tambahan lainnya sebagai bahan campuran. Saat ini, perusahaan kadang mengalami masalah keterlambatan dalam proses penyelesaian produk yang berdampak pada keterlambatan dalam pengiriman pesanan ke pelanggan. Hal ini terkait dengan penjadwalan produksi yang dilakukan oleh perusahaan. Dalam melakukan penjadwalan, perusahaan menggunakan aturan First Come First Served
(FCFS). Penjadwalan dengan FCFS mengasumsikan bahwa job yang datang diproses sesuai dengan job mana yang datang terlebih dahulu (Ginting, 2009). Dengan metode FCFS, job yang datang terlebih dahulu diproses terlebih dahulu, dan job yang terakhir datang, diproses setelah job yang lebih dulu datang selesai. Padahal bisa jadi job yang datang terlebih dahulu memiliki batas waktu yang lebih lama dibandingkan job yang datang terakhir. Sehingga terjadi akhirnya sering terjadi keterlambatan. Oleh karena itu diperlukan suatu perbaikan metode penjadwalan sehingga diharapkan dapat diperoleh waktu penyelesaian produk optimal yang akan memperlancar proses produksi dan dapat mengurangi keterlambatan serta meningkatkan efisiensi dan efektivitas baik material maupun non-material. Dalam hal ini, akan digunakan metode heuristik; yaitu melakukan pendekatan suatu solusi optimal dengan menggunakan algoritma genetika. Algoritma genetika (Genetic Algorithm) dapat
diimplementasikan untuk mendapatkan solusi terbaik dari suatu penjadwalan, baik untuk job shop maupun flow shop yang bertipe MTO (Ginting, 2009). Tujuan dari penelitian ini adalah melakukan penjadwalan dengan menggunakan algoritma genetika untuk mendapatkana penjadwalan yang optimal. Kriteria optimal didasarkan pada nilai makespan dan mean flow time yang minimum.
maka flow time untuk tiap job sama dengan completion time-nya. Mean Completion Time Ci = 93 = 18,6 hari = 5 n Mean Flow Time Ci = 93 = 18,6 hari = 5 n Makespan = ti = 5 +10 + 2 + 8 + 6 =31 hari
2. LANDASAN TEORI Menurut Baker, “penjadwalan didefinisikan sebagai proses pengalokasian sumber daya untuk memilih sekumpulan tugas dalam jangka waktu tertentu” (Ginting, 2009). Penjadwalan proses produksi yang baik dapat mengurangi waktu menganggur (idle time) pada unit-unit produksi dan meminimumkan barang yang sedang dalam proses (work in process). 2.1 Penjadwalan Produksi dengan Aturan First Come First Served (FCFS) Aturan ini mengasumsikan bahwa job akan diproses sesuai dengan urutan kedatangannya. Contoh kasus sederhana: Tabel 1 Data Job
2.2 Penjadwalan Algoritma Genetika
dengan
Pada algoritma genetika, data dan informasi yang akan diolah dinyatakan dalam bentuk kromosom yang melambangkan genetik manusia. Pembuatan peta kromosom diartikan sebagai pengurutan job dalam penjadwalan diilustrasikan pada Gambar 1.
-
gen
Processing Time (hari) A 5 B 10 C 2 D 8 E 6 Penjadwalan dengan aturan FCFS, hasilnya adalah sebagai berikut:
Produksi
Gambar kromosom
locus
kromosom
Job
Gambar 1 Kromosom
Gambar penjadwalan job 4
2
1
Gen
3
5
locus
6
4 Job 4 pada locus 1
Gambar 2 Kromosom Penjadwalan Job Tabel 2 Hasil Penjadwalan dengan FCFS Job A B C D E Total Mean
Start Time 0
Processing Time 5 10 2 8 6 31
Completion Time 5 15 17 25 31 93 18,6
Flow Time 5 15 17 25 31 93 18,6
Catatan: diasumsikan semua job siap dikerjakan pada saat jadwal dimulai (t=0),
Secara umum, tahapan yang perlu dilakukan untuk melakukan penjadwalan dengan algoritma genetika digambarkan pada Gambar 3.
Tabel 5 Kapasitas Mesin Tiap Job Populasi Awal
Evaluasi
Seleksi
Fitness
Individu
Job J1 J2 J3 J4 J5 J6 J7
Reproduksi:
Crossover Populasi Baru
Dan Mutasi
M1 200 220 220 200 200 220 200
Kecepatan Mesin (meter per menit) M2 M3 200 200 200 200 200 200 200 200 200 200 200 200 200 200
M4 150 150 150 150 150 150 150
Keterangan: M1 = Mesin Gravure Printing M2 = Mesin LRM M3 = Mesin LMD M4 = Mesin BC
Gambar 3 Langkah Algoritma Genetika
3. DATA PENELITIAN Data yang digunakan dalam penelitian ini adalah contoh data pesanan produksi yang digunakan dalam penelitian, daftar mesin yang ada, kapasitas mesin untuk setiap job dan waktu proses setiap job.
Tabel 3 Data Pesanan Produksi J1 MT. Ultra Blue
Color C 7
J2 MT. Ultra Blue
6
30
500
300
169000
J3 MT. Ultra SB Blue
6
300
500
170
95000
J4 MT. Ultra SB Grenn
7
300
500
124
69000
J5 MT. Wangi Pink
7
30
700
160
120000
J6 MT. Soft Blue Sky
6
450
700
102
80000
J7 MT. Soft Pink Airflow
7
30
700
100
78000
Ji
Article
Size (ml) 15
Length Qty Order (meter) (roll) 500 250
Qty Meter (meter) 140000
Sumber: PPC PT DNP Indonesia
Keterangan: Ji = job keQty = Jumlah Qty M = Jumlah meter Tabel 4 Mesin-Mesin yang Digunakan untuk Pengerjaan Pesanan Prioritas Kode Mesin
Jumlah Mesin
GR-601
1
GR-701
1
Large Rewind Machine
LRM-02
1
Lamination Machine Dryer
LMD-02
1
BC-04
1
Mesin Gravure Printing
Bobbin Cutting
Sumber: PPC PT DNP Indonesia
Tabel 6 Waktu Proses Tiap Job pada MasingMasing Mesin Waktu Proses/ti (menit ) Ji M1 M2 M3 M4 J1 700,00 700,00 630,00 840,00 J2 768,18 845,00 760,50 1014,00 J3 431,82 475,00 427,50 570,00 J4 345,00 345,00 310,50 414,00 J5 600,00 600,00 540,00 720,00 J6 363,64 400,00 360,00 480,00 J7 390,00 390,00 351,00 468,00
4. METODOLOGI PENELITIAN Langkah langkah yang digunakan dalam melakukan penelitian ini adalah sebagai berikut: 1. Pembentukan populasi awal Sebuah populasi awal terdiri dari sejumlah kromosom. Pembentukan populasi awal dapat diperoleh secara acak atau menggunakan metode heuristik tertentu (Purwanto, 2003). Pembentukan ini dilakukan secara terusmenerus sampai didapatkan jumlah kromosom yang diinginkan. Dalam proses selanjutnya tidak perlu lagi dilakukan pembangkitan populasi karena populasi berikutnya merupakan hasil seleksi dan operasi genetika, maka diupayakan ukuran populasi tetap dan konvergen pada kromosom terbaik (Lukas dkk, 2005). 2. Perhitungan fungsi tujuan dari setiap kromosom Perhitungan fungsi tujuan dari tiap kromosom berdasarkan kromosom yang terbentuk. Fungsi tujuan ini merupakan sebuah fungsi yang memberikan penilaian kepada kromosom yang disebut sebagai nilai fitness. Nilai fitness inilah
yang kemudian menjadi bobot suatu kromosom, apakah suatu kromosom layak untuk dipertahankan dalam keturunan/generasi berikutnya. Oleh karena itu, fungsi fitness menjadi masalah atau penentu utama keberhasilan algoritma genetika (Djunaidy dkk). Fungsi fitness dari proses penjadwalan ini adalah: Fungsi fitness =
1
makespan (Ms) + mean flow time (MFT)
3. Pembangkitan populasi baru a. Seleksi Seleksi dilakukan untuk mendapatkan calon induk yang baik. Induk yang baik akan menghasilkan keturunan yang baik. Proses seleksi ini dilihat dari nilai fitness, semakin tinggi nilai fitness suatu individu maka semakin besar kemungkinannya untuk terpilih. b. Pindah silang (crossover) Crossover merupakan salah satu operator dalam algoritma genetika yang melibatkan dua induk untuk menghasilkan keturunan yang baru. Crossover dilakukan dengan melakukan pertukaran gen dari dua induk secara acak (Basuki, 2003). b. Mutasi Mutasi merupakan operator yang menukar nilai gen dengan nilai inversinya. Setiap individu mengalami mutasi gen dengan probabilitas mutasi yang ditentukan (Basuki, 2003). 4. Pengulangan Ulangi langkah kedua dan ketiga sampai tercapai kriteria pemberhentian tertentu atau maksimum generasi tercapai. Semakin banyak percobaan semakin baik hasil yang diperoleh, hanya kromosom dengan hasil terbaik yang akan bertahan sampai pengulangan terakhir. Beberapa kriteria pemberhentian yang sering dilakukan adalah: Berhenti pada generasi tertentu. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah. Berhenti bila dalam n generasi berikutnya tidak didapatkan nilai fitness yang lebih tinggi.
5. HASIL DAN PEMBAHASAN 5.1 Penjadwalan dengan Metode FCFS Perusahaan melakukan penjadwalan dengan menggunakan aturan First Come First Served (FCFS), yaitu pesanan yang pertama datang dijadwalkan terlebih dahulu. Dalam tugas akhir ini, dari data pesanan tabel 4.2 terlihat bahwa pesanan job ke 1 (J1) diproses terlebih dahulu dan selanjutnya diteruskan dengan J2, J3, J4, J5, J6 sampai pada job terakhir yaitu J7. Penjadwalan untuk tiap job dilakukan sesuai dengan pesanan yang diterima, dengan jumlah tiap pesanan (quantity order) yang berbedabeda (lihat tabel 4.2). Waktu penyelesaian (makespan) dan rata-rata waktu yang digunakan (mean flow time) dari ke-7 job yang telah dijadwalkan tersebut adalah masing-masing sebesar 10991,50 menit dan 9331,57 menit. 5.2 Implementasi Penjadwalan Job dengan Menggunakan Metode Algoritma Genetika Parameter yang ditentukan dalam penelitian ini adalah sebagai berikut: Ukuran populasi =7 Populasi awal = Generasi 0 (GEN=0) Generasi (GEN) = 10 Probabilitas crossover (Pc) =1 Probabilitas mutasi (Pm) = 0,01 Pembangkitan Populasi Awal Solusi awal dibangkitkan dengan menggunakan urutan 4-6-7-3-5-1-2 yang diperoleh dari metode CDS. Berdasarkan spesias awal tersebut dibangkitkan kromosom dengan ukuran populasi yang tetap pada setiap generasi. Langkah berikut:
perhitungannya
adalah
sebagai
Menukar urutan gen ke- k dengan gen kek+1 dari kromosom. Kromosom berasal dari sub populasi 1 dan sub populasi 2, ditentukan bahwa ukuran populasi adalah
7. Hasil perhitungannya dapat dilihat pada tabel 4.15.
Kromosom
Sub Populasi 1
Ms
MFT
1/fitness
1
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
2
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
MFT
3
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
Tabel 7 Urutan Gen serta Makespan dan Mean Flow Time Sub Populasi 1 Kromosom
Sub Populasi 1
Ms
Tabel 8 Generasi Kesepuluh (GEN=10) pada Metode Algoritma Genetika
1
4-6-7-3-5-1-2
10194,50
7623,57
4
2
6-4-7-3-5-1-2
10213,14
7696,14
5
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
7614,21
6
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
3
4-7-6-3-5-1-2
10194,50
4
4-6-3-7-5-1-2
10194,50
7656,00
7
5
4-6-7-5-3-1-2
10194,50
7693,86
Kromosom
Sub Populasi 2
Ms
MFT
1/fitness
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
6
4-6-7-3-1-5-2
10194,50
7685,00
1
7
4-6-7-3-5-2-1
10334,50
7707,79
2
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
3
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
4
4-7-6-3-5-1-2
10194,50
7614,21
5,615E-05
5
4-6-7-3-5-1-2
10194,50
7623,57
5,612E-05
6
4-6-7-3-5-1-2
10194,50
7623,57
5,612E-05
7
4-6-7-3-5-1-2
10194,50
7623,57
5,612E-05
Dari Tabel 7 dapat dijelaskan bahwa awal urutan gen (job) dari sub populasi 1 yaitu 4-67-3-5-1-2, kemudian ditukarkan urutan gen ke1 (k) dengan gen ke-2 (k+1) menjadi 6-4-7-35-1-2. Letakkan lagi ke urutan gen awal kemudian ditukarkan kembali urutan gen ke-2 dengan gen ke-3 menjadi 4-7-6-3-5-1-2. Selanjutnya, kembalikan lagi urutan gen ke posisi awal lalu tukarkan kembali urutan gen ke-3 dengan gen ke-4 menjadi 4-6-3-7-5-1-2. Demikian selanjutnya sampai dengan urutan gen terakhir yaitu urutan gen ke-6 (k) dengan gen ke-7 (k+1). Setelah menukar urutan gen tersebut, maka didapatkan kromosomkromosom baru dengan ukuran populasi adalah 7. Kromosom baru tersebut merupakan urutan job baru dengan menghasilkan nilai makespan (Ms) dan mean flow time (MFT) yang berbeda. Dari Tabel 7 telah didapatkan hasil makespan dan mean flow time masingmasing kromosom. Dari populasi awal yang dibangkitkan dilakukan pembangkitan populasi selanjutnya dengan melakukan seleksi nilai fitness, crossover dan mutasi. Pada populasi ke-10, dihasilkan populasi seperti pada Tabel 8. Pada populasi tersebut dapat dilihat nilai mean flow time lebih kecil dari generasi pertama, tapi untuk nilai makespan tidak mengalami perbaikan. Hal ini disebabkan populasi awal dibangkitkan dari metode yang cukup handal yaitu metode CDS.
Berdasarkan algoritma genetika yang diterapkan untuk penjadwalan tersebut, diperoleh perbaikan nilai fitness dari penjadwalan job seperti yang tercantum pada Gambar 4. Sejak populasi ke 6, perubahan nilai fitness mendekati 0 sehingga pengulangan dihentikan. 0.000058 0.000056 0.000054 0.000052 0.00005 0.000048 Generasi 0
fitness
1
2
3
4
5
6
7
8
9 10
Gambar 4 Nilai Fitness untuk Setiap Generasi
Analisis Perbandingan Penjadwalan Job Perusahaan dengan Penjadwalan Job Menggunakan Algoritma Genetika Tujuan penjadwalan dengan algoritma genetika pada penelitian ini adalah untuk menghasilkan urutan job dengan makespan dan mean flow time yang minimum. Hasil dari algoritma genetika ini kemudian dibandingkan dengan metode penjadwalan perusahaan. Perbandingan keduanya dapat dilihat pada Tabel 9.
Tabel 9 Perbandingan Performansi Penjadwalan Perusahaan (FCFS) dengan Algoritma Genetika Penjadwalan
Perusahaan (FCFS)
Algoritma Genetika
Urutan Job
J1-J2-J3-J4-J5-J6-J7
J4-J7-J6-J3-J5-J1-J2
Makespan
10991,5 menit
10194,5 menit
Mean Flow Time
9331,57 menit
7614,23 menit
Sumber: Hasil Pengolahan Data
Dari Tabel 9 terlihat bahwa penjadwalan job dengan algoritma genetika menghasilkan performansi yang lebih baik. Ini dilihat dari terjadinya penurunan nilai makespan dan mean flow time. Untuk nilai makespan terjadi penurunan sebesar 7,25 %, sedangkan untuk nilai mean flow time mengalami penurunan sebesar 18,4 %. Artinya terjadi penghematan waktu makespan dan mean flow time dengan menggunakan algoritma genetika. Perubahan ini terlihat cukup besar sehingga metode algoritma genetika yang diterapkan menghasilkan urutan job dengan nilai makespan dan mean flow time yang optimal. 6. KESIMPULAN DAN SARAN Kesimpulan 1. Penjadwalan dengan algoritma genetika menghasilkan performansi yang lebih baik dibandingkan dengan penjadwalan perusahaan, metode penjadwalan yang dibuat dengan menggunakan algoritma genetika mendapatkan hasil penjadwalan yang optimal. Ini terlihat dari waktu penyelesaian seluruh pengerjaan pesanan dan rata-rata waktu yang digunakan oleh tiap job pada lantai produksi mengalami penghematan waktu masingmasing sebesar 7,25 % dan 18,4 %. Penghematan waktu tersebut berdampak pula pada pengurangan waktu tunggu bahan yang berada dalam proses pengerjaan. 2. Urutan penyelesaian job yang diperoleh dengan menggunakan metode algoritma genetika adalah J4 – J7 – J6 – J3 – J5 – J1 – J2, dengan kriteria yang diperoleh berdasarkan nilai makespan yaitu sebesar 10194,50 menit dan mean flow time sebesar 7614,23 menit. Saran Berdasarkan penelitian yang dilakukan saran yang diberikan adalah sebagai berikut:
1. Perusahaan sebaiknya melakukan pengerjaan pesanan di lantai produksi tidak berdasarkan pada pesanan yang datang terlebih dahulu, tetapi perlu dilihat dari spesifikasi job dan quantity yang dipesan serta waktu penyelesaian untuk pengiriman pesanan tersebut. 2. Perusahaan dapat menerapkan sistem penjadwalan baru yaitu algoritma genetika yang dapat menghasilkan kriteria dalam penjadwalan yang lebih baik, seperti memperkecil nilai makespan dan mean flow time sehingga masalah keterlambatan penyelesaian pesanan dapat segera diatasi. 7. DAFTAR PUSTAKA Basuki, A. 2003. Algoritma Genetika: Suatu Alternatif Penyelesaian Permasalahan Searching, Optimasi dan Machine Learning. Politeknik Elektronika Negeri Surabaya. PENS-ITS. Surabaya. http://www.eepisits.edu/~basuki/lecture/ AlgoritmaGenetika.pdf. Buffa, E. S dan Sarin R. K. 1996. Manajemen Operasi dan Produksi Modern. Jilid 1. Binarupa Aksara. Djunaidy, A. dkk. Simulasi Penjadwalan JobShop Dinamis Dengan Menggunakan Algoritma Genetika. Fakultas Teknologi Informasi-ITS. Surabaya. http://www.si.its.ac.id/penelitian/jurnal /eka_aditya.pdf. Elsayed, A. 1990. Analysis and Control of Production Systems. Prentice-Hall International Edition. New Jersey. Ginting, R. 2009. Penjadwalan Mesin. Edisi Pertama. Graha Ilmu. Yogyakarta. Lukas, S. dkk. 2005. Penyelesaian Masalah Penugasan dengan Algoritma Genetika Teknik Cycle Crossover. Jurnal Ilmiah Ilmu Komputer. Vol. 3 Nomor 2. Jakarta. Purwanto, A. 2003. Algoritma Genetika sebagai Alternatif Proses Pencarian dan Optimasi. Jurnal Komputer dan Informatika. Vol. 4 Nomor 1. Fakultas Teknologi Informatika. Universitas Tarumanegara. Jakarta.
