Conflict-Free School Timetabling Using Graph Coloring and Hybrid Metaheuristic Algorithms

Abstract
Scheduling academic activity, staff, and spaces within schools is a complex yet vital exercise that requires attention to an enormous number of rigidity and flexibility constraints during the assignment. Manual or heuristic approaches are often sunk by the demand for scalability and find it difficult to provide schedules that are free of conflicts in fast changing academic environments. With ability to create a robust and flexible timetabling system in mind, this study utilises graph theory and state-of-the-art tools for optimization purposes in order to increase the scheduling performance and minimise problems associated with overlapping of resources. The unique aspect of the study is the application of a combination of Genetic Algorithms and Simulated Annealing in a graph theory-based framework. By borrowing graph coloring for scheduling conflicts, the model deviates from traditional methods, and improves refinement through the combined use of GA exploration and SA\'s local optimization capabilities; generating more optimized timetables. This is enhanced by the usage of chromosome encoding in GA and matrix format in SA to improve efficiency in conflict detection and clearer view representation. The proposed framework was validated using benchmark data - with 98% accuracy achieved in satisfying all constraints. The lowest solution, using solution 2 with the aid of the hybrid model, was 45 units of cost, compared to the others that cost 85 and 70 units and with the reduction in violations and processing time. By integrating graph theory and GA-SA hybrid optimization, we end up with ordurable, conflict-free and resource-saving algorithm for school timetabling. Future works will include deep learning methods to refine the framework\'s performance and flexibility to large academic set ups.

Author
Sazan Kamal Sulaiman

DOI
https://doi.org/10.1109/I2ITCON65200.2025.11210664

ISSN
2161-2064

Publish Date: 4-Jul-2025