Genetički algoritmi za probleme satnice

magistarski rad

• Autor: Branimir Sigl
• Mentor: Vedran Mornar (mentor)
• Član povjerenstva: Leo Budin (predsjednik povjerenstva)
• Član povjerenstva: Vedran Mornar (član povjerenstva)
• Član povjerenstva: Luka Neralić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; (Zavod za primijenjenu matematiku); Zagreb
• Datum i država obrane: 2004-10-22, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Univerzalna decimalna klasifikacija (UDC): 004 - Računalna znanost i tehnologija. Računalstvo. Obrada podataka

Sažetak

Usprkos raširenosti problema rasporeda sati, ne postoji jedinstveno programsko rješenje prilagođeno svim institucijama. Programsko rješenje i genetički algoritam predstavljeni u ovom radu koriste se za izradu rasporeda sati fakulteta i srednjih škola. Predloženi genetički algoritam provjeren je na više podskupova podataka Fakulteta elektrotehnike i računarstva u Zagrebu, te skupu problema Ekonomske i birotehničke škole u Bjelovaru. Osnovni genetički algoritam je zbog brže konvergencije prema rješenju u ovom radu proširen metodama lokalnog pretraživanja i rekurzivnim algoritmom usmjerenog pretraživanja. Rekurzivni algoritam posebno je prilagođen radu sa strukturama genetičkog algoritma. Dobiveno rješenje poboljšano je posebnim metodama optimizacije nad glomaznim strukturama genetičkog algoritma. Programsko rješenje implementirano je u paketu Microsoft Visual Studio.NET - programski jezik C#. Genetički algoritam je zbog brzine rada izveden u programskom jeziku C++. Kao relacijska baza podataka korišten je Microsoft Office Access. U prvih nekoliko poglavlja govori se o općem problemu raspoređivanja u sklopu kojeg je dan pregled tehnika rješavanja problema raspoređivanja. Opći dio govori i o formulacijama problema rasporeda sati, te općenito o genetičkim algoritmima. U središnjem dijelu rada govori se o načinu rješavanja problema rasporeda sati pomoću genetičkog algoritma, te o problemima sa kojima se susretalo u izradi ovog rada. Detaljno su opisane cjeline koje su pomogle efikasnom rješavanju postavljenog problema. Posljednja poglavlja predstavljaju dobivene rezultate i analizu rješenja potkrijepljenu grafovima.

Sažetak (engleski)

Despite of popularity of timetable scheduling problems, there is no common program solution suitable for all institutions. Program solution and genetic algorithm presented in this thesis are used to produce university and high school timetables. Presented genetic algorithm is tested on multiple data sets of Faculty of Engineering and Computing in Zagreb and School of Economics in Bjelovar. In this thesis the common genetic algorithm is broadened by local search methods to establish faster solution convergence. A recursive directed search algorithm is specially adopted for work with genetic algorithms structures. The solution is improved with special optimization techniques presented on the huge genetic algorithm structures. The program solution is developed in Microsoft Visual Studio.NET IDE - program language C#. The genetic algorithm is developed in C++ due to algorithm speed issues. Microsoft Office Access is used as relational database. In the first few chapters general scheduling problems are described. The survey of timetable scheduling techniques is also given. This part also presents some known formulations of timetable scheduling problem. In the central part of the thesis ways of solving of timetable scheduling problem using genetic algorithms are described and problems which came across. Last few chapters present obtained results and solution analysis fortified with graphs.

• Ključne riječi: Raspored sati; raspoređivanje; genetički algoritam; memetički algoritam; lokalna potraga
• Ključne riječi (engleski): Timetable; scheduling; genetic algorithm; memetic algorithm; local search
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:384518
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: poslijediplomski znanstveni (magistarski); Akademski / stručni naziv: magistar inženjer računarstva (mag. ing. comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-06-12 13:07:49