Graph Coloring Application in Course Scheduling Using the Welch-Powell Algorithm (Case Study: Mathematics Study Program, Dharma Andalas University)

Source abstract

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.