Penyelesaian Penjadwalan Flexible Job Shop Problem dengan menggunakan Real Coded Genetic Algorithm

Penyelesaian Penjadwalan Flexible Job Shop Problem dengan menggunakan Real Coded Genetic Algorithm M. C. C. Utomo 1, Wayan Firdaus Mahmudy 2, Marji Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Indonesia [email protected], [email protected] Kata kunci: Job Shop, FJSP, Flexible Job Shop Problem, Algoritma Genetika, GA, Genetic Algorithm, RCGA, Real Code Genetic Algorithm, Scheduling, Penjadwalan. Abstrak. Menjadwalkan 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). Prakata Masalah job shop adalah masalah penjadwalan untuk memproduksi permintaan pelanggan dengan waktu secepat mungkin. Sebuah produksi membutuhkan berbagai operasi tergantung permintaannya dan setiap operasi hanya bisa diselesaikan oleh mesin tertentu. 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 [5]. 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 [4].

Dengan kata lain flexible job shop tidak hanya memutuskan kapan operasi tersebut dilakukan tetapi juga memutuskan dengan mesin mana operasi tersebut dilaksanakan. Objek dalam FJSP umumnya meminimalkan makespan seperti, waktu penyelesaiannya dari semua operasi atau pekerjaan [1]. Optimalisasi Penyelesaian penjadwalan flexible job shop problem dengan menggunakan real code genetic algorithm adalah algoritma yang ditemukan oleh Mahmudi, dkk [1]. Disini 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. Data yang digunakan adalah MK06 dari

Original Article Utomo, MCC, Mahmudy, WF & Marji 2014, 'Penyelesaian penjadwalan flexible job shop problem dengan menggunakan real coded genetic algorithm', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 3, no. 13.

Brandimarte [6] dengan parameter sebagai berikut, • • •

Population size Crossover rate Mutation rate

= 100 = 0.5 = 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

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.

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 Original Article Utomo, MCC, Mahmudy, WF & Marji 2014, 'Penyelesaian penjadwalan flexible job shop problem dengan menggunakan real coded genetic algorithm', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 3, no. 13.

• •

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. Performalisasi 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 Jumlah generasi

= 1000 = 1000

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.


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.

Tabel 1. Hasil uji coba pada data MK01 sampai MK07 serta perbandingannya dengan algoritma lain Problem

Jobs

Macs

Ops

Mine RCGA MK01 10 6 55 40 MK02 10 6 58 27 MK03 15 8 150 204 MK04 15 8 90 61 MK05 15 4 106 173 MK06 10 15 150 66 MK07 20 5 100 142 MK08 20 10 225 MK09 20 10 240 MK10 20 15 240 Pada Tabel 1. adalah Hasil uji coba pada data MK01 sampai MK07 serta perbandingannya dengan algoritma lain dari sumber reference [2] 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 GENANCE untuk data MK01, MK02, MK04, MK06, MK07 dan hPSO untuk data MK04, MK07. Kesimpulan Untuk real code genetic algorithm, Metode seleksi yang lebih baik adalah binary tournament selection, sedangkan

From reference RCGA GENACE GA hPSO hGA 41 40 40 40 40 27 29 27 26 26 204 204 204 204 67 63 61 60 60 176 173 173 173 173 66 68 63 65 62 142 148 139 145 141 523 523 523 523 523 328 311 331 307 307 231 214 212 212 223 metode mutasi yang lebih baik adalah reciprocal exchange mutation. Untuk metode crossover yang cocok dan mudah diimplementasikan hanya satu yaitu onecut 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. Daftar Pustaka [1] Mahmudy, W. F., R. M. Marian and L. H. S. Luong (2013). "Real coded genetic algorithms for solving


Flattening Search for the Flexible Job Shop Scheduling Problem. Twenty Second International Joint Conference.

flexible job-shop scheduling problem – Part I: modeling." Advanced Materials Research 701: 359-363. [2]

[3]

Mahmudy, W. F., R. M. Marian and L. H. S. Luong (2013). "Real coded genetic algorithms for solving flexible job-shop scheduling problem – Part II: optimization." Advanced Materials Research 701: 364-369. Mastrolilli, M., Gambardella, L. M., (1999) Effective Neighborhood Functions for the Flexible Job Shop Problem. Switzerland: IDSIA.

[4] Pezzella, F., Morganti, G., Ciaschetti, G., (2008). A Genetic Algorithm for the Flexible Job-Shop Scheduling Problem. Elsevier. [5]

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.

[6]

P. Brandimarte, Routing and Scheduling in a Flexible Job Shop by Tabu Search, Annals of Operations Research, vol. 41 no. 3 (1993), pp. 157-183.

[7]

Jansen, K., Mastrolilli, M., Solisoba, R., 2000. Approximation Algorithms for Flexible Job Shop Problems. World Scientific Publising.

[8]

Oddi, A., Rasconi, R., Cesta, A., Smith, S. F., 1991. Iterative

[9]

Thornblad, K., Almgren, T., Patriksson, M., Stromberg, A., Mathematical Optimization of A Flexible Job Shop Problem Including Preventive Maintenance and Availability of Fixtures.

[10] Behnke, D., Geiger, M. J., 2012. Test Instance for the Flexible Job Shop Scheduling Problem with Work Centers. Hamburg: HelmutSchmidt-University. [11] Mahmudy, W. F., R. M. Marian and L. H. S. Luong (2012). Solving part type selection and loading problem in flexible manufacturing system using real coded genetic algorithms – Part I: modeling. International Conference on Control, Automation and Robotics, Singapore, World Academy of Science, Engineering and Technology. [12] Mahmudy, W. F., R. M. Marian and L. H. S. Luong (2012). Solving part type selection and loading problem in flexible manufacturing system using real coded genetic algorithms – Part II: optimization. International Conference on Control, Automation and Robotics, Singapore, World Academy of Science, Engineering and Technology.

Pernyataan Penulis Naskah ini dikirimkan untuk keperluan repository skripsi mahasiswa di Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya dan tidak melalui proses evaluasi oleh reviewer ahli seperti layaknya naskah jurnal ilmiah.


Penyelesaian Penjadwalan Flexible Job Shop Problem dengan menggunakan Real Coded Genetic Algorithm

Recommend Documents