Primjena metaheuristika na problem izrade dislociranog školskog rasporeda sati

master's thesis

• Title (english): Metaheuristics applied on dislocated school timetabling
• Author: Tihana Jonjić
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Marko Đurasević (član povjerenstva)
• Committee member: Ante Đerek (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu ukratko je obrađen problem školskog rasporeda sati i pristup rješavanju. Dodatno ograničenje u ovom radu kojim se prostor problema proširuje je dislokacija rasporeda. Obzirom da su rasporedi jako bitna stavka užurbanog i modernog načina života, potreba za kvalitetnim rasporedima je sve veća. Dobar raspored teško je napraviti ručno, i zato dolazi do potrebe za automatiziranim pristupom pravljenju rasporeda. Konkretno, problem školskog rasporeda sati se ubraja u NP teške probleme. Za rješavanje ovakvih problema izbjegavaju se pristupi kao što je iscrpno pretraživanje a najčešće se koriste heurističke metode optimizacije koje ne osiguravaju uvijek najbolje rješenje, ali dovoljno dobro rješenje. U ovom radu opisana je implementacija metaheuristike koja stvara raspored koji zadovoljava čvrsta ograničenja. Konačno, Sustav je testiran nad konkretnim podacima OŠ Jure Kaštelan u Zagrebu i rezultati su prikazani u poglavlju 6.

Abstract (english)

Modern day societies bring about the hastiness and rush into the daily life of every individual. Loosing as little time as possible on menial tasks is becoming more and more crucial in everyday living. The need for proper scheduling and planning of public transportation grows as our lives become more intertwined each day. These schedules are not easy to make by hand and this is where heuristic approaches can change the way we organise daily commuters with goal of making their commutes as effective as possible. This thesis covers the difficulties of creating optimised school schedule and details heuristic approach in solving the said issue. Public transport and student dislocation expands and limit this thesis with factors that need to be taken in account when coming to a conclusion. This problem is categorised as NP hard problem, where exhaustive research approaches are generally avoided and heuristic optimisation met- hods offer viable results. The research and implementation use metaheuristic which generates schedule with hard limitations. Ultimately, the entire system is tested on the data provided by the Elementary School Jure Kaštelan in Zagreb and conclusions are placed in chapter 6.

• Keywords: problem raspoređivanja; školski raspored; dislokacija; optimizacija; heuristike; metaheuristike; evolucijski algoritmi; selekcija
• Keywords (english): scheduling problem; school timetable; dislocation; optimization; heuristics; metaheuristics; evolution algorithms; selection
• Language: croatian
• URN:NBN: urn:nbn:hr:168:947904
• 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: 2023-01-14 20:41:20