pravidlené semináře

Smíšené celočíselné lineární programování (MILP) je klíčovým nástrojem mnoha pokročilých algoritmů pro řešení základních problémů kombinatorické optimalizace. Složitost řešení MILP přímo souvisí s velikostí jeho podpory, což je minimální počet nenulových celočíselných proměnných v optimálním řešení. Významný výsledek Eisenbranda a Shmonina (Oper. Res. Lett., 2006) ukazuje, že každé proveditelné celočíselné lineární programování (ILP) má řešení s velikostí podpory s≤2m⋅log⁡(4mΔ)s \leq 2m \cdot \log(4m\Delta)s≤2m⋅log(4mΔ), kde mmm je počet omezení a Δ\DeltaΔ je největší absolutní hodnota koeficientu v jakémkoli omezení. Hlavní kombinatorický výsledek představujeme vylepšené hranice velikosti podpory pro ILP. Ukazujeme, že každé ILP má řešení s velikostí podpory s≤m⋅(log⁡(3∥A∥1)+log⁡(∥A∥1)),s \leq m \cdot (\log(3\|A\|_1) + \sqrt{\log(\|A\|_1)}),s≤m⋅(log(3∥A∥1​)+log(∥A∥1​)​), kde ∥A∥1\|A\|_1∥A∥1​ označuje 1-normu matice omezení AAA. Naše horní hranice platí také s ∥A∥1\|A\|_1∥A∥1​ nahrazenou hodnotou mΔ\sqrt{m\Delta}mΔ​, což zlepšuje dosud nejlepší známé konstanty v lineární podobě. Hlavní algoritmický výsledek – vyvinuli jsme nejrychlejší známé aproximační schémata (EPTAS) pro základní problémy plánování, která využívají zlepšené hranice podpory. Navrhujeme efektivní aproximační schéma pro minimalizaci makespanu na strojích s různými rychlostmi (Q||Cmax). Naše EPTAS poskytuje (1+ε)(1 + \varepsilon)(1+ε)-aproximaci pro Q||Cmax na NNN úlohách v čase 2O(1/ε⋅log⁡3(1/ε)⋅log⁡(log⁡(1/ε)))+O(N),2^{O(1/\varepsilon \cdot \log^3(1/\varepsilon) \cdot \log(\log(1/\varepsilon)))} + O(N),2O(1/ε⋅log3(1/ε)⋅log(log(1/ε)))+O(N), což exponenciálně zlepšuje dosud nejrychlejší algoritmus od Jansena, Kleina a Verschaeho (Math. Oper. Res., 2020). Navíc je naše aproximační schéma jednodušší než všechna předchozí EPTAS pro Q||Cmax, protože problém redukujeme na novou formulaci MILP s malou velikostí podpory.

Zabýváme se variantou jednoduchého problému vyvažování montážní linky, ve kterém je počet pracovních stanic a cyklický čas pevně stanoven, avšak některé úlohy podléhají nejistotě, protože jejich doby zpracování se mohou prodloužit. Cílem je udržet proveditelnost plánu i v případě zvýšení doby trvání úloh. Pro dosažení tohoto cíle zvažujeme dvě míry stability, které chceme maximalizovat: stabilizační poloměr a stabilizační faktor, jež odpovídají různým typům nárůstu délky úloh. Plánovací problém je formulován jako smíšené celočíselné lineární programování (MILP). Tato formulace je posílena zavedením horní meze a heuristiky. Konkrétně jsou alokované intervaly úloh na základě precedence zúženy, což následně zlepšuje výsledky jak heuristiky, tak formulace MILP. Tento přístup umožňuje lepší odolnost plánů proti nejistotě trvání úloh a efektivní využití zdrojů při reálných provozních podmínkách.

V této přednášce se zabýváme problémem sestavování personálních rozvrhů, které jsou robustní vůči narušením způsobeným absencí zaměstnanců. Pokud se zaměstnanec neočekávaně stane nepřítomným, musí být nahrazen jiným zaměstnancem, což může ovlivnit pracovní dobu ostatních zaměstnanců a způsobit nežádoucí řetězový efekt, který změní velkou část rozvrhu. Zkoumáme, jak lze využitím pohotovostních služeb takovým velkým změnám předejít. Nejprve představujeme metriku pro kvantifikaci robustnosti rozvrhu, která je následně použita k sestavení dostatečně robustních rozvrhů. Ve druhé části přednášky diskutujeme podmínky, za kterých může strojové učení vést k lepším řešením. Je představena nová metodologie, která určuje minimální požadovaný výkon predikce potřebný k překonání přístupu k sestavování rozvrhů, který nevyužívá data.

