izpis_h1_title_alt

Paralelizacija evolucijskega algoritma za razporejanje opravil s kompleksnimi omejitvami
Stanovnik, Sašo (Author), Lotrič, Uroš (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (750,03 KB)

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:Slovenian
Keywords:evolucijski algoritem, paralelizacija, MPI, urnik
Work type:Bachelor thesis/paper (mb11)
Organization:FRI - Faculty of computer and information science
Year:2015
Views:994
Downloads:266
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share: Bookmark and Share

Secondary language

Language:English
Title:Parallelization of an evolutionary algorithm for scheduling with complex constraints
Abstract:
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.

Keywords:evolutionary algorithm, parallelization, MPI, timetable

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back