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 tematù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í rozvrhovácích problémù s alternativami, které jsou motivovány realný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á stadardizovaná 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