Název:
Úlohy rozvrhování s pevnými časy prací - stochastická rozšíření, formulace a algoritmy
Překlad názvu:
Fixed interval scheduling problems - stochastic extensions, formulations and algortihms
Autoři:
Leder, Ondřej ; Branda, Martin (vedoucí práce) ; Kopa, Miloš (oponent) Typ dokumentu: Diplomové práce
Rok:
2018
Jazyk:
cze
Abstrakt: [cze][eng] Úlohy rozvrhování s pevnými intervaly prací mají široké praktické uplatnění v plánování výroby, dopravě, při plánováni operací v nemocnicích, nebo ve školách při rozvrhování výuky. Bohužel je jejich častou součásti požadavek celočíselnosti proměnných a porušení této celočíselnosti není zanedbatelné jako v~některých případech ze světa financí. Předložíme proto několik možných formulací rozvrhovacích problému a jejich stochastická rozšíření. Navrhneme novou formulaci stochastického rozšíření rozvrhovací úlohy s pevnými intervaly prací založenou na teorii proudění v sítích a ukážeme, že celočíselné řešení je důsledkem jejího tvaru. Srovnáme ji s jinou ekvivalentní formulací. Pojednáme o Gâteauxově derivaci a jejím užití při zkoumání stability řešení stochastické optimalizační úlohy pod vlivem kontaminace. Zformulujeme větu o stabilitě řešení stochastických rozvrhovacích úloh s pevnými konci prací a uplatníme ji na příkladu.Fixed interval scheduling problems have wide range of practical use in production planning, transportation, in hospitals or in schools when planning timetables. When solving these problems we often encounter requirement of integrality of solutions. Ignoring this condition is often not possible. In this thesis we propose some formulations of scheduling problems and their stochastic extensions. We also propone a new formulation of stochastic FIS problem, for which integrality of solution is byproduct of its definition. We present Gâteaux derivative and its relationship to stability of optimal value function of stochastic optimization problems under the influence of contamination. We propose a new theorem on the stability of such functions for fixed interval scheduling problems.
Klíčová slova:
Gâteauxova derivace; rozvrhování; stabilita; stochastická celočíselná optimalizace; Gâteaux derivative; scheduling; stability; stochastic integer optimisation