Algoritmy barvení grafů v úlohách rozvrhování za náhody
| Thesis title in Czech: | Algoritmy barvení grafů v úlohách rozvrhování za náhody |
|---|---|
| Thesis title in English: | Vertex coloring algorithms in scheduling problems under uncertainty |
| Key words: | rozvrhování za náhody, práce s pevnými intervaly výkonu, úloha barvení grafu, celočíselné programování, stochastické programování |
| English key words: | scheduling under uncertainty, fixed interval scheduling, vertex colo- ring, integer programming, stochastic programming |
| Academic year of topic announcement: | 2014/2015 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Probability and Mathematical Statistics (32-KPMS) |
| Supervisor: | doc. RNDr. Martin Branda, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 15.10.2014 |
| Date of assignment: | 15.10.2014 |
| Confirmed by Study dept. on: | 19.02.2015 |
| Date and time of defence: | 16.09.2015 00:00 |
| Date of electronic submission: | 29.07.2015 |
| Date of submission of printed version: | 31.07.2015 |
| Date of proceeded defence: | 16.09.2015 |
| Opponents: | RNDr. Karel Lavička |
| Guidelines |
| Úloha barvení vrcholů grafu neslouží pouze k barvení map, avšak nachází své aplikace například v úlohách rozvrhování v letectví, zdravotnictví nebo telekomunikacích. V příslušném grafu představují vrcholy jednotlivé úlohy (joby) a hrany spojují vrcholy, které nemohou být zařazeny na stejný stroj například kvůli časovým požadavkům. Barvy poté reprezentují jednotlivé stroje a obarvení grafu přiřazení úloh ke strojům.
Řešitel(-ka) uvede různé formulace výše uvedeného problému ve tvaru optimalizačních úloh, například celočíselné lineární nebo kvadratické. Zaměří se především na varianty s náhodnými částmi (hranami i vrcholy), které mohou lépe reprezentovat reálné situace. Řešitel(-ka) též popíše základní algoritmy pro řešení těchto úloh a stručně popíše jejich výpočetní náročnost. Součástí práce bude numerická studie. |
| References |
| M.Y. Kovalyov, C.T. Ng, T.C.E. Cheng: Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research 178 (2007) 331--342.
L.G. Kroon, M. Salomon, L.N. Van Wassenhove: Exact and approximation algorithms for the operational fixed interval scheduling problem. European Journal of Operational Research 82 (1995) 190--205. L.G. Kroon, M. Salomon, L.N. Van Wassenhove: Exact and approximation algorithms for the tactical fixed interval scheduling problem. Operations Research 45(4) (1997) 624--638. I. Méndez-Díaz, P. Zabala: A cutting plane algorithm for graph coloring�. Discrete Applied Mathematics 156 (2008) 159--179. C. Murat, V.Th. Paschos: On the probabilistic minimum coloring and minimum k-coloring. Discrete Applied Mathematics 154 (2006) 564--586. A. Schrijver: Theory of linear and integer programming. Wiley, New York, 1999. J. Yanez, J. Ramirez: The robust coloring problem. European Journal of Operational Research 148 (2003) 546--558. F. Wang, Z. Xu: Metaheuristics for robust graph coloring. Journal of Heuristics 19 (2013) 529--548. L.A. Wolsey, G.L. Nemhauser: Integer and Combinatorial Optimization. Wiley, New York, 1999. |