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

diplomski rad

• Naslov (engleski): Stohastic Algorithms for University Course Timetabling
• Autor: Dominik Poljak
• Mentor: Marin Golub (mentor)
• Član povjerenstva: Marin Golub (predsjednik povjerenstva)
• Član povjerenstva: Željka Mihajlović (član povjerenstva)
• Član povjerenstva: Marko Čupić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-14, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: sveučilišna satnica; pristupi rasporedu predavanja na sveučilištu; metaheuristike; simulirano kaljenje; tabu pretraga
• Ključne riječi (engleski): university timetabling; approaches to university course timetabling; metaheuristics; tabu search; simulated annealing
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:319306
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 11:22:35