Penyelesaian Penjadwalan Flexible Job Shop Problem Menggunakan Real Coded Genetic Algorithm

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer Vol. 1, No. 1, Januari 2017, hlm 57-62

e-ISSN: 2548-964X http://j-ptiik.ub.ac.id

Penyelesaian Penjadwalan Flexible Job Shop Problem Menggunakan Real Coded Genetic Algorithm M. C. C. Utomo 1, Wayan Firdaus Mahmudy 2, Marji 3 Fakultas Ilmu Komputer, Universitas Brawijaya, Indonesia [email protected], [email protected], [email protected] Abstrak Penjadwalan adalah masalah yang cukup sulit jika harus dituntut dalam waktu cepat dan akan menjadi lebih merepotkan lagi jika susunan yang dijadwalkan adalah sesuatu yang tidak pasti dengan banyaknya pilihan yang membutuhkan keputusan yang lebih rumit. Model penjadwalan jobshop merupakan salah satu contoh masalah penjadwalan yang banyak ditemui dalam industri manufaktur. Penyelesaiannya rumit dan solusi terbaik hanya bisa didapatkan dengan mencoba semua kemungkinan. Algoritma genetika adalah salah satu algoritma yang dapat memberikan solusi permasalahan rumit dalam waktu yang bisa diterima secara rasional, sehingga dapat diterapkan untuk masalah Flexible Job Shop. Algoritma Genetika mampu menemukan solusi dengan mencoba menukarkan susunan-susunan yang diberikan dan/atau mencoba mengganti susunan tersebut secara langsung (crossover dan/atau mutation) Kata kunci: Job Shop, FJSP, Flexible Job Shop Problem, Algoritma Genetika, Real Code Genetic Algorithm, Penjadwalan Abstract Scheduling is a problem that is quite difficult if it should be prosecuted in quick time and will be more troublesome if the arrangement is scheduled for something uncertain with many options that require a more complicated decision. Jobshop scheduling model is one example of scheduling problems that were encountered in the manufacturing industry. Completion of complex problem and the best solution can only be obtained by trying all possibilities. Genetic algorithm is one of algorithms which can provide complex solutions to problems within acceptable time rationally, so that it can be applied to the Flexible Job Shop problem. Genetic Algorithm is able to take into account by trying to exchange arrangements provided and/or try to replace the array directly (crossover and/or mutation). Keywords: Job Shop, FJSP, Flexible Job Shop Problem, Genetic Algorithm, Real Code Genetic Algorithm, Scheduling operasi hanya bisa diselesaikan oleh mesin tertentu. Masalah penjadwalan job shop fleksibel (Flexible Job Shop Problem, FJSP) umumnya berasal dari masalah job shop klasik (Classical Job Shop Problem). FJSP lebih sulit daripada JSP klasik. karena melibatkan tingkat keputusan yang lebih rumit selain urutan pekerjaan misalnya. Untuk menentukan urutan pekerjaan berarti juga menentukan setiap operasi untuk mesin mana yang tersedia yang harus memprosesnya (Al-Hinai dan Elmekkawy, 2012).

1. PENDAHULUAN Penjadwalan job shop termasuk hal yang penting untuk sistem manufaktur. Sebuah jadwal yang baik harus dibentuk untuk mencapai pemanfaatan sistem yang tinggi dan mengurangi biaya produksi dari sistem manufaktur. Masalah job shop adalah masalah penjadwalan untuk memproduksi permintaan pelanggan dengan waktu secepat mungkin. Sebuah produksi membutuhkan berbagai operasi tergantung permintaannya dan setiap Fakultas Ilmu Komputer Universitas Brawijaya

57

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

