Plánování a rozvrhování

Abstrakt: Článek pojednává o technikách výpočtu výrobních rozvrhů a o pojmu optimální výrobní rozvrh (výrobní plán). Smyslem článku je objasnit okolnosti dosažitelnosti optimálního výrobního rozvrhu.

Úvod do teorie výrobního rozvrhování

Anglická literatura rozlišuje dvě činnosti - plánování (planning) a rozvrhování (scheduling). Zjednodušeně řečeno, při plánování se rozhodujeme, co chceme udělat a jakým postupem toho lze dosáhnout. V pojmech MES systémů je výsledkem plánování soupis výrobních operací a jejich konkrétních parametrů; jako je doba trvání operace, její potřebné časové návaznosti na jiné operace, potřebné výrobní a materiálové zdroje.

Tato činnost je profesí technologa výroby a v tomto článku není zkoumána. Zformulování operací a výrobních zdrojů tvoří zadání úlohy pro rozvrhování.
Zadání úlohy pro rozvrhování je dáno:

  • Množinou operací o1, o2, ..., oN.
  • Množinou zdrojů se specifikovanou kapacitou (v každém okamžiku smí být na zdroji přiřazena skupina operací menší nebo rovna jeho kapacitě).
  • Přiřazením množiny možných zdrojů pro každou operaci.
  • Specifikací povolených časových návazností mezi operacemi (např. operace o1 nesmí začít dříve než jiná operace o2 skončí a podobně).

Při rozvrhování vycházíme z konkrétní úlohy a naší snahou je rozložit výrobní operace na výrobní zdroje v čase způsobem, který dle našeho zvoleného kritéria považujeme za optimální. Rozvrh je dán přiřazením zdroje a startovního času pro každou operaci v úloze. Aby byl rozvrh platný, musí být dodrženo zadání úlohy a to zejména časové návaznosti operací a kapacity zdrojů.
Jistě lze souhlasit s tvrzením, že na zadanou úlohu lze sestavit více možných způsobů rozvržení operací v čase. Získání rozvrhu pro zadanou úlohu je tedy naším řešením úlohy. Úlohy s operacemi a zdroji se v anglické literatuře nazývají Resource-Constrained Project Scheduling Problem (RCPSP) a jsou také typickým problémem pro vědu zvanou Operační výzkum.
Rozvrh se startovními časy operací je konečným vyjádřením rozložení operací ve výrobě. Není však praktické při optimalizaci pracovat s pojmem rozvrh, ale s nějakým jeho vhodným zakódovaním. Rozvrh se startovními časy totiž umožňuje vyjádřit velké kvantum neplatných rozvrhů a to by práci optimalizátoru kazilo. Proto přecházíme z časového vyjádření rozvrhu k relativnímu-abstraktnímu vyjádření formou kódu. Mezičlánkem mezi kódem a časovým rozvrhem je rozvrhovací algoritmus - ve formě funkce RA(K), která pro zadaný kód K vytvoří vždy platný rozvrh se startovními časy.
Naznačil jsem, že může existovat více kritérií pro posuzování kvality řešení úlohy, tedy návrhu pro výrobní rozvrh. Mějme tedy dva různé rozvrhy A a B. Chceme rozhodnout, který z nich je lepší. Naše rozhodnutí by mělo být zdůvodnitelné, tedy racionální. Jaké aspekty nás na rozvrhu zajímají? Může to být vytížení zdrojů, způsob čerpání zásob materiálu, doba výroby, splnění termínu dodávek produktů a podobně. Pokud se zaměříme na jeden aspekt rozvrhu, je to vcelku snadné, ovšem ne typické pro praktické výrobní optimalizátory. Ve výsledku dojdeme k potřebě tak zvaného více-kriteriálního rozhodování. Tato problematika rozhodně není triviální a mohla by být tématem pro samostatný článek. Pro účely tohoto článku však zkoumání aspektů rozvrhů není esenciální a smíme tedy zůstat v abstraktní rovině.

