Toky v sítích v úlohách rozvrhování
| Thesis title in Czech: | Toky v sítích v úlohách rozvrhování |
|---|---|
| Thesis title in English: | Network flows in scheduling problems |
| Academic year of topic announcement: | 2017/2018 |
| Thesis type: | Bachelor's 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: | 30.09.2017 |
| Date of assignment: | 08.10.2017 |
| Confirmed by Study dept. on: | 15.12.2017 |
| Date and time of defence: | 12.09.2018 08:00 |
| Date of electronic submission: | 18.07.2018 |
| Date of submission of printed version: | 20.07.2018 |
| Date of proceeded defence: | 12.09.2018 |
| Opponents: | doc. RNDr. Petr Lachout, CSc. |
| Guidelines |
| Úlohy rozvrhování se zabývají přiřazením prací na stroje podle stanovených kritérií. Obvykle se tedy jedná o zobecnění přiřazovacího problému vedoucí na celočíselné optimalizační úlohy, kde plánování přiřazení práce ke stroji probíhá pomocí binárních proměnných. Pro větší rozsahy rozvrhovacích úloh je poté nutné nalézt efektivní výpočetní postupy. Jako nejefektivnější se ukazují reformulace pomocí úloh toků v sítích.
Řešitel(-ka) pojedná o různých rozvrhovacích problémech, které je možné řešit jako toky v sítích. Pojedná o struktuře těchto sítí a demonstruje jejich efektivitu v numerické studii na simulovaných, případně reálných zadáních. |
| References |
| E. M. Arkin, E. B. Silverberg: Scheduling jobs with fixed start and end times, Discrete Applied Mathematics 18 (1987) 1-8.
K. I. Bouzina, H. Emmons, Interval scheduling on identical machines, Journal of Global Optimization 9 (1996) 379-393. M. Branda: A stochastic-integer programming approach to tactical fixed interval scheduling problems. Proceeding of Mathematical Methods in Economics (2017). V. Mkinen, V. Staneva, A. I. Tomescu, D. Valenzuela, S.Wilzbach: Interval scheduling maximizing minimum coverage, Discrete Applied Mathematics 225 (2017) 130-135. L. A. Wolsey: Integer programming, Wiley-Interscience series in discrete mathematics and optimization, J. Wiley & Sons, New York, 1998. |