Analisis Komparatif Algoritma Genetika dan Constraint Programming pada Penjadwalan dan Penugasan Guru SMA Negeri 2 Ungaran

Abstract

Penjadwalan sekolah adalah persoalan optimasi yang rumit secara matematis (NP-hard), dan menjadi lebih sulit ketika penjadwalan mata pelajaran dan penentuan guru pengampu harus diselesaikan secara bersamaan, terlebih jika sekolah mewajibkan guru memenuhi jam mengajar minimum. Penelitian ini membandingkan dua metode, yaitu Algoritma Genetika (GA) dan Constraint Programming (CP-SAT), untuk menyusun jadwal mata pelajaran sekaligus menentukan guru pengampu pada SMA Negeri 2 Ungaran, sebuah sekolah menengah atas negeri di Indonesia. Model mencakup 52 unit penjadwalan (36 kelas reguler dan 16 kelompok mata pelajaran agama), 68 guru, dan 47 ruang, dengan sebelas aturan wajib dan satu aturan yang diupayakan, termasuk kewajiban guru mengajar minimal 24 jam pelajaran per minggu. Kedua metode diuji pada dua tingkat kepadatan jadwal, yaitu 46 dan 48 jam pelajaran per minggu. Kinerja keduanya diukur dari tujuh hal yaitu jumlah bentrok jadwal, jam kosong di tengah hari, jumlah guru yang memenuhi beban minimum, jumlah guru yang belum memenuhinya, waktu komputasi, nilai skor kualitas jadwal (fitness), dan tingkat keberhasilan. Hasil menunjukkan CP-SAT berhasil menyusun jadwal tanpa bentrok pada kedua tingkat kepadatan (keberhasilan 100%), sedangkan GA berhasil penuh pada tingkat kepadatan yang lebih longgar tetapi gagal total pada tingkat kepadatan yang lebih padat. Meskipun kedua skenario hanya berbeda dua jam pelajaran per kelas. Perubahan kecil ini menunjukkan bahwa GA kehilangan ruang gerak ketika jadwal terisi penuh, sedangkan CP-SAT tetap mampu menyelesaikannya secara sistematis. GA juga menghasilkan jam kosong lebih sedikit dibanding CP-SAT saat berhasil, tetapi tidak menjamin seluruh guru mencapai beban minimum. Perbandingan ini perlu dibaca hati-hati karena CP-SAT pada penelitian ini tidak diprogram untuk mencari jadwal paling efisien, melainkan hanya mencari jadwal yang sah. Temuan ini membantu sekolah memilih metode penjadwalan yang sesuai dengan tingkat kepadatan jadwal dan ketatnya aturan yang berlaku.

GS Cited Analysis