Pro zjednodušení si zaveďme funkci f(X), která zadanému řešení X přiřadí jednoznačně jeho číselné ohodnocení kvality. Prohlásíme, že řešení A je lepší než řešení B právě tehdy, když f(A) < f(B) - obvykle totiž kritéria minimalizujeme. Pokud pro A a B platí f(A) = f(B), pak považujme A a B za stejně dobrá řešení; tedy nenalézáme důvod, proč preferovat jedno před druhým (pokud bysme přesto nacházeli důvod preferovat např. A před B, pak je hodnotící funkce f(X) navržena chybně).

Celkově vzato povedeme úvahu o hledání optimálního rozvrhu v této linii:

  • Kódujeme možné rozvrhy,
  • pomocí rozvrhovacího algoritmu převádíme kódy na rozvrhy v časové doméně,
  • získané rozvrhy ohodnocujeme naší specifickou hodnotící funkcí f(X),
  • hledáme rozvrh O s nejlepší možnou hodnotou f(O), tj. hledáme kód K vedoucí na nejlépe hodnocený rozvrh O.

Definice optimálního rozvrhu

Bylo by dobré říci hned v úvodu, že množina všech platných řešení zadané úlohy může být potenciálně obrovská, naštěstí však konečná. Její velikost může růst až exponenciálně s velikostí úlohy, přesněji řečeno s počtem operací v úloze. Naším cílem bude vytvořit strojový postup (algoritmus v počítači), který v zadané úloze bude směřovat k nalezení optimálního řešení.Dostáváme se k výkladu názvu tohoto článku - je možné vždy najít optimální řešení úlohy? Teoreticky to možné je, stačí vypočítat všechny možné rozvrhy - a těch je “pouze” konečně mnoho, každý z nich ohodnotit funkcí f(X) a vybrat si ten nejlepší. Co nás omezuje, je čas, který jsme ochotni strávit čekáním na výsledek, tedy algoritmická časová složitost problému. Často upřednostníme jakékoliv rozumně dobré řešení dosažitelné v akceptovatelném čase před vidinou optimálního řešení. Abychom lépe porozuměli pojmu optimální řešení rozvrhovací úlohy, zavedeme následující klasifikaci řešení:

  • Optimální řešení - je rozvrh X, pro který jsme dokázali, že neexistuje jiný rozvrh Y, pro který platí f(Y) < f(X).
  • Sub-optimální řešení - je nejlepší řešení, které bylo v časově ohraničeném výpočtu nalezeno.
  • Technicky dosažitelné optimální řešení - je kód rozvrhu X, pro který neexistuje jiný kód Y, že by f(RA(X)) < f(RA(Y)).

Technicky dosažitelné optimální řešení zadané úlohy může být obecně horší než optimální řešení zadané úlohy. Zvolené kódování prostě může mít tu vlastnost, že neumožní vyjádřit optimální rozvrh. Celkově musíme vždy počítat se dvěma závěry:

  1. Nikdy nebudeme z časových důvodů schopni dokázat, že nalezené řešení je optimálním vzhledem k použitému kódování řešení (je technicky dosažitelné optimum).
  2. Pokud přesto dokážeme, že nalezené řešení je technicky dosažitelné optimum, přesto toto řešení nemusí být obecně optimálním řešením.

Fundamentální otázkou při hledání optimálního řešení je, kolik má zadaná úloha celkově platných řešení, kolik z nich je optimálních a kolik řešení připadá každé ze tříd kvality řešení. Jak se sobě podobají řešení ze dvou sousedních tříd a co odlišuje optimální řešení od o kousek horšího (již sub-optimálního) řešení?

Kódování rozvrhu a rozvrhovací algoritmus

