Genetički algoritmi za probleme satnice

scientific master's theses

• Author: Branimir Sigl
• Mentor: Vedran Mornar (mentor)
• Committee member: Leo Budin (predsjednik povjerenstva)
• Committee member: Vedran Mornar (član povjerenstva)
• Committee member: Luka Neralić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Applied Mathematics); Zagreb
• Defense date and country: 2004-10-22, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

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.

Abstract (english)

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.

• Keywords: Raspored sati; raspoređivanje; genetički algoritam; memetički algoritam; lokalna potraga
• Keywords (english): Timetable; scheduling; genetic algorithm; memetic algorithm; local search
• Language: croatian
• URN:NBN: urn:nbn:hr:168:384518
• 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
• Created on: 2019-06-12 13:07:49