Hyper-heuri̇sti̇c approaches for examination timetabling problems

Exam timetabling is to plan a series of exams, a series of timeslots and a series of rooms, taking into account hard and soft constraints. Exam timetabling problems are constrained and multi-parameter optimization problems that require time and labor to be solved especially encountered in universities during each exam period. There are many different studies in the literature for the solution of these problems. In these studies, many methods have been proposed for solving exam timetabling problems. However, researchers have recently seen that the hyper-heuristic approaches are successful in these problems and have turned to this field. Hyper-heuristic approaches are independent from the problem area that produces the appropriate combination of low level heuristics using the predefined low level heuristics for a particular problem or set of problems. In this thesis, hyper-heuristic approaches are presented for solving exam timetabling problems. The main purpose of the thesis study is to examine exam timetabling problems and to solve the exam timetabling problems with hyper-heuristic methods. Hyper-heuristic approaches are divided into heuristic selection and heuristic generation. In this study, selection hyper-heuristics are used. Hyper-heuristic approaches that select heuristic consists of two phases: heuristic selection and move acceptance. Of heuristic selection methods, simple random and random permutation which was changed within the scope of the thesis study was used in this study. Of the move acceptance methods, only improving was used. Two different hyper-heuristic approaches have been designed with these heuristic selection and move acceptance methods. In this study, hard constraints are provided firstly. Then low level heuristics based on penalty matrices were used to increase the quality of the solution by supplying soft constraints. The focus is on supporting to the hyper-heuristic approach with the low level heuristics. The designed two hyper-heuristic approaches were tested on the problems presented in 2007 by the International Timetabling Competition (ITC-2007), which are real world examples. When the results were examined, it was seen that these two approaches gave close results, but the second approach was better. When the hyper heuristic approaches are compared with some studies in the literature; they were superior in some results and competitive in some results.