Cílem tohoto článku je představení výsledků diplomové práce Michala Křena vypracované pod vedením Ing. Martina Hrubého, Ph.D., kterou úspěšně zakončil studium na Fakultě informačních technologií VUT v Brně. Jak je již z názvu patrné, práce se zabývá vytvořením modulu plánování výroby v MES a nově zkoumá možné přístupy k okamžitému přeplánování v důsledku poruchy původního rozvrhu.

V současné době jsou výrobní operace v mnohých firmách rozvrhovány na základě zkušeností, přičemž často dochází ke střetu protichůdných požadavků. Vedoucí výroby požadují dopředu znát přesné požadavky výroby, kdežto lidé z logistiky je musí neustále měnit s ohledem na aktuální potřeby zákazníka. Tento konflikt lze vyřešit nasazením MES s modulem plánování výroby a tím využívat firemní zdroje mnohem efektivněji než v případě rozvrhování lidským expertem.

Základní optimalizátor

Problém rozvrhování výrobních operací lze formálně reprezentovat mnoha způsoby - v této práci byl zvolen Resource-Constrained Project Scheduling Problem (RCPSP). Jeho cílem je nalezení optimálního přiřazení množiny operací na množinu zdrojů (strojů) s omezenou kapacitou, přičemž každá operace musí dodržovat své předchůdce. Příklad tohoto problému je zobrazen na obrázku níže. První a poslední operace představuje začátek a konec celého rozvrhu. V příkladu jsou použity celkem dva zdroje s kapacitami 7 a 4, dále 10 skutečných operací, přičemž pro každou operaci je definována doba  jejího trvání (p) a požadavky na zdroje (r). Relace předchůdce mezi operacemi jsou zobrazeny ve formě orientovaného grafu. Výsledkem řešení je určení startovních časů pro všechny operace, čímž je sestaven rozvrh výroby, který v tomto případě není optimální, protože existuje lepší přiřazení s celkovou dobou trvání 12.

Alokace zdrojů

RCPSP jakožto zobecnění "job-shop" problému patří mezi NP-těžké kombinatoricko optimalizační problémy, což znamená, že nejsou známy algoritmy na nalezení optimálního řešení s polynomiální časovou složitostí. K řešení RCPSP lze přistupovat dvěma způsoby. Zaprvé, hledat optimální řešení například pomocí metody celočíselného programování nebo SAT. V případě většího množství operací (stovky až tisíce), narážení tyto metody na svá omezení, a proto se s výhodou používají stochastické metody využívající heuristické funkce při prohledávání stavového prostoru (např. genetické algoritmy nebo simulované žíhání). U těchto metod není zaručeno, že naleznou optimální řešení.

Základní optimalizátor RCPSP je založen na genetickém algoritmu, přičemž jednotlivá kandidátní řešení jsou reprezentována jako posloupnost operací dodržující relace předchůdce. Algoritmus Schedule Generation Schemes (SGS) vybírá operace v pořadí definovaném v jedinci a umísťuje je na první možný čas s ohledem na omezující podmínky. Následně je doba trvání takto vytvořeného rozvrhu použita na ohodnocení jedince. Příklad tohoto principu je demonstrován na obrázku níže.

Řazení operací

Pro reálné použití byl algoritmus SGS rozšířen o praktické skutečnosti - měnící se kapacita zdrojů v čase (směny, údržba), instalační doba operací na zdroje, priority apod.

Příklad praktického nasazení

Tato diplomová práce byla konzultována s firmou Visteon-Autopal, s.r.o. sídlící v Hluku a dále je popsáno, jak by bylo možné základní optimalizátor použít v praxi.

Firma ve svém závodě vyrábí různé typy chladičů pro automobilový průmysl. Výroba každého chladiče se skládá z několika výrobních operací, které jsou obvykle velmi podobné pro různé chladiče. Liší se obvykle pouze strojem, na kterém má být operace provedena. Příklad takového technologického postupu je na obrázku níže.

Návaznost výrobních operací

