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.
