Penjadwalan Menggunakan Metode Graph Coloring

Share A. Latar belakang masalah
Penjadwalan kuliah merupakan suatu pekerjaan rutin dalam sistem akademik di Perguruan Tinggi yang dilakukan setiap menghadapi semester baru. Pada pelaksaanaannya, seringkali jadwal yang telah dikeluarkan belum pasti sehingga membutuhkan adanya penjadwalan ulang. Hal ini mengakibatkan perkuliahan di awal semester berjalan tidak efektif karena harus melakukan penyesuaian jadwal dengan keadaan real setelah jadwal dikeluarkan. Selain itu, kesulitan dalam hal pencarian slot yang masih kosong juga menjadi suatu kendala terutama pada saat mencari jadwal kuliah pengganti atau kuliah tambahan.
Dalam melakukan penjadwalan kuliah, diperlukan pemikiran yang cukup rumit untuk dapat memetakan sejumlah komponen penjadwalan (mata kuliah, dosen, mahasiswa, ruang, dan waktu) ke dalam timeslot (matriks ruang dan waktu) dengan mempertimbangkan semua batasan yang ada. Proses manual memerlukan waktu yang cukup lama untuk dapat melakukan hal ini dan memungkinkan terjadinya pelanggaran constraint akibat human error. Pelanggaran constraint dalam penjadwalan menjadikan jadwal tidak valid dan harus direkonstruksi ulang. Jika kejadian seperti ini selalu berulang tiap kali menghadapi semester baru, maka sepatutnya permasalahan ini mendapat prioritas untuk dicari solusinya demi peningkatan mutu sistem akademik di Perguruan Tinggi.
Permasalahan penjadwalan kuliah terkait erat dengan masalah optimasi. Oleh karena itu, pengembangan sistem penjadwalan kuliah dilakukan dengan melalui beberapa iterasi perbaikan. Fungsi tujuannya adalah memenuhi sejumlah constraint penjadwalan, seperti menghindari terjadinya bentrok jadwal. Dalam kajian ilmu di Matematika Diskrit, teori Graph memberi solusi untuk permasalahan ini melalui bahasannya tentang pewarnaan Graph. Pembangunan sistem penjadwalan kuliah yang menerapkan teori ini diharapkan mampu menjawab permasalahan ini secara jitu sehingga dapat diimplementasikan untuk penjadwalan kuliah.

Download Proposalnya DI SINI