Graph Coloring Application in Course Scheduling Using the Welch-Powell Algorithm (Case Study: Mathematics Study Program, Dharma Andalas University)
DOI:
https://doi.org/10.64570/jamm.v2i1.58Keywords:
Graph, Graph Coloring, Course Scheduling, Welch-Powell Algorithm, Chromatic NumberAbstract
Course scheduling is a crucial and routine academic activity carried out by universities prior to the commencement of a new academic year, requiring precise arrangements to avoid timing conflicts for both lecturers and students. The course scheduling for the odd semester of the 2024/2025 academic year at the Mathematics Study Program of Dharma Andalas University (UNIDHA) faces high complexity in manually allocating various combinations of lecturers, classes, and courses. This study aims to optimize the scheduling system by utilizing the concept of graph coloring, specifically employing the Welch-Powell Algorithm. The research method involves transforming the lecturer's teaching assignment data into an undirected graph model. Course variations are modeled as 21 vertices, while potential scheduling conflicts due to identical lecturers or student groups are represented as edges. The Welch-Powell Algorithm is then applied by sorting the vertices based on the largest degree ordering to color them progressively. The results indicate that this graph representation successfully yields a chromatic number of x(G) = 6. Consequently, from a total of 9 lecturers teaching 21 courses, the entire academic schedule is optimally distributed into 6 distinct color groups without any conflicts. These color groups are successfully implemented into 6 academic working days (Monday to Saturday) with precise time-slot allocations corresponding to the respective credit semester units (SKS). The study concludes that the application of graph coloring using the Welch-Powell Algorithm is highly effective, objective, and systematic in resolving course scheduling conflicts within the Mathematics Study Program at UNIDHA.
References
Bettinelli, A., Cacchiani, V., Roberti, R., & Toth, P. (2015). An overview of curriculum-based course timetabling. TOP, 23, 313-349. https://doi.org/10.1007/s11750-015-0366-z .
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. London: Springer. Munir, R. (2010). Matematika diskrit. Bandung: Informatika.
Burke, E. K., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for timetabling problems. European Journal of Operational Research, 176(1), 177-192. https://doi.org/10.1016/j.ejor.2005.08.012 .
Chartrand, G., & Zhang, P. (2012). A First Course in Graph Theory. Dover.
Chen, M., Werner, F., & Shokouhifar, M. (2023). Mathematical modeling and exact optimizing of university course scheduling considering preferences of professors. Axioms, 12(5), 498. https://doi.org/10.3390/axioms12050498.
Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Harary, F. (1969). Graph Theory. Addison-Wesley.
Given, L. M., & Saumure, K. (2008). The SAGE Encyclopedia of Qualitative Research Methods. Sage.
Gross, J. L., & Yellen, J. (2006). Graph Theory and Its Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. Jensen, T. R., & Toft, B. (2011). Graph Coloring Problems. New York: Wiley.
Jensen, T. R., & Toft, B. (2011). Graph Coloring Problems. Wiley.
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr+Ps)-free graphs. Algorithmica, 82, 1833-1858. https://doi.org/10.1007/s00453-020-00675-w .
Lewis, R. M. R. (2021). Guide to graph colouring: Algorithms and applications (2nd ed.). Springer. https://doi.org/10.1007/978-3-030-81054-2 .
Munir, R. (2010). Matematika Diskrit. Informatika.
Tassopoulos, I. X., Iliopoulou, C. A., Katsaragakis, I. V., & Beligiannis, G. N. (2023). An effective local particle swarm optimization-based algorithm for solving the school timetabling problem. Algorithms, 16(6), 291. https://doi.org/10.3390/a16060291 .
Welch, T., & Powell, M. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85–86.
West, D. B. (2001). Introduction to Graph Theory (2nd Bettinelli, A., Cacchiani, V., Roberti, R., & Toth, P. (2015). An overview of curriculum-based course timetabling. TOP, 23, 313-349. https://doi.org/10.1007/s11750-015-0366-z .
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. London: Springer. Munir, R. (2010). Matematika diskrit. Bandung: Informatika.
Burke, E. K., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper-heuristic for timetabling problems. European Journal of Operational Research, 176(1), 177-192. https://doi.org/10.1016/j.ejor.2005.08.012 .
Chartrand, G., & Zhang, P. (2012). A First Course in Graph Theory. Dover.
Chen, M., Werner, F., & Shokouhifar, M. (2023). Mathematical modeling and exact optimizing of university course scheduling considering preferences of professors. Axioms, 12(5), 498. https://doi.org/10.3390/axioms12050498.
Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Harary, F. (1969). Graph Theory. Addison-Wesley.
Given, L. M., & Saumure, K. (2008). The SAGE Encyclopedia of Qualitative Research Methods. Sage.
Gross, J. L., & Yellen, J. (2006). Graph Theory and Its Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. Jensen, T. R., & Toft, B. (2011). Graph Coloring Problems. New York: Wiley.
Jensen, T. R., & Toft, B. (2011). Graph Coloring Problems. Wiley.
Klimošová, T., Malík, J., Masařík, T., Novotná, J., Paulusma, D., & Slívová, V. (2020). Colouring (Pr+Ps)-free graphs. Algorithmica, 82, 1833-1858. https://doi.org/10.1007/s00453-020-00675-w .
Lewis, R. M. R. (2021). Guide to graph colouring: Algorithms and applications (2nd ed.). Springer. https://doi.org/10.1007/978-3-030-81054-2 .
Munir, R. (2010). Matematika Diskrit. Informatika.
Tassopoulos, I. X., Iliopoulou, C. A., Katsaragakis, I. V., & Beligiannis, G. N. (2023). An effective local particle swarm optimization-based algorithm for solving the school timetabling problem. Algorithms, 16(6), 291. https://doi.org/10.3390/a16060291 .
Welch, T., & Powell, M. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85–86.
West, D. B. (2001). Introduction to Graph Theory (2nd ed.). New Jersey: Prentice Hall.