Flexible job shop berarti beberapa atau seluruh operasi tersebut bersifat fleksibel yang berarti terdapat mesin lain yang dapat menyelesaikan dengan hasil yang sama baiknya. Tentu saja dengan semakin banyaknya pilihan akan semakin membuat bingung untuk mengambil keputusan dan membutuhkan proses yang lebih rumit daripada job shop biasa (AlHinai dan Elmekkawy, 2012). FJSP dalam sistem manufaktur yang sebenarnya seringkali terjadi insiden yang tidak terduga, jika secara teori mungkin menghasilkan jadwal yang optimal atau mendekati optimal namun kinerjanya menjadi buruk ketika diimplementasikan pada pekerjaan yang sebenarnya (Pezzella, Morganti, Ciaschetti, 2008). Dengan kata lain flexible job shop tidak hanya memutuskan kapan operasi tersebut dilakukan tetapi juga memutuskan dengan mesin mana operasi tersebut dilaksanakan. Pada penelitian ini digunakan algoritma genetika dengan pengkodean real menye saikan FJSP. 2. FLEXIBLE JOB SHOP PROBLEM Ada dua keputusan harus dibuat dalam FJSP tersebut, yaitu memilih mesin mana untuk setiap operasi harus dilakukan dan mengatur urutan operasi pada mesin. Tujuan dalam FJSP umumnya meminimalkan makespan seperti waktu penyelesaiannya dari semua operasi atau pekerjaan (Mahmudy, Marian dan Luong 2013a). Pentingnya FJSP untuk lingkungan industry manufaktur ditunjukkan dalam sejumlah literatur yang mengusulkan berbagai macam metode untuk menghasilkan solusi yang baik. Sebagai contoh Yazdani dkk. (2009) dan Witkowski, dkk. (2010) mengggunakan simulated annealing untuk menyelesaikan FJSP. Li dkk. (2010) mengusulkan hybrid particle swarm optimization and tabu search algorithm (hPSO). Sebagai algoritma yang dikenal unggul untuk masalah optimasi kompleks (Mahmudy, 2014), algoritma genetika juga banyak digunakan. Misalnya, Ho dan Tay (2004) mengusulkan a cultural-based GA (GENACE). Algoritma genetika juga diusulkan oleh Pezzella, Morganti, dan Ciaschetti (2008). Penyelesaian penjadwalan flexible job shop problem dengan menggunakan real code genetic algorithm adalah pendekatan yang diusulkan oleh Mahmudy, Marian dan Luong Fakultas Ilmu Komputer, Universitas Brawijaya

58

(2013b). Pada penelitian ini akan dilakukan uji coba untuk mengetahui metode yang mampu mendapatkan hasil yang lebih baik. Metode yang akan dibandingkan adalah metode seleksi antara lain roulette wheel selection, binary tournament selection, dan etilist selection serta metode mutasi antara lain reciprocal exchange mutation, insertion mutation, dan invertion mutation. 3. METODE PENELITIAN Bagian ini membahas langkah-langkah yang digunakan dalam pembuatan perangkat lunak dan metode percobaan. Tahap-tahap pembuatannya adalah sebagai berikut: Analisis permasalahan dan perancangan sistem penjadwalan paling efisien dengan menggunakan algoritma genetika. Membuat sistem penjadwalan berdasarkan analisis permasalahan dan perancangan yang dilakukan. Melakukan uji coba terhadap sistem penjadwalan. Melakukan evaluasi (analisa hasil) yang diperoleh dari uji coba sistem. 4. PROSES ALGORITMA GENETIKA Representasi kromosom dan langkahlangkah dalam algoritma genetika diadopsi dari penelitian Mahmudy, Marian dan Luong (2013b). Langkah-langkah proses penyelesaian flexible job shop problem dengan menggunakan algoritma genetika adalah sebagai berikut: 1. Inisialisasi parameter awal, yaitu: - Memasukkan berbagai parameter permintaan pekerjaan beserta operasioperasi yang diperlukan, mesin-mesin yang mampu menangani, dan waktu operasi dari masing-masing mesin yang mampu menangani. - Jumlah individu atau popSize pada sebuah populasi - Jumlah generasi atau iterasi yang akan dilakukan. - Probabilitas crossover ( ) - Probabilitas mutasi ( ) 2. Bangkitkan populasi awal sebanyak sejumlah individu yang telah ditentukan sebagai kromosom induk. 3. Membuat populasi baru atau offspring dengan menggunakan langkah-langkah berikut sebanyak jumlah generasi atau iterasi yang telah ditentukan:

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

- Pilih 2 kromosom induk secara acak dan lakukan proses crossover pada induk tersebut. Lakukan berulang berdasarkan yang telah ditentukan. - Pilih sebuah kromosom induk secara acak dan lakukan proses mutasi pada induk tersebut. Lakukan berulang berdasarkan nilai yang telah ditentukan. - Hitung nilai fitness pada masingmasing kromosom yang didapatkan. - Lakukan proses seleksi dengan metode Roulette whell untuk menentukan kromosom induk untuk generasi berikutnya. 4. Jika kondisi akhir terpenuhi, berhenti dan hasilnya adalah solusi terbaik pada seluruh generasi. 5. UJICOBA DAN ANALISIS Data yang digunakan adalah MK06 dari Brandimarte (1993) dengan parameter sebagai berikut,  Population size = 100  Crossover rate = 0.5  Mutation rate = 0.25 Pada uji coba metode seleksi terbaik sementara menggunakan metode reciprocal exchange mutation karena metode tersebut yang paling terkenal dan yang paling sering diimplementasikan. Sedangkan untuk uji coba metode mutasi terbaik menggunakan metode seleksi terbaik yang telah didapatkan. Uji coba dilakukan sebanyak 10 kali dan diambil nilai minimal, rata-rata, dan maksimal.

Gambar 1. Grafik hasil uji coba metode seleksi

