pravidlené semináře

Uvažujeme variantu jednoduchého problému vyvažování montážní linky, ve které jsou počet pracovních míst a doba cyklu pevně stanoveny, ale některé úlohy podléhají nejistotě (doba zpracování se může prodloužit). Cílem je zachovat proveditelnost rozvrhu, když se doba trvání úloh zvyšuje. Abychom toho dosáhli, uvažujeme dvě míry stability (které je třeba maximalizovat): poloměr stability a faktor stability, které odpovídají různým typům nárůstu trvání úloh. Problém rozvrhování je formulován jako smíšený celočíselný lineární program a tato formulace je posílena horní hranicí a heuristikou. Přesněji řečeno, zužují se intervaly přidělování úloh, které vycházejí z precedenčních omezení, jež se zase používají ke zlepšení výsledků heuristiky a formulace smíšeného celočíselného lineárního programování.

V této přednášce se zabýváme problémem generování personálních seznamů, které jsou odolné vůči poruchám způsobeným absencí zaměstnanců. Pokud se zaměstnanec stane neočekávaně nepřítomným, musí být nahrazen jiným zaměstnancem. To následně může ovlivnit pracovní dobu dalších zaměstnanců, čímž vzniká nežádoucí vlnový efekt, který mění velkou část soupisu. Zkoumáme, jak může využití pracovní pohotovosti zabránit takovým velkým poruchám. Začneme tím, že nejprve zavedeme metriku pro kvantifikaci robustnosti rozpisu, kterou pak použijeme pro generování dostatečně robustních rozpisů. Ve druhé části přednášky se zabýváme podmínkami, za kterých může strojové učení vést k lepším řešením. Je představena nová metodika pro určení minimálního výkonu předpovědi, který je nutný k překonání přístupu k sestavování soupisek bez dat.

Řešitel CP-SAT je vyvinut týmem Operations Research ve společnosti Google a je součástí optimalizační sady OR-Tools s otevřeným zdrojovým kódem. Jedná se o implementaci čistě integrálního řešitele programování s omezeními nad řešitelem SAT využívajícím Lazy Clause Generation. Inspiraci čerpá z chuffed solveru a z plenárního zasedání CP 2013 Petera Stuckeyho o Lazy Clause Generation. Řešitel CP-SAT vylepšuje chuffed solver ve dvou hlavních směrech. Zaprvé používá vedle motoru SAT také simplex. Za druhé implementuje a spoléhá se na portfolio různých pracovníků pro svou vyhledávací část. Použití simplexu přináší zřejmé výhody lineární relaxace na lineární části úplného modelu. Zahájil také integraci technologie MIP do CP-SAT. Jedná se o obrovské úsilí, protože řešiče MIP jsou vyspělé a složité. Zahrnuje presolve – který byl již součástí CP-SAT -, duální redukce, specifická pravidla větvení, řezy, opravu snížených nákladů a další pokročilé techniky. Umožňuje také úzkou integraci výzkumu z komunity Scheduling on MIP spolu s nejpokročilejšími algoritmy plánování. To umožnilo průlom v řešení a dokazování obtížných instancí rozvrhování problémů Job-Shop a problémů rozvrhování projektů s omezením zdrojů. Použití portfolia různých pracovníků usnadňuje zkoušení nových nápadů a začlenění ortogonálních technik bez větších komplikací, kromě kontroly exploze potenciálních pracovníků. Tyto pracovníky lze rozdělit do několika kategorií podle různých kritérií, jako je hledání primárních řešení – buď pomocí úplných řešičů, lokálního hledání nebo hledání ve velkém okolí -, zlepšování duálních hranic, snaha o redukci problému pomocí spojitého zkoumání. Tato rozmanitost chování zvýšila robustnost řešitele, zatímco průběžné sdílení informací mezi pracovníky přineslo obrovské zrychlení při paralelním běhu více pracovníků. Celkově lze říci, že CP- SAT je špičkový řešitel s nepřekonatelným výkonem v komunitě řešitelů programování s omezeními, průlomovými výsledky na benchmarcích plánování (s uzavřením mnoha otevřených problémů) a konkurenceschopnými výsledky s nejlepšími řešiteli MIP (na čistě integrálních problémech).

Díky úspěchu elektronického obchodování se dnešní sklady mění v plně automatizované továrny na plnění. Mnohé z nich se řídí paradigmatem „parts-to-picker“ a používají mobilní roboty zvedající regály nebo dopravníky, které dodávají skladové jednotky (SKU) stacionárním vychystávačům pracujícím na vychystávacích pracovištích. Cílem této přednášky je strukturovat a přezkoumat skupinu problémů souvisejících s plánováním plnění, které v tomto prostředí vznikají: Na vstupní straně musí být pořadí, v jakém jsou na pracoviště dodávány zásobníky SKU, synchronizováno s objednávkami, které se na něm ve stejnou dobu kompletují na výstupní straně. Tímto způsobem lze dosáhnout efektivnějšího procesu plnění a odlehčit systému zásobování zásobníky. Tato přednáška klasifikuje rodinu mírně odlišných problémů plánování plnění zakázek, které vznikají při různých nastaveních pracovních stanic v alternativních skladech. Toto klasifikační schéma slouží k přehledu stávající literatury, analýze výpočetní složitosti a systematickému vyčíslení přínosů alternativních uspořádání pracovních stanic. Přednáška také upozorňuje na cenné nápady pro budoucí výzkum v této nově vznikající oblasti plánování.

Firmy, které pracují na základě objednávky, nemusí uspokojit celou poptávku z důvodu omezené kapacity a krátkých dodacích lhůt. To vyžaduje výběr pouze části zákaznických objednávek s cílem maximalizovat celkový příjem, což vede k problémům s přijetím a plánováním objednávek (OAS). V této studii zkoumáme zobecněnou verzi problému OAS (GOAS), který vychází z reálného prostředí. Vzhledem k několika složkám problému, jako jsou časy uvolnění, termíny splatnosti, konečné termíny a časy nastavení závislé na posloupnosti, je nalezení přesného řešení problému GOAS, které určuje, které zakázky přijmout a jak je současně naplánovat, aby se maximalizoval příjem, v rozumném čase i v prostředí jednoho stroje obtížné. Proto jsme pro problém GOAS vyvinuli účinnou a efektivní matematiku, která se skládá z modelu smíšeného celočíselného lineárního programování založeného na časových kbelících, algoritmu prohledávání okolí proměnných a algoritmu tabu vyhledávání. Výsledky výpočtů ukazují, že navržená matheuristika překonává nejmodernější algoritmy vyvinuté pro problém GOAS. Hranice optimálně řešené velikosti instance je posunuta dále a téměř optimální řešení jsou získána v rozumném čase pro instance spadající za tuto hranici. Společná práce s İstençem Tarhanem.

Uvažujeme problém 1 || ∑ wj Uj, problém minimalizace váženého počtu zpožděných úloh na jednom stroji. Tento problém je jedním z nejzákladnějších a nejfundamentálnějších problémů v teorii rozvrhování s několika různými aplikacemi v teorii i praxi. Dokážeme, že 1 || ∑ wj Uj je W[1]-těžká vzhledem k počtu různých časů zpracování na vstupu i vzhledem k počtu různých vah na vstupu. To spolu s předchozími pracemi poskytuje úplný obraz pro 1 || ∑ wj Uj z hlediska parametrizované složitosti, jakož i téměř těsné meze složitosti problému podle hypotézy exponenciálního času (ETH). Na základě společné práce s Dannym Hermelinem.