Člověk si může po jisté praxi vypěstovat metodu ručního vytváření rozvrhu. Vyjde z balíčku popsaných obdélníků papíru symbolizující operace a postupně je rozkládá na velkou tabuli symbolizující rozvrh. Po prvotním rozložení dosáhne počátečního rozvrhu a dále operace zkouší přemisťovat, protože přemisťováním chce aktuální řešení vylepšit. Může doufat, že kvalitní rozvrh na tabuli “nějak uvidí”. Spíše budeme souhlasit, že časem může podléhat zažitým stereotypům. Tento postup nazvěme laickou metodou.
Na kvalitních řešeních v rozvrhovacích úlohách je nejzajímavější poznání, že jsou takřka nelidská. Člověk prostě nemusí nutně rozumět tomu, proč je vypočtené řešení dobré. Stačí, když věří své optimalizační metodě. Navíc lze velmi jednoduše ověřit platnost vypočteného řešení.
Počítačové programy s charakterem umělé inteligence mechanizují lidské postupy, a proto můžeme mechanizovat i laickou metodu. Při implementaci laické metody narazíme na následující problémy k rozhodnutí:

  • Kdy linii přemisťování obdélníků-operací ukončit? Pokud řekneme: ve stavu, kdy už nejde aktuální řešení na tabuli dále vylepšit, je tedy tím dosaženo optimálního rozvrhu?
  • V každém stavu procesu vylepšování zřejmě bude existovat více operací, se kterými by bylo možné nějak “pohnout”. Jak rozhodneme o konkrétním dalším vylepšovacím kroku? Zkusíme je všechny formou stromového zanořování do variant a podvariant?
  • A především: je nějak důležité, z jakého počátečního rozvrhu jsme v laické metodě vyšli? Ano, rozhodně. Který počáteční stav by tedy byl nejlepší?

Právě počáteční stav tabule s papírovými obdélníky operací (nebo prvotní uspořádání papírových obdélníků v balíčku) je totiž pro hledání dobrého rozvrhu nejdůležitějším aspektem. Problém hledání dobrého rozvrhu je totiž transformovatelný na problém hledání dobrého počátečního stavu tabule pro laickou metodu, respektive počátečního uspořádání operací v balíčku.

Praktické nástroje počítačového optimalizování výroby, respektive výpočtu optimálního rozvrhu výroby staví na následujících principech:

  • Definují jednoznačný způsob vyjádření pořadí, v jakém budeme na pomyslnou tabuli umisťovat operace. Pořadí operací se nazývá v anglické literatuře Activity List (AL). Activity list je nejčastěji používaným způsobem kódového vyjádření rozvrhu.
  • Definují co možná nejjednodušší (nejjednoznačnější) soubor pravidel umisťování operací do rozvrhu takový, že výsledkem umístění všech operací je vždy platné řešení úlohy. Tento soubor pravidel tvoří již zmíněný rozvrhovací algoritmus. Snahou je mít co možná nejsilnější vazbu mezi pořadím umisťování operací (AL) a výslednou kvalitou rozvrhu. Každé zkomplikování souboru pravidel rozmývá vazbu mezi pořadím operací (AL) a kvalitou rozvrhu. Optimalizační metoda tak ztrácí na účinnosti.
  • Optimalizační metoda je v zásadě experimentální. Generuje kódové pořadí operací (AL), z každého AL vytvoří rozvrh X, rozvrh X ohodnotí jako f(X) a porovná s předchozími vygenerovanými řešeními.

 Je možno vymyslet nepřeberné množství kódování rozvrhů, většina však vždy svou formu transformuje do podoby pořadí operací. Proto budeme pořadí operací (AL) považovat za základ kódování rozvrhů. Z jednoho pořadí (AL) lze jednoznačně generovat příslušný rozvrh, proto budeme rozvrhy dále vyjadřovat pořadími operací (AL). Naopak to však tak jednoznačné není.

Rozvrhovací úloha má charakter tak zvané kombinatorické optimalizační úlohy. Na výše uvedených principech vidíme, že výpočetní rozsah problému souvisí s počtem všech možných vygenerovatelných pořadí operací z úlohy. Matematik by řekl, že jsou to všechny permutace množiny operací. Máme-li množinu sta operací, pak lze vytvořit 100! (faktoriál) permutací, tj. cca 9.3 x 10^157 možných pořadí operací (AL).

Snahou je výpočet optimalizace dokončit v rozumném čase - a z toho plyne - s omezeným počtem vygenerovaných AL k ohodnocení a srovnání.

Není pravděpodobné, že na 100 různých AL dostaneme 100 různých rozvrhů s různým ohodnocením. Naopak, počet odlišných rozvrhů vytvořitelných ze všech AL dané úlohy je řádově menší než počet AL v úloze. Nikdo však nedokáže říci, kolik jich zadaná úloha má. Stejně tak je velmi pravděpodobné, že libovolně velká množina různých rozvrhů bude mít z hlediska funkce f(X) stejné ohodnocení, tedy kvalitu. Protože nemáme důvod rozlišovat mezi dvěma stejně ohodnocenými rozvrhy (řešeními), budeme řešení rozlišovat výhradně podle ohodnocení a zavedeme třídy rozvrhů podle jejich ohodnocení.

