Application of the Welch-Powell Graph Coloring Algorithm for Optimizing Course Scheduling Using Python (Case Study: Computer Science Program, Faculty of Mathematics and Natural Sciences, HKBP Nommensen University, Pematangsiantar)

Ropitta Anjelina  Manik; Juli Antasari  Sinaga; Gayus  Simarmata

doi:10.55927/ijar.v5i6.16577

Authors

Ropitta Anjelina Manik Universitas HKBP Nommensen
Juli Antasari Sinaga Universitas HKBP Nommensen
Gayus Simarmata Universitas HKBP Nommensen

DOI:

https://doi.org/10.55927/ijar.v5i6.16577

Keywords:

Graph Theory, Graph Coloring, The Welch-Powell Algorithm, Course Scheduling

Abstract

Course scheduling is the process of assigning courses to specific time slots and classrooms while taking into account various applicable academic constraints. This study discusses the application of graph theory in the development of a course schedule for the Computer Science Program at the Faculty of Mathematics and Natural Sciences (FMIPA). The main problem in course scheduling is schedule conflicts caused by instructors teaching more than one course. To address this problem, the graph coloring method using the Welch-Powell algorithm is employed. Each course is represented as a vertex, while scheduling conflicts between courses are represented as edges based on shared instructors. The research process begins with the construction of a conflict graph, the determination of vertex degrees, and the sorting of vertices by highest degree, followed by the graph coloring process using the Welch-Powell algorithm. The coloring results show that course schedules can be grouped into several colors representing class days without causing conflicts in faculty schedules. Semester 2 requires 4 colors, semester 4 requires 5 colors, semester 6 requires 6 colors, and semester 8 requires 2 colors. The research results show that the graph coloring method using the Welch-Powell algorithm is capable of producing a more structured and effective class schedule while minimizing faculty schedule conflicts. Thus, the application of graph theory can serve as an alternative solution in the process of developing class schedules in higher education settings.

Downloads

Download data is not yet available.

References

A. A. Pratama, M. Bettiza, dan A. Uperiati, “Aplikasi Penjadwalan Mata Pelajaran Menggunakan Algoritma Genetika,” Student Online J. Umr., vol. 2, no. 1, hal. 97–105, 2021.

A. M. Nasir and D. Setyawan, “Optimalisasi Penjadwalan Mata Kuliah Menggunakan Teori Pewarnaan Graf,” vol. 5, pp. 57–69, 2021.

Abdulsalaam, S. A., & Saddiq, K. (2021). University undergraduate courses timetabling with graph coloring. Abacus (Math. Sci. Ser.), 48(2), 142-150

Amalia, R. N., & Affandi, P. (2025). Penerapan Pewarnaan Graf Untuk Optimalisasi Penjadwalan Kuliah Di Program Studi Matematika: Algoritma Welch-Powell. Equiva Journal, 3(1), 34-42.

Biggs, N. L., Lloyd, E. K., & Wilson, R. J. (1976). Graph Theory 1736–1936. Oxford: Clarendon Press.

Biswas, S., Nusrat, S. A., Sharmin, N., & Rahman, M. (2023). Graph coloring in university timetable scheduling. International Journal of Intelligent Systems and Applications, 15(3), 16-32.

Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. London: Springer.

Buhaerah, B., Busrah, Z., & Sanjaya, H. (2022). Teori Graf dan Aplikasinya.

Carlson, S. C. (2017). Königsberg bridge problem. Encyclopaedia Britannica.

Daniel, F., & Taneo, P. N. (2020). Teori Graf. Deepublish.

Diestel, R. (2017). Graph Theory (5th ed.). Berlin: Springer.

Downey, A. B. (2015). Think Python: How to Think Like a Computer Scientist (2nd ed.). O’Reilly Media.

Even, S., Itai, A., & Shamir, A. (1976). On the complexity of timetabling and multicoloring problems. SIAM Journal on Computing, 5(4), 691–703.

F. F. Kawatu, V. E. Regar, P. Studi, P. Matematika, and U. N. Manado, “Welch-Powell Algorithm Implementation In Compiling Lecture Schedules In The Mathematics Education Study Program, Manado State University,” vol. 1, no. 2, 2023.

Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman.

Ghozali, I. (2021). Aplikasi analisis multivariate dengan program IBM SPSS 26 (10th ed.). Badan Penerbit Universitas Diponegoro.

Gross, J. L., & Yellen, J. (2018). Graph Theory and Its Applications (3rd ed.). Boca Raton: CRC Press.

Jain, M., Raikoti, S., Bala, S. J., Kumar, V. J., Sulaiman, S. K., & Vijayalakshmi, B. A. (2025, July). Conflict-Free School Timetabling Using Graph Coloring and Hybrid Metaheuristic Algorithms. In 2025 International Conference on Information, Implementation, and Innovation in Technology (I2ITCON) (pp. 1-5). IEEE.

Kehinde, O. S., Idowu, P. O., Funmilayo, O. F., Kemi, O. O., & Omidiora, E. O. (2024). Optimizing University Course Timetabling Using Graph Coloring Techniques. Mathematics and Computer Science: Contemporary Developments Vol. 5, 42-62.

Lewis, R. (2021). A Guide to Graph Colouring: Algorithms and Applications (2nd ed.). Springer.

Lutz, M. (2013). Learning Python (5th ed.). O’Reilly Media.

M. Van Der Wegen, Complexity of Graph Problems : Gonality , Colouring and Scheduling. 2021. doi: 10.33540/709.

Marinu waruwu dkk. (2025). Metode Penelitian Kuantitatif: Konsep, Jenis, Tahapan dan Kelebihan. Waruwu et al.,(2025). Jurnal Ilmiah Profesi.

Primadi, dkk (2024). Konsep Penelitian Kuantitatif: Populasi, Sampel, dan Analisis Data (sebuah Tinjauan Pustaka). Jurnal Ilmu Multidisiplin. Vol.3, No. 1.

Putu Gede Subhaktiyasa . (2024). Menentukan Populasi dan Sampel: Pendekatan Metodologi Penelitian Kuantitatif dan Kualitatif. Jurnal Ilmiah profesi Pendidikan. Vol.9 No.4

R. M. Rohmawati and M. I. A. Fathoni, “Penerapan Algoritma Welch-Powell Pada Penyusunan Jadwal Perkuliahan di Program Studi Pendidikan Matematika,” vol. 10, no. 2, pp. 200–210, 2022.

Rao, G. R., & Shobha Latha, G. (2026). Applications of edge coloring graph with chromatic index. Advanced International Journal For Research (AIJFR),7(1).

Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13, 87–127.

Shiqing Hua, Hongda Quan, and Lingbao Kong, "Efficient scanning strategy via graph coloring for crosstalk mitigation in chromatic confocal measurement," Opt. Express 34, 5966-5981 (2026).

Sugiyono. (2022). Metode penelitian kuantitatif, kualitatif, dan R&D (3rd ed.). Alfabeta.

Van Rossum, G., & Drake, F. L. (2009). Python 3 Reference Manual. Scotts Valley: CreateSpace.

Welch, D. J. A., & Powell, M. B. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85–86.

Zelle, J. (2017). Python Programming: An Introduction to Computer Science (3rd ed.). Franklin, Beedle & Associates.