Üniversite Ders Çizelgeleme Probleminin Tamsayılı Doğrusal Programlama ve Sezgisel Yaklaşımlar İle Çözümü

Abstract

University course timetabling is a problem type that is in the NP-Complete problem class and can become even more difficult due to the specific requirements of each university. In this study, it is aimed to design to a solver that can be used to solve university course timetabling problems which consists of multiple departments, have many common resources as well as have elective and multi-section courses at faculty level by using integer liner programming or heuristic approaches, and to develop assignment models that can be easily adapted to the problem in the similar structure. In this context, ILP and heuristic models that can take into account availability of mandatory, multi-section mandatory and elective of the courses were developed. In the ILP model, the number of decision variables and constraints have significantly reduced since the parameters were grouped according to indices. In this way, Faculty of Economics and Administrative Sciences at Hacettepe University course timetabling problem which is a large scale real-life problem could has been solved optimally. While this model is an exact algorithm, heuristics algorithms are two-stage. In the first stage, a feasible initial solution is obtained and in the second stage, the quality of the solution is improved. Two different approaches are proposed for the initial solution: a greedy heuristics (GH) and an iterative forward search (IFS). In the second stage, tabu search (TS) and simulating annealing (SA), which are local search heuristics, are used. When an additional constraint (room stability constraint) has added to the models, the complexity of the problem has increased and the optimal solution could has not be reached with the ILP model. When heuristic models have used, relatively bettered solutions have obtained. The results have shown that the GH algorithm is faster than the IFS algorithm in the initial solution stage and that the SA heuristic give better results than the TS heuristic in the improvement stage