Diz 51 cz
Rozvrhování s alternativními výrobními postupy
Autor: Čapek Roman
Tato disertační práce se věnuje návrhu a implementaci efektivních modelů a algoritmů pro řešení praktických problémů z oblasti optimalizace výrobních procesů. Pozornost je věnována hlavně problematice alternativních výrobních postupů, které s sebou přinášejí možnost velmi flexibilního zadání pro rozvrhovací úlohy.
S ohledem na analýzu souvisejících prací v oblasti kombinatorické optimalizace je cílem této práce rozšířit portfolio existujících přístupů o řešení, které spojuje výběr konkrétního výrobního postupu a samotné rozvrhování vybraných operací v jednom společném modelu. Práce se tak věnuje především dvěma propojeným tématům - zaprvé vytvoření vhodného modelu pro zvolený typ rozvrhovacích úloh a zadruhé návrhu, implementaci a testování optimalizačních algoritmů pro řešení rozvrhovacích problémů s alternativami, které jsou motivovány reálnými výrobními procesy.
Matematický model pro uvažované problémy vychází z notace Resource Constrained Project Scheduling Problem (RCPSP), která je dále rozšířena o definici alternativních výrobních postupů s využitím formalismu Nested Temporal Networks With Alternatives (NTNA). Navržený model odpovídá typické struktuře výrobních procesů a přitom zachovává většinu předpokladů a omezení pro RCPSP. Model zahrnuje obnovitelné zdroje s libovolnou diskrétní kapacitou, přestavbové časy a zobecněná temporální omezení (minimální a maximální časové intervaly mezi začátky operací v rozvrhu). Díky tomu umožňuje navržený model velmi flexibilní přístup k definici úloh pro rozvrhování výrobních procesů s mnoha často používanými omezeními.
Práce se dále věnuje detailní třem různým rozvrhovacím úlohám s alternativními výrobními postupy. První úloha zahrnuje kladné a záporné hrany mezi operacemi, kritériem je minimalizace délky celého rozvrhu. Pro tento problém byla vytvořena konstruktivní heuristika, ve které jsou jednotlivé operace přidávány a odebírány z rozvrhu na základě dynamických priorit. Motivací pro druhou úlohu jsou výrobní procesy, ve kterých hrají zásadní roli drahé stroje, u nichž je potřeba minimalizovat finanční nákladné přestavby. Řešení je v tomto případě založeno na iterativní heuristice, která využívá lokální optimalizaci pro časově disjunktní části rozvrhu. Kritériem ve třetí úloze je minimalizace celkových nákladů spojených s výrobním plánem. Ty jsou dány zaprvé cenou samotných výrobních operací a za druhé penalizací za pozdě dokončené zakázky. Pro řešení jsou vytvořeny dva odlišné evoluční algoritmy, jejichž výkonnost je důkladně porovnána velkým množstvím testů.
Jelikož je model uvažovaný v této práci inovativní a prozatím neexistují žádná standardizovaná testovací data, bylo pro všechny testy použito dvou zdrojů dat - zaprvé nově vygenerované instance pro každou uvažovanou rozvrhovací úlohu a zadruhé instance podobných problémů z literatury. Přestože tyto instance reflektují jen určitou část námi uvažované problematiky, všechny vytvořené algoritmy ukazují velmi dobrou výkonnost. Ve většině případů jsou jejich výsledky srovnatelné nebo i lepší než výsledky uváděné v literatuře.
- Roman Čapek, mailto:capekrom@fel.cvut.cz