|
|
Fixed interval scheduling problems with endogenous uncertainty
Hamerníková, Iva ; Branda, Martin (vedoucí práce) ; Lachout, Petr (oponent)
V této práci se zaměřujeme na úlohy s pevnými intervaly prací (dále FIS problémy). V první kapitole zadefinujeme FIS problémy a endogenní a exogenní náhodu, následně v další kapitole shrneme výsledky zabývající se FIS problémy a jejich vztahem k robust- nímu obarvování grafů. Na ty navážeme představením nového modelu FIS s údržbou. Jde o specifický případ problému s náhodou ovlivněnou rozhodnutím. Představíme nový typ práce - údržbu, která nám umožňuje pozitivně ovlivnit pravděpodobnostní rozdělení zpoždění prací. Zadeifnujeme nejprve problém, kdy údržbu lze použít pouze na začátku, poté představíme obecný problém, kdy se údržba může vyskytnout kdykoliv i později rozvrhu prací. Ukážeme, že tento přístup vede na optimální řešení, zároveń přidáme ilustrativní příklad a budeme diskutovat některá možná rozšířemí problému. Na závěr uvedem výsledky numerické studie, kdy řešíme představený FIS problém s údržbou pomocí solveru Cplex. Ukážeme, že údržba se projevuje pouze při určtých nastaveních, jako velký nepoměr mezi cenou outsourcingu a údržby nebo v případě prací s velkou pravděpodobností zpoždění. Bohužel se ukáže, že už pro středně velké rozměry úloh je problém výpočetně příliš náročný. 1
|
|
|
Minimax v úlohách rozvrhování za nejistoty
Jeliga, Jan ; Branda, Martin (vedoucí práce) ; Lachout, Petr (oponent)
V práci se zabýváme rozvrhovací úlohou pro úkoly s daným časem začátku a konce práce (FIS) při možnosti náhodného zpoždění konce práce. Nejprve představujeme základní deterministické úlohy FIS a možnosti jejich řešení. Dále zavádíme koncept minimaxu a představujeme dvě známé a jednu novou úlohu FIS za nejistoty, kdy jsou náhodná zpoždění úkolů uvažována z vybrané množiny rozdělení. Dále se věnujeme řešení dříve představených FIS úloh pro pět konkrétních množin pravděpodobnostních rozdělení. Uvádíme jak dříve dosažené, tak původní výsledky. Práci zakončuje shrnutí numerické studie dvou úloh. Nejprve zkoumáme možnost aplikace Lagrangeovské relaxace na první z uvedených úloh. Dále zkoumáme kvalitu aproximace umožňující ře- šení druhé úlohy jako LP. 1
|
|
|
Algoritmy barvení grafů v úlohách rozvrhování za náhody
Hájek, Štěpán ; Branda, Martin (vedoucí práce) ; Lavička, Karel (oponent)
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
|
host ::
RSS.