Solving examination timetabling problem within a hyper-heuristic framework

Shinta Dewi, Raras Tyasnurita, Febriyora Surya Pratiwi

Abstract


Scheduling exams in colleges are a complicated job that is difficult to solve conventionally. Exam timetabling is one of the combinatorial optimization problems where there is no exact algorithm that can answer the problem with the optimum solution and minimum time possible. This study investigated the University of Toronto Benchmark Dataset, which provides 13 real instances regarding the scheduling of course exams from various institutions. The hard constraints for not violate the number of time slots must be fulfilled while paying attention to fitness and running time. Algorithm of Largest Degree, Hill Climbing, and Tabu Search within a Hyper-heuristic framework is investigated with regards to each performance. This study shows that the Tabu Search algorithm produces much lower penalty value for all datasets by reducing 18-58% from the initial solution.

Keywords


Examination timetabling; Hill climbing; Hyper-heuristic; Largest degree; Tabu search



DOI: https://doi.org/10.11591/eei.v10i3.2996

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Bulletin of EEI Stats