Abstract

Dalam bidang pendidikan khususnya pada  tingkat universitas terdapat permasalahan yang kerap kali ditemui salah satunya adalah sistem pembuatan jadwal ujian. Pada sistem pembuatan jadwal ujian mata kuliah sering terjadi tumpang tindih antara jadwal mata kuliah satu dengan yang lainnya. Penjadwalan ujian harus dibuat sedemikian rupa sehingga tidak ada mata kuliah yang saling tumpang tindih. Dengan demikian seluruh mahasiswa dapat mengikuti ujian dan tidak ada mata kuliah yang ujiannya menyusul. Dalam  kasus jadwal Ujian Tengah Semester Genap Program Studi Ilmu Informatika terdapat kesalahan pembuatan jadwal ujian,  yakni adanya jadwal ujian mata kuliah yang saling  tumpang tindih sehingga dapat merugikan mahasiswa yang akan mengikuti ujian.  Oleh karena itu diperlukan perbaikan dalam sistem penjadwalan ujian tersebut. Pembuatan jadwal ujian dapat dilakukan dengan menggunakan pewarnaan simpul dan implementasi algoritma Welch Powell. Pengaplikasian pewarnaan simpul pada graf adalah dengan mewakili setiap simpul dengan nama mata kuliah yang tertera di jadwal ujian dan dilanjutkan dengan mengikuti tahapan dari algoritma Welch Powell. Algoritma Welch Powell bekerja dengan cara mengurutkan simpul-simpul yang ada berdasarkan besaran derajat yang dimiliki oleh simpul-simpul tersebut. Setelah diurutkan, simpul yang terbesar akan diberi warna dan simpul yang memiliki hubungan dengan simpul tersebut tidak akan mendapat warna yang sama. Proses ini akan terus berulang hingga semua simpul telah selesai diwarnai, dari simpul yang telah diwarnai ini menghasilkan sebuah jadwal yang tidak tumpang tindih dan siap digunakan. Berdasarkan hasil penelitian, diperoleh bahwa Algoritma Welch Powell mampu menghasilkan jadwal jadwal Ujian Tengah Semester Genap Program Studi Ilmu Informatika yang efisien dan tidak adanya mata kuliah bertabrakan satu dengan yang lainnya.