Penjadwalan Pelajaran Sekolah Menggunakan Sistem Multi Agen dan Particle Swarm Optimization Studi Kasus: SMA Negeri 9 Yogyakarta

POERWIYANTO, Dr. Azhari, M.T.

2016 | Tesis | S2 Ilmu Komputer

Penjadwalan adalah proses membuat daftar, tabel kegiatan atau rencana kegiatan dengan pembagian waktu pelaksanaan yang terperinci. Penjadwalan pelajaran sekolah dinilai lebih rumit dibandingkan dengan penjadwalan-penjadwalan lain karena melibatkan guru, mata pelajaran, ruangan, dan siswa. Dilihat dari perspektif Ilmu Komputer, penjadwalan pelajaran sekolah digolongkan dalam masalah NP-complete yang artinya tidak ada algoritma waktu polinomial yang bisa digunakan untuk menyelesaikan masalah penjadwalan pelajaran sekolah. Oleh karena itu, metode-metode optimasi alternatif telah digunakan untuk mendapatkan solusi optimal. Berbagai metode telah digunakan untuk menyelesaikan masalah penjadwalan pelajaran sekolah. Tiga diantaranya adalah Particle Swarm Optimization, Simulated Annealing, dan Sistem Multi Agen. Pada penelitian ini, ketiga metode digabungkan untuk melakukan penjadwalan pelajaran sekolah yang selanjutnya dinamakan MAPSO-SA. Metode ini diuji dengan data 19 kelas, 46 guru, dan 18 mata pelajaran dan dibandingkan dengan 4 metode lainnya, yaitu PSO, PSO dengan mutasi, PSO-SA, dan MAPSO. Hasil penelitian menunjukkan MAPSO-SA lebih unggul dibandingkan 4 metode lainnya dan bisa menghasilkan jadwal yang bisa langsung dipakai dengan soft constraints seminimal mungkin dari data uji yang diberikan.

Scheduling is the process of making a detail list or table of activities or planned activities. School course scheduling is considered to be more complicated than other scheduling problems because school course scheduling involves more entities, such as teachers, subjects, rooms, and students. From the perspective of Computer Science, school course scheduling is classified as NP-complete problems, which means there is no polynomial time algorithm that can be used to solve school course scheduling. Therefore, alternative optimization methods have been used to obtain a (near) optimal solution. Various methods have been used to solve school course scheduling, some of those are Particle Swarm Optimization, Simulated Annealing, and Multi-Agent Systems. This research will hybrid those three methods hereinafter called MAPSO-SA. The method is tested with 19 classes, 46 teachers, and 18 subjects data and compared to four other methods, the PSO, PSO with mutation, PSO-SA, and MAPSO. The result shows that MAPSO-SA has better performance than the other four methods and is able to produce a ready-to-use schedule with minimal soft constraints from the test data.

Kata Kunci : Penjadwalan Pelajaran Sekolah, Particle Swarm Optimization, Simulated Annealing, Sistem Multi Agen