Normal view MARC view ISBD view

Raspoređivanje nastavnih aktivnosti evolucijskim računanjem : doktorski rad / Marko Čupić ; [mentor Marin Golub]

By: Čupić, Marko.
Contributor(s): Golub, Marin [ths].
Material type: TextTextPublisher: Zagreb : M. Čupić ; Fakultet elektrotehnike i računarstva, 2011Description: 285 str. : graf. prikazi ; 30 cm +CD.Summary: 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. Ključne riječi: raspoređivanje nastavnih obaveza, algoritmi evolucijskog računanja, paralelizacija algoritama, hibridni algoritam evolucijskog računanja.Summary: ------------------------------------------------ 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: scheduling of school activities, evolutionary computation algorithms, parallelization of algorithms, hybrid evolutionary computation algorithm.
Tags from this library: No tags from this library for this title. Log in to add tags.
Item type Current location Call number Copy number Status Date due Barcode Item holds
Doktorska disertacija Doktorska disertacija Središnja knjižnica
KF
KF-4459 28944 Available 0000000837910
Doktorska disertacija Doktorska disertacija Središnja knjižnica
KF-4459 28945 1 0000000837927
Doktorska disertacija Doktorska disertacija Središnja knjižnica
KF-4459 28945/cd 1 0000000837934
Total holds: 0

Doktorski rad je izrađen na Sveučilištu u Zagrebu,
Fakultetu elektrotehnike i računarstva,
Zavodu za elektroniku, mikroelektroniku, računalne i inteligentne sustave

Bibliografija: str. 269-282. Sažetak na eng. i hrv.

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. Ključne riječi: raspoređivanje nastavnih obaveza, algoritmi evolucijskog računanja, paralelizacija algoritama, hibridni algoritam evolucijskog računanja.

------------------------------------------------ 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: scheduling of school activities, evolutionary computation algorithms, parallelization of algorithms, hybrid evolutionary computation algorithm.

There are no comments for this item.

Log in to your account to post a comment.

Središnja knjižnica Fakulteta elektrotehnike i računarstva, Unska 3, 10000 Zagreb
tel +385 1 6129 886 | fax +385 1 6129 888 | ferlib@fer.hr