Graph Coloring with Welch-Powell Algorithm in Determining Lecture Schedule

Abstract

Penataan jadwal perkuliahan di perguruan tinggi melibatkan pembagian waktu, ketersediaan dosen, dan ketersediaan ruang kelas. Salah satu algoritma yang dapat digunakan untuk membuat jadwal yang baik tanpa adanya konflik adalah algoritma Welch Powell. Pada Program Studi Matematika FMIPA USU terdapat 61 mata kuliah untuk semester ganjil dan 44 mata kuliah untuk semester genap tahun 2023/2024. Oleh karena itu, diperlukan pewarnaan graf untuk mengatur jadwal perkuliahan agar tidak terjadi konflik antara pembagian waktu, ketersediaan dosen, dan ketersediaan ruang kelas. Mata kuliah direpresentasikan dalam bentuk grafik dan selanjutnya grafik tersebut diwarnai dengan algoritma Welch-Powell yang menghasilkan 12 bilangan kromatik atau 12 warna sehingga terdapat 12 sesi optimum yang dibutuhkan untuk penjadwalan perkuliahan pada semester ganjil dan genap. Berdasarkan hasil tersebut, warna yang sama dapat dijadwalkan pada hari dan waktu yang sama dengan kelas yang berbeda.