Stohastic Algorithms for University Course Timetabling

Izrada rasporeda predavanja na sveučilištu je izuzetno važan i vrlo težak optimizacijski problem za koji pronalazak kvalitetnih rješenja predstavlja vrlo izazovan zadatak. Smatra se NP-teškim kombinatornim problemom s vrlo ograničenim prostorom rješenja. U literaturi su razvijene brojne tehnike za rješavanje ovog problema. Predstavljene tehnike u ovom radu razvijene su na temelju aktualnih pristupa problemu sveučilišne satnice. Između postojećih pristupa odabrani su metaheuristički pristupi s obzirom da su smatrani jednim od najboljih za rješavanje problema sveučilišne satnice. Preciznije, odabrani su tabu pretraga i simulirano kaljenje u kombinaciji s algoritmom unatražnog pretraživanja i pretragom velikog susjedstva. Dekompozicija problema je ostvarena podjelom problema u četiri faze gdje svaka sljedeća faza rješava sve složeniji problem. Rezultati su zadovoljavajući te su dane smjernice za daljnja poboljšanja.University course timetabling is extremely important and very difficult optimization problem for which finding a high quality solution is a challenging task. It is considered as NP-hard and highly constrained combinatorial problem. Various techniques have been developed in the literature to tackle this problem. The work presented in this thesis aims to build upon the state of the art in the search methodologies for university timetabling. Among many approaches metaheuristics are considered to be one of the best and therefore are more thoroughly analyzed. Particularly, tabu search and simulated annealing in combination with backtracking and large neighborhood search are employed within multi-phase approach. Problem decomposition is achieved by dividing problem into four phases where each following phase deals with more complexity. Examined approaches provided suitable results and further directions for improvement are given