Raspoređivanje nastavnih aktivnosti evolucijskim računanjem

doctoral thesis

• Title (english): Scheduling School Activities Using Evolutionary Computation
• Author: Marko Čupić
• Mentor: Marin Golub (mentor)
• Committee member: Leo Budin (predsjednik povjerenstva)
• Committee member: Vedran Mornar (član povjerenstva)
• Committee member: Nedeljko Štefanić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; (Department of Electronics, Microelectronics, Computer and Intelligent Systems); Zagreb
• Defense date and country: 2011-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Universal decimal classification (UDC): 004 - Computer science and technology. Computing. Data processing

Abstract

Problemi izrade rasporeda nastavnih aktivnosti sveprisutni su i izrazito važni na svim obrazovnim institucijama. Prema računalnoj složenosti ovi problemi uobičajeno pripadaju u razred NP-teških problema. U znanstvenoj literaturi obrađuje se nekoliko pojednostavljenih verzija problema; međutim, u praksi je broj problema koje je potrebno riješiti znatno veći. Stoga je u okviru ovog rada dan pregled većeg skupa problema raspoređivanja nastavnih aktivnosti. Za svaki od problema dan je formalni model te odgovarajući optimizacijski problem. Dodatno su razmotreni različiti zahtjevi koji se još postavljaju na konačna rješenja te način njihove ugradnje u optimizacijski problem. Zbog svoje složenosti, najčešći se problemi raspoređivanja nastavnih aktivnosti ne mogu rješavati iscrpnom pretragom kao niti jednostavnim heuristikama. U okviru ovog rada postavljena je hipoteza da su algoritmi odnosno metaheuristike evolucijskog računanja prikladne za rješavanje svih prethodno formalno definiranih problema raspoređivanja. Hipoteza je provjerena izradom niza metaheurističkih algoritama i provjerom njihove sposobnosti rješavanja stvarnih primjera. Razmotreni su načini paralelizacije ovih algoritama, počev od problemski specifičnih. Ostvaren je i hibridni paralelni algoritam evolucijskog računanja. Definiran je formalni model sustava za potporu procesima raspoređivanja koji omogućava objavu napravljenih rasporeda te provođenje analiza zauzeća korisnika. Temeljem tog modela izgrađen je programski sustav čiji je rad ispitan u praksi.

Abstract (english)

Problems of scheduling of school activities are ubiquitous and extremely important to all educational institutions. According to the computational complexity of these problems they usually belong to the class of NP-hard problems. The scientific literature usually deals with simplified versions of several such problems. However, in practice, a number of problems that needs to be solved is much larger. In this thesis therefore an overview of a larger set of scheduling problems of school activities is given. For each problem a formal model is determined and an associated optimization problem is given. In addition, a various requirements are described that are usually additionally placed on the final schedule as well as the technique for its inclusion in optimization problem. Because of complexity, the most common scheduling problems of school activities can not be solved by means of exhaustive search nor simple heuristics. In this thesis, we hypothesize that the evolutionary computation algorithms / metaheuristics are suitable for solving all previously formally defined scheduling problems. Hypothesis was verified by creating a series metaheuristics algorithms and checking their ability to solve real-world problem instances. In this thesis the parallelization of these algorithms is also researched, starting from problem-specific paralelization techniques. Also, the parallel hybrid evolutionary computation algorithm is described. Finally, a formal model of the system is described which offers the support for publishing results of scheduling and which allows conducting the analysis of users business. Based on this model, a software system was built and tested in practice.

• Keywords: raspoređivanje nastavnih obaveza; algoritmi evolucijskog računanja; paralelizacija algoritama; hibridni algoritam evolucijskog računanja
• Keywords (english): scheduling of school activities; evolutionary computation algorithms; parallelization of algorithms; hybrid evolutionary computation algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:626133
• Project: Number: 036-0361994-1995; Title: Univerzalna posrednička platforma za sustave e-učenja; Leader: Vlado Glavinić; Jurisdiction: Croatia; Funder: MZOS; Funding stream: ZP
• Study programme: Title: Computer Science; Study programme type: university; Study level: postgraduate; Academic / professional title: Doktor znanosti (Doktor znanosti)
• Catalog URL: http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=36754
• Type of resource: Text
• Extent: 285 str ; 30 cm
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-06-28 11:35:07