Rješavanje problema rasporeda pomoću meta-heuristika

master's thesis

• Title (english): Solving scheduling problems using meta-heuristics
• Author: Vedran Deduš
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Committee member: Nikola Sandrić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-03-04, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: raspored sati za fakultete; NP-teško; meta-heuristika genetski algoritam
• Keywords (english): university course timetable; NP-hard; meta-heuristic genetic algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:014995
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-03-24 12:10:27