Optimasi Penjadwalan Mata Pelajaran pada Kurikulum 2013 dengan menggunakan Hibridisasi Algoritme Genetika dan Simulated Annealing (Studi Kasus: SMA Negeri 6 Surabaya)

Abstrak

Penjadwalan merupakan salah satu masalah komputasi yang tidak mudah diselesaikan. Dalam menyelesaikannya harus disiapkan secara sistematis, dengan memaksimalkan sumber daya dan waktu yang ada secara efektif dan efisien. Masalah penjadwalan dapat terjadi dalam berbagai bidang, tidak terkecuali bidang pendidikan. SMA Negeri 6 Surabaya merupakan salah satu sekolah menengah atas di Surabaya yang memiliki permasalahan dalam menemukan slot waktu yang tepat dengan jumlah guru yang terbatas serta terdapat beberapa constraint yang harus dipenuhi dalam penjadwalan mata pelajaran. Salah satu metode yang dapat digunakan dalam penjadwalan mata pelajaran  adalah dengan menggunakan hibridisasi algoritme genetika dan simulated annealing (GA-SA) karena GA memiliki kelemahan konvergensi dini dan kemungkinan terjebak dalam local optimum, maka diberikan SA sebagai solusi untuk menutupi kelemahan GA dan mampu bertahan pada local optimum. Proses hibridisasi algoritme ini dilakukan dengan langkah pertama pada GA menggunakan representasi kromosom bilangan integer, one-cut point crossover, reciprocal exchange mutation, dan elitism selection. Pada langkah yang kedua, dilakukan proses simulated annealing dengan menggunakan neighborhood move. Hasil yang diberikan adalah penjadwalan mata pelajaran dengan memenuhi constraint yang ada. Berdasarkan penelitian yang dilakukan, didapatkan parameter-parameter optimal yaitu jumlah generasi 270, jumlah populasi 90, kombinasi nilai cr dan mr adalah 0.3 dan 0.7 dengan rata-rata nilai fitness sebesar 0,999000.