Když bychom tedy očekávali u zadané úlohy dosažitelná ohodnocení kvalitou h1, h2, h3, ..., hN a dále řekli, že hodnocení h1 je nejlepší (optimální) a hN nejhorší, pak nás bude zajímat, jak velké jsou množiny AL(h), kde symbolem AL(h) označujeme množinu všech pořadí X ohodnocených f(X)=h.

Velikosti množin AL(h) jsou velmi ovlivněny charakterem zadané úlohy. Předpokládejme jakousi normalizaci rozvrhů, která způsobí, že nelze rozvrh nekonečně zhoršovat ve smyslu hodnotící funkce a tedy hN je konečné (například prohlásíme, že v rozvrhu neexistuje operace, kterou by bylo možné v čase posunout doleva). Pak je zajímavé zjištění, že v mnohých úlohách jsou rozvrhy z třídy AL(h1) stejně obtížně dosažitelné jako rozvrhy z třídy AL(hN). Jinak řečeno, najít ten nejhorší rozvrh je stejně pracné, jako najít ten nejlepší. V optimalizaci může být poznání nekvality užitečné pro hledání kvality.

Jednu dobu jsem zkoumal následující stochastický proces: náhodně jsem generoval AL různých úloh se známým optimálním řešením a vyhodnocoval jejich ohodnocení f(X). Zajímala mě četnost náhodně generovaných AL v různých třídách hodnocení od optimálního k nejhoršímu; respektive - sestavoval jsem funkci hustoty pravděpodobnosti jevu “náhodný vzorek AL bude mít hodnocení h”. Dospěl jsem k názoru, že velikosti tříd AL rozhodně nejsou rozloženy gaussovsky, ale velmi nesymetricky. Od vrcholu grafu, tj. od nejpravděpodobnějšího - a tedy průměrného rozvrhu - křivka klesá velmi strmě doleva směrem k optimálním rozvrhům a poměrně zvolna směrem k nejhorším rozvrhům.

Genetické optimalizační algoritmy v rozvrhovacích úlohách

V předchozích odstavcích zaznělo, že principy výpočtu optimalizace výrobních rozvrhů jsou založeny na generování experimentálních AL a jejich ohodnocování.

Když si uvědomíme potenciální velikost množiny všech možných AL zadané úlohy a omezený čas, tak by nemělo nikoho překvapit, že můžeme AL generovat naprosto a zcela náhodně.

Zkušenosti z vědeckých publikací i praktických průmyslově nasazených optimalizátorů ukazují, že slušné rozvrhy lze nalézt již po ohodnocení pár set náhodně vygenerovaných AL (viz. výše provedený experiment). Je to však velmi závislé na charakteru úlohy. Řešení nalevo od těch průměrných, tj. ta lepší řešení, najdeme pouze cíleným optimalizačním výpočtem. Jak již bylo řečeno, můžeme nalézt optimální řešení úlohy, ale obecně vzato se nikdy nedozvíme, že toto řešení je skutečně optimální.

Genetické algoritmy (GA) jsou univerzální prostředek v optimalizačních úlohách, kde nelze prakticky použít exaktní postup v řešení optimalizace a jsme ochotni akceptovat náhodnost jako součást jinak deterministického výpočtu. Genetické algoritmy pracují s následujícími pojmy:

