Combination of Evolutionary Algorithms and Constraint Programming for Scheduling
| Název práce v češtině: | Kombinace evolučních algoritmů a programování s omezujícími podmínkami pro rozvrhování |
|---|---|
| Název v anglickém jazyce: | Combination of Evolutionary Algorithms and Constraint Programming for Scheduling |
| Klíčová slova: | evoluční algoritmus, rozvrhování, CSP, pořadí proměnných |
| Klíčová slova anglicky: | evolutionary algorithm, scheduling, CSP, variable ordering |
| Akademický rok vypsání: | 2014/2015 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra teoretické informatiky a matematické logiky (32-KTIML) |
| Vedoucí / školitel: | Mgr. Martin Pilát, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 15.09.2015 |
| Datum zadání: | 15.09.2015 |
| Datum potvrzení stud. oddělením: | 05.10.2015 |
| Datum a čas obhajoby: | 09.02.2016 09:30 |
| Datum odevzdání elektronické podoby: | 03.12.2015 |
| Datum odevzdání tištěné podoby: | 04.12.2015 |
| Datum proběhlé obhajoby: | 09.02.2016 |
| Oponenti: | Ing. Martin Klíma, Ph.D. |
| Zásady pro vypracování |
| Mnoho evolučnich algoritmů řeší rozvrhovací problémy tak, že kódují permutaci akcí, která potom slouží jako vstup pro rozvrhovací heuristiku a určuje, v jakém pořadí bude heuristika akce přidávat do rozvrhu. Hlavní nevýhodou takového přístupu je, že jen složitě škáluje pro rozvrhovací problémy s velkým množstvím akcí. Techniky založené na programování s omezujícími podmínkami naopak umí velké rozvrhovací problémy řešit lépe, ale není úplně jednoduché do nich přidat optimalizaci obecných kritérií. Cílem této práce je odstranít nedostatky obou těchto technik jejich kombinací.
Student se seznámí s programováním s omezujícími podmínkami (constraint programming - CP) a evolučními algoritmy pro rozvrhování. Na základě získaných znalostí se pomocí postupů inpirovaných evolučními algoritmy pokusí optimalizovat rozvrhy získané pomocí CP. Především se bude věnovat možnosti určení pořadí ohodnocování proměnných při řešení problému s omezujícími podmínkami - tzv. branching strategii - pomocí evolučních algoritmů. |
| Seznam odborné literatury |
| [1] Prud’homme, Charles, Jean-Guillaume Fages, and Xavier Lorca. "Choco3 Documentation". TASC, INRIA Rennes, LINA CNRS UMR 6241 (2014).
[2] Michalewicz, Zbigniew, and David B. Fogel. "How to solve it: modern heuristics". Springer Science & Business Media, 2013. [3] Hart, Emma, Peter Ross, and David Corne. "Evolutionary scheduling: A review". Genetic Programming and Evolvable Machines 6.2 (2005): 191-220. |