Return to search

Kombinace evolučních algoritmů a programování s omezujícími podmínkami pro rozvrhování / Combination of Evolutionary Algorithms and Constraint Programming for Scheduling

Scheduling problems and constraint satisfaction problems are generally known to be extremely hard. This thesis proposes a new evolutionary al- gorithm approach to solve a constrained-based scheduling problem. In this approach, variable orderings are evolved. The variable ordering serves as a parameter for the constraint solver. Its purpose is to determine the order in which variables are labelled by the solver. Hence the evolving individuals may be encoded as permutations. Therefore, our approach can be applied to a wider range of constraint satisfaction problems. Methods for generating the initial population of individuals based on the analysis of the precedence constraints graph are proposed. New genetic operators are presented and successfully applied. Our approach succeeded in finding a range of diverse schedules with the optimal makespan. Furthermore, multi-objective opti- mization was successfully attempted with the NSGA-II. 1

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:346749
Date January 2016
CreatorsŠtola, Miroslav
ContributorsPilát, Martin, Klíma, Martin
Source SetsCzech ETDs
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0017 seconds