Izrada sveučilišne satnice uporabom stohastičkih algoritama

master's thesis

• Title (english): Stohastic Algorithms for University Course Timetabling
• Author: Dominik Poljak
• Mentor: Marin Golub (mentor)
• Committee member: Marin Golub (predsjednik povjerenstva)
• Committee member: Željka Mihajlović (član povjerenstva)
• Committee member: Marko Čupić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-07-14, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: sveučilišna satnica; pristupi rasporedu predavanja na sveučilištu; metaheuristike; simulirano kaljenje; tabu pretraga
• Keywords (english): university timetabling; approaches to university course timetabling; metaheuristics; tabu search; simulated annealing
• Language: croatian
• URN:NBN: urn:nbn:hr:168:319306
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 11:22:35