Original title: Algoritmy barvení grafů v úlohách rozvrhování za náhody
Translated title: Vertex coloring algorithms in scheduling problems under uncertainty
Authors: Hájek, Štěpán ; Branda, Martin (advisor) ; Lavička, Karel (referee)
Document type: Master’s theses
Year: 2015
Language: cze
Abstract: [cze] [eng]
Diplomová práce se věnuje optimalizačním problémům, které vznikají při rozvrhování prací s pevnými intervaly výkonu za náhody, které jsou repre- zentovány náhodným zpožděním prací. Tyto problémy je možné řešit po- mocí úlohy barvení grafu s náhodnými hranami a lze je zformulovat pomocí celočíselného lineárního, kvadratického nebo stochastického programování. V diplomové práci je navržena nová celočíselná lineární formulace a za určitých předpokladů je dokázána její ekvivalence se stochastickou formulací, ve které se hledá rozvržení maximalizující pravděpodobnost přípustnosti. Navrhovaná formulace je dále v práci modifikována tak, aby lépe odpovídala reálným situacím. Součástí diplomové práce je numerická studie, ve které jsou po- rovnány popsané formulace z hlediska výpočetního času při řešení rozvrho- vací úlohy. Ukazuje se, že s pomocí navrhované formulace jsme schopni vyřešit úlohy podstatně rychleji než s využitím ostatních formulací. 1 This thesis concerns solutions to problems that arise in optimizing fixed interval scheduling under situations of uncertainty such as when there are random delays in job process times. These problems can be solved by using a vertex coloring with random edges and problems can be formulated using integer linear, quadratic and stochastic programming. In this thesis is propo- sed a new integer linear formulation. Under certain conditions there is proved its equivalence with stochastic formulation, where is maximized the schedule reliability. Moreover, we modified the proposed formulation to obtain bet- ter corresponding to real life situations. In a numerical study we compared computational time of individual formulations. It turns out that the propo- sed formulation is able to solve scheduling problems considerably faster than other formulations. 1
Keywords: fixed interval scheduling; integer programming; scheduling under uncertainty; stochastic programming; vertex colo- ring; celočíselné programování; práce s pevnými intervaly výkonu; rozvrhování za náhody; stochastické programování; úloha barvení grafu

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/81170

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


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