APLIKASI PEWARNAAN GRAF DALAM PENJADWALAN MATA KULIAH

Abstrak

Tujuan dilakukan penelitian ini adalah untuk mengaplikasikan teori pewarnaan graf dalam penjadwalan mata kuliah di Program Studi Pendidikan Matematika di Universitas Muslim Nusantara Al-Washliyah. Hal ini dilakukan karena memang salah satu kendala dalam penyusunan jadwal kuliah adalah bagaimana menyusun jadwal kuliah yang sesuai dengan kesediaan hari dan jam para dosen yang mengampu mata kuliah tersebut untuk mengajar, sehingga tidak terjadi bentrok diantaranya. Hal seperti ini merupakan suatu permasalahan yang selalu dijumpai dalam penjadwalan. Penjadwalan mata kuliah ini haruslah teratur agar perkuliahan dapat terlaksana dengan lebih optimal. Pewarnaan graf merupakan salah satu teknik dalam teori graf yang dapat dijadikan penanganan dalam menghadapi masalah penjadwalan tersebut. Teknik ini menggunakan representasi graf, dimana mata kuliah dan dosen direpresentasikan sebagai vertex dan hubungan antara dua buah vertex tersebut direpresentasikan sebagai jalur. Algoritma yang digunakan dalam pewarnaan graf pada penelitian ini adalah algoritma Welch-Powell. Algoritma ini menghasilkan jadwal mata kuliah yang sesuai dengan kesediaan hari dan jam para dosen yang mengampu mata kuliah tersebut tanpa ada bentrokan jadwal diantaranya. Penggunaan algoritma tersebut pada penelitian ini menghasilkan 4 susunan jadwal yang berbeda untuk penjadwalan kuliah semester II dengan 9 orang dosen dan 5 hari kuliah, 4 susunan jadwal yang berbeda untuk penjadwalan kuliah semester IV dengan 9 orang dosen dan 5 hari kuliah, 3 susunan jadwal yang berbeda untuk penjadwalan kuliah semester VI dengan 7 orang dosen dan 4 hari kuliah dan 2 susunan jadwal yang berbeda untuk penjadwalan kuliah semester VIII dengan 3 orang dosen dan 3 hari kuliah