Penyelesaian Masalah NP-Complete pada Penjadwalan Menggunakan Algoritma Welch-Powell (Graph Coloring) - Lastri Putri Silaban; Bicanro Gebriyan Panjaitan; Azis Kurniadi; Adidtya Perdana (Jurnal Riset Informatika dan Inovasi, 2026)
Penjadwalan mata kuliah merupakan permasalahan kompleks yang termasuk dalam kategori NP-hard karena melibatkan berbagai kendala seperti ketersediaan dosen, ruang, dan waktu. Proses penyusunan jadwal yang dilakukan secara manual sering kali menimbulkan konflik dan membutuhkan waktu yang cukup lama. Penelitian ini bertujuan untuk menerapkan algoritma Welch-Powell dengan pendekatan graph coloring dalam menyelesaikan permasalahan penjadwalan mata kuliah secara efektif dan efisien. Metode yang digunakan adalah pemodelan graf konflik, di mana setiap mata kuliah direpresentasikan sebagai simpul dan hubungan konflik sebagai sisi yang menghubungkan simpul-simpul tersebut. Proses pewarnaan graf dilakukan untuk menentukan slot waktu yang berbeda bagi mata kuliah yang saling berkonflik. Data yang digunakan terdiri dari enam mata kuliah dengan atribut dosen, kelas, dan ruang. Hasil penelitian menunjukkan bahwa algoritma Welch-Powell mampu menghasilkan penjadwalan yang tidak mengalami benturan dengan jumlah slot waktu yang efisien. Dengan demikian, metode ini dapat menjadi solusi sederhana dan efektif dalam menyusun jadwal perkuliahan secara optimal.