Fakultas Ilmu Komputer, Universitas Brawijaya

59

Gambar 2. Grafik hasil uji coba metode mutasi Dari hasil uji coba tersebut didapatkan sebuah grafik seperti pada Gambar 1. dan dapat diambil kesimpulan bahwa metode seleksi terbaik adalah binary tournament selection. Pada generasi sekitar 100 dan di bawahnya diketahui bahwa metode seleksi terbaik adalah etilist selection mungkin disebabkan karena metode tersebut mampu membentuk populasi berkualitas dengan cepat tetapi tidak jika dalam waktu yang lama. Metode binary tournament selection mampu memberikan hasil yang terbaik untuk jumlah generasi yang besar mungkin disebabkan karena metode tersebut mampu membentuk populasi yang berkualitas sekaligus mempertahankan individu yang bervariasi di dalam populasi, ini berbeda dengan metode etilist selection di mana hanya individu yang terbaik saja yang diambil. Dari hasil pengamatan tersebut juga didapatkan bahwa populasi yang homogen dan kurang bervariasi pada individunya menyebabkan sulit berkembang dan dapat dilihat dari grafik yang cenderung mendatar. Individu yang terbaik dari setiap generasi tidak disimpan secara eksklusif atau terjamin untuk terpilih semakin membuktikan bahwa metode binary tournament selection mampu membentuk populasi yang semakin berkualitas dalam generasi yang besar, ini berbeda dengan metode yang murni dari etilist selection yang sudah menjamin individu yang terbaik terpilih dari setiap generasinya. Sedangkan pada Gambar 2. dapat diambil kesimpulan bahwa metode reciprocal exchange mutation adalah yang terbaik di samping mudahnya untuk diimplementasikan. Tidak mengherankan memang bahwa metode tersebut yang paling terkenal dan yang paling banyak digunakan.

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

Gambar 3. Grafik hasil uji coba perbandingan probabilitas crossover dan mutation Setelah mendapatkan metode seleksi dan mutasi terbaik maka selanjutnya mendapatkan perbandingan probabilitas crossover dan mutation terbaik. Total perbandingan adalah 1.0 sehingga didapatkan populasi hingga 2 kali lipat, maka dipilih 0.7:0.3, 0.6:0.4, 0.5:0.5, 0.4:0.6, 0.3:0.7. Dengan menggunakan data yang sama, population size yang sama, jumlah generasi = 300, metode seleksi dan mutasi yang sudah diketahui yang terbaik di atas maka didapatkan hasil uji coba seperti pada Gambar 3. Dari hasil uji coba tersebut dapat diambil kesimpulan bahwa perbandingan probabilitas terbaik antara crossover dan mutation adalah 0.5:0.5. Setelah mengetahui metode seleksi terbaik (binary tournament selection) dan metode mutasi terbaik (reciprocal exchange mutation) serta perbandingan probabilitas antara crossover dan mutation terbaik (0.5:0.5) maka selanjutnya menguji real code genetic algorithm pada flexible job shop problem untuk jumlah generasi dan population size yang besar. Data yang digunakan adalah MK01 sampai MK07 dari Brandimarte yang dapat diunduh (download) dari alamat http://www.idsia.ch/~monaldo/fjsp.html dengan parameter sebagai berikut,  Population size = 1000  Jumlah generasi = 1000

Fakultas Ilmu Komputer, Universitas Brawijaya

60

Gambar 4. Grafik hasil uji coba pada data MK01

Gambar 5. Grafik hasil uji coba pada data MK06

Gambar 6. Grafik hasil uji coba pada data MK01 sampai MK07 Uji coba dilakukan sebanyak 10 kali dan diambil nilai rata-rata. Hasil uji coba dapat dilihat pada Gambar 6 dan dengan skala 100 iterasi.

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

61

Tabel 1. Hasil uji coba pada data MK01 sampai MK07 serta perbandingannya dengan algoritma lain Problem MK01 MK02 MK03 MK04 MK05 MK06 MK07 MK08 MK09 MK10

Jobs 10 10 15 15 15 10 20 20 20 20

Macs 6 6 8 8 4 15 5 10 10 15

Ops 55 58 150 90 106 150 100 225 240 240

Usulan RCGA 40 27 204 61 173 66 142 -