Na obrázku níže je naznačen postup, jak by mohlo probíhat vygenerování požadovaného RCPSP. V podnikovém informačním systému (ERP) se obvykle hromadí požadavky zákazníků na výrobu. Tyto systémy obvykle umožňují export těchto informací do běžně používaných formátů. Tento soubor, který by obsahoval seznam výrobků a jejich požadovaný počet, by byl jedním ze vstupů do uvažovaného generátoru RCPSP.

Tok informací

Dále musí generátor znát pro každý výrobek jeho přesný technologický postup. Musí tedy existovat seznam výrobních operací a jejich závislostí, které je nutno provést pro výrobu daného produktu (např. jako na obrázku výše). U každé operace musí být také jasně definován stroj, na kterém má být operace provedena a odhadovaná výrobní doba pro určitý počet kusů. Databáze by také měla obsahovat případné instalační doby operací. Dále musí mít generátor k dispozici seznam strojů a jejich provozní doby. Program by také měl uživateli umožňovat měnit jednotlivé položky ve vygenerovaném RCPSP a definovat případné priority. Po provedení optimalizace by výstupem byl Ganttův diagram, ze kterého lze snadno vyčíst, kdy má být jaká operace zahájena. Příklad tohoto diagramu je zobrazen na obrázku níže.

Výsledek rozvrhu

Real-time optimalizátor

Doposud byl popsán způsob řešení RCPSP a možnosti jeho použití při praktickém rozvrhování výrobních operací. Tento základní optimalizátor ovšem předpokládá přesnou znalost všech požadovaných údajů a také předpokládá vykonávání výrobních operací ve statickém, deterministickém prostředí. Na reálnou výrobu je ovšem nutné nahlížet jako na dynamické prostředí, protože ve výrobě často dochází k neočekávaným událostem (např. porucha stroje), které zapříčiní, že se původní rozvrh stává neplatným.  Z tohoto důvodu byl vytvořen real-time optimalizátor, jehož úkolem je v krátkém čase vytvořit opět efektivní rozvrh, který je zároveň i podobný původnímu.  V této práci bylo experimentováno s různými přístupy řešení tohoto problému.

V reálném nasazení by byl real-time optimalizátor připojen k výrobnímu informačnímu sytému (MES).  Tento  systém nebyl k dispozici, proto byl vytvořen SW nástroj imitující jeho činnost, který pracuje jako simulátor s diskrétním časem.  Namísto skutečných dat z terminálů ve výrobě byl navržen model poruch umožňující popsat například výpadek stroje. Kompletní schéma celého systému je zobrazeno na obrázku níže.

Schéma systému

Z obecného pohledu lze k dynamickým změnám přistupovat dvěma způsoby. První možností je zaujmout aktivnější přístup a vytvářet robustní rozvrh výroby, který již anticipuje s případnými budoucími poruchami. Jedním ze způsobů, jak toho lze docílit je, že nebudeme uvažovat předem známou konstantní dobu trvání operací. Doba trvání jednotlivých operací bude tedy popsána pomocí určitého pravděpodobnostního rozložení. Tímto vznikne problém, který je v literatuře označován jakožto "stochastic RCPSP" (SRCPSP). Další možností aktivnějšího přístupu je vytvořit prvotní rozvrh běžným způsobem a následně se jej snažit učinit robustnějším vkládáním časových prodlev. Obecně ovšem není možno vytvořit natolik robustní rozvrh, který by byl odolný vůči všem poruchám. Je tedy nutné tento aktivnější přístup zkombinovat s pasivnějším (reaktivním) přístupem, který je popsán v dalších odstavcích.

Druhou možností je tedy zaujmout pasivnější přístup a reagovat na problém až v okamžiku jeho vzniku. Jednou z možností je provést přeplánování pomocí metod hledajících přesné řešení. Tento přístup je ovšem velmi časově náročný i pro poměrně malé problémy.

Další možností pasivnějšího přístupu je provést přeplánování podobným způsobem jako výpočet základního rozvrhu. V případě této práce by se tedy jednalo o genetické algoritmy. Případně lze určit operace postihnuté danou poruchou a pouze je se snažit přeplánovat.

