UNIVERZITA PALACKÉHO V OLOMOUCI PŘÍRODOVĚDECKÁ FAKULTA KATEDRA MATEMATICKÉ ANALÝZY A APLIKACÍ MATEMATIKY
SEMINÁRNÍ PRÁCE Metody analýzy kritické cesty
Vypracoval: Tomáš Talášek AME, I. ročník
Obsah 1 Základní pojmy
3
2 CPM - Critical Path Method 2.1 On-line řešení CPM . . . . . . . . . . . . . . . . . . . . . . . . . .
5 8
3 PERT
10
4 Závěr
11
Úvod V této semestrální práci se budu zabývat problémy, které vznikají s plánováním rozsáhlejších projektů ve firmách. Při plánování náročnějších projektů je velmi důležité rozvrhnout si dílčí činnosti tak, aby výsledná doba, potřebná k vykonání celého projektu byla co nejkratší. Abychom toho mohli dosáhnout, musíme si nejprve stanovit realistické požadavky na trvání jednotlivých činností (a je rozumné u každé činnosti zanechat menší časovou rezervu). Bohužel s rostoucím počtem jednotlivých činností je velmi náročné pamatovat si všechny souvislosti a umět rozvrhnout, kdy bude která činnost vykonána. Proto bylo vyvinuto několik matematických metod, které se zabývají takzvanou analýzou kritické cesty (kritická cesta nám určuje minimální délku trvání celého projektu). V roce 1957 pánové Morgan R. Walker a James E. Kelley, Jr. vytvořili metodu pro analýzu kritické cesty, zvanou Critical path method (CPM)1 , která byla nejprve využita v chemickém průmyslu2 . V současné době se všeobecně používá pro libovolné typy projektů (např. softwarový vývoj, výzkumné projekty, vývoj nových produktů. . . ). Tato metoda je velmi obecná a lze ji aplikovat na libovolný projekt, kde se objevují vzájemně provázané a závislé činnosti. V roce 1958 byla metoda CPM upravena a vznikla metoda Program Evaluation and Review Technique (PERT). Tato metoda se liší tím, že do metody CPM zavádí statistiku a snaží se lépe odhadnout dobu trvání celého projektu. Metoda PERT byla vyvinuta pro americké námořnictvo, konkrétně při návrhu zbraňového systému ponorky Polaris. Metodu lze použít všude, kde se používá metoda CPM, ovšem ne vždy je to vhodné (u menších projektů máme zbytečně složité výpočty). 1
V česky psaných textech lze velmi často narazit na slovní spojení „metoda CPMÿ (tato práce není výjimkou). Toto označení není zcela správné, poněvadž zkratka CPM obsahuje slovo metoda. Přesto se toto slovní spojení hojně užívá. 2 Za zmínku jistě stojí, že tato metoda byla použita i v projektu Manhattan
2
1
Základní pojmy Předtím, než se seznámíme s jednotlivými metodami, bude nutné zavést ně-
kolik pojmů z teorie grafů, které se v těchto metodách běžně používají. Definice 1.1. Grafem ve smyslu teorie grafů rozumíme dvojici množin G = (U, H), kde U je množina uzlů a H je množina hran. Hranou rozumíme neuspořádanou dvojici [u, v], kde u ∈ U , v ∈ U jsou uzly grafu. Poznámka 1.1. V následujícím textu budeme předpokládat, že množiny U a H jsou konečné. Definice 1.2. Dva uzly, které jsou spojeny hranou, nazýváme sousední. Stupeň uzlu je dán počtem hran, které z uzlu vycházejí. Definice 1.3. Graf nazýváme úplný, jestliže pro každé dva různé uzly u ∈ U, v ∈ U platí: [u, v] ∈ H. Definice 1.4. Existuje-li v grafu alespoň jedna hrana [u, u], kde u ∈ U , nazveme ji smyčkou. Existuje-li více hran mezi dvěma uzly, nazveme je paralelními hranami. Graf, v němž se vyskytuje alespoň jedna smyčka nebo paralelní hrany, nazveme multigrafem. Poznámka 1.2. Při analýze kritické cesty použijí pouze takové grafy, který nemají žádnou smyčku ani paralelní hranu. Definice 1.5. Sledem v grafu G nazýváme posloupnost uzlů ui0 , ui1 , ..., uik takovou, že [ui,j−1 , ui,j ] ∈ H, pro j = 1, ..., k. Sled, v němž se ani jeden uzel nevyskytuje vícekrát, se nazývá cesta v G. Číslo k se nazývá délka sledu nebo cesty. Definice 1.6. Nechť h je reálná funkce definovaná na množině hran H grafu G = (U, H). Potom trojici Gh = (U, H, h) nazýváme hranově ohodnoceným grafem. Definice 1.7. Orientovaným grafem rozumíme dvojici množin G0 = (U, H), kde U je množina uzlů a H množina orientovaných hran, kterými rozumíme uspořádané dvojice (u, v), kde u ∈ U, v ∈ V jsou dva různé uzly grafu G. 3
Projekty budeme zobrazovat pomocí nezáporně hranově ohodnocených souvislých acyklických síťových grafů se vstupem a výstupem. Každá hrana představuje nějakou činnost, kdežto uzly představují začátky a konce činností. Hodnost hrany představuje dobu, která je potřebná pro vykonání činnosti. Různé činnosti našeho projektu na sebe mohou různě navazovat: • činnosti na sebe bezprostředně navazují • více činností následuje po ukončení jediné činnosti • jedna činnost následuje po ukončení více činností • více činností následuje po ukončení více činností • mezi dvěma činnostmi může existovat více paralelních činností • činnost C následuje po ukončení činnosti A a B, kdežto činnost D následuje pouze po ukončení činnosti A Projekt nejčastěji znázorňujeme graficky:
Obr. 1: Grafické znázornění projektu.
4
2
CPM - Critical Path Method Našim cílem je nalézt nejdelší cestu v grafu, kterou nazýváme kritická cesta.
Celková délka kritické cesty je dána součtem dob trvání jednotlivých činností, které na kritické cestě leží. Tato doba odpovídá minimální možné délce celého projektu. Činnost, které leží na kritické cestě se nazývají kritické. Pokud dojde k prodloužení doby, potřebné na vykonání kritické činnosti, doba potřebná na vykonání celého projektu se prodlouží. Je důležité si uvědomit, že kritická cesta nemusí být v projektu pouze jedna. Při používání metody CPM hledáme různé časové rezervy, které nám říkají, o kolik se jednotlivé činnosti mohou prodloužit případně začít později. Pokud chceme použít metodu CPM, je potřeba znát tyto informace o projektu: • technologická struktura projektu • pevný odhad doby trvání každé dílčí činnosti • termín zahájení nebo dokončení projektu, případně celková dobu trvání projektu Používané (i, j) yij T n ti (0) ti (0) + yij ti (1) ti (1) − yij
značení: činnost začínající v uzlu i a končící v uzlu j , i < j doba trvání činnosti (i, j) doba trvání projektu počet uzlů v grafu termín nejdříve možného začátku činností začínajících v uzlu i termín nejdříve možného konce činnosti (i, j) termín nejpozději přípustného konce činností začínajících v uzlu i termín nejpozději přípustného začátku činnosti (i, j)
5
Postup při řešení projektu: Nejprve stanovíme hodnotu nejdříve možných začátků tj (0): t1 (0) = 0 tj (0) = max(ti (0) + yij ), j = 2, 3, ..., n (i<j)
Následně stanovíme hodnotu nejpozději přípustných konců ti (1) tn (1) = T, pokud je T zadáno, v opačném případě tn (1) = tn (0) ti (1) = min(tj (1) − yij ), i = n − 1, ..., 2, 1 (i<j)
Výpočet různých časových rezerv: Celková časová rezerva nám určuje maximální možné zpoždění, způsobující prodloužení činnosti, které neprodlouží celkovou dobu projektu. Předpokládáme, že všechny předchozí činnosti začaly co možná nejdříve. Celkovou časovou rezervu vypočítáme podle vzorce: CRij = tj (1) − ti (0) − yij Jestliže doba trvání projektu není předem daná, potom T = tn (0). V takovéto situaci jsou celkové časové rezervy kritických činností rovny nule. Pokud T > tn (0), pak i kritické činnosti mají celkovou časovou rezervu, která je rovna T − tn (0). Pakliže by ovšem bylo T < tn (0), znamená to, že daný projekt nelze v požadovaném čase realizovat. V takovémto případě se musíme pokusit zkrátit dobu trvání jednotlivých činností, což vetšinou znamená růst nákladů. Volná časová rezerva nám určuje maximální možné zpoždění začátku nebo prodloužení trvání činnosti, které neovlivní nejdříve možné doby začátku všech bezprostředně následujících činností, za předpokladu, že všechny bezprostředně předchozí činnosti byly zahájeny co možná nejdříve. Volnou časovou rezervu vypočítáme podle vzorce: V Rij = tj (0) − ti (0) − yij 6
Závislá časová rezerva nám určuje maximální možné zpoždění začátku nebo prodloužení trvání činnosti, které neovlivní nejpozději přípustné termíny začátku všech bezprostředně následujících činností, za předpokladu, že všechny bezprostředně předchozí činnosti skončí co možná nejpozději. Závislou časovou rezervu vypočítáme podle vzorce: ZRij = tj (1) − ti (1) − yij Nezávislá časová rezerva nám určuje maximální možné zpoždění začátku nebo prodloužení trvání činností, které neovlivní nejdříve možné termíny začátku všech bezprostředně následujících činností, za předpokladu, že všechny bezprostředně předchozí činnosti skončí co možná nejpozději. Nezávislou časovou rezervu vypočítáme podle vzorce: N Rij = max
0 tj (0) − ti (1) − yij
Příklad užití metody CPM při plánování koupě rodinného domu:
7
2.1
On-line řešení CPM
Pro jednodušší řešení projektů pomocí metody CPM je vhodné použít k tomu určený software. Při hledání softwaru jsem narazil na Critical Path Calculator, který se nachází na internetové adrese http://sporkforge.com/sched/critical path.php. Jedna se on-line nástroj, který počítá nejkratší dobu potřebnou na vykonání projektu a celkovou časovou rezervu. Použití nástroje je velmi snadné, i když se celý ovládá čistě textově. Kompletní práci s nástrojem si ukážeme na jednoduchém projektu, který popisuje zvučení kapely před koncertem. Nejprve si připravíme seznam všech činností v textové podobě. Každou činnost napíšeme na jeden řádek v takovéto syntaxi: "Název činnosti" délka "Na čem činnost závisí" Pakliže naše činnost závisí na více jiných činnostech, napíšeme je všechny za sebe. Pokud je činností více, můžeme je uložit do textového souboru a následně jej načíst pomocí pole ...or upload the task list as a plain text file:. Na pořadí činností v našem seznamu nezáleží, jejich počet je omezen na 1000.
Obr.4: Zadání projektu ve formě textu. V momentě, kdy máme seznam činností hotový, stačí kliknout na tlačítko Analyze project... a náš projekt bude zpracován.
8
Obr.3: Výsledné zpracování projektu. • Critical path lenght určuje délku kritické cesty • Tasks on the critical path určuje, které činnosti leží na kritické cestě (včetně začátku a konců jejich trvání) • Task scheduling details nám popisuje, kdy můžou začít jednotlivé činnosti a jakou mají časovou rezervu
9
3
PERT Metoda PERT je zobecněním metody analýzy kritické cesty CPM. Tato me-
toda se používá k řízení složitých projektů majících stochastickou povahu. Dobu trvání každé dílčí činnosti zde chápe jako náhodnou proměnnou mající určité rozložení pravděpodobnosti. Empiricky bylo zjištěno, že v praxi toto nejlépe vystihuje tzv. beta rozdělení, které lépe vystihuje proměnlivost provozních podmínek. Pro každou činnost nejprve stanovíme 3 odhady doby trvání: aij - optimistický odhad, mij - nejpravděpodobnější odhad, bij - pesimistický odhad. Pomocí těchto odhadů si popíšeme základní charakteristiku β-rozdělení: y ij =
aij + 4mij + bij , 6
σij2 =
(bij − aij )2 , 36
σij =
(bij − aij ) 6
Postup výpočtu pro metodu PERT: Nejprve vypočítáme střední hodnoty y ij pro každou činnost (i,j). Následně pomocí metody CPM určíme kritickou cestu, jejíž délka bude představovat průměrnou dobu trvání projektu T . Celková doba trvání projektu pak leží v intervalu T ± σ. Příklad užití metody PERT při plánování koupě rodinného domu:
10
4
Závěr V této práci jsme si ukázali dvě základní metody pro analýzu kritické cesty.
I když jsou tyto metody starší, pořád jsou hojně užívané pro svou jednoduchost, přehlednost a velmi uspokojivé výsledky. Navíc jsou tyto metoda velmi rychlé, jak jsme si ukázali s použitím on-line aplikace. Největším problémem těchto metod je jednoznačně příprava před samotným výpočtem. Je velmi složité odhadnout čas jednotlivých činností, zvláště pokud jsme nikdy podobnou činnost neprováděli. Tento problém se snaží vykompenzovat metoda PERT, nicméně i zde musím odhadnout doby, potřebné na vykonání činností. Sám jsem se s analýzou kritické cesty setkal několikrát v oblasti ekonomických modelů, tak v oblasti managementu. Přesto, že jsou metody CPM a PERT dostačující, objevují se i nové, vyspělejší metody (např. Critical Chain Project Management - CCPM). Nicméně tyto metody už nejsou čistě matematické, poněvadž se zaměřují i na psychologický přístup (odvozují se z teorie omezení (Theory of Constraints – TOC).
Literatura [1] Demel J.: Grafy a jejich aplikace, Academia Praha (2002) [2] Bohanesová E.: Matematické modely v ekonomii, Univerzita Palackého, (2010) [3] Critical Path Calculator: http://sporkforge.com/sched/critical path.php (on-line 25.8.2011) [4] Wikipedie(ENG): http://en.wikipedia.org/wiki/Critical path method (online 24.8.2011)
11
