Paralelizacija evolucijskega algoritma za razporejanje opravil s kompleksnimi omejitvami

 URL - Presentation file, Visit http://eprints.fri.uni-lj.si/3097/

Abstract
V delu se osredotočimo na problem generiranja urnikov s paraleliziranim evolucijskim algoritmom. Raziščemo pogosto uporabljene metode razporejanja opravil ter ugotovimo, katere so primerne za primere s kompleksnimi omejitvami in izberemo paralelizacijsko shemo, ki je najbolj ustrezna za učinkovit izračun. Prav tako izberemo primerno predstavitev podatkov, ki se sklada z genetskimi operatorji in kriterijsko funkcijo, ki lahko enostavno pokrije velik nabor kompleksnih omejitev. Implementiramo in paraleliziramo razširljiv algoritem za izračun rešitev ter raziščemo uspešnost generiranja. Predstavimo način minimizacije prostorske kompleksnosti problema s pametnim deljenjem dela med procesi. Lastnosti paralelnega programa analiziramo skozi podrobno analizo časov izvajanja in teoretično analizo paralelizacije.

Language: Unknown evolucijski algoritem, paralelizacija, MPI, urnik Not categorized (r6) FRI - Faculty of computer and information science 2015 1536530883 429 96 (0 votes) Voting is allowed only to logged in users.

## Secondary language

Language: Unknown Parallelization of an evolutionary algorithm for scheduling with complex constraints The focus of our work is on the problem of generating a timetable using a parallel evolutionary algorithm. We explore commonly used scheduling methods and determine their suitability for cases with complex constraints, then select a parallelization scheme most suitable for efficient computation. Furthermore, we choose a data representation that best complements genetic operators and the fitness function, which covers a wide range of complex constraints. We implement and parallelize an extensible algorithm for computing solutions to our problem. A method of minimizing the space complexity of the problem by efficiently dividing data between processes is also described. We analyse the properties of our solution through a thorough analysis of run times and memory consumptions coupled with a theoretical analysis of the results. evolutionary algorithm, parallelization, MPI, timetable