Populace jedinců - jedinec je kódově vyjádřený jeden konkrétní rozvrh. Může to být přímo AL nebo nějaká forma určení priorit operací, ze které však v potřebný okamžik vznikne AL. Skupina jedinců tvoří populaci. V každé populaci lze nalézt ohodnocením nejlepšího jedince. Počáteční populace se vytvoří náhodným vygenerováním a bude obsahovat průměrné jedince.

  • Generace evoluce výpočtu - populace jedinců se během výpočtu obměňuje. Někteří jedinci jsou vyloučeni, někteří jsou rekombinování s jinými, někteří jsou do populace přidáni jako noví. Krok výpočtu znamená transformaci aktuální populace na následující generaci populace. V každé generaci můžeme výpočet ukončit a prohlásit nejlepšího jedince populace za naše nalezené (sub-optimální) řešení optimalizace.
  • Křížení jedinců - náhodnou nebo zdůvodněnou rekombinací dvou jedinců (rodičů) se vytvoří jedinec (potomek) s potenciálně odlišným ohodnocením, než mají jeho rodiče. Chtěli bychom, aby potomek byl hodnocen lépe než jsou hodnoceni jeho rodiče. Vtipné je, že pravděpodobnost tohoto jevu klesá se zvyšující se kvalitou rodičů. Výběr páru rodičů pro křížení je samostatný výzkumný problém v tomto oboru.
  • Mutace jedince - libovolný náhodný nebo zdůvodnitelný zásah do formulace jedince s cílem změnit jeho hodnocení. Pouhým křížením by populace brzy ukončila svoje zlepšování (evoluce by uvázla v lokálním extrému hodnotící funkce). Mutace tomu má zabránit. Smysluplně provedená mutace je klíč k efektivnímu optimalizačnímu algoritmu.

Z pojmů GA lze usoudit, že výpočet optimalizace pro zadanou úlohu může obsahovat značné množství náhodných rozhodnutí (vytvoření počáteční populace, způsob volby rodičů pro křížení, způsob provedení křížení, způsob volby jedince pro mutaci, způsob provedení mutace a další). Jako značná nevýhoda GA se také jeví fakt, že pro zadanou úlohu může opakovaný výpočet optimalizace pokaždé skončit s obecně jiným výsledkem z hlediska ohodnocení nejlepšího jedince i z hlediska podoby rozvrhu.

Přesto poskytují GA v současné době nejlepší výsledky pro řešení rozvrhovacích úloh. Různé optimalizátory s GA se pak mohou kvalitativně odlišovat v počtu zdůvodněných rozhodnutí v okamžicích, kdy jiné provedou náhodné rozhodnutí. GA se tak výpočtem mohou dostat libovolně blízko optimálnímu řešení a teoreticky je pouze na uživateli, kolik si dovolí věnovat času na čekání na výsledek - čím je totiž populace větší, tím více poskytuje “genetické pestrosti” a čím více postupuje evoluce generacemi, tím je větší šance na evoluční vývoj kvalitního jedince. Toto ovšem spotřebovává výpočetní čas počítače. Nějvětším nevyřešeným problémem GA je určení pravděpodobnosti, že současná generace v sobě nese potenciál pro nalezení jedince lepšího než je její současný nejlepší jedinec. Jinak řečeno, neexistuje algoritmizovatelné rozhodnutí, zda-li má smysl se pouštět do další generace výpočtu.

Ve svém výzkumu optimalizačních postupů v rozvrhovacích úlohách jsem si stanovil ideály výpočtu GA:

  • Algoritmus je schopen poznat v jedincích prvky, ze kterých lze komponovat kvalitní jedince - řekněme, dobré charakterové rysy jedinců. Podobně, algoritmus je schopen rozpoznat rysy vedoucím vždy ke špatným jedincům.
  • Algoritmus je schopen řízeně extrahovat dobré charakterové rysy jedinců a skládat z nich nové.
  • Algoritmus je schopen predikovat pravděpodobnost zlepšení populace v další generaci.

Pro úplnost dodejme, že kromě iteračních algoritmů (např. GA) existují v řešení rozvrhovacích úloh i tak zvané exaktní algoritmy optimalizace. Tyto však dávají výsledky pouze v malých úlohách (řekněme kolem třiceti operací) a jsou pro praktické nasazení absolutně nepoužitelné.

Řízená evoluce populace jedinců v GA

Snahou mého současného výzkumu je nějak formálně popsat charakteristické rysy různých rozvrhů způsobem, aby bylo možné srovnávání napříč třídami rozvrhů. Cílem je umět vysvětlit, co způsobuje v dobrém řešení to, že je dobré a podobně, co může dobré řešení posunout mezi ta špatná.

Navrhněme si několik snadno zjistitelných charakteristik rozvrhů:

  • Operace o1 a o2 startují současně, tady paralelně - PSE(o1,o2).
  • Operace o2 startuje těsně po ukončení operace o1.
  • Operace o1 a o2 mají časový překryv.

