Název:
Úlohy rozvrhování za náhody při heterogenních strojích
Překlad názvu:
Scheduling problems under uncertainty with nonidentical machines
Autoři:
Matoušková, Monika ; Branda, Martin (vedoucí práce) ; Lachout, Petr (oponent) Typ dokumentu: Diplomové práce
Rok:
2022
Jazyk:
eng
Abstrakt: [eng][cze] This thesis deals with operational fixed interval scheduling problems under uncer- tainty. The topic has been covered for identical machines and the theory is summarized in this thesis. The stochastic programming problem has a deterministic reformulation based on network flow under the assumption that the multivariate distribution of ran- dom delays follows an Archimedean copula. In this thesis, we focus on the problem with heterogeneous machines. When there are more possible types of machines, this problem somewhat complicates. The deterministic problem with no delays and more than one machine type is NP-hard. We generalized the deterministic reformulation of the stochas- tic problem with possible random delays for nonidentical machines. This formulation for more than one machine type loses an important property that holds for identical machines reformulation using network flow. Then an algorithm based on Lagrangean relaxation is proposed, implemented and compared with a solution obtained by MIP solver. 1Tato práce se zabývá úlohami rozvrhování s pevnými časy prací za náhody, kde úkolem je přiřadit zadané práce strojům. Jednotlivé práce mohou nabírat zpoždění. Toto téma již bylo zpracováno pro identické stroje a dostupnou literaturu v práci shrnujeme. Pro tento problém stochastického programování existuje deterministická reformulace, pokud před- pokládáme, že sdružené rozdělení zpoždění prací je dáno Archimedovskou kopulí. V práci se dále zaměřujeme na úlohu s heterogenními stroji. V případě, že máme více než jeden typ strojů, se úloha poněkud zkomplikuje. Deterministický problém, kde neuvažujeme možnost zpoždění prací, je NP-těžký, pokud máme více než jeden typ strojů. Zobecnili jsme deterministickou reformulaci problému stochastického programování s náhodnými zpožděními pro případ s heterogenními stroji. Tato formulace ztrácí v případě s více než jedním typem strojů důležitou vlastnost - totální unimodularitu. Ta v případě formulace pro homogenní stroje, která využívá toky v sítích, platí. Dále jsme navrhli a implemen- tovali algoritmus založený na Lagrangeově relaxaci. Navržený algoritmus jsme porovnali se solverem pro smíšené celočíselné programy na vygenerovaných problémech. 1
Klíčová slova:
rozvrhování prací|stochastické programování|toky v sítích|heterogenní stroje|Lagrangeova relaxace; fixed interval scheduling|stochastic programming|network flow|heterogeneous machines|Lagrangean relaxation