Original title: Kombinace evolučních algoritmů a programování s omezujícími podmínkami pro rozvrhování
Translated title: Combination of Evolutionary Algorithms and Constraint Programming for Scheduling
Authors: Štola, Miroslav ; Pilát, Martin (advisor) ; Klíma, Martin (referee)
Document type: Master’s theses
Year: 2016
Language: eng
Abstract: [eng] [cze]
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 Je známé, že rozvrhovací problémy a problémy splňování podmínek jsou velice těžké. Tato práce nabízí nový přístup, jak pomocí evolučních algoritmů řešit rozvrhování s omezujícími podmínkami. Evoluce probíhá na pořadí proměnných, které solver postupně ohodnocuje. Tento přístup umožňuje jedince zakódovat jako permutace, a tedy je použitelný na širší škálu problémů s omezujícími podmínkami. Na základě analýzy grafu závislostí byly navrženy metody pro inicializaci počáteční populace jedinců. Rovněž byly vymyšleny a úspěšně použity nové genetické operátory. Naše metoda nalezla mnoho rozličných rozvrhů s optimální délkou. Dále byla úspěšně vy- zkoušena vícekriteriální optimalizace za pomoci algoritmu NSGA-II. 1
Keywords: CSP; evolutionary algorithm; scheduling; variable ordering; CSP; evoluční algoritmus; pořadí proměnných; rozvrhování

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/77240

Permalink: http://www.nusl.cz/ntk/nusl-346749


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses