Combination of Evolutionary Algorithms and Constraint Programming for Scheduling
| Thesis title in Czech: | Kombinace evolučních algoritmů a programování s omezujícími podmínkami pro rozvrhování |
|---|---|
| Thesis title in English: | Combination of Evolutionary Algorithms and Constraint Programming for Scheduling |
| Key words: | evoluční algoritmus, rozvrhování, CSP, pořadí proměnných |
| English key words: | evolutionary algorithm, scheduling, CSP, variable ordering |
| Academic year of topic announcement: | 2014/2015 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | Mgr. Martin Pilát, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 15.09.2015 |
| Date of assignment: | 15.09.2015 |
| Confirmed by Study dept. on: | 05.10.2015 |
| Date and time of defence: | 09.02.2016 09:30 |
| Date of electronic submission: | 03.12.2015 |
| Date of submission of printed version: | 04.12.2015 |
| Date of proceeded defence: | 09.02.2016 |
| Opponents: | Ing. Martin Klíma, Ph.D. |
| Guidelines |
| 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ů. |
| References |
| [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. |