Penyelesaian Masalah NP-Complete pada Penjadwalan Menggunakan Algoritma Welch-Powell (Graph Coloring)
Keywords:
Scheduling, Graph Coloring, Welch-Powell Algorithm, NP-hard, OptimationAbstract
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.
References
Amalia, R. N., & Affandi, P. (2025). Penerapan pewarnaan graf untuk optimalisasi penjadwalan kuliah di program studi matematika. EQUIVA Journal of Mathematics & Information Technology, 3(1).
Andriani, F. R., Maimunah, & Qadarsih, N. D. (2023). Penerapan algoritma Welch-Powell pada penjadwalan mata pelajaran SD. E-Jurnal Matematika, 12(4), 268–273.
Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266–280. https://doi.org/10.1016/S0377-2217(02)00069-3
Fadhilla, C. A. (2024). Penjadwalan mata kuliah otomatis menggunakan algoritma Late Acceptance Hill-Climbing Hyper-Heuristics dengan domain permasalahan ITC. Jurnal Ilmu Komputer dan Sistem Informasi (JIRSI), 3(3), 243–251.
Farisi, S. A., Suhendra, S., Rachman, M. A., Trilaksana, Y., & Destriani, D. (2026). Optimasi penjadwalan perkuliahan menggunakan pemrograman linear: Studi kasus program studi informatika Universitas Baturaja. Sudo Jurnal Teknik Informatika.
Gross, J., & Yellen, J. (2005). Graph theory and its applications. CRC Press.
Hakim, M. L., & Hasibuan, M. (2021). Penerapan metode simulated annealing untuk penjadwalan perkuliahan. Computer Technology and Information System (CTIS), 5(2), 25–38.
Hiryanto, L., & Thio, J. S. (2017). Pengembangan metode graph coloring untuk university course timetabling problem pada Fakultas Teknologi Informasi Universitas Tarumanagara. Jurnal Teknik Informatika, 82–91.
Leighton, F. T. (1979). A graph coloring algorithm for large scheduling problems. Journal of Research of the National Bureau of Standards.
Lubis, M. H., & Syahputra, D. (2024). Penerapan graph coloring dengan algoritma Welch-Powell dalam penjadwalan perkuliahan. Jurnal Informatika dan Sistem Informasi, 8(2), 101–110.
Mutia, A., & Amiroch, S. (2021). Penerapan pewarnaan graf menggunakan algoritma Welch-Powell pada penempatan kamar mahasiswa (studi kasus: Asrama F Universitas Islam Darul ‘Ulum). Jurnal UJMC, 11(1), 103–109.
Septiano, F., Putra, E. K., & Sostriano. (2017). Implementasi metode pewarnaan graf menggunakan algoritma Welch-Powell untuk simulasi penerapan frekuensi radio di Jawa Timur. Jurnal Sains dan Seni ITS, 6(2), A73–A78.
Setiawan, M. A., & Hidayat, T. (2016). Solusi pendekatan SAT problem dengan algoritma genetika. Jurusan Informatika, Fakultas Teknologi Industri, Universitas Islam Indonesia.
Siagian, Q. A. A., Hasibuan, M. S., & Suhardi. (2024). Sistem penjadwalan mata pelajaran memakai algoritma genetika berbasis web. INFOMATEK: Jurnal Informatika, Manajemen dan Teknologi, 26(2).
Suhandi, V., Arisandy, V., & Liputra, D. T. (2023). Penjadwalan mata kuliah dengan mempertimbangkan ketersediaan waktu pengajar dan satuan kredit semester yang tidak terpisah menggunakan integer linear programming. Journal of Integrated System (JIS), 6(1), 73–86.