Dari hasil uji coba tersebut dapat diambil kesimpulan bahwa pada Gambar 4. mampu mendapatkan hasil yang paling efisien pada generasi ke 600, sedangkan pada Gambar 5. pada generasi ke 1000 meskipun belum mampu mendapatkan hasil yang paling efisien, tetapi dilihat dari pola grafik sepertinya masih memiliki potensi untuk mendapatkan hasil yang lebih optimal apabila menggunakan jumlah generasi dan population size yang lebih besar. Dengan jumlah generasi dan population size yang lebih besar tentu berakibat pada kebutuhan perangkat keras yang lebih tinggi untuk melakukan proses. Perbedaan hasil pada MK01 dan MK06 disebabkan karena kompleksitas di mana MK06 lebih kompleks daripada MK01. Pada Tabel 1. adalah Hasil uji coba pada data MK01 sampai MK07 serta perbandingannya dengan algoritma lain dari sumber referensi (Mahmudy, Marian dan Luong, 2013b). menunjukkan bahwa hasil penelitian ini mampu menandingi RCGA dari referensi untuk data MK01, MK02, MK03, MK05, MK06, MK07 dan tidak pada data MK04. Selain itu hasil penelitian ini juga mampu menandingi pendekatan lain untuk data MK01, MK03, MK05 dan tidak untuk data MK02, MK04, MK06, MK07. Setidaknya hasil penelitian ini mampu melakukan dengan lebih baik dari pada a cultural-based GA (GENACE) yang diusulkan Ho dan Tay (2004) untuk data MK01, MK02, MK04, MK06, MK07 dan hybrid particle swarm optimization and tabu search algorithm (hPSO) yang diusulkan Li dkk. (2010) untuk data MK04, MK07. 6. KESIMPULAN Untuk real code genetic algorithm, Metode Fakultas Ilmu Komputer, Universitas Brawijaya

RCGA 40 27 204 60 173 66 142 523 307 231

Dari Literatur GENACE GA 41 40 29 26 204 67 60 176 173 68 63 148 139 523 523 328 311 212 212

hPSO 40 27 204 63 173 65 145 523 331 223

hGA 40 26 204 61 173 62 141 523 307 214

seleksi yang lebih baik adalah binary tournament selection, sedangkan metode mutasi yang lebih baik adalah reciprocal exchange mutation. Untuk metode crossover yang cocok dan mudah diimplementasikan hanya satu yaitu one-cut point crossover. Perbandingan antara crossover rate dan mutation rate yang mendekati terbaik adalah 0.5:0.5. Sedangkan untuk jumlah generasi yang paling efektif dan efisien adalah relatif tergantung besarnya data yang diproses untuk dibentuk jadwal, waktu untuk memproses data, kerugian tiap makespan, termasuk juga spesifikasi kebutuhan perangkat keras yang digunakan untuk memproses sedangkan besaran populasi mungkin hanyalah masalah spesifikasi komputer yang digunakan. 7. DAFTAR PUSTAKA Al-Hinai, N., Elmekkawy, T. Y., (2012). Solving the Flexible Job Shop Scheduling Problem with Uniform Processing Time Uncertainty. World Academy of Science, Enginering and Technology. Brandimarte, (1993) Routing and Scheduling in a Flexible Job Shop by Tabu Search, Annals of Operations Research, vol. 41 no. 3 (1993), pp. 157-183. Ho, NB & Tay, JC (2004), GENACE: an efficient cultural algorithm for solving the flexible job-shop problem, IEEE international conference on robotics and automation, pp. 1759–1766. Li, J-q, Pan, Q-k, Xie, S-x, Jia, B-x & Wang, Y-t (2010), A hybrid particle swarm optimization and tabu search algorithm for flexible job-shop scheduling problem,

Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer

International Journal of Computer Theory and Engineering, vol. 2, no. 2, pp. 1793-8201. Mahmudy, W. F. (2014), Optimisation of Integrated Multi-Period Production Planning and Scheduling Problems in Flexible Manufacturing Systems (FMS) Using Hybrid Genetic Algorithms, School of Engineering, University of South Australia. Mahmudy, W. F., R. M. Marian and L. H. S. Luong (2013a). Real coded genetic algorithms for solving flexible job-shop scheduling problem – Part I: modeling. Advanced Materials Research 701: 359363. Mahmudy, W. F., R. M. Marian and L. H. S. Luong (2013b). Real coded genetic algorithms for solving flexible job-shop scheduling problem – Part II: optimization. Advanced Materials

Fakultas Ilmu Komputer, Universitas Brawijaya

62

Research 701: 364-369. Pezzella, F, Morganti, G & Ciaschetti, G (2008), 'A genetic algorithm for the flexible job-shop scheduling problem', Computers & Operations Research, vol. 35, no. 10, pp. 3202-3212. Witkowski, T, Antczak, P & Antczak, A (2010), Solving the flexible open-job shop scheduling problem with grasp and simulated annealing', Artificial Intelligence and Computational Intelligence (AICI), 2010 International Conference on, 23-24 Oct. 2010, pp. 437442. Yazdani, M, Gholami, M, Zandieh, M & Mousakhani, M (2009), A simulated annealing algorithm for flexible jobshop scheduling problem, J. Applied Sci, vol. 9, pp. 662-670.