V případě potřeby provést přeplánování je nejprve nutné vytvořit aktuální model popsaný RCPSP. Aktuální RCPSP lze sestavit z původního RCPSP a aktuálního stavu výroby. Příklad činnosti real-time optimalizátoru a vytvoření aktuálního RCPSP je zobrazen na obrázku níže. Jedná se o již prezentované zadání problému. Základní optimalizátor vytvořil neoptimální rozvrh s celkovým časem 13. Doba trvání operace číslo 6 se zvýšila z doby 5 na dobu 6. To zapříčiní, že v čase 7 vzniká narušení původního rozvrhu výroby, neboť operace 9 nemá dostatek zdrojů na své zahájení. Aktuální stav v čase 7 je charakterizován následovně:

  • zbývající kapacitou na zdrojích (zdroj 1 – 1, zdroj 2 – 1),
  • operacemi, které právě probíhají {6, 7, 8},
  • operacemi, které již byly vykonány {0, 1, 2, 3, 4, 5},
  • operacemi, které jsou připraveny na své zahájení {9},
  • operacemi, které nejsou připraveny na své zahájení {10, 11},
  • operacemi, jejichž provádění bylo přerušeno {}.

Postihnutými operacemi jsou prohlášeny všechny právě vykonávané operace a všechny operace, které ještě nebyly zahájeny. Následně je z postihnutých operací sestaven aktuální RCPSP na základě původního problému. U právě probíhajících operací je nutno zkrátit novou dobu trvání podle již provedeného času. V uvažovaném příkladě na obrázku je aktuální RCPSP zobrazen vpravo dole. Tento problém již obsahuje pouze operace {6, 7, 8, 9, 10, 11}, které jsou v uzlu uvedeny jako druhé číslo. První číslo značí nové číslo operace. Nad tímto aktuálním RCPSP je následně provedeno přeplánování a jsou určeny nové startovní časy jednotlivých operací. Přeplánovaný rozvrh s celkovým časem 14 lze vidět na zmiňovaném obrázku vpravo nahoře.

Rozdílné výsledky rozvrhu

Závěr

Tato práce uvažuje pouze pasivní přístup a na neočekávanou událost je reagováno jedním z následujících způsobů:

  1. Přepočítáním původního plánu (activity list) pomocí algoritmu SGS. Plán je určen vybráním postihnutých operací v pořadí odpovídajícímu základnímu plánu.
  2. Zcela novým výpočtem nad aktuálním RCPSP. Tento výpočet je realizován genetickým algoritmem podobně jako u základního optimalizátoru, jen je nutné snížit počet vypočtených plánů, aby se snížila doba výpočtu.
  3. Stejným způsobem jako v druhém případě, jen je přidán do populace jedinec (plán), který odpovídá základnímu vypočtenému rozvrhu.

V práci bylo experimentováno se všemi popsanými přístupy a byly zjištěny následující skutečnosti:

  • Okamžité přeplánování je výhodné pouze u poruch, kde dochází ke zkrácení doby trvání operace. Je tomu tak z důvodu, že real-time optimalizátor neposkytuje natolik kvalitní rozvrh jako základní optimalizátor. Z tohoto důvodu je výhodné provádět přeplánování, jen pokud je to opravdu nutné nebo se jedná o zkrácení doby trvání operace.
  • Přeplánování se nevyplatí vždy ani u zkrácení doby trvání operace. Za předpokladu reagování na poruchu pouhým přepočtením původního plánu nastává často následující situace. Na zdroji se objeví dostatečná kapacita na zahájení operace, která byla v původním rozvrhu odkládána právě kvůli nedostatečné kapacitě. To ovšem má obvykle za následek, že další operace začínají později a nové uspořádání nemusí být příliš výhodné.
  • Varianta s přepočítáním původního plánu nalezne v krátkém čase nový rozvrh, který je podobný původnímu. Nevýhodou ovšem je, že kvalita rozvrhu není příliš velká v porovnání s novým výpočtem.
  • Při novém výpočtu genetického algoritmu se vyplatí vložit do populace původní nejlepší plán (jedince). Tyto rozvrhy jsou obecně mírně kvalitnější a podobnější původnímu rozvrhu než v případě genetického algoritmu bez tohoto jedince. Pokud by bylo cílem získávat co nejvíce efektivní rozvrhy výroby, byl by zvolen tento přístup.

Michal Křen

Celá diplomová práce je volně ke stažení na adrese zde.