Examination Timetabling Automation and Optimization using Greedy-Simulated Annealing Hyper-heuristics Algorithm

摘要

Examination timetabling problem (ETP) is one of challenging combinatorial optimization problems, either scientifically or practically. In the scientific literatures, ETP has been proven as a non-deterministic polynomial (NP)-hard problem. In practice, examination timetabling is known as tedious and stressful work especially when double degree was offered by the university. In this study, two real-world datasets of ETP are introduced and solved using a combination of graph-coloring based sequential greedy algorithm and simulated annealing (SA) algorithm. Different from the state-of-the-art approaches in the literature, in which SA was employed within meta-heuristics, in this study SA was implemented within hyper-heuristics framework. The experimental results show that the proposed algorithm successfully automate the timetabling process and generates better timetable compared to the timetable generated manually. More specifically, tested over the two datasets the proposed algorithm, in terms of soft constraint penalty that should be minimized, could improve manual timetable from 39,569 to 33,649 and from 76,763 to 34, 929. In addition to new real datasets, the main contribution of this study is a better understanding on the performance of Simulated Annealing within hyper-heuristics for solving real-world examination timetabling problem.