CPM a PERT Mystery Cache

CPM a PERT

Pozor, změna listingu!

Plánování provází lidstvo už odpradávna. Vždyť třeba před 25 tisíci lety ulovit mamuta, to nebyla žádná legrace! Zjistit, kudy mamuti chodí, najít místo, kde je nablízku rokle nebo prudký sráz, zhotovit spoustu oštěpů, kyjů a dalších zbraní, zorganizovat naháňku mamuta ke srázu za pomoci ohňů a řevu celé tlupy, spadlého zraněného mamuta pak dobít a bránit ho před divokou zvěří i nepřejícími sousedy. Stáhnout ho z kůže, maso a tuk rozporcovat a uskladnit, vyrobit z jeho kůže oděvy a z kostí různé předměty...  Zkrátka práce až nad hlavu, ale udělat se musela. Jeden člověk by to samozřejmě nezvládl a tak nezbylo, než se nějak vzájemně dorozumět a kooperovat – a hlavně u toho myslet. Plynuly další tisíce let, lidé se rychle vyvíjeli a příležitostí, vyžadujících dobré plánování, neustále přibývalo.

Samostatnou kapitolou je plánování vojenských operací. Naplánovat takový plán Barbarossa (přepadení SSSR v r. 1941) nebo operaci Overlord (invazi do Normandie v r. 1944) vyžadovalo zapojení tisíců vojenských odborníků ve štábech všech zúčastněných jednotek. Dobrý plán a jeho dodržení často dokázaly převážit i několikanásobnou přesilu protivníka. O tom se na vlastní kůži přesvědčili třeba Francouzi v bitvě s Angličany u Kresčaku (1346), císař Zikmund a jeho křižáci na Vítkově (1420)  nebo rakousko-ruská koalice v bitvě u Slavkova (1804). 

S rozvojem vědy a techniky už ale začalo plánování pomalu přesahovat lidské možnosti. F. W. Taylor, Henry Ford i Tomáš Baťa se jistě velmi zasloužili o racionalizaci průmyslové výroby i o zdokonalení metod řízení, ale rozhodující posun nastal až tehdy, když se do věci vložili matematici spolu s ekonomy. Vymysleli matematické metody, které usnadnily plánování výzkumu, vývoje, výroby, marketingu a dalších činností. V koncernu Du Pont  byla v r. 1957 poprvé aplikována metoda CPM (Critical Path Method, česky Metoda kritické cesty). Dalším úspěchem CPM bylo její využití v projektu Apollo 11, kde NASA vytvořila účinný harmonogram pro dva miliony úkolů, které nakonec vedly k přistání prvních lidí na Měsíci (1969). 

Rovněž program PERT (Program Evaluation and Review Technique) vznikl proto, aby zjednodušil plánování a kontrolu velkých a složitých projektů. Byl vyvinut pro Úřad speciálních projektů US Navy v roce 1958 a úspěšně použit pří vývoji raketových systémů Polaris A-1 (dvoustupňové rakety odpalované z ponorek s doletem 2 200 km (později více) a nesoucí jedinou jadernou hlavici s ničivým účinkem srovnatelným se 40 pumami svrženými na Hirošimu(!); takových ponorek měly USA 41 a každá si vezla 16 těchto raket...). Jiným příkladem byla aplikace PERT v rámci přípravy zimních olympijských her v roce 1968 v Grenoblu (od roku 1965); PERT pak postupně nacházel další využití ve výzkumu i v průmyslu.
O metodě PERT řeknu pouze tolik, že je to vlastně jen CPM rozšířená o počet pravděpodobnosti. Nepracuje s jediným odhadem délky každé činnosti, ale rovnou se třemi: optimistickým, pesimistickým a nejpravděpodobnějším. Ze spousty nepřesných čísel pak PERT kupodivu vypočítá jejich (skoro) přesný součet .

Ale vraťme se k CPM. Metoda CPM je matematický algoritmus plánování průběhu množiny činností projektu. Je to jeden z důležitých nástrojů řízení projektů. Používá se pro libovolné typy projektů, včetně výstaveb, softwarového vývoje, výzkumných projektů, vývoje výrobků a mnoha inženýrských aplikací. Obecně lze tuto metodu aplikovat na plánování jakéhokoli projektu se vzájemně provázanými a závislými činnostmi (1). Vychází z teorie grafů.

 „Sestrojíme orientovaný, ohodnocený graf reprezentující projekt. Každá hrana v něm má svoji váhu (trvání) a každý vrchol své označení + dvě proměnné (levou a pravou) pro zápis hodnot cest (vlevo: termín nejdříve možný, vpravo: termín nejpozději přípustný.)"  (podle (1), nepatrně upraveno)

Přeloženo do lidské řeči: Sestavíme plán jednotlivých činností, jak následují za sebou i vedle sebe. Vrcholy (uzly) tohoto grafu značí začátky a konce jednotlivých činností (jsou to jakési milníky nebo kontrolní body projektu) a čísla u jejich spojnic (hran) označují jejich trvání. Rozlišujme označení časového okamžiku a doby trvání:  je  pět hodin a pět minut nebo trvá to  pět hodin a pět minut. (Němčina pro to má dva termíny: die Uhr a die Stunde). Jak se to počítá, pochopíte asi nejlépe z (4).

Nehodlám  psát učebnici CPM ani PERT. Na webu totiž existuje velké množství dobrých a názorných textů. Na ty psané pro naprosté laiky odkazuji v seznamu literatury (2, 3 a 4). Výpočet časů v CPM sice vypadá velmi komplikovaně, ale ve skutečnosti je velmi jednoduchý (jen se sčítá a odčítá), takže ho pochopíte velmi rychle. 

* * *

Podívejte se na následující obrázek. Budete vařit oběd: zeleninovou polévku a dušené maso s vařenými brambory. Zobrazil jsem zhruba postup přípravy tohoto oběda formou síťového grafu. Na něm vidíte návaznost jednotlivých činností. Pokusil jsem se odhadnout doby jejich trvání v minutách  a zakreslit je do grafu. Na začátku bude trochu víc práce a tak předpokládám, že vám na chvíli pomůže další člen rodiny (a taky že se do kuchyně vejdete).

Legenda: B-D: očištění a nakrájení zeleniny na polévku, D-I: vaření a dochucování polévky, I-K: přenesení hrnce s polévkou ke stolu a její servírování, C-H: osmažení cibulky, E-H: příprava masa – omytí, krájení, osolení, okořenění, H-J: dušení masa, F-G: loupání brambor, G-J: vaření brambor, K-L: konzumace polévky, J-L: servírování hlavního jídla, L-M: konzumace hlavního jídla. A-B a další čárkované šipky vycházející z uzlu A jsou fiktivní činnosti, které mají nulové trvání. V tomto případě slouží jen k „zastřešení“ celého projektu.

Nyní aplikujte na síťový graf přípravy oběda metodu CPM. Vypočtěte příslušné časové hodnoty uzlů A až M  podle návodů (1, 2, 3, 4). Hned zjistíte, které činnosti nemají žádnou časovou rezervu, takže leží – řečeno terminologií CPM a PERT – na kritické cestě. U ostatních, které na kritické cestě neleží, můžete z grafu vypočítat časové rezervy. Ty jsou různého druhu – viz literatura (2,3). 

Asi jste už pochopili, v čem tkví přínos CPM nebo PERT: Manažeři projektu se mohou soustředit především na hlídání termínů činností ležících na kritické cestě. Pokud by se na ní něco zpozdilo, tak se zpozdí i termín ukončení projektu. Obě zmíněné metody umožňují takový problém snadno a rychle odhalit a vedení může okamžitě adekvátně jednat: motivovat podřízené třeba proplácením přesčasů a odměnami, zavést mimořádné sobotní směny, dočasně převést několik pracovníků z oddělení zrovna vykonávajícího nekritickou činnost na pracoviště, kde zrovna „hoří termín“ atd. U ostatních (nekritických) činností pak stačí sledovat hlavně čerpání časových rezerv a zasahovat až tehdy, když hrozí jejich přečerpání do mínusu; zasáhlo by totiž do kritické cesty (prodloužilo ji) a tím oddálilo termín dokončení celého projektu.
Pro operativní řízení se používá názornější zobrazení, např. Ganttův diagram, kde jsou zobrazeny začátky a konce všech činností a jejich rezervy na časové ose v reálném měřítku. (viz obr. v příloze).

