Comparative Study of Graph Colouring and Simulated Annealing for Examination Timetabling at UTHM Pagoh

Abstract

The Examination Timetabling Problem (ETP) represents a significant challenge in academic administration. It requires the efficient allocation of exams to limited number of time slots while avoiding conflicts where a student is scheduled for two exams at once. Although various automated heuristics exist to solve this problem, but few studies directly compare their performance under identical conditions. This gap in the literature makes it difficult for institutions to select the most appropriate method. This study aims to fill that gap by fairly comparing two popular methods, namely as Graph Colouring (GC) and Simulated Annealing (SA). This study uses a real dataset from Universiti Tun Hussein Onn Malaysia. The dataset consists of 34 examinations with 941 students in five academic programmes. Both algorithms successfully generated conflict-free timetables. The findings show that the two methods have very different strengths. The results show that Graph Colouring performs well in terms of speed and compactness, and can schedule all exams in 0.0056 seconds with 6 time slots. However, this efficiency generates high load imbalance, with the highest number of 387 students in one session. In contrast, SA is more focus on balance, decreasing the peak occupancy by 75.7% to 94 students per slot, but needs 16 slots and take more computation time. According to this analysis, Graph Colouring is recommended as the more practical choice in this study, providing a fast and compact solution that aligns with the goal of minimizing the examination period. This study offers evidence-based guidelines to help administrators in selecting the most suitable timetabling approach that fits their specific context.