A takto bychom mohli pokračovat.

Ve svých experimentech jsem zjistil, že mohou existovat charakteristiky, které nedovolí, aby se řešení dostalo do třídy lepší než je např. AL(hx).

Definici tohoto jevu si provedeme na příkladu - mějmě zadanou konkrétní úlohu, dvě operace o1 a o2, a charakteristiku PSE(o1,o2). Řekneme, že charakteristika PSE(o1,o2) vylučuje třídu AL(hx), pokud neexistuje rozvrh, ve kterém by tyto dvě operace startovaly paralelně a současně by hodnocení rozvrhu bylo hx nebo lepší. Přítomost takových charakteristik v úlohách není zatím obecně dokázaná, ale pravděpodobná. Ve svých experimentech jsem takových charakteristik našel hodně. Pokud nějaká charakteristika tvořená vzájemným časovým vztahem dvou operací vylučuje nějakou třídu kvality řešení, pak taky vylučuje optimální řešení (rigoróznější popis zde nemá smysl provádět).

Informaci o charakteristikách vylučujících řešení třídy lepší než nějaké hx (potažmo vylučujícími optimální řešení) nemůže mít optimalizační algoritmus k dispozici před započetím výpočtu optimalizace rozvrhu pro zadanou úlohu. Optimalizátor prostě obdrží novou úlohu a výpočtem ji začne analyzovat.

Stejně jako je to s prokázáním optimálního řešení, tak i u vylučujících charakteristik je nutné exaktně dokázat fakt, že daná charakteristika je vylučující optimum. To není z principu možné, přesto však algoritmus může pracovat s hypotézou, že nějaká charakteristika má na řešení tento vliv. Tyto hypotézy GA může v průběhu evoluce zpřesňovat a dokonce je může použít v rozhodováních jak křížit nebo mutovat jedince.

Soubor hypotéz o vylučujících charakteristikách může identifikovat dobré a špatné rysy řešení a jak již bylo výše řečeno, nalezením toho špatného jsme schopni lépe směřovat k tomu dobrému. Soubor hypotéz je dynamickým modelem vlastností úlohy, který GA bude budovat v průběhu evoluce. Velmi důležitým důsledkem zavedeného souboru hypotéz o vylučujících charakteristikách je dále evidence o již zmapovaném prostoru všech možných řešeních úlohy - optimalizátor tak řízeně prohledává prostor řešení do šířky.

Moje současné experimenty a výzkum ukazují, že dynamický model vlastností úlohy umožní GA rychlejší konvergenci k technicky dosažitelnému sub-optimálnímu řešení a mohl by také garantovat opakovatelnost výsledků při experimentování, jinak řečeno by mohl potlačit nepříjemné důsledky principiální náhodné evoluce výpočtu. Z experimentů na pevně stanovené sadě šesti set úloh (sada j120 knihovny PSPLIB) se dále ukazuje velmi vysoké přiblížení vypočtených rozvrhů ke známým optimálním řešením (průměrná odchylka od optimálních řešení přes celou sadu j120) a průměrná odchylka od optim vychází několikanásobně menší než u jiných publikovaných optimalizačních algoritmů.

Závěr

Cílem článku bylo zejména zdokumentovat teoretické mantinely v možnostech optimalizačních technik v rozvrhovacích úlohách. Jejich dokonalé pochopení je dle mého názoru základním předpokladem pro další vývoj výrobních optimalizátorů a jejich nasazování u reálných uživatelů. Teorie rozvrhování operací v úlohách s omezenými zdroji je jednou z vědecko-technických oblastí, kde se potkává mimořádně zajímavá matematika a algoritmizace s vážně míněným zájmem o praktické implementace ze strany praxe.

Další pokrok v nasazování rozvrhovacích optimalizátorů v praxi je pouze otázkou dalšího posilování motivace a důvěry uživatelů v podnicích. Pokud v budoucnu zvítězí racionalita, budou optimalizátory ne pouze pomůckou pro organizaci výroby, ale inteligentním jádrem automatizovaného řízení postupu výroby.

Martin Hrubý
Fakulta informačních technologií
Vysoké učení technické v Brně