IMPLEMENTASI ALGORITMA OPTIMASI BEE COLONY UNTUK PENJADWALAN JOB SHOP Nafiuna Hidayatus Saidah, Mahendrawathi Er, Ph.D., Rully Soelaiman M.Kom. Jurusan Sistem Informasi, Institut Teknologi Sepuluh Nopember, Kampus Keputih, Sukolilo, Surabaya 60111, Indonesia
Abstraksi Penjadwalan merupakan permasalahan yang sering ditemui pada perusahaan-perusahaan manufaktur. Salah satu tugas yang paling penting di dalamnya adalah bagaimana meningkatkan utilitas mesin dan pengurangan waktu siklus sebuah produk. Oleh karena itulah tugas penjadwalan job shop sangat berperan untuk mendapatkan solusi yang paling optimal. Permasalahan penjadwalan job shop merupakan salah satu masalah optimasi kombinatorial non deterministik dengan waktu polinomial (NP-complete) yang paling rumit. Berbagai metode telah dikembangkan dalam menyelesaikan permasalahan ini, namun ada beberapa metode yang dirasa kurang dalam hal performansinya. Salah satu metode yang mampu menyelesaikan permasalahan ini adalah menggunakan algoritma bee colony. Dalam implementasi tugas akhir ini, optimasi bee colony akan diterapkan untuk menyelesaikan permasalahan penjadwalan Job shop. Optimasi bee colony merupakan algoritma heuristik yang tergolong dalam algoritma swarm intelegent. Proses algoritma optimasi ini meniru tingkah laku lebah dalam pencarian terhadap sumber makanan. Dua karakteristik utama yang ditampilkan dalam optimasi ini, yaitu forage dan waggle dance. Dengan karakteristik ini, permasalahan penjadwalan yang tergolong permasalahan kombinatorial ini mampu mendapatkan solusi yang optimal. Pada akhir tugas akhir ini, akan ditampilkan hasil uji coba penyelesaian permasalahan penjadwalan job shop menggunakan algoritma optimasi bee colony yang akan dibandingkan dengan hasil penyelesaian dengan menggunakan algoritma Particle Swarm Optimization (PSO ) dengan modifikasi. Kata kunci: penjadwalan, optimasi, penjadwalan job shop, optimasi bee colony.
1. Pendahuluan Adanya kompetisi pasar global yang semakin kuat telah menimbulkan tantangan dalam perusahaan manufaktur untuk beroperasi dengan biaya produksi yang rendah, serta life cycle yang pendek. Semua manajemen perusahaan pasti menginginkan pekerjaannya dapat terlaksanakan secara efektif dan efisien agar tujuannya tercapai. Oleh karena itu pemahaman mengenai konsep penjadwalan sangat penting, sehingga para pelaksana mengetahui kapan waktu harus memulai suatu pekerjaan dan kapan waktu mengakhirinya. Penjadwalan disusun dengan mempertimbangkan berbagai batasan yang ada. Penjadwalan yang baik akan memberikan dampak positif,
yaitu rendahnya biaya operasi dan waktu pengiriman, yang akhirnya dapat meningkatkan kepuasan pelanggan. Perusahaan manufaktur beroperasi dengan berbagai sistem produksi antara lain flow shop dan job shop. Sistem produksi job shop adalah penjadwalan yang memiliki kendala urutan pemrosesan tugas, dan setiap tugas harus melalui setiap mesin tepat satu kali. Ada beberapa jenis penjadwalan job shop yang ada, di antaranya penjadwalan dilihat dari segi waktu kedatangan job. Berdasar waktu kedatangan job, penjadwalan job shop dapat dikelompokkan menjadi penjadwalan job shop statis, dan penjadwalan job shop dinamis. Disebut penjadwalan job shop statis apabila semua job diterima pada saat yang sama. Sedangkan penjadwalan dinamis yaitu
apabila waktu kedatangan job diterima pada waktu yang bervariasi. Jika variasi waktu kedatangannya diketahui sebelumnya , maka penjadwalan tersebut dinamakan sebagai penjadwalan job shop deterministik,. Namun jika waktu kedatangan yang bervariasi tersebut tidak diketahui sebelumnya maka disebut penjadwalan job shop non deterministik atau stokastik. Salah satu tantangan yang dihadapi oleh perusahaan bertipe job shop untuk dapat memelihara level inventori yang rendah serta respon yang cepat untuk permintaan pelanggan adalah masalah penjadwalan. Karakterististik dari penjadwalan ini didefinisikan oleh sekumpulan job, dimana tiap job mempunyai satu atau lebih operasi. Operasi dari tiap job tersebut ditetapkan secara urut pada mesin yang spesifik. Sehingga tujuan dari penjadwalan seperti yang telah diungkapkan oleh Rejendran dan Holthaus (1999) yaitu untuk meminimalkan (memaksimalkan) ukuran atau beberapa ukuran dalam pelaksanaannya agar dapat tercapai. Ukuran-ukuran performansi yang berhubungan dengan penjadwalan job shop yaitu utilisasi mesin, waktu siklus, rata-rata penyelesaian, level inventori dan utilisasi sumber manufaktur. Berbagai teknik juga dapat diterapkan untuk penjadwalan. Teknik yang digunakan tergantung dari volume produksi, variasi produk, keadaan operasi, dan kompleksitas dari pekerjaan sendiri. Selain itu, setiap perusahaan perlu untuk melakukan penjadwalan sebaik mungkin agar memperoleh utilitas maksimum dari sumber daya produksi dan asset lain yang dimiliki. Jika permasalahan job shop scheduling diselesaikan dengan teknik yang sederhana, maka akan meliputi permasalahan FIFO (first in first out) dan SPT (shortest processing time). Sedangkan jika diselesaikan dengan teknik yang lebih rumit, maka Branch and Bound (Brucker et. al. 1994), tabu search (Nowicki dan Smutnicki 1996), shiftping bottleneck algorithms (Balas dan Vazacopoulos 1998), dan ant colony (Blum dan Sampels 2004) dapat mewakilinya. Penggunaan algoritma honey bee ini diinspirasi oleh Nakarani dan Tovey
(2004) dalam pengalokasian dinamik pada server internet. Server dan HTTP yang meminta antrian dalam kumpulan server internet dimodelkan sebagai lebah lebah dan flower patches respectively. Untuk menyelesaikan permasalahan ini, Chin Soon Chong, Malcolm Yoke Hean Low, Appa Iyer Sivakumar, dan Kheng Leng Gay (2006) mengusulkan untuk menyelesaikan permasalahan job shop scheduling dengan pendekatan ide baru yang menggunakan model lebah madu. Tugas akhir ini akan mengimplementasikan algoritma optimasi bee colony dalam menyelesaikan permasalahan penjadwalan job shop. 2. Penjadwalan Job Shop Penjadwalan merupakan suatu proses pengaturan sumber daya untuk menyelesaikan tugas-tugas dengan melibatkan pekerjaan, sumber daya, dan waktu. Pekerjaan diproses pada setiap sumber daya dengan urutan tertentu selama waktu tertentu. Tujuan penjadwalan adalah untuk meminimalkan waktu proses, meminimumkan waktu penyelesaian semua tugas (makespan), waktu tunggu langganan, dan tingkat persediaan, serta penggunaan yang efisien dari fasilitas, tenaga kerja, dan peralatan. Tujuan utama dari proses penjadwalan disini adalah menentukan waktu suatu operasi mulai dikerjakan. Hal ini dilakukan pada seluruh operasi sampai seluruh operasi sudah dijadwalkan dan memenuhi setiap batasan masalah yang dirumuskan. Permasalahan penjadwalan job shop merupakan salah satu masalah penjadwalan yang memiliki kendala urutan pemrosesan tugas, dan setiap tugas harus melalui setiap mesin tepat satu kali. Terdapat dua jenis metode yang biasa digunakan untuk menyelesaikan masalah penjadwalan job shop. Metode eksak, seperti pemrograman linier dan pemrograman non-linier, dapat digunakan untuk ukuran permasalahan penjadwalan job shop yang kecil. Sedangkan untuk ukuran masalah yang besar, digunakan suatu pendekatan secara
aproksimasi, seperti local search, simulated annealing, genetic algorithm, tabu search, dan ant colony optimization. Hal ini disebabkan karena untuk ukuran masalah yang besar, kompleksitasnya akan semakin besar. Dari pengertian di atas, dapat disimpulkan bahwa penjadwalan job shop merupakan usaha pengalokasian sumber daya yang ada dalam memenuhi permintaan konsumen. Penjadwalan ini dilakukan dengan memperhatikan penanganan pesanan pada proses produksi diurutkan pada tiap mesin dengan tujuan untuk mendapat waktu penyelesaian optimal. Masalah penjadwalan merupakan salah satu aspek penting pada lingkungan industri Pada permasalahan penjadwalan job shop ini terdiri dari batasan kumpulan J dari n job untuk diproses pada batasan kumpulan M dari m mesin. Tiap job Ji harus diproses pada setiap mesin dan terdiri dari rangkaian mi operasi Oi1, Oi2, …, Oim, yang telah dijadwalkan pada pre-penentuan pemberian pesanan. Oij merupakan operasi ke-j dari job Ji yang telah diproses pada mesin Mx untuk periode waktu proses ij tanpa interupsi dan preemption (pengosongan). Setiap mesin dapat memproses hanya satu job, dan setiap job dapat diproses oleh hanya satu mesin dalam waktu yang sama. Durasi terlama dalam semua operasi dari semua job dilengkapi direferensikan sebagai makespan (Cmax). Lebih khususnya, Ai dianggap menjadi pasangan pesanan operasi yang dibatasi oleh hubungan presedensi untuk setiap job Ji. Untuk setiap mesin Mx, kumpulan Ex menggambarkan kumpulan semua pasangan operasi yang dikerjakan pada mesin. Untuk setiap operasi Oij, anggap kemungkinan waktu mulai proses yang paling awal sebagai tij. Sehingga permasalahan penjadwalan job shop dapat dimodelkan sebagai berikut, Fungsi tujuan : Meminimalkan t (akhir)
(1)
Batasan : ti(j+1) –tij ij ............ (Oij,Oi(j+1)) Ai (2) tij – tkl kl atau tkl – tij ij….. (Oij, Okl) Ex (3) tij , tkl 0 ……….. (Oij,Okl) Ai , Ak (4) Variabel keputusan : tij , tkl ...................... (Oij,Okl) Ai , Ak (5) Pada persamaan (1) disebutkan bahwa fungsi tujuan dari penyelesaian permasalahan penjadwalan job shop adalah meminimalkan makespan. Dalam persamaan tersebut makespan diwakili oleh waktu mulai dari operasi yang paling akhir (t (akhir)). Jika semakin minimum waktu mulai dari operasi yang paling akhir, maka semakin minimum juga waktu selesai dari keseluruhan operasi yang ada (makespan). Fungsi Tujuan : Meminimumkan (makespan) = Meminimumkan ( t finish(akhir) – t0 ) = Meminimumkan (t finish(akhir) – 0 ) = Meminimumkan (t finish(akhir) ) = Meminimumkan (t finish(akhir) ) = Meminimumkan ( t (akhir) ) Persamaan (2) merupakan batasan dari model penjadwalan job shop yang menjelaskan bahwa selang waktu antara pemrosesan dua operasi dari satu job yang sama, harus lebih besar dari pada waktu proses dari operasi pertama yang diproses. Dengan kata lain waktu mulai operasi selanjutnya dari suatu operasi lain yang dimiliki oleh satu job yang sama tidak boleh kurang dari waktu proses dari operasi awal yang diproses. Persamaan (3) masih menjelaskan mengenai batasan dari model penjadwalan job shop. Dari persamaan tersebut dijelaskan bahwa selang waktu antara pemrosesan operasi satu dan operasi selanjutnya yang diproses pada mesin yanga sama (berbeda job) harus lebih besar atau sama dengan waktu proses dari operasi pertama yang diproses. Dengan kata lain waktu mulai operasi selanjutnya dari suatu operasi lain yang diproses oleh mesin yang sama tidak boleh kurang dari waktu proses
dari operasi awal yang diproses. Persamaan (4) ini sebagai batasan bahwa variabel keputusan dari permasalahan penjadwalan job shop harus bernilai integer. Dalam permasalahan penjadwalan job shop, hasil akhir yang diharapakan sebagai variabel keputusan adalah seperti yang ditunjukkan pada persamaan (5) yaitu waktu mulai dari setiap operasi pada semua job yang ada. Seperti yang dipaparkan oleh [4], secara umum permasalahan penjadwalan Job shop dapat didefinisikan sebagai berikut : Terdapat m-mesin yang harus memproses n-job secara tuntas. Terdapat serangkaian operasi dari sebuah job. Tiap operasi yang ada sudah ditetapkan akan diproses dimesin tertentu. Setiap operasi memiliki waktu pemrosesan yang telah ditetapkan sebelumnya. Mempunyai tujuan membuat sebuah jadwal yang memiliki waktu penyelesaian seluruh job (makespan) yang paling minimum. Adapun aturan yang digunakan dalam tugas akhir ini terkait dengan implementasi penjadwalan job shop adalah sebagai berikut: Sebuah mesin hanya diperbolehkan memproses sebuah job sekali saja dan job yang sama tidak boleh diproses dalam mesin yang sama sebanyak 2 kali atau lebih.
Serangkaian operasi dalam sebuah job sudah memiliki urutan pemrosesan tertentu. Saat sebuah operasi sedang diproses dalam suatu mesin, maka pemrosesan tersebut tidak boleh dihentikan sebelum pemrosesan operasi itu benar-benar selesai. Dengan kata lain, tidak diijinkan terjadinya overlap.
Representasi umum untuk permasalahan penjadwalan job shop adalah disjungtive graph seperti yang ditunjukkan pada Gambar 2.3. Dalam graph tersebut, ada node untuk setiap operasi. Ada juga dua tambahan node, yang diketahui sebagai sumber dan
tujuan yang merepresentasikan operasi awal dan akhir. Bobot positif setiap node sama dengan waktu proses yang menghubungkan operasi. Titik awal dan waktu penyelesaian sumber dan tujuan merepresentasikan waktu mulai dan akhir dari permasalahan job shop. Sumber dihubungkan ke operasi inisial dari setiap job dimana operasi final setiap job dihubungkan ke tujuan. Kumpulan conjungtive arch secara langsung digunakan untuk merepresentasikan batasan presedensi untuk setiap job. Kumpulan disjungtive arch digunakan untuk merepresentasikan batasan kapasitas untuk memastikan bahwa tidak ada dua proses operasi dengan mesin yang sama dapat di eksekusi secara simultan. Contoh dari disjungtive arch 3x3 ditunjukkan pada gambar 2.3. Conjungtive arch ditunjukkan dengan garis tebal, sedangkan garis titik-titik merepresentasikan disjungtive arch. [10] mengungkapkan bahwa solusi untuk permasalahan job shop scheduling dapat menghasilkan secara langsung disjungtive arch dari disjungtive graph yang sesuai dengan permutasi mesin (dengan membuat arch dua arah untuk menjadi arch satu arah). Makespan dari solusi merupakan panjang lintasan langsung terlama dalam graph. Panjang dari lintasan diberikan dengan menjumlah waktu proses dari operasi pada lintasan. Solusi yang dapat dikerjakan dengan mudah untuk permasalahan penjadwalan job shop yang lebih cepat ditunjukkan dalam gambar.
O
O
O
O
O
O
O
O
O
O
*
Conjungtive arch Disjungtive arch Gambar 2.1 Representasi Disjungtive Graph
Selain itu, permasalahan penjadwalan job shop yang optimal harus merupakan penjadwalan aktif. Menurut [11]
sebuah jadwal, layak disebut jadwal aktif jika tidak ada perubahan apapun sehingga beberapa operasi diselesaikan secepatnya dan tidak ada operasi lain yang diselesaikan kemudian.Pada tugas akhir ini, pembentukan jadwal akhir akan digunakan algoritma dengan sistem random. Hasil akhir dari jadwal yang sudah terbentuk, selanjutnya akan diinterpretasikan dalam bentuk gantt chart. 3. Bee Colony Menurut [8], perilaku pencari makanan di sebuah koloni lebah tetap menjadi misteri selama bertahun-tahun, sampai akhirnya Von Frisch menerjemahkan bahasa tertanam dalam lebah saat ia menggoyangkan tarian. Sekitar seperlima dari lebah-lebah di dalam sebuah sarang bertugas sebagai pengumpulnektar. Tugas mereka adalah berkelana di antara bunga-bunga dan mengumpulkan nektar sebanyak mungkin. Ketika kembali ke sarang, mereka menyerahkan muatan nektar mereka kepada lebah-lebah penyimpan-makanan yang menjaga sarang dan menyimpan bahan makanan. Lebahlebah ini kemudian menyimpan nektar di dalam petak-petak madu. Seekor lebah pengumpul-nektar juga dibantu oleh rekanrekannya dalam menentukan seberapa bagus mutu sumber bunganya. Lebah pengumpulnektar tersebut menunggu dan mengamati seberapa lama waktu yang dibutuhkan untuk bertemu dengan seekor lebah penyimpanmakanan yang siap menerima muatan. Jika waktu tunggu ini berlangsung lama, maka sang lebah pengumpul-nektar memahami hal ini sebagai isyarat bahwa sumber bunganya bukan dari mutu yang terbaik, dan bahwa lebah-lebah yang lain kebanyakan telah melakukan pencarian yang berhasil. Sebaliknya, jika ia disambut oleh sejumlah besar lebah-lebah penyimpan-makanan untuk mengambil muatannya, maka semakin besar pula kemungkinan bahwa muatan nektar tersebut bermutu baik. Lebah yang mendapatkan informasi ini memutuskan apakah sumber bunganya senilai dengan kerja keras yang akan dilakukan berikutnya. Jika iya, maka ia melakukan tarian-getarnya agar dipahami
maksudnya oleh lebah-lebah lain. Lama tarian ini memperlihatkan seberapa besar keuntungan yang mungkin dapat diperoleh dari sumber bunga ini. Menurut [9], lebah madu mempunyai dua pola tarian dalam menginformasikan adanya sumber makanan. Tarian keliling (round dance), menginformasikan sumber makanan yang dekat dengan sarang. Tarian goyang (waggle dance), untuk jarak sumber makanan yang lebih dari 15 m. Lebah pemandu melakukan tarian di dalam sarang diikuti oleh 3 sampai 5 ekor lebah pekerja. Metode komunikasi dengan menggunakan tarian goyang, dapat menentukan arah sumber makanan berdasarkan kompas matahari. Banyaknya sumber makanan ditentukan dari lamanya tarian. Jumlah gelombang yang dibentuk pada waktu trayek lurus dan jumlah angka delapan yang terbentuk selama seekor lebah pemandu melakukan tarian goyang, berkorelasi negatif dengan jarak sumber makanan yang dikunjungi. Coding dan decoding ini pada akhirnya membawa lebih banyak lebah terhadap penemuan makanan baru. Tingkah laku lebah ini pada akhirnya meginspirasi Seeley (1995) untuk menjadikannya sebuah model untuk sistem belajar fungsional organisasi di tingkat grup karena sifat interaksinya dengan lingkungan sebagai suatu keseluruhan koheren dan memiliki sejumlah adaptasi yang berfungsi untuk grup. Sunil Nakrani dari University Oxford dan Craig Tovey dari The Georgia Institute of Technology menerapkan cara penyelesaian masalah oleh lebah madu tersebut pada permasalahan pada internet host. Setiap server mengambil peranan sebagai lebah pengumpul manisan, dan setiap permintaan pelanggan bertindak sebagai sumber bunga. Dengan cara ini, Nakrani dan Tovey mengembangkan sebuah algoritma ´lebah madu´ untuk server internet ´host´. Langkah-langkah penyelesaian Optimasi bee colony adalah sebagai berikut : Langkah 1 : Forage Forage ini akan diberikan pada lebah yang akan mengunjungi sumber-sumber makanan yang ada.
Aturan ini akan dilakukan ketika lebah dihadapkan pada beberapa pilihan node yang bisa dikunjungi. Pada persamaan (6) berikut ini adalah fungsi dari waktu proses antar operasi dan arc fitness yang ditampilkan pada edge yang terhubung, Pij (t) =
(t ) . d1
jallowed _ nodes
ij
ij = 1 - m k–m
(6)
(t ) . d1
ij
(7)
ij
node yang ada dalam pilihan. Hal ini akan diungkapkan melalui persamaan (7) di bawah ini.
ij
Dimana: ij = rata-rata sisi antara node i dan node j d ij = jarak heuristic antara node i dan node j Pij = kemungkinan percabangan dari node i dan node j
ij merupakan arc fitness dari node i ke node j. Sedangkan dij merupakan heuristik distance, atau dalam hal ini yang dimaksudkan adalah waktu proses operasi dari operasi yang berhubungan dengan node j. Pij berbanding terbalik dengan dij. Dengan kata lain, dibawah pengaruh heuristic distance, lebah akan mengunjungi node dengan waktu proses yang lebih cepat. merupakan variabel yang berperan sebagai pembobot untuk arc fitness, sedangkan berfungsi untuk mengontrol signifikan level untuk heuristic distance-nya. Untuk pembobotan pada arc fitness pun terdapat aturan bahwa untuk node pilihan yang ada ternyata tersedia pada preferred path, maka node tersebut akan diberikan bobot yang paling tinggi. Sedangkan nodenode pilihan yang lain akan diberi bobot dari rata-rata sisa pembobotan. Jumlah keseluruhan pembobotan adalah 1 untuk semua
Dimana, = nilai yang diberikan ke lintasan yang diinginkan, < 1,0 k = jumlah node yang diijinkan m = jumlah lintasan yang diinginkan, m = 1 atau 0 Langkah 2 : Waggle Dance Saat lebah hendak melakukan pencarian makanan sekembalinya ke sarang dari eksplorasi nektar, lebah akan mencoba dengan probabilitas p untuk menunjukkan waggle dance dalam dance floor. Waggle dance akan berakhir dengan durasi tertentu yang ditunjukkan oleh fungsi linear. Durasi waggle dance akan di definisikan dengan persamaan sebagai berikut : D = A. di = A . Pfi Pfcolony
(8)
dengan durasi D = diA, dimana di berubah dengan profitability rating ketika A menunjukkan faktor skala waggle dance. Selanjutnya ia juga akan berusaha dengan kemungkinan ri untuk mengobservasi dan mengikuti tarian yang terpilih secara random. Kemungkinan ri itu dinamis dan juga berubah dengan profitability rating. Jika lebah memilih untuk mengikuti tarian yang terpilih, dia akan menggunakan ‘path’ yang diambil oleh lebah yang menunjukkan tarian untuk memandu sebagai pemimpin bunga yang ada. Path disebut sebagai ’lintasan yang paling disukai’. Path untuk lebah merupakan rangkaian penunjuk dari sumber (sarang) ke tujuan (nectar).
Untuk penjadwalan job shop, profitability rating seharusnya dihubungkan ke fungsi tujuan, dimana dalam kasus ini adalah makespan. Tarian akan dilakukan oleh seekor lebah ke lebah yang lainnya selama dia mengikuti aturan bahwa lebah yang membangun path lebih pendek atau lebih cepat dari percobaan sebelumnya yang diijinkan untuk melakukan tarian. Dengan kata lain, tidak semua lebah diijinkan untuk melakukan waggle dance. Tetapi hanya lebah yang berhasil mendapatkan solusi yang lebih baik dari solusi terbaik yang dimiliki saat ini yang boleh melakukan waggle dance. Anggap Pfi merupakan profitability rating untuk lebah, seperti rumus yang diberikan di bawah ini: Pfi =
1 i C max
(9)
Dimana, Cimax = makespan dari jadwal yang digenerate oleh lebah fi. Rata-rata profitability rating bee colony, Pfcolony seperti rumus berikut: 1 n 1 Pfcolony = j (10) n j 1 C max Dimana, n = jumlah waggle dance yang dilakukan dalam waktu t (kita hanya menganggap lebah itu yang menari saat profitability rating diperhitungkan) Cjmax = makespan dari jadwal yang digenerate oleh lebah fj yang menunjukkan waggle dance. Pfi dapat diinterpretasikan sebagai kuantitas nektar yang dikoleksi oleh lebah i dimana lebah diasumsikan dapat mengkoleksi sebanyak mungkin nektar. Kualitas nektar tertinggi akan dikoleksi jika lebah
melakukan perjalanan dengan rute yang paling pendek. Jadi semakin tinggi profitabilty, maka kuantitas dan kualitas nektar semakin baik. Kemungkinan ri mengikuti path yang biasa menurut profitability rating dari lebah dan koloni pada dasarnya seperti yang diperlihatkan di tabel 1 (diambil dari Nakrani dan Tovey 2004). Terutama, lebah lebih menyukai mengobservasi secara random dan mengikuti waggle dance dalam dance floor jika profitability rating rendah sebagai perbandingan terhadap koloni. Tabel 3.1 Penyesuaian kemungkinan mengikuti waggle dance
Profitability Rating Pfi < 0.9Pfcolony 0.9Pfcolony Pfi < 0.95Pfcolony 0.95Pfcolony Pfi < 1.15Pfcolony 1.15 Pfcolony Pfi
ri 0.60 0.20 0.02 0.00
Dalam kasus ekstrim, dimana ri adalah nol, maka lebah akan memelihara path-nya sendiri. Lebah lebih suka melakukan pencarian secara random dan mengikuti waggle dance jika profitability rating-nya rendah ketika dibandingkan dengan ratarata profitability koloninya. 4. Hasil Uji Coba Data masukan pada aplikasi yang dibangun ini di ambil dari website ORLibrary dengan alamat http://people.brunel. ac.uk/~mastjjb/jeb/orlib/files/jobshop1.txt. Data-data yang terpilih tersebut antara lain : • Data matriks 6x6 (ftp06) • Data matriks 10x5 (la05) • Data matriks 15x10 (la23) Uji coba kali ini dijalankan selama 5 kali dengan parameter-parameter yang telah ditentukan.
4.1 Analisis Uji Coba Pada bagian ini, keseluruhan hasil uji coba dari data yang digunakan pada proses uji coba akan dibandingkan dengan solusi terbaik yang telah ditemukan sampai pada saat ini untuk masing-masing data. Di bagian ini juga akan dilengkapi dengan analisis terhadap skenario yang telah dilakukan terhadap masing-masing data yang digunakan dalam uji coba. 4.1.1
Analisis Uji Coba Data ftp06 Bagian analisis uji coba data ftp06 akan dibagi ke dalam 2 bagian yaitu analisis perubahan jumlah lebah dan konfigurasi parameter alpha_rating, alpha dan beta. 4.1.1.1 Analisis Skenario Perubahan Jumlah Lebah Data ftp06 Gambar 4.1 menunjukkan hasil yang telah didapatkan dari hasil uji coba tersebut dibandingkan dengan hasil yang pernah didapatkan oleh Pratama (2009) yang menyelesaikan permasalahan yang sama dengan menggunakan algoritma PSO dengan modifikasi .
Dari penjelasan di atas, maka dapat ditarik kesimpulan bahwa semakin banyak jumlah lebah yang diikutkan dalam pencarian solusi, maka solusi yang didapatkanpun akan semakin baik. Hal ini karena dengan menambah jumlah lebah dalam satu koloninya, maka ruang pencarian solusinya pun akan menjadi lebih luas lagi. Sehingga solusi minimalpun akan menjadi semakin mudah untuk ditemukan. Namun jika dibandingkan dengan solusi yang didapatkan oleh Pratama (2009) dengan menggunakan algoritma PSO dengan modifikasi, maka solusi yang dihasilkan oleh bee colony tidak lebih baik. Solusi yang didapatkan oleh bee colony tidak mampu mendapat solusi sebagus dan seoptimal yang dihasilkan oleh PSO. Jika dilihat dari waktu komputasi yang dibutuhkan dalam menghasilkan makespan yang paling minimal pada tabel 4.4 untuk masing-masing skenario uji coba lebah data ftp06, akan semakin bertambah lama apabila jumlah lebah dalam satu koloninya semakin ditingkatkan. 4.1.1.2 Analisis Skenario Perubahan Konfigurasi Parameter Data ftp06 Pada gambar 4.2 akan ditunjukkan hasil yang telah didapatkan dari hasil uji coba tersebut akan dibandingkan dengan hasil yang pernah didapatkan oleh Pratama (2009) yang menyelesaikan permasalahan yang sama dengan menggunakan algoritma PSO dengan modifikasi.
Gambar 4.1 perbandingan makespan masingmasing skenario uji coba perubahan jumlah lebah dengan solusi terbaik yang pernah ditemukan dari data ftp06
Berdasarkan gambar grafik 4.1 dapat disimpulkan bahwa perubahan jumlah lebah memiliki pengaruh untuk membuat solusi yang dihasilkan menjadi semakin lebih baik pada data ftp06. Semakin banyak jumlah lebah, maka semakin baik pula solusi yang dihasilkan. Dengan menggunakan 6, 50, 75, dan 100 lebah, solusi yang dihasilkan mejadi lebih baik saat jumlah lebah semakin diperbanyak hingga berjumlah 100 lebah.
Gambar 4.2 perbandingan makespan masingmasing skenario uji coba perubahan konfigurasi parameter alpha_rating, alpha, dan beta dengan solusi terbaik yang pernah ditemukan dari data ftp06
Berdasarkan gambar grafik 4.2 dapat disimpulkan bahwa semakin diperkecil nilai dari alpha_rating, maka akan membantu mendapatkan solusi yang lebih minimal lagi. Karena, jika nilai alpha_rating diperbesar maka kemungkinan untuk mengambil node akan selalu sama seperti preffered path. Dan hal tersebut menyebabkan jadwal yang dihasilkan antara preferred path dan pembuatan jadwal baru selalu tepat sama. Oleh karena itulah jika nilai alpha_rating diperkecil akan membuat pembangunan jadwal baru tidak selalu tepat sama, tetapi membuat banyak variasi jadwal dan semakin membuka kemungkinan untuk mendapat solusi makespan yang lebih minimal lagi daripada preffered path. Untuk parameter alpha dan beta, kedua variabel ini sangatlah berkaitan erat. Alpha yang mendukung agar node yang dipilih adalah berdasar alpha _rating, sedangkan beta lebih mendukung untuk memilih node berdasar heuristic distance atau waktu prosesnya. Berdasar Gambar 4.2, terlihat bahwa solusi makespan terbaik didapatkan oleh keadaan dimana nilai beta lebih tinggi dibanding nilai alpha. Perubahan konfigurasi parameter ini, tidak berpengaruh cukup berarti terhadap waktu komputasi yang dibutuhkan program untuk menghasilkan solusi makespannya. 4.1.2 Analisis Uji Coba Data la05 Bagian analisis uji coba data la05 akan dibagi ke dalam 2 bagian yaitu analisis perubahan jumlah lebah dan konfigurasi parameter alpha_rating, alpha dan beta. 4.1.2.1 Analisis Skenario Perubahan Jumlah Lebah Data la05 Dari hasil uji coba bee colony akan dibandingkan dengan hasil yang pernah didapatkan oleh Pratama (2009) dengan menggunakan algoritma PSO dengan modifikasi.
Gambar 4.3 perbandingan makespan masingmasing skenario uji coba perubahan jumlah lebah dengan solusi terbaik yang pernah ditemukan dari data la05
Perubahan jumlah lebah ternyata tidak banyak berpengaruh terhadap solusi yang dihasilkan, lihat gambar 4.3. Hasil yang didapatkan oleh lebah yang berjumlah 10, 50, 75 dan 100 menunjukkan angka yang sama dengan hasil yang dicapai oleh PSO. Meskipun demikian, jika dilihat pada gambar 4.23, 4.25, 4.27, dan 4.29 dari perubahan makespan yang dicapai dengan menggunakan jumlah lebah dari 10, 50, 75, hingga 100 lebah selalu mengalami penurunan makespan. Dengan kata lain, dengan meningkatkan jumlah lebah, kemungkinan untuk mendapatkan makespan yang paling minimal setiap kali percobaannya men jadi lebih besar. Tetapi, waktu komputasi yang dihasilkan semakin bertambah lama apabila jumlah lebahnya ditingkatkan. Penghitungan waktu komputasi ini berdasarkan pada waktu komputer. 4.1.2.2 Analisis Skenario Perubahan Konfigurasi Parameter Data la05 Pada gambar 4.4 akan ditunjukkan hasil yang telah didapatkan dari hasil uji coba akan dibandingkan dengan hasil yang pernah didapatkan oleh Pratama (2009) yang menyelesaikan permasalahan yang sama dengan menggunakan algoritma PSO dengan modifikasi.
tersebut akan dibandingkan dengan hasil yang pernah didapatkan oleh Pratama (2009) yang menyelesaikan permasalahan yang sama dengan menggunakan algoritma PSO dengan modifikasi .
Gambar 4.4 perbandingan makespan masingmasing skenario uji coba perubahan konfigurasi parameter alpha_rating, alpha, dan beta dengan solusi terbaik yang pernah ditemukan dari data la05
Jika kita lihat dari gambar 4.4 di atas, dapat disimpulkan bahwa perubahan konfigurasi parameter alpha_rating, alpha dan beta tidak banyak berpengaruh terhadap solusi yang dihasilkan. Meskipun konfigurasi parameter alpha_rating, alpha dan beta telah diubah-ubah mulai dari (0.9,1,1), (0.001,1,1), (0.001,10,1), dan (0.001,1,10), makespan yang dihasilkan tetap konstan pada nilai 593 dan makespan tersebut sama seperti solusi makespan yang dihasilkan oleh Pratama (2009) dengan menggunakan algoritma PSO dari data la05. Hal ini menunjukkan bahwa perubahan kofigurasi parameter alpha_rating, alpha dan beta tidak terlalu memberi pengaruh cukup signifikan terhadap peningkatan kemungkinan pencapaian makespan yang paling minimal yang dihasilkan dari uji coba data la05 untuk setiap percobaannya. Perubahan konfigurasi parameter ini, tidak berpengaruh cukup berarti terhadap waktu komputasi yang dibutuhkan program untuk menghasilkan solusi makespan-nya. 4.1.3 Analisis Uji Coba Data la23 Bagian analisis uji coba data la23 akan dibagi ke dalam 2 bagian yaitu analisis perubahan jumlah lebah dan konfigurasi parameter alpha_rating, alpha dan beta. 4.1.3.1 Analisis Skenario Perubahan Jumlah Lebah Data la23 Pada gambar 4.5 akan ditunjukkan hasil yang telah didapatkan dari hasil uji coba
Gambar 4.5 perbandingan makespan masingmasing skenario uji coba perubahan jumlah lebah dengan solusi terbaik yang pernah ditemukan dari data la23
Berdasarkan gambar grafik 4.5 dapat disimpulkan bahwa solusi makespan paling minimal di dapatkan ketika jumlah lebah menunjukkan angka 75. Meskipun demikian, jika di lihat pada gambar 4.39, 4.41, 4.43, dan 4.45 dimana solusi makespan yang dihasilkan dari perubahan jumlah lebah yang semakin meningkat tersebut, ternyata semakin menunjukkan angka yang semakin minimal pula. Dengan kata lain, dengan meningkatkan jumlah lebah, maka solusi makespan yang dihasilkan setiap kali percobaannya jadi lebih kecil. Tetapi waktu komputasi yang dihasilkan semakin bertambah lama apabila jumlah lebahnya ditingkatkan. 4.1.3.2 Analisis Skenario Perubahan Konfigurasi Parameter Data la23 Pada gambar 4.6 akan ditunjukkan hasil yang telah didapatkan dari hasil uji coba tersebut akan dibandingkan dengan hasil yang pernah didapatkan oleh Pratama (2009) yang menyelesaikan permasalahan yang sama dengan menggunakan algoritma PSO dengan modifikasi.
Gambar 4.6 perbandingan makespan masingmasing skenario uji coba perubahan konfigurasi parameter alpha_rating, alpha, dan beta dengan solusi terbaik yang pernah ditemukan dari data la23
Berdasarkan gambar grafik 4.6 dapat disimpulkan bahwa semakin perubahan konfigurasi parameter alpha_rating, alpha, dan beta, tidak memberikan pengaruh yang cukup signifikan terhadap perolehan solusi makespan. Namun pada gambar di atas dapat dilihat bahwa makespan terkecil di dapatkan ketika alpha_rating menunjukkan angka 0.001, alpha 10, dan beta 1. Dari keseluruhan percobaan yang dilakukan, solusi yang dihasilkan menunjukkan angka yang tidak sama dengan solusi yang berhasil dicapai oleh Pratama (2009) pada data la23. Tetapi, perubahan konfigurasi parameter ini, tidak berpengaruh cukup berarti terhadap waktu komputasi yang dibutuhkan program untuk menghasilkan solusi makespannya. 5. Kesimpulan Berdasarkan proses uji coba dan analisis yang telah dilakukan pada bagian sebelumnya, maka dapat diambil beberapa kesimpulan diantaranya yaitu : 1. Penjadwalan job shop dapat dimodelkan secara matematis dengan memenuhi aturan dan batasan yang berlaku sesuai pengertian secara luas mengenai penjadwalan job shop. 2. Metode optimasi bee colony dapat digunakan sebagai alternatif untuk menyelesaikan permasalahan penjadwalan job shop. 3. Jika dibandingkan dengan algoritma PSO, metode optimasi bee colony ini tidak menyelesaikan permasalahan penjadwalan job shop dengan lebih baik.
Karena nilai makespan yang dihasilkan secara keseluruhan proses uji coba terhadap data yang digunakan tidak berhasil mencapai makespan yang paling minimal, sesuai dengan nilai makespan terbaik yang didapatkan oleh Pratama (2009). Data 6 job dan 6 mesin (ftp06) dengan PSO hasilnya 55, sedangkan dengan bee colony 56. Untuk data 10x5 (la05), hasil PSO sama dengan hasil bee colony yaitu 593. Namun untuk data 15x10 (la23), hasil PSO menunjukkan angka yang lebih minimal yaitu 1032, jika dibanding dengan hasil bee colony yang masih mencapai angka 1313. 4. Untuk mendapat hasil makespan yang semakin minimal (optimal), penambahan jumlah lebah dalam satu koloninya perlu dilakukan. Hal ini terjadi karena semakin banyak jumlah lebah dalam satu koloninya, maka ruang solusi yang akan didapatkanpun menjadi semakin luas. Namun hal ini memiliki kelemahan yaitu jika jumlah lebah ditingkatkan maka waktu komputasinya pun akan semakin meningkat. 5. Pemilihan nilai alpha dan beta sangat berpengaruh dalam menyelesaikan permasalahan penjadwalan job shop khususnya dalam menentukan solusi makespan yang dihasilkan. 6. Daftar Pustaka [1]
Panggabean, Henry Pantas, 2002. Penjadwalan Job shop Statik Dengan Algoritma Simulated Annealing.
[2]
Jain. A. S. and Meeran. S., Deterministic job shop scheduling: past, present and future. European Journal of Operational Research, Vol. 113, No. 2 (1999), pp. 390-434.
[3]
Pervaiz Ahmed, Reza Tavakkoli Moghaddam, Fariborz Jolai & Farzaneh Vaziri, 2004. Solving stochastic job shop scheduling problems by a hybrid method. UK : University of Wolverhampton.
[4] Pratama Hinsa Adi, 2009. Optimasi Permasalahan Penjadwalan Job shop Dengan Menggunakan Metode Particle Swarm Optimization Yang Dimodifikasi. Surabaya : Institut Teknologi Sepuluh Nopember. [5] Maharesi Retno, 2002. Perbandingan Antara Pendekatan Branch And Bound Dan Pemrograman Linear : Dengan Sebuah Contoh Kasus Optimasi. Jakarta: Universitas Gunadharma.
[6]
Henry P. Panggabean. 2005. Penjadwalan Job shop Statik Dengan Algoritma Tabu Search. Integral, vol 10 no 1.
[7] Nahmias, Steven. 1989 & 1993. Production and Operastions Analysis, Second Edition. Sydney: Santa Clara University. [8]
Butt, Norman. 2009. Bee Colonies Applied To Multiprocessor Scheduling. Borlange Sweeden: Dalarna University.
[9] Nismah. 2006. Evaluasi Perilaku Antara Lebah Pekerja Apis Cerana Javana FABR Untuk Menginformasikan Sumber Makanan. Indonesia: Institut Teknologi Bandung [10] Chong, Low, Sivakumar, and Gay. 2006. A Bee Colony Optimization Algorithm To Job shop Scheduling. Proceeding of the 2006 Winter Simulation Conference. [11]
Pinedo L Michael, 2008. Scheduling:Theory, Algorithms, and Systems. USA : NewYork University.