CP-SAT solver byl vyvinut týmem Operations Research společnosti Google a je součástí open-source optimalizačního balíku OR-Tools. Jedná se o implementaci čistě celočíselného řešitele Constraint Programming (CP) postaveného na SAT solveru s využitím Lazy Clause Generation. Inspirací mu byl solver chuffed a přednáška Petera Stuckeyho na CP 2013 o Lazy Clause Generation. CP-SAT solver přináší oproti solveru chuffed dvě hlavní vylepšení. Prvním je použití simplexové metody vedle SAT enginu. Druhým je implementace a využití portfolia různorodých workerů pro vyhledávací část. Použití simplexové metody přináší zjevné výhody lineární relaxace pro lineární část celého modelu a zároveň odstartovalo integraci MIP technologií do CP-SAT. To je náročný úkol, protože MIP solvery jsou vyspělé a složité. Integrace zahrnuje presolve (již dříve přítomný v CP-SAT), duální redukce, specifická pravidla větvení, řezání, fixace nákladů na základě redukovaných nákladů a další pokročilé techniky. Tato integrace také umožnila těsné propojení výzkumu v oblasti plánování založeného na MIP s nejpokročilejšími plánovacími algoritmy. Díky tomu došlo k průlomům v řešení a dokazování složitých plánovacích instancí, jako jsou Job-Shop problémy a Resource Constrained Project Scheduling Problems. Použití portfolia různých workerů umožňuje snadnější zkoušení nových nápadů a integraci ortogonálních technik s minimálními komplikacemi, kromě nutnosti kontrolovat explozi potenciálních workerů. Tito workeři mohou být kategorizováni podle různých kritérií, například hledání primálních řešení (za použití kompletních solverů, lokálního vyhledávání nebo Large Neighborhood Search), zlepšování duálních hranic nebo redukce problému za pomoci kontinuálního prohledávání. Tato různorodost chování zvýšila robustnost solveru, zatímco kontinuální sdílení informací mezi workery přineslo výrazné zrychlení při paralelním běhu více workerů. CP-SAT je tak dnes špičkovým solverem s bezkonkurenčním výkonem v komunitě Constraint Programming. Dosahuje průlomových výsledků v benchmarkech pro plánování (včetně uzavření mnoha otevřených problémů) a konkurenceschopných výsledků vůči nejlepším MIP solverům na čistě celočíselných problémech.

Pod vlivem úspěchu e-commerce se dnešní sklady mění na plně automatizované výrobní závody pro plnění objednávek. Mnohé z nich používají paradigma „parts-to-picker“, kdy mobilní roboti na zvedání regálů nebo dopravníky doručují jednotky skladových položek (SKU) ke stacionárním pracovníkům, kteří na pickingových stanicích kompletují objednávky. Tato přednáška si klade za cíl strukturovat a přehledně zhodnotit rodinu problémů plánování spojených s plněním objednávek, které vznikají v tomto prostředí: Na vstupní straně musí být sekvence, ve které jsou přepravky se SKU doručovány na pracovní stanici, synchronizována s objednávkami, které jsou na této stanici současně kompletovány na výstupní straně. Tímto způsobem lze dosáhnout efektivnějšího procesu plnění objednávek a ulehčit systém dodávky přepravek. Přednáška klasifikuje rodinu mírně odlišných problémů plánování plnění objednávek, které vznikají při různých nastaveních pracovních stanic ve skladech. Tato klasifikační schémata jsou použita pro přehled současné literatury, analýzu výpočetní složitosti a systematické kvantifikování zisků z alternativních pracovních nastavení. Přednáška také vyzdvihuje cenné výzkumné směry pro tuto nově vznikající oblast výzkumu v oblasti plánování.

Firmy, které fungují na bázi výroby na zakázku, nemusí být schopny uspokojit celkovou poptávku kvůli omezené kapacitě a přísným dodacím lhůtám. To vyžaduje výběr pouze části zákaznických objednávek, aby se maximalizoval celkový zisk, což vede k problémům akceptace objednávek a plánování (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 doby uvolnění, termíny dodání, lhůty a závislé časy přípravy, je obtížné najít přesné řešení pro problém GOAS, které určí, které objednávky přijmout a jak je naplánovat současně s cílem maximalizovat zisk, a to v rozumném čase, i v prostředí s jediným strojem. Proto jsme vyvinuli efektivní a výkonnou matheuristiku, která se skládá z modelu smíšeného celočíselného lineárního programování založeného na časových segmentech, algoritmu pro vyhledávání v proměnlivých sousedstvích a tabu vyhledávacího algoritmu pro problém GOAS. Výpočetní výsledky ukazují, že navržená matheuristika překonává současné algoritmy pro problém GOAS. Hranice optimálně vyřešených instancí byla posunuta dále a blízká optimální řešení byla získána v rozumném čase pro instance, které leží za touto hranicí. Společná práce s İstenç Tarhanem.

Zkoumáme problém 1 || ∑ wj Uj, což je problém minimalizace váženého počtu opož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 plánování, s několika různými aplikacemi jak v teorii, tak v praxi. Důkazujeme, že 1 || ∑ wj Uj je W[1]-těžký vzhledem k počtu různých časů zpracování ve vstupu, stejně jako vzhledem k počtu různých vah ve vstupu. Tato skutečnost, spolu s předchozími pracemi, poskytuje kompletní obraz o problému 1 || ∑ wj Uj z pohledu parametrizované složitosti, stejně jako téměř těsné hranice složitosti pro tento problém pod Exponenciální časovou hypotézou (ETH). Společná práce s Dannym Hermelinem.