Rješavanje problema rasporeda pomoću meta-heuristika

diplomski rad

• Naslov (engleski): Solving scheduling problems using meta-heuristics
• Autor: Vedran Deduš
• Mentor: Goranka Nogo (mentor)
• Član povjerenstva: Goranka Nogo (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Dijana Ilišević (član povjerenstva)
• Član povjerenstva: Nikola Sandrić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2021-03-04, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu je predstavljen problem rasporeda sati za fakultete. Instanca problema koju promatramo je NP-teška, pa za njegovo rješavanje koristimo meta-heuristiku genetski algoritam. U radu je opisana svaka faza algoritma - od generiranja početne populacije do implementacije križanja i mutacija. Istaknute su prednosti i mane svake faze algoritma. Rezultati su uspoređeni s rezultatima iz radova koji koriste istu instancu problema te su navedeni mogući načini poboljšanja algoritma.

Sažetak (engleski)

In this thesis we present university course timetable problem and one way of solving it. The instance of the problem we are observing is NP-hard, so we use the meta-heuristic genetic algorithm to solve it. All phases of the algorithm, starting from generating initial population to crossover and mutations, are described with their advantages and disadvantages. Results are then compared with others in similar papers. Finally, possible algorithm improvements are described as well.

• Ključne riječi: raspored sati za fakultete; NP-teško; meta-heuristika genetski algoritam
• Ključne riječi (engleski): university course timetable; NP-hard; meta-heuristic genetic algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:014995
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-03-24 12:10:27