Graph Colouring Technique for Timetable Scheduling in UTHM

Abstract

Timetable scheduling is a complex combinatorial optimization problem that requires assigning courses, instructors, classrooms, and time slots while satisfying hard and soft constraints. Traditional methods often struggle in solving scheduling conflicts making it inefficient for students and instructors. This study proposes an automated timetable scheduling for university using the graph colouring technique. The main objective of this study is to create a conflict-free academic timetable for university scheduling using custom graphical user interface (GUI). This study implements graph colouring technique where each course is modelled as a vertex and edges represent conflicts. The Welsh-Powell algorithm ensures a valid colouring that no two conflicting vertices share the same colour. The problems were converted into a conflict graph to represent all conflicts, and the colouring process used to generate conflict-free timetable. A GUI was created to load dataset, interpret data, and evaluate the scheduling outcomes. The performance of the generated timetable is evaluated through the penalty score that measure soft constraint violations, slot utilization efficiency and engagement days. Experimental results demonstrates that the proposed approach successfully eliminates hard constraints, reduces soft constraints and produces a structured academic timetable. In this study, the graph colouring technique has effectively proven in producing conflict-free academic timetables, offering a practical tool for departmental timetabling. The current practice of this study is focusing on medium-sized dataset; therefore, the GUI performance must be tested before applying for larger dataset.