Výzkum a vývoj

historie, milníky, fakta

Řešení komplexních úloh 

 

Pro řešení optimalizačních úloh, mezi které patří také rozvrhovací úlohy, se většinou využívá specializovaný software nazývaný optimalizační solver. Ten dokáže „chytře“ prohledávat stavový prostor a nacházet dobrá či dokonce optimální řešení.

 

Existují různé typy solverů jako mip/lp solvery, constraint solvery, sat solvery a jiné. U všech je potřeba pro konkrétní optimalizační problém potřeba nalézt vhodný způsob modelování problému a případně solver rozšířit. Známý solver je například Gurobi, Cplex nebo knihovna solverů OR-Tools.   

Náš přístup 

 

Od počátku vývoje naší platformy bylo zřejmé, že standardní způsob řešení, tedy zadání kompletní úlohy optimalizačnímu solveru a následné čekání na nalezení řešení, překračuje u komplexnějších a rozsáhlejší úloh možnosti solverů i techniky ve vztahu k paměťové i časové náročnosti.

Proto jsme využili přirozenou dekompozici optimalizační úlohy na podúlohy řešené na úrovni pracovních stanic, která umožňuje řešení škálovat. Tento přístup v praxi odpovídá způsobu řízení výroby, kdy je manažer zodpovědný za určité pracovní stanice. Tímto řešením jsme získali možnost izolovat dopady nenadálých změn ve výrobě pouze na určité stanice a zachovat původní řešení na ostatních stanicích.

Naše řešení

• Naše řešení podporuje vertikální i horizontální směr. Vertikální umožňuje sdílení zdrojů mezi pracovními stanicemi. Horizontální umožňuje simulovat nejen současný stav, ale také následné kroky, až do definovaného cíle.
   
• V horizontálním směru jde typicky o možnost vykonávat operaci na různých stanicích, což se jeví jako výhodné. Zde ovšem vzniká riziko přetížení poslední možné stanice způsobené špatným rozhodnutím z minulosti.  

 

• Tato vrstva řešení je implementována pomocí multiagentního systému. Zde autonomní SW modul (agent) reprezentuje pracovní stanici či skupinu stanic v konkrétním časovém intervalu. Cílem je najít nejlepší řešení (rozvrh). Vzhledem k možnosti sdílení zdrojů a přijímání operací jiných agentů musí počítat s různými alternativami. Výsledek je kombinací nekonfliktních řešení jednotlivých agentů
  

 

• Komunikace mezi agenty je zároveň hledáním alternativního zadání, které umožní nalézt nejlepší řešení. Multiagentní systém zastupuje klasické solvery např. v přípravě alternativ. Jedna velká monolitická úloha se tak rozpadne na menší řešitelné podúlohy. Komunikace mezi agenty vede k dosažení nejlepšího řešení původní velké úlohy.

• Druhá vrstva řešení je v současnosti opřena o dva solvery. Prvním je klasický constraint solver. Pro ten jsme vedle vlastní prohledávací strategie vyvinuli i specializované propagátory. Ty slouží zejména pro podporu pracovníků. Druhý solver je CP-SAT z knihovny Or-Tools. Tento hybridní solver využívající techniky z CP, MIP a SAT solverů z velké části kompenzuje nedostatky prvního solveru. Oba solvery fungují jako služby pro agenty multiagentního systému poskytující doplňková řešení pro zaslaná zadání. Výhodou tohoto přístupu je mimo jiné spolupráce mezi solvery, kdy je můžeme nechat paralelně řešit stejnou úlohu a sdílet nalezená řešení.  

 

• Výkon CPU typicky neumožňuje současně počítat zadání pro všechny stanice. Během výpočtu se mohou objevit další zadání vzniklá z komunikace mezi agenty. Vedle doplňkového zpracování, kdy systém reaguje na právě nalezený lokální výsledek, tomu předcházíme i rozvrhováním samotného výpočtu. Zde se rozhoduje mezi variantami, kterým dáme přednost, které pozdržíme a které zrušíme.

Vývoje nástroje EPIQA

časová osa

• 2013 VÝZKUM

  Počátek výzkumného evropského projektu ARUM z programu EU Horizon 2020. Získáváme přístup k reprezentativním datům v oblasti výrobních linek od partnerských společností Airbus a Iacobucci.

• 2017 Nasazení

  Klíčová aplikace pro plánování výroby a customizaci letadel Airbus.

• 2018 UŽIVATELSKÉ ROZHRANÍ

  Nasazení uživatelské aplikace pro definici různých scénářů a optimalizaci výsledků.

• 2022 INTEGRACE

  Uvedení sady REST API pro napojení externích systémů aplikací.

• 2024 KOMERČNÍ ŘEŠENÍ

  EPIQA je uvedena na trh jako produkt pro plánování investičních celků nebo staveb.