Diz 79 cz
Rozvrhování s neurčitými dobami zpracování popsanými empirickými distribucemi
Autor: Antonín Novák
Doba zpracování úlohy je jedním z nejdůležitějších parametrů rozvrhovacích problémů, ovšem je také jedním z těch, které je velmi obtížné získat - obvykle není znám, je drahý na měření nebo nemá deterministickou povahu. Klasické metody deterministického rozvrhování, které nahrazují chybějící informaci například bodovými odhady, mohou produkovat výsledky které jsou nestabilní a obecně náchylné na nečekané realizace hodnot parametrů. Kvůli tomu je potřeba v prostředí s nepřesnou znalostí parametrů použít optimalizační přístupy, které jsou schopny vypořádat se s neurčitostí parametrů. Důležitá část v návrhu takových algoritmů je volba modelu neurčitosti a přístupu k potlačení jeho důsledků. Je například odhad střední hodnoty a rozptylu dostatečný? Můžeme předpokládat že pouze jistý počet parametrů se při realizaci odkloní od své odhadované hodnoty? Potřebujeme optimalizovat kriteriální funkci zohledňující riziko, a pokud ano, jaká je za to cena? Toto jsou zásadní otázky, protože příliš jednoduché modely vedou ke konzervativním a neefektivním řešením nebo naopak dokonce mohou zcela selhat při ochraně proti neurčitosti. Díky pokrokům technologií, umožňující sběr velikých souborů dat různých aspektů průmyslových procesů, můžeme zmíněné výzvy adresovat daty-řízenými přístupy k rozvrhování za neurčitosti.
V této práci studujeme různé způsoby včlenění distribuční znalosti časů zpracování do rozvrhovacích problémů. Metody navržené v této práci jsou z části inspirovány technikami ze strojového učení, kde známe škálující algoritmy a přičemž také čelíme neurčitosti parametrů. Například jsme použili navzorkovaná data k odhadu parametrů množiny nejednoznačnosti ke konstrukci distribučně-robustního řešení metodami regularizace normami, což přineslo velké urychlení běhů algoritmů. Další cesta ve vylepšování výkonu rozvrhovacích algoritmů se nachází ve vhodné volbě modelu neurčitosti. Zde jsme navrhli metodu jak modelovat úlohy s neurčitou dobou zpracování pomocí abstrakce takzvaných F-tvarých úloh která diskretizuje kumulativní distribuční funkci časů zpracování. Výsledná formulace problému je v podstatě balící problém, který je velmi dobře řešitelný v praxi s výhodou, že pravděpodobností garance výsledných rozvrhů jsou verifikovatelné pomocí Bayesovských sítí. Na závěr studujeme situaci kdy distribuční funkce dob zpracování lze nahradit normálním rozdělením. Úplná znalost distribuční funkce je využita v $\beta$-robustní formulaci kdy se maximalizuje pravděpodobnost, že všechny úlohy jsou dokončeny před společným termínem. Zmíněné problémy jsme charakterizovali z hlediska výpočetní složitosti a navrhli pro ně škálující algoritmy které poskytují vysoce kvalitní řešení pro instance se stovkami úloh.