|
|
Two-phase scheduling with unknown speeds
Minařík, Josef ; Sgall, Jiří (vedoucí práce) ; Eberle, Franziska (oponent)
Rychlostně robustní rozvrhování je dvoufázový rozvrhovací problém. Na vstupu je dána doba běhu pro každý z n úkolů, počet strojů m a počet balíčků b. Naším úkolem je rozdělit úkoly do balíčků, které budou následně zpracovány na strojích, které mají v tomto okamžiku neznámé rychlosti. Naším cílem je minimalizovat poměr délky našeho rozvrhu a délky optimáního rozvrhu, který by vznil umisťováním úkolů rovnou na stroje. Nejpodrobněji studovaný případ doposud byl b = m. V této práci zobecňujeme známé výsledky pro infinitizemálně malé úkoly (tento případ se nazývá písek) a dokážeme, že nejlepší kompetitivní poměr, kterého je možné dosáhnout, je mb mb−(m−1)b . Dále formulujeme algoritmus řešící případ s identickými úkoly (nazývaný cihly) za podmínky b = m s kompetitivním poměrem 1.6, což zlepšuje nejlepší doposud známou hodnotu 1.8. Zavedeme nový speciální případ, který budeme nazývat p-oblázky. V tomto případě jsou doby běhu jednotlivých úkolů nejvýše p-násobky průměrné zátěže stroje. Oblázky jsou vlastnostmi i obtížností na půl cesty mezi pískem a obecným případem (nazývaným kameny). Popíšeme algoritmus pro oblázky, který je pro malé hodnoty p lepší než nejlepší známý algoritmus pro kameny (pro p menší než 2 − e e−1 v případě b = m). 1
|
|
|
Rozkládání některých tříd kostičkových mnohostěnů
Minařík, Josef ; Kynčl, Jan (vedoucí práce) ; Tiwary, Hans Raj (oponent)
Rozklad mnohostěnu je tvořen řezy jeho povrchu takovými, že rozřezaný povrch je možné rozložit do roviny, aniž by vznikl překryv. Hranový rozklad je omezený typ roz- kladu, ve kterém je povolené řezy vést jen po hranách mnohostěnu. Kostičkový mno- hostěn je speciální druh mnohostěnu, který je tvořen jednotkovými krychlemi slepenými k sobě celými stěnami. V případě kostičkových mnohostěnů můžeme v hranovém roz- kladu řezat po hranách všech jednotkových krychlí. V této práci se zabýváme zejména jednovrstvými kostičkovými mnohostěny a popíšeme několik algoritmů pro rozklad růz- ných speciálních tříd. Ukážeme, že je možné hranově rozložit jednovrstvé krychličkové mnohostěny s krychlovými dírami, tenkými horizontálními dírami a oddělitelnými ob- délníkovými dírami. Otázka hranového rozkladu obecných jednovrstvých krychličkových zůstává otevřena. Také se krátce zabýváme rozklady některých tříd vícevrstvých krych- ličkových mnohostěnů. 1
|
host ::
RSS.