V současnosti, kdy je k dispozici řada softwarových produktů zaměřených na využívání metod projektového řízení, jsou v praxi hojně využívány i metody, které byly původně pro svou složitost aplikovány jen zřídka. Příkladem může být metoda CPM/COST. Jejím základem je metoda kritické cesty, která je však rozšířena o nákladovou analýzu. Vznikla tak optimalizační metoda umožňující současnou optimalizaci nákladů a času. Metoda PDM (Precedence Diagram Metod) zase využívá grafické vyjádření projektů prostřednictvím tvorby složitých struktur diagramů s podporou pro optimalizaci i při změnách v projektu. Kromě základních metod projektového řízení je navíc pro plánování a řízení projektů využívána celá řada dalších metod systémové a operační analýzy: metody pro podporu rozhodování, procesní modelování, počítačová simulace projektů atd.

Jak najít keš

Zadání úlohy je uvedeno výše. Postupujte podle návodů v literatuře. 

Až budete mít všechny potřebné výpočty hotové, tak odpovězte na následující otázky:

1. Jak dlouho bude trvat příprava a konzumace oběda (tzn. čas A-M), půjde-li všechno podle plánu? Počet minut dosaďte za T₁.

2. Kdy nejpozději musíme začít servírovat polévku (činnost I-K), aby nedošlo k prodloužení času A-M? Čas v minutách od začátku přípravy oběda dosaďte za T₂.

3. Kdy nejpozději musíme ukončit vaření brambor (činnost G-J), aby nedošlo k prodloužení času A-M? Čas v minutách od začátku přípravy oběda dosaďte za  T₃.

4. Jaká je celková časová rezerva v minutách činnosti G-J?  Vypočtenou hodnotu dosaďte za T₄. 

5.  Podívejte se na tuto značku: Jedete-li motorovým vozidlem a nebydlíte-li tam, tak:
     - můžete tam vjet a odlovit si keš  –  za T₅ dosaďte 2
     - nesmíte tam vjet                         –  za T₅ dosaďte 4

Vypočtené hodnoty dosaďte do vzorce  

a vypočtěte druhou odmocninu z X. Tím dostanete číslo ABCDEFGH. Desetinné čárky si nevšímejte a číslici H nezaokrouhlujte. Pak už jen dosaďte:

Ještě kontrola

... a je to!

Vlastně není! Ta dopravní značka v 5. otázce tam není pro legraci!!! Až vám někdo vynadá (a nebudete zdaleka první!), tak to bude jen vaše chyba.

Poznámky

Za uvedený postup vaření a časový odhad mě nekamenujte. Tohle jsem ještě nevařil (resp. jsem k tomu neměl důvod). Zkrátka to berte jen jako matematickou úlohu. Mimochodem velmi lehkou...  . T₅ je „výchovná“ proměnná. 

Literatura

(1) https://cs.wikipedia.org/wiki/Metoda_kritick%C3%A9_cesty
(2) Kašpar, V.: Vybrané metódy operačnej analýzy... Učebnice dostupná na  http://www.fbi.uniza.sk/ktvi/publikacie/05_vmoa-cpmpert_u_1998.html
(3) Doležalová, J.: Možnosti využití metody kritické cesty. Diplomová práce dostupná  zde. 
(4) Mařík, R.: Metoda kritické cesty (CPM). Dostupné zde  

Konec

GC8G3W4 – verze 1.1 z 22. 1. 2020

(CC BY-SA 3.0 CZ) ladislavappl, 2019