Original title: Úlohy rozvrhování s pevnými časy prací - stochastická rozšíření, formulace a algoritmy
Translated title: Fixed interval scheduling problems - stochastic extensions, formulations and algortihms
Authors: Leder, Ondřej ; Branda, Martin (advisor) ; Kopa, Miloš (referee)
Document type: Master’s theses
Year: 2017
Language: cze
Abstract: [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.
Keywords: Gâteaux derivative; scheduling; stability; stochastic integer optimisation; Gâteauxova derivace; rozvrhování; stabilita; stochastická celočíselná optimalizace

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/91135

Permalink: http://www.nusl.cz/ntk/nusl-367661


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses