Zjednodušené datové struktury pro plánování a řízení výroby
Práce s kusovníkem
 Tisk

Práce s kusovníkem

Kontrola na zacyklení při zadávání kusovníkových vazeb


Práce s kusovníkem patří mezi algoritmicky poměrně složité. Pro studijní účely byl vytvořen jednoduchý demonstrační program o rozsahu cca 1000 řádek. Následující algoritmy jsou v tomto programu otestovány.


Kusovník je definován jako acyklická síťová struktura. Nelze připustit, aby nadřazená položka byla přímým nebo nepřímým následníkem své přímé nebo nepřímé podřazené položky. Jako příklad takového zacyklení lze uvést, že do správné kusovníkové struktury lokomotivy by bylo omylem zadáno, že celá lokomotiva je další částí podvozku.


V reálných systémech řízení výroby je třeba zajistit:


  1. aby k zacyklení nemohlo dojít.
  2. v případě, že k němu např. poruchou dat nebo chybou nějaké části programu došlo, aby nedošlo k nekonečnému cyklu nebo nekonečné rekursi při zpracování, což může být velmi obtížný problém s velkou odpovědností programátorů.


Algoritmus:


  1. Předpokládá se, že se kusovník může postupně vytvářet a upravovat zadáváním dalších vazeb.
  2. Prázdný kusovník (bez jakékoliv vazby) není zacyklen.
  3. Před každým vložením nové vazby je třeba prohledat pro vkládanou podřazenou položku v jejím úplném kusovníkovém rozpadu, zda se tam nevyskytuje vkládaná nadřazená položka.
  4. Dále je před každým vložením nové vazby třeba prohledat pro vkládanou nadřazenou položku v jejím úplném inversním kusovníkovém rozpadu, zda se tam nevyskytuje vkládaná podřazená položka.

Body 3 a 4 se řeší rekursí nebo vhodným převodem rekurse na cyklus.


Tisky rozpadu kusovníku


Tisk rozpadu kusovníku, resp. inversního rozpadu je typická rekurzivní úloha.


Algoritmus:


  1. Pro zadaný uzel (např. vrcholovou položku) se provede volání tisku kusovníku s parametrem požadovaného množství = 1.
  2. V rámci tisku jedné úrovně se vypíší postupně jednotlivé položky nižší úrovně včetně množství nižší položky vstupující do vyšší položky a celkového množství na provedení jakožto součinu množství nižší položky vstupující do vyšší položky a parametru volání tisku kusovníku.
  3. Po tisku každé vazby se volá rekurzivně úloha tisku, tentokrát je výchozím uzlem nižší položka a zadaným množstvím množství na provedení příslušné nižší položky.
  4. Rekurze končí, pokud již neexistují nižší položky.
  5. Při tisku se pro každou úroveň rekurse (rovnající se úrovni kusovníku, nikoliv kódu dispoziční - nízké úrovně) provede odsazení. Tím se vytiskne kusovník orientovaný zleva doprava.


Termínování kusovníku


Předpokládejme kusovník podle obrázku .

Cílem termínování je zjištění celkových průběžných dob.


Algoritmus


Algoritmus se skládá ze dvou kroků:


  1. výpočet kódu dispoziční (nízké) úrovně ,
  2. výpočet průběžných dob.


Výpočet kódu úrovně


  1. nulování všech úrovní, nastavení běžné úrovně na 0,
  2. pro všechny položky, které jsou podřazeny běžné úrovni nastavit úroveň o 1 vyšší,
  3. nastavit běžnou úroveň o jednu vyšší,
  4. pokračovat bodem 2 až do maximální úrovně v kusovníku.


Výpočet průběžných dob


  1. pro nejnižší úroveň (nakupované položky) nastavení celkové průběžné doby na průběžnou dobu,
  2. nastavit běžnou úroveň na nejnižší,
  3. pro vyšší úroveň nastavení celkové průběžné doby na maximum z již nastavené průběžné doby a součtu průběžné doby vyšší položky a celkové průběžné doby nižší položky,
  4. nastavit běžnou úroveň na vyšší,
  5. pokud není dosaženo úrovně 0, pokračuje se bodem 2.


Určení množství v kusovníku


Na obrázku je zobrazen tentýž kusovník jako při vysvětlení termínování.

Cílem je výpočet potřebného množství jednotlivých položek bez ohledu na čas výroby a umístění položky v rozpadu kusovníku. Předpokládáme, že kód dispoziční (nízké) úrovně je již stanoven z úlohy termínování kusovníku.


Algoritmus:


  1. nulování plánovaných kusů,
  2. nastavení úrovně na 0,
  3. pro zadanou úroveň připočtení požadovaného množství do plánovaného množství, pro podřazenou úroveň připočtení potřebného rozpadu do plánovaného množství,
  4. nastavení další úrovně a pokračování bodem 3, pokud existuje nižší úroveň.