Název: Minimax v úlohách rozvrhování za nejistoty
Překlad názvu: Minimax in scheduling problems under uncertainty
Autoři: Jeliga, Jan ; Branda, Martin (vedoucí práce) ; Lachout, Petr (oponent)
Typ dokumentu: Diplomové práce
Rok: 2019
Jazyk: cze
Abstrakt: [cze] [eng]
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 In this work, we deal with fixed interval scheduling problems with the possibility of random delay of the end of the tasks (FIS). First, we pre- sent the basic deterministic FIS problems and ways to solve them. Next, we introduce the concept of minimax and present two well-known and one new FIS problem under uncertainty, when random task delays are conside- red to belong to a certain uncertainty set. Next, we deal with the solution of previously presented FIS problems for five chosen uncertainty sets. We present both previously achieved and original results. The work concludes with a summary of a numerical study of two problems. First, we explore the possibility of Lagrange relaxation application to the first presented problem. Next we explore the quality of approximation allowing to solve the later of problems as LP. 1
Klíčová slova: minimax; optimalizace; robustifikace; rozvrhovací úlohy; fixed interval scheduling; minimax; optimisation; robustification

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/109272

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-404131


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce