Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom

Glavač, Vjekoslav

No public access

scientific master's theses

8 0

Object Oriented Approach to Timetable Problem Solving Using a Genetic Algorithm

Vjekoslav Glavač (2001)

University of Zagreb
Faculty of Electrical Engineering and Computing
Department of Applied Mathematics

Cite this document

APA 6th Edition

Glavač, V. (2001). Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom (Scientific master's theses). Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:791213

MLA 8th Edition

Glavač, Vjekoslav. "Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom." Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, 2001. https://urn.nsk.hr/urn:nbn:hr:168:791213

Chicago 17th Edition

Harvard

Glavač, V. (2001). 'Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom', Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 23 October 2019, https://urn.nsk.hr/urn:nbn:hr:168:791213

Vancouver

Glavač V. Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom [Scientific master's theses]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2001 [cited 2019 October 23] Available at: https://urn.nsk.hr/urn:nbn:hr:168:791213

IEEE

V. Glavač, "Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom", Scientific master's theses, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2001. Available at: https://urn.nsk.hr/urn:nbn:hr:168:791213

Cite this item: https://urn.nsk.hr/urn:nbn:hr:168:791213

Metadata

Title	Objektni pristup rješavanju problema rasporeda sati genetičkim algoritmom
Title (english)	Object Oriented Approach to Timetable Problem Solving Using a Genetic Algorithm
Author	Vjekoslav Glavač
Mentor	Vedran Mornar (mentor)
Committee member	Leo Budin (predsjednik povjerenstva)
Committee member	Vedran Mornar (član povjerenstva)
Committee member	Robert Manger (član povjerenstva)
Granter	University of Zagreb Faculty of Electrical Engineering and Computing (Department of Applied Mathematics) Zagreb
Defense date and country	2001-06-04, Croatia
Scientific / art field, discipline and subdiscipline	TECHNICAL SCIENCES Computing
Universal decimal classification (UDC)	004 GENERALLY Computer science and technology. Computing. Data processing
Abstract	Genetički algoritmi danas predstavljaju moćnu adaptivnu metodu rješavanja mnogih kombinatornih problema i problema optimizacije. Od posebnog je interesa rješavanje složenih, NP teških kombinatornih problema, a jedan od takvih problema je i izrada školskog rasporeda sati. Problem se u osnovi sastoji od smještanja svih (nastavnim planom određenih) predavanja u unaprijed definirani skup vremenskih termina (sati) uz poštivanje određenih ograničenja. U ovom radu načinjen je genetički algoritam i računalni program za izradu školskog rasporeda sati koji uzima u obzir sve specifičnosti hrvatskog školstva. Algoritam je verificiran na realnom slučaju. Za probne podatke uzeta je gimnazija u Bjelovaru s nastavnim programom za 1999/2000. školsku godinu. Cilj je bio pronaći alternativu napornoj ručnoj izradi rasporeda i ocijeniti primjenjivost, učinkovitost i ograničenja genetičkog algoritma na ovoj problematici u realnim uvjetima. Provedeni su pokusi s različitim varijantama genetičke jezgre algoritma, a isprobana je i hibridizacija s nekoliko tehnika lokalne potrage i simulacijom klasičnih metoda. Algoritam je implementiran u objektnom programskom jeziku Smalltalk u kombinaciji s DB2 bazom podataka u okviru razvojnog alata IBM VisualAge for Smalltalk. Rad je podijeljen u nekoliko cjelina. Na početku je ukratko predstavljena povijest genetičkih algoritama, osnovni pojmovi, operatori, teoretska podloga i usporedba s ostalim tehnikama optimizacije. Sljedeće poglavlje općenito opisuje problematiku rasporeda sati uz matematički model i iznosi dosadašnje rezultate u primjeni genetičkih algoritama u rješavanju problematike. Četvrto poglavlje detaljno opisuje problem školskog rasporeda u Hrvatskoj sa svim specifičnostima, oslanjajući se na primjer bjelovarske gimnazije. U petom poglavlju opisan je korišteni algoritam, njegov dizajn i implementacija na računalu. U sljedećem poglavlju prikazani su dobiveni rezultati i performanse algoritma. Sedmo poglavlje donosi ocjenu rezultata i zaključke.
Abstract (english)	Today, genetic algorithms represent a powerful adaptive method in solving many optimization and combinatorial problems. Solving complex, NP hard combinatorial and optimization problems is of particular interest and school timetable problem is one of that kind. The essence of the problem is placing all the lectures (determined by a curriculum) in a set of predefined timeslots without breaking certain constraints at the same time. A genetic algorithm and a computer program for creating a school timetable were developed in this thesis. All specific details of Croatian school system were taken into account and the solution was tested on a real world problem. The curriculum for school year 1999/2000 of Bjelovar grammar school was taken as a test set of data. The goal was to find an alternative solution to hard manual process of creating a school timetable and to estimate usefulness, performance and limitations of genetic algorithms when applied to real timetable problems. Different variations of genetic kernel of algorithm were tested. Hybridization with a few local search techniques and simulated manual methods were also tried. Algorithm was implemented with object oriented programming language Smalltalk and DB2 database within IBM VisualAge for Smalltalk developing environment. The thesis is organized as follows. First of all, a short history of genetic algorithms, basic terms, operators, theoretical background and comparison with other optimization techniques are presented. The next chapter describes the timetable problem in general using a mathematical model. It outlines current achievements in applying genetic algorithms in solving timetable problems. The fourth chapter brings detailed description of the school timetable problem in Croatia with reference to Bjelovar grammar school example. Design and computer implementation of the algorithm are described in the fifth chapter. Obtained results and algorithm performance are presented in the next chapter. The seventh chapter brings the evaluation of obtained results and conclusions.
Keywords
Keywords (english)
Language	croatian
URN:NBN	urn:nbn:hr:168:791213
Study programme	Title: Postgraduate master programe in computing Study programme type: university Study level: postgraduate Academic / professional title: magistar inženjer računarstva (magistar inženjer računarstva)
Type of resource	Text
File origin	Born digital
Access conditions	Closed access
Terms of use
Repository	FER Repository
Created on	2019-04-16 13:43:21