Hybrid Approach for Automated University Academic Timetable using Graph Coloring Techniques and Linear Programming Mathematical Resource Optimization Model

Abstract

University course timetabling is a complex optimization problem that must satisfy multiple hard and soft constraints. These include avoiding clashes among courses and lecturers, allocating limited classroom and laboratory spaces, and ensuring efficient use of academic resources. Traditional manual or semi-manual timetabling methods often result in scheduling conflicts, inefficient utilization of facilities, and significant time wastage, which adversely affects academic activities. To overcome these challenges, this study proposes an integrated approach that combines graph coloring techniques with a linear mathematical optimization model to automate the university timetabling process. The proposed methodology is adaptable to different academic environments and institutional contexts. Its effectiveness is validated through a real-world case study conducted at the Faculty of Computing, Sabaragamuwa University of Sri Lanka, using academic and scheduling data analyzed with MATLAB. The study is organized into two main phases. In the first phase, a graph-based model represents courses as vertices and scheduling conflicts as edges. An adjacency matrix and the Welsh–Powell graph coloring algorithm are employed to assign a minimum number of conflict-free time slots. In the second phase, a linear programming model is applied to optimize room allocation with the objective of maximizing the utilization of available lecture halls and laboratories. The results indicate that the proposed system can produce completely conflict-free timetables while significantly enhancing lecture room utilization. As a next step, the study aims to evaluate seat wastage by analyzing unoccupied seating capacity. Future enhancements include increasing automation through the development of a more user-friendly interface. Overall, this research provides a structured and practical solution to the university timetabling problem, contributing to improved administrative efficiency and effective resource utilization.