prof. Dr. Ing. Zdeněk Hanzálek

Uvažovaným základním problémem je RCPSP (Resource-Constrained Project Scheduling Problem). Je dán množinou činností, které mají být naplánovány. Pořadí těchto činností je částečně definováno relacemi následností. Každá činnost vyžaduje určité množství obnovitelných zdrojů (např. stroje, zaměstnance), přičemž každý zdroj má plánovanou kapacitu a určitou energii (tj. spotřební zdroj s limity danými 15minutovými smlouvami). Cílem je najít posloupnost činností přiřazených ke zdrojům (tj. rozvrh) a kapacitu zdrojů s ohledem na dvě kritéria. Jedním z cílů je minimalizovat penalizaci za včasnost/zdržení (náklady vzniklé dokončením některých zakázek před nebo po termínu jejich splatnosti). Druhým cílem je minimalizace nákladů spojených se zvyšováním kapacity zdrojů (např. přijímání více zaměstnanců nebo práce přesčas). Pak by řešení problému mohlo uvažovat o lineární kombinaci nebo o Pareto optimu s ohledem na tyto dva cíle.

Problém můžeme dále rozšířit při zvažování alternativ nebo módů provádění procesů. Nakonec bychom mohli prozkoumat využití strojového učení k urychlení našich algoritmů, například k urychlení výpočtu objektivní funkce v algoritmu provádějícím časté záměny úloh, jak se ukázalo jako užitečné v naší předchozí práci zabývající se rozpisem sester ve směnném provozu.

• Čapek, R. - Šůcha, P. - Hanzálek, Z.: Production Scheduling with Alternative Process Plans, European Journal of Operational Research, Volume 217, Issue 2, March 2012, Pages 300–311.
• Módos, I. - Šůcha, P. - Hanzálek, Z.: Algorithms for robust production scheduling with energy consumption limits, Computers & Industrial Engineering, Volume 112, October 2017, Pages 391-408.
• Václavík, R. - Šůcha, P. - Hanzálek, Z.: Roster evaluation based on classifiers for the nurse rostering problem, Journal of Heuristics, October 2016, Volume 22, Issue 5, Pages 667–697

Vzhledem k tomu, že počet úloh a zdrojů v mnoha aplikacích rychle roste, je výpočet časového plánu (TT) velmi obtížný. I u velmi základních modelů je známo, že tyto problémy jsou NP-těžké. U rozsáhlých problémů je proto první výzvou získat rozumné řešení v rozumném čase. Nejběžnějším přístupem je modelování problému rozvrhování pomocí určitého formalismu, obvykle SMT nebo ILP, a nalezení proveditelného řešení pomocí univerzálního řešiče. Nevýhodou tohoto přístupu je jeho omezený výkon. Pro dosažení dostatečné škálovatelnosti je třeba vyvinout specifický algoritmus.

Máme zájem vyvinout efektivní a škálovatelné algoritmy, které budou schopny vypočítat rozvrhy (např. časem spouštěné komunikace v IEEE 802.1Qbv Time-Sensitive Networks) s desítkami tisíc úloh (tj. zpráv) pokrývajících stovky zdrojů (tj. komunikační kanály). Kromě toho se očekává, že algoritmy budou během vyhledávání uchovávat některé cenné informace, označované jako kontext, které pak budou využity k urychlení procesu vývoje plánu v reakci na měnící se požadavky.

Můžeme dále rozšířit naše algoritmy, aby společně zpracovávaly TT a Event-Triggered (ET) komunikace, čímž zlepšíme vlastnosti systémového časování. Nakonec bychom mohli prozkoumat použití strojového učení k urychlení našich algoritmů. Nedávno jsme navrhli hlubokou neuronovou síť kombinovanou s Lawlerovým rozkladem pro problém zpožděných dokončení na jednom stroji. Výsledky ukazují, že náš algoritmus založený na datech překonal dřívější moderní heuristiku a my vidíme velký potenciál rozšířit jej na další problémy se známým dekompozičním pravidlem.

• Vlk, M. - Brejchova, K. - Hanzalek, Z. - Tang, S.: Large-Scale Periodic Scheduling in Time-Sensitive Networks, Computers & Operations Research, Volume 137, January 2022.
• Minaeva, A. - Hanzalek, Z.: Survey on Periodic Scheduling for Time-Triggered Hard Real-Time Systems, ACM Computing Surveys, Volume 54, Issue 1, March 2021, Article 23, Pages 23:1-23:32.
• Bouška, M., Novák, A., Šůcha, P., Módos, I., Hanzálek, Z.: Data-driven Algorithm for Scheduling with Total Tardiness. In: Proceedings of the 9th International Conference on Operations Research and Enterprise Systems, ICORES 2020.

Rozvrhování výpočetních a komunikačních úloh v systémech, jako jsou například real-time časem řízené vestavěné jednotky (TTRES) v automatizovaných automobilech, se řídí předem definovaným statickým rozvrhem. Pro jeho nalezení je potřeba navrhnout komplexní rozvrhovací algoritmus. Tradiční časem řízené paradigma je však příliš rigidní a nezohledňuje vývoj konfigurace TTRES během jejího životního cyklu. Na základě našich zkušeností se domníváme, že současné algoritmy pro TTRES se nedokáží: (i) přizpůsobit změnám při přidávání dalších úloh do rozvrhu a (ii) zlepšit strategii vyhledávání o informace automaticky získané z řešení příbuzných problémů a instancí. Algoritmy řešící nedostatky (i) a (ii) lze řídit vstupními daty problému, jejichž charakter má vliv na omezení a kritéria daného rozvrhovacího problému. Věříme, že jde o významný nevyužitý potenciál v rozvrhovacích algoritmech. Naším cílem je uvolnit tento potenciál s využitím strojového učení a navázat na naše předchozí výsledky kombinující strojové učení a kombinatorickou optimalizaci.