Efficient Hybrid Iterated Local Search with Threshold Acceptance Algorithm for Addressing Real World Examination Timetabling Problem

The scheduling of exams in universities is a complex optimization problem, especially when resources like room capacity are limited. This paper explores optimization approaches using Iterated Local Search (ILS), Threshold Acceptance (TA), and Hill Climbing algorithms for optimizing exam timetabling in the Department of Information Systems at the Institut Teknologi Sepuluh Nopember (ITS). The primary challenge is to maximize room usage while satisfying strict hard constraints, such as student and proctor availability, alongside minimizing penalties from soft constraints like timing and location preferences. The study compares the performance of ILS-TA with Hill Climbing and manual scheduling solution across multiple datasets. Generally, the experimental results indicate that ILS-TA outperforms both Hill Climbing algorithm and manual solution. More specifically, over Dataset 1 and Dataset 2 ILS-TA outperform Hill Climbing by 47% and 9% respectively. On the other hand, compared to manual solutions, the solution from the proposed algorithm is better by 63%, 27%, and 37% over Datasets 1,2,3 respectively.