A β -hill climbing optimizer for examination timetabling problem

Examination timetable is a non-trivial task for administrators of the academic institutions repeated every semester. In terms of optimization, examination timetabling is a combinatorial optimization problem concerned with assigning a set of exams to a predefined number of timeslots and rooms with accordance to a given constraints. In this paper, the extended version of hill climbing algorithm called β-hill climbing is utilized to tackle the examination timetabling problem. β-hill climbing is a new local search-based method that has two operators (β-operator and N-operator) to iterate towards the optimal solution. The saturation degree heuristic method is utilized in the improvement loop of β-hill climbing to ensure the solution feasibility. For experimental evaluation, Carter dataset is used comprising 12 instances selected from several real-world universities. Eight convergence scenarios are designed to sensitively analyze the behavior of the proposed algorithm. For comparative evaluations, the results produced by β-hill climbing are comparatively comparable with previous methods that utilized the same Carter instances.