Penerapan Modifikasi Algoritma Genetika Dengan Penambahan Konsep Improvement Dalam Permasalahan Penjadwalan Hybrid Flowshop

Abstract

Penjadwalan adalah suatu proses pengalokasian sumber daya (mesin) yang terbatas untuk menyelesaikan sejumlah pekerjaan (job) berbeda. Permasalahan yang muncul pada penjadwalan terjadi apabila pada tahapan operasi tertentu beberapa atau seluruh pekerjaan membutuhkan stasiun kerja yang sama sehingga perlu adanya pengurutan pekerjaan dalam suatu produksi. Salah satu permasalahan dalam penjadwalan adalah penjadwalan Flowshop. Penjadwalan Flowshop adalah penjadwalan proses produksi dari masing-masing 𝑛 job yang mempunyai urutan proses produksi dan melalui 𝑚 mesin yang sama. Permasalahan penjadwalan Flowshop sendiri ada beberapa macam sesuai dengan kondisi dan asumsi yang digunakan. Permasalahan yang sering timbul di perusahaan adalah penjadwalan yang memiliki satu operasi atau lebih yang memiliki lebih dari satu mesin. Permasalahan tersebut termasuk dalam kategori Hybrid Flowshop Scheduling Problem. Pada penelitian ini akan diselesaikan permasalahan Hybrid Flowshop Scheduling menggunakan algoritma improve genetika yaitu pengembangan algoritma genetika dengan menambahkan konsep improvement dari algoritma Hybrid Tabu Search. Selain itu pada proses crossover dan mutasi akan dikembangkan juga metode-metodenya menjadi delapan kombinasi untuk dicari kombinasi terbaiknya. Data Hybrid Flowshop yang digunakan adalah data sekunder dengan banyak stage adalah 5 dan 8 serta banyak job adalah 20 dan 50. Data tersebut berisi banyaknya mesin pada setiap stage, waktu dan banyaknya mesin yang dibutuhkan untuk menyelesaikan setiap job. Hasil penelitian yang diperoleh setelah melakukan percobaan sebagai berikut. Nilai parameter threshold yang paling baik pada data kecil maupun data besar yaitu = 30. Hal ini karena threshold 30 tidak terlalu kecil maupun tidak terlalu besar, karena jika nilai threshold terlalu kecil, maka semakin cepat populasi berganti dengan yang baru. Hal tersebut menyebabkan sulit untuk konvergen. Akan tetapi jika nilai threshold terlalu besar, maka hasilnya akan terjebak pada lokal optimum yang terlalu lama. Perbandingan hasil kombinasi terbaik dari data kecil dan data besar yaitu kombinasi Two Cut Point dan Hybrid mutation, hal ini karena pada kombinasi Two cut point memiliki offspring atau anak yang sangat berbeda dengan induknya, sehingga kemungkinan ruang pencariannya semakin luas. Perbandingan maxgen 500 dan maxgen 1000 secara keseluruhan baik pada percobaan data kecil maupun data besar, nilai maxgen yang semakin besar menghasilkan makespan yang lebih optimal. Hal ini dipengaruhi oleh nilai maxgen yang semakin besar maka ruang pencariannya semakin luas atau semakin mendekati total kemungkinan solusi. Penelitian nilai makespan yang paling optimal diperoleh dari algoritma improve genetika. Makespan yang dihasilkan pada data kecil yaitu 1062,4 dengan nilai APDA = 8,8%. Sedangkan pada data besar menghasilkan makespan yaitu 2735,9 dengan nilai APDA = 3,6%. Dengan demikian, penerapan algoritma improve genetika pada permasalahan penjadwalan hybrid flowshop lebih efektif daripada algoritma genetika, namun tingkat kecepatan dan kekonvergenan algoritma improve genetika tidak dapat dipastikan karena terdapat proses random. Waktu komputasi rata-rata yang dibutuhkan untuk menyelesaikan 5 stage 20 job adalah 20,8 detik (500 iterasi) dan 57,9 detik (1000 iterasi). Sedangkan untuk menyelesaikan 8 stage 50 job adalah 158,2 detik (500 iterasi) dan 312,7 detik (1000 iterasi).