Metoda kritické cesty

Metoda kritické cesty (anglicky Critical Path Method, zkráceno 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ů.

PERT síťový diagram pro projekt s pěti milníky (10 až 50) a šesti činnostmi (A až F). Projekt má dvě kritické cesty: B-C nebo A-D-F, minimální doba trvání tohoto projektu je tedy 7 měsíců (s použitím fast-trackingu). Činnost E je podkritická, tzn. může se zpozdit až o 2 měsíce, aniž by zpozdila projekt.

Tato metoda byla vyvinuta v 50. letech 20. století jako společný projekt dvou společností: DuPont Corporation a Remington Rand Corporation pro řízení projektů správy továren. V současné době se všeobecně používá 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.

Algoritmus nalezení kritické cesty

Příklad grafu - červeně je vyznačena kritická cesta ABDGH.

Sestrojíme orientovaný, ohodnocený graf reprezentující projekt. Každá hrana v něm má svoji váhu (doba trvání) a každý vrchol své označení + dvě prázdné proměnné (levá a pravá) pro zápis hodnot cest (vlevo: "termín nejdříve možný", vpravo: "termín nejpozději přípustný").^[1] Hrany, které budou ležet na cestách, si budeme označovat. Graf může obsahovat i více než jednu kritickou cestu.

Nejprve projdeme graf zleva ze vstupního vrcholu (hodnota jeho levé proměnné je na začátku 0). Do levé proměnné tohoto vrcholu pak zapíšeme hodnotu cesty (hodnota cesty z předchozího vrcholu + hodnota hrany). Hranu vybíráme tak, že při vstupu do nějakého vrcholu budeme vybírat vždy hranu, ze které dostaneme nejvyšší hodnotu cesty (např. do vrcholu D půjdeme po hraně z B, protože cesta má hodnotu 7, což je vyšší než z C, kde má cesta hodnotu 4).

Tímto postupem vyplníme levé proměnné všech vrcholů a dojdeme až do výstupního (koncového) vrcholu grafu. V jeho levé proměnné nyní máme minimální délku projektu.

Druhý průchod grafu začínáme v koncovém vrcholu, opíšeme hodnotu z jeho levé proměnné do pravé a jdeme proti směru orientovaných hran (vpravo). Nyní však vybíráme cestu s nejmenší možnou hodnotou a její hodnotu hran odečítáme, výsledek zapíšeme do pravé proměnné vrcholu (např. do D půjdeme přes G, protože dostaneme hodnotu 7, což je menší, než kdybychom tam šli přímo z H). Když dojdeme do počátečního bodu, měli bychom v něm mít vpravo 0. Vrcholy se stejnými hodnotami vlevo a vpravo leží na kritické cestě.

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Critical path method na anglické Wikipedii.

↑ Preclík Vratislav: Průmyslová logistika, 359 s., ISBN 80-01-03449-6, Nakladatelství ČVUT v Praze, 2006, str.63 - 73, 75 - 85, 246 - 347

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu kritická cesta na Wikimedia Commons
Critical path web calculator (anglicky)

[1] Preclík Vratislav: Průmyslová logistika, 359 s., ISBN 80-01-03449-6, Nakladatelství ČVUT v Praze, 2006, str.63 - 73, 75 - 85, 246 - 347

[1]