Scheduling School Activities Using Evolutionary Computation

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.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