5.2.6 Tabulkové řešení metod CPM a PERT Tabulkové řešení umožňuje algoritmizovat postupy jednotlivých metod, algoritmy realizovat programově s použitím běžného tabulkového procesoru nebo databázového prostředí. Pro realizaci analýzy je nutno zpracovat strukturu síťového grafu do podoby tabulek, ve kterých jsou údaje potřebné pro řešení. Pro metodu CPM jsou to údaje podle tabulky Tab. 5.4, pro metodu PERT pak v Tab. 5.6. Matematická formulace výpočtu Pro jednotlivé charakteristiky byly použity vztahy předchozího textu (5.4) až (5.16): Pro metodu PERT je použita metoda Monte Carlo , kde pro určení náhodného čísla n z intervalu
je použit vztah podle [Kvoch,1995] pro rovnoměrné rozdělení pravděpodobnosti:
n = Int ((h − d + 1).RND + d ) kde:
(5.20)
Int()
celá část čísla
RND
pseudonáhodné číslo v intervalu <0,1>
Algoritmizace a tvorba modelu Požadavkem úspěšné algoritmizace je předpoklad, že orientace činnosti je od uzlu s nižším číslem k uzlu s číslem vyšším. V případě změny struktury musí dojít k přečíslování uzlů. Časovou analýzu lze rozdělit do čtyř kroků: 1) výpočet charakteristik ZM a KM; (přímý průchod) 2) výpočet charakteristik ZP a KP (zpětný průchod); 3) výpočet rezerv RC, RV, RN, a charakteristik uzlů TM a TP 4) určení kritické cesty. Postup řešení CPM ad 1): V tomto kroku se postupuje od počátečního uzlu síťového grafu směrem ke koncovému, proto seznam činností musí být seřazen podle označení počátečního uzlu (uk_vych). Pak je možno postupně počítat charakteristiky jednotlivých činností podle vztahů (5.4 – 5.6). Je nutné ošetřit výpočet u výchozího uzlu síťového grafu.
Tab. 5.6 Vstupní údaje pro metodu PERT c_hrany
pop_hrany
uz_vych uz_konc
a
b
0
Uvolnění závěsů
1
2
1
3
1
Vývaz dvojkolí
2
3
2
4
2
Demont. nápr. převodovky
3
5
3
5
3
Demont. lož. domků
3
4
4
6
4
Kont. ložisek
4
11
5
7
c_hrany
pop_hrany
uz_vych uz_konc
a
b
5
Kont. náprav
4
10
6
8
6
Kont. pružnic
6
8
7
9
7
Měření char. pružnic
8
15
8
10
8
Vývaz TM
5
9
9
11
9
Kont. TM
9
10
10
12
10
Kont. nápr . převodovek
9
13
11
13
11
Odstrojení brz. výstroje
2
7
12
14
12
Oprava mech. části brz.
7
12
13
15
13
Kont. vzd. potrubí
7
17
14
16
14
Oprava brz. válců
7
16
15
17
15
Mont. mech. části brzdy
12
17
14
16
16
Mont. brz. válců
16
17
13
15
17
Složení náprav a TM
10
13
12
14
18
Kompletace nápr.
13
18
11
13
převodovek 19
Složení lož. domků
11
14
10
12
20
Mont. pružnic
15
18
9
11
21
Mont. lož. domků
14
18
8
10
22
Závaz dvojkolí
18
19
7
9
23
Mont. uchycení dvojkolí
19
20
6
8
24
Zkouška fce brzdy
20
21
5
7
25
Záběh podvozku
21
22
4
6
26
Demont. pružnic
3
6
3
5
102
Složení brz.
17
18
2
4
Vysvětlivky: c_hrany pop_hrany uz_vych uz_konc
číslo hrany popis hrany – činnost číslo výchozího uzlu hrany číslo koncového uzlu hrany
a b
optimistický odhad doby trvání pesimisticky odhad doby trvání
ad 2): Postup v tomto kroku je od koncového uzlu síťového grafu směrem k počátečnímu. Proto seznam musí být seřazen podle označení koncových uzlů činností (uz_konc). Při výpočtu je opět nutno ošetřit výpočet charakteristik (5.7 – 5.9) pro činnosti končící v posledním uzlu síťového grafu. ad 3):
V tomto kroku není pořadí činností v tabulce rozhodující. Postupně pro všechny činnosti probíhá výpočet podle vztahů (5.7 – 5.16).
ad 4): Pro činnosti ležící na kritické cestě platí: RCi;j = RVi;j = RNi;j = 0
(5.21)
Podle této podmínky se vyberou záznamy s činnostmi v tabulce, které tvoří kritickou cestu. Tato skutečnost znamená, že tyto činnosti nemají žádnou časovou rezervu a nedodržení daných časů znamená prodloužení celkového času Tn. Algoritmus výpočtu charakteristik CPM ve formě vývojového diagramu pro tvorbu zdrojového kódu je na obrázku Obr. 5.9. Zdrojový text rutiny výpočtu parametrů vytvořený pro databázový systém FoxPro je na obrázku Obr. 5.10. Základem výpočtu charakteristik je tabulka databáze. Její struktura je zobrazena v Tab. 5.7. Tato tabulka je indexována podle položky uz_vych jako index č. 1, podle položky uz_konc jako index č. 2. Tato indexace je pak použita pro třídění v rámci výpočtů. Ř.1 - setřídění vzestupně podle čísel výchozích uzlů činnosti a nastavení na 1. záznam. Ř. 4 – 15 – cyklus pro výpočet kroku 1). Ř.5 - ošetření na výpočty pro činnosti vycházející z počátečního uzlu SG. Ř.8 – 12 – výpočet a záznam ZM a KM. Ř.16, 17 – seřazení sestupně podle čísla koncových uzlů. Ř.20 – 30 – cyklus výpočtu etapy 2), průběh výpočtu je obdobný jako u kroku 1). Ř.34 – 47 – cyklus výpočtů parametrů kroku 3). Ř.36 – 40 – výpočet proměnných pro určení parametrů TM a TP uzlů. Ř.41 – 43 – výpočet hodnot rezerv. Ř.44, 46 – zápis vypočtených parametrů do záznamů činnosti.
Obr. 5.9: Vývojový diagram metody CPM.
** VYPOCET NEJDRIVE MOZNYCH HODNOT 1 SET ORDE TO 1 2 GO TOP 3 UZ_0 = UZ_VYCH 4 DO WHILE .NOT. EOF() 5 IF UZ_VYCH = UZ_0 6 REPLA ZM WITH 0, KM WITH ZM+T_IJ 7 ELSE 8 ZAZN=RECNO() 9 UZ_V=UZ_VYCH 10 CALCULATE MAX(KM)TO ZM_HODN FOR UZ_KONC=UZ_V 11 GO ZAZN 12 REPLA ZM WITH ZM_HODN,KM WITH ZM+T_IJ 13 ENDIF 14 SKIP 15 ENDDO ** VYPOCET NEJPOZDEJI PRIPUSTNYCH HODNOT 16 SET ORDER TO 2 17 GO TOP 18 UZ_0 = UZ_KONC 19 DO WHILE NOT EOF() 20 IF UZ_KONC = UZ_0 21 REPLA KP WITH KM, ZP WITH KP-T_IJ 22 ELSE 23 ZAZN=RECNO() 24 UZ_V=UZ_KONC 25 CALCULATE MIN(ZP)TO ZM_HODN FOR UZ_VYCH=UZ_V 26 GO ZAZN 27 REPLA KP WITH ZM_HODN,ZP WITH KP-T_IJ 28 ENDIF 29 SKIP 30 ENDDO ** VYPOCET REZERV 31 GO TOP 32 DO WHILE NOT EOF() 33 ZAZN=RECNO() 34 UZ_K=UZ_KONC 35 UZ_V=UZ_VYCH 36 CALCULATE MAX(KM)TO TM_J FOR UZ_KONC=UZ_K 37 CALCULATE MIN(ZP)TO TP_I FOR UZ_VYCH=UZ_V 38 CALCULATE MAX(KM)TO TM_I FOR UZ_KONC=UZ_V 39 CALCULATE MIN(ZP)TO TP_J FOR UZ_VYCH=UZ_K 40 GO ZAZN 41 RC_H=KP-KM && CELKOVA REZERVA 42 RV_H=TM_J-TM_I-T_IJ && VOLNA REZERVA 43 RN_H=MAX(TM_J-TP_I-T_IJ,0) && NEZAVISLA REZERVA 44 REPLA RC WITH RC_H, RV WITH RV_H, RN WITH RN_H 45 REPLA TM_JJ WITH TM_J, TP_JJ WITH TP_J, TM_II WITH TM_I, TP_II WITH TP_I 46 SKIP 47 ENDDO
Obr. 5.10: Zdrojový text výpočtu charakteristik CPM. (čísla řádku nejsou součástí textu, jsou pouze pro orientaci)
Tab. 5.7: Struktura tabulky databáze modelu CPM. Pole
Název pole
Typ
1
C_HRANY
Numeric
3
Ne
POP_HRANY Character
30
Ne
2
Délka Des.
Index
Třídit
Null
3
UZ_VYCH
Character
3
Vzestupně CZECH Ne
4
UZ_KONC
Character
3
Sestupně CZECH Ne
5
T_IJ
Numeric
5
1
Ne
6
ZM
Numeric
5
1
Ne
7
KM
Numeric
5
1
Ne
8
ZP
Numeric
5
1
Ne
9
KP
Numeric
5
1
Ne
10
RC
Numeric
5
1
Ne
11
RV
Numeric
5
1
Ne
12
RN
Numeric
5
1
Ne
13
TM_JJ
Numeric
5
1
Ne
14
TP_II
Numeric
5
1
Ne
15
TM_II
Numeric
5
1
Ne
16
TP_JJ
Numeric
5
1
Ne
Metoda PERT Metoda PERT je řešena postupem nazývaným Monte Carlo, kdy ohodnocení hran je stochastické. Jejich hodnota je při jednotlivých průchodech přiřazena jako náhodná hodnota z intervalu , což odpovídá rovnoměrnému rozdělení pravděpodobnosti. Tento interval je součástí vstupní tabulky. Výpočet parametrů činností při průchodu je obdobný jako v kroku 1) až 3) u metody CPM. Jediná změna je v kroku 1), kde dochází k přiřazení náhodné doby trvání činnosti zpracovávané činnosti. Vypočtené parametry se ukládají a dochází k dalšímu průchodu. Počet cyklů ovlivňuje přesnost konečných výsledků. Konečnou fází je statistické zpracování parametrů jednotlivých činností a určení kritické cesty podle podmínky (5.21). Na tomto základě je realizován vývojový diagram podle obrázku Obr 5.11 jako podklad pro zdrojový kód modelu (Obr. 5.12) obdobně jako u metody CPM.
Obr. 5.11: Vývojový diagram metody PERT.
Základem výpočtu je tabulka databáze. Její struktura je v tabulce Tab. 5.8. Tato tabulka s činnostmi je indexována podle položky uz_vych jako index č. 1, podle položky uz_konc jako index č. 2. Tato indexace je pak použita pro třídění v rámci výpočtů.
Tab. 5.8 Struktura tabulky databáze modelu PERT. Pole Název pole
Typ
Délka Des. Index
Numeric
3
Třídit
Null
1
C_HRANY
Ne
2
POP_HRANY Character 30
3
UZ_VYCH
Character 3
Vzestupně CZECH Ne
4
UZ_KONC
Character 3
Sestupně
5
A
Numeric
5
1
Ne
6
B
Numeric
5
1
Ne
7
T_IJ
Numeric
5
1
Ne
8
ZM
Numeric
5
1
Ne
9
KM
Numeric
5
1
Ne
10
ZP
Numeric
5
1
Ne
11
KP
Numeric
5
1
Ne
12
RC
Numeric
5
1
Ne
13
RV
Numeric
5
1
Ne
14
RN
Numeric
5
1
Ne
15
TM_JJ
Numeric
5
1
Ne
16
TP_II
Numeric
5
1
Ne
17
TM_II
Numeric
5
1
Ne
18
TP_JJ
Numeric
5
1
Ne
Ne
CZECH Ne
Ř.1 – otevření souboru s popisem SG. Ř.2 – 57 – řídící cyklus průchodů pro metodu Monte Carlo. Ř.4 – 54 – výpočet obdobný jako u metody CPM. Ř.10 – přiřazení náhodné hodnoty ohodnocení činnosti pomocí uživatelské funkce definované na ř. 58-60. Ř.57 – přidání vypočtených parametrů do pomocné tabulky databáze pro další statistické zpracování. Výstupy modelu CPM jsou v tabulce Tab. 5.9.
1 FOR 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
I=1 TO 15 ** VYPOCET NEJDRIVE MOZNYCH HODNOT SELE PERT1 SET ORDE TO 1 REPLA ALL ZM WITH 0, KM WITH 0, ZP WITH 0, KP WITH 0 GO TOP UZ_0 = UZ_VYCH DO WHILE .NOT. EOF() REPLA T_IJ WITH CAS(A,B) IF UZ_VYCH = UZ_0 REPLA ZM WITH 0, KM WITH ZM+T_IJ ELSE ZAZN=RECNO() UZ_V=UZ_VYCH CALCULATE MAX(KM)TO ZM_HODN FOR UZ_KONC=UZ_V GO ZAZN REPLA ZM WITH ZM_HODN,KM WITH ZM+T_IJ ENDIF SKIP ENDDO ** VYPOCET NEJPOZDEJI PRIPUSTNYCH HODNOT SET ORDER TO 2 GO TOP UZ_0 = UZ_KONC DO WHILE NOT EOF() IF UZ_KONC = UZ_0 REPLA KP WITH KM, ZP WITH KP-T_IJ ELSE ZAZN=RECNO() UZ_V=UZ_KONC CALCULATE MIN(ZP)TO ZM_HODN FOR UZ_VYCH=UZ_V GO ZAZN REPLA KP WITH ZM_HODN,ZP WITH KP-T_IJ ENDIF SKIP ENDDO ** VYPOCET REZERV A CASU UZLU GO TOP DO WHILE NOT EOF() ZAZN=RECNO() UZ_K=UZ_KONC UZ_V=UZ_VYCH CALCULATE MAX(KM)TO TM_J FOR UZ_KONC=UZ_K CALCULATE MIN(ZP)TO TP_I FOR UZ_VYCH=UZ_V CALCULATE MAX(KM)TO TM_I FOR UZ_KONC=UZ_V CALCULATE MIN(ZP)TO TP_J FOR UZ_VYCH=UZ_K GO ZAZN RC_H=KP-KM && CELKOVA REZERVA RV_H=TM_J-TM_I-T_IJ && VOLNA REZERVA RN_H=MAX(TM_J-TP_I-T_IJ,0) && NEZAVISLA REZERVA REPLA RC WITH RC_H, RV WITH RV_H, RN WITH RN_H REPLA TM_JJ WITH TM_J, TP_JJ WITH TP_J, TM_II WITH TM_I, TP_II WITH TP_I SKIP ENDDO SELE PERT2 APPE FROM PERT1 ENDFOR
58 FUNCTION CAS && NAHODNE CISLO PRO MONTE CARLO 59 PARA AA,BB 60 RETU INT((BB-AA+1)*RAND(-1)+AA)
Obr. 5.12: Zdrojový text výpočtu charakteristik PERT. (čísla řádku nejsou součástí textu, jsou pouze pro orientaci)
Tab. 5.9 Výstupní parametry modelu CPM c_hrany
pop_hrany
uz_ uz_ t_ij zm km zp kp rc rv rn tm_ii tp_ii tm_jj tp_jj vyc kon h
c
0
Uvolnění závěsů
1
2
1
0
1
0
1
0
0
0
0
0
1
1
1
Vývaz dvojkolí
2
3
2
1
3
1
3
0
0
0
1
1
3
3
2
Demont. nápr. převodovky
3
5
3
3
6
3
6
0
0
0
3
3
6
6
3
Demont. lož. domků
3
4
4
3
7 15 19 12
0
0
3
3
7
19
4
Kont. ložisek
4 11
5
7 12 25 30 18
0
0
7
19
12
30
5
Kont. náprav
4 10
6
7 13 19 25 12 12
0
7
19
25
25
6
Kont. pružnic
6
8
7
6 13 24 31 18
0
0
6
24
13
31
7
Měření char. pružnic
8 15
8 13 21 31 39 18
0
0
13
31
21
39
8
Vývaz TM
5
9
9
9
Kont. TM
9
10
10
Kont. nápr . převodovek
11
6 15
6 15
0
0
0
6
6
15
15
10 15 25 15 25
0
0
0
15
15
25
25
9 13
11 15 26 26 37 11 11 11
15
15
37
37
Odstrojení brz. výstroje
2
7
12
12
Oprava mech. části brz.
7
13
Kont. vzd. potrubí
14
Oprava brz. válců
15
1 13
6 18
5
0
0
1
1
13
18
12
13 13 26 19 32
6
0
0
13
18
26
32
7
17
14 13 27 32 46 19 14
9
13
18
41
46
7
16
15 13 28 18 33
5
0
0
13
18
28
33
Mont. mech. části brzdy
12 17
14 26 40 32 46
6
1
0
26
32
41
46
16
Mont. brz. válců
16
17
13 28 41 33 46
5
0
0
28
33
41
46
17
Složení náprav a TM
10 13
12 25 37 25 37
0
0
0
25
25
37
37
18
Kompletace nápr.
13
18
11 37 48 37 48
0
0
0
37
37
48
48
14
10 12 22 30 40 18
0
0
12
30
22
40
převodovek 19
Složení lož. domků
11
20
Mont. pružnic
15 18
9 21 30 39 48 18 18
0
21
39
48
48
21
Mont. lož. domků
14
18
8 22 30 40 48 18 18
0
22
40
48
48
22
Závaz dvojkolí
18
19
7 48 55 48 55
0
0
0
48
48
55
55
23
Mont. uchycení dvojkolí
19 20
6 55 61 55 61
0
0
0
55
55
61
61
24
Zkouška fce brzdy
20 21
5 61 66 61 66
0
0
0
61
61
66
66
25
Záběh podvozku
21 22
4 66 70 66 70
0
0
0
66
66
70
70
26
Demont. pružnic
6 21 24 18
0
0
3
3
6
24
102
Složení brz.
5
0
41
46
48
48
3
6
17 18
3
3
2 41 43 46 48
Činnosti kritický cesty jsou sestaveny v tabulce Tab. 5.10.
5
Tab. 5.10: Kritická cesta určená modelem CPM. c_hrany uz_vych uz_konc t_ij zm km zp kp rc rv rn tm_ii tp_ii tm_jj tp_jj 0
1
2
1
0
1
0
1
0
0
0
0
0
1
1
1
2
3
2
1
3
1
3
0
0
0
1
1
3
3
2
3
5
3
3
6
3
6
0
0
0
3
3
6
6
8
5
9
9
6 15
6 15
0
0
0
6
6
15
15
9
9
10
10 15 25 15 25
0
0
0
15
15
25
25
17
10
13
12 25 37 25 37
0
0
0
25
25
37
37
18
13
18
11 37 48 37 48
0
0
0
37
37
48
48
22
18
19
7 48 55 48 55
0
0
0
48
48
55
55
23
19
20
6 55 61 55 61
0
0
0
55
55
61
61
24
20
21
5 61 66 61 66
0
0
0
61
61
66
66
25
21
22
4 66 70 66 70
0
0
0
66
66
70
70
Model PERT je aplikován na vstupní údaje o stejné topologii jako u metody CPM. Vstupní hodnoty odhadů doby činnosti jsou v tabulce Tab. 5.6. Pro ukázkový výpočet byl zvolen počet průchodů roven 30. Při praktickém použití je počet průchodů omezen pouze požadovanou přesností a očekávanou dobou trvání výpočtu. Výstupy modelu jsou v tabulkách Tab. 5.11 – Střední hodnoty parametrů, Tab. 5.12 – Rozptyl parametrů a Tab. 5.13 – Směrodatná odchylka parametrů. Kritická cesta je označena zvýrazněním záznamů kritických činností. Tab. 5.11: Výstupní parametry modelu PERT (střední hodnota parametrů). c_hrany
t_ij
zm
km
zp
kp
rc
rv
rn
tm_ii
tp_ii
tm_jj
tp_jj
0
1,933 0,000 1,933 0,000 1,933 0,000 0,000 0,000 0,000 0,000 1,933 1,933
1
3,033 1,933 4,967 1,933 4,967 0,000 0,000 0,000 1,933 1,933 4,967 4,967
2
3,867 4,967 8,833 4,967 8,833 0,000 0,000 0,000 4,967 4,967 8,833 8,833
3
5,000 4,967 9,967 17,733 22,733 12,767 0,000 0,000 4,967 4,967 9,967 22,733
4
5,967 9,967 15,933 28,867 34,833 18,900 0,000 0,000 9,967 22,733 15,933 34,833
5
7,067 9,967 17,033 22,733 29,800 12,767 12,767 0,000 9,967 22,733 29,800 29,800
6
8,033 9,033 17,067 28,133 36,167 19,100 0,000 0,000 9,033 28,133 17,067 36,167
7
8,800 17,067 25,867 36,167 44,967 19,100 0,000 0,000 17,067 36,167 25,867 44,967
8
10,167 8,833 19,000 8,833 19,000 0,000 0,000 0,000 8,833 8,833 19,000 19,000
9
10,800 19,000 29,800 19,000 29,800 0,000 0,000 0,000 19,000 19,000 29,800 29,800
10
12,000 19,000 31,000 30,800 42,800 11,800 11,800 11,800 19,000 19,000 42,800 42,800
11
12,967 1,933 14,900 8,767 21,733 6,833 0,000 0,000 1,933 1,933 14,900 21,733
12
13,967 14,900 28,867 22,933 36,900 8,033 0,000 0,000 14,900 21,733 28,867 36,900
13
15,133 14,900 30,033 36,800 51,933 21,900 15,067 8,233 14,900 21,733 45,100 51,933
14
15,900 14,900 30,800 21,900 37,800 7,000 0,000 0,000 14,900 21,733 30,800 37,800
15
15,033 28,867 43,900 36,900 51,933 8,033 1,200 0,000 28,867 36,900 45,100 51,933
16
14,133 30,800 44,933 37,800 51,933 7,000 0,167 0,000 30,800 37,800 45,100 51,933
17
13,000 29,800 42,800 29,800 42,800 0,000 0,000 0,000 29,800 29,800 42,800 42,800
18
12,233 42,800 55,033 42,800 55,033 0,000 0,000 0,000 42,800 42,800 55,033 55,033
19
11,067 15,933 27,000 34,833 45,900 18,900 0,000 0,000 15,933 34,833 27,000 45,900
20
10,067 25,867 35,933 44,967 55,033 19,100 19,100 0,000 25,867 44,967 55,033 55,033
21
9,133 27,000 36,133 45,900 55,033 18,900 18,900 0,000 27,000 45,900 55,033 55,033
22
8,033 55,033 63,067 55,033 63,067 0,000 0,000 0,000 55,033 55,033 63,067 63,067
23
7,033 63,067 70,100 63,067 70,100 0,000 0,000 0,000 63,067 63,067 70,100 70,100
24
6,100 70,100 76,200 70,100 76,200 0,000 0,000 0,000 70,100 70,100 76,200 76,200
25
5,100 76,200 81,300 76,200 81,300 0,000 0,000 0,000 76,200 76,200 81,300 81,300
26
4,067 4,967 9,033 24,067 28,133 19,100 0,000 0,000 4,967 4,967 9,033 28,133
102
3,100 45,100 48,200 51,933 55,033 6,833 6,833 0,000 45,100 51,933 55,033 55,033
Tab. 5.12: Výstupní parametry modelu PERT (rozptyl). c_hrany t_ij
zm
km
zp
kp
rc
rv
rn
tm_ii tp_ii
tm_jj tp_jj
0
0,596 0,000 0,596 0,000 0,596 0,000 0,000 0,000 0,000 0,000 0,596 0,596
1
0,699 0,596 0,832 0,596 0,832 0,000 0,000 0,000 0,596 0,596 0,832 0,832
2
0,716 0,832 1,806 0,832 1,806 0,000 0,000 0,000 0,832 0,832 1,806 1,806
3
0,600 0,832 1,899 1,996 1,729 1,979 0,000 0,000 0,832 0,832 1,899 1,729
4
0,632 1,899 1,396 8,249 5,272 5,157 0,000 0,000 1,899 1,729 1,396 5,272
5
0,529 1,899 2,499 1,729 1,827 1,979 1,979 0,000 1,899 1,729 1,827 1,827
6
0,566 1,166 1,329 10,382 7,339 8,890 0,000 0,000 1,166 10,382 1,329 7,339
7
0,693 1,329 1,982 7,339 5,099 8,890 0,000 0,000 1,329 7,339 1,982 5,099
8
0,472 1,806 1,467 1,806 1,467 0,000 0,000 0,000 1,806 1,806 1,467 1,467
9
0,693 1,467 1,827 1,467 1,827 0,000 0,000 0,000 1,467 1,467 1,827 1,827
10
0,733 1,467 2,733 1,760 2,227 1,227 1,227 1,227 1,467 1,467 2,227 2,227
11
0,766 0,596 0,623 5,379 3,929 3,872 0,000 0,000 0,596 0,596 0,623 3,929
12
0,699 0,623 1,182 3,596 2,423 4,366 0,000 0,000 0,623 3,929 1,182 2,423
13
0,716 0,623 1,032 4,227 3,396 4,157 0,662 4,912 0,623 3,929 0,957 3,396
14
0,623 0,623 0,360 3,957 3,827 3,800 0,000 0,000 0,623 3,929 0,360 3,827
15
0,699 1,182 2,357 2,423 3,396 4,366 1,893 0,000 1,182 2,423 0,957 3,396
16
0,716 0,360 0,996 3,827 3,396 3,800 0,206 0,000 0,360 3,827 0,957 3,396
17
0,600 1,827 2,227 1,827 2,227 0,000 0,000 0,000 1,827 1,827 2,227 2,227
18
0,712 2,227 3,899 2,227 3,899 0,000 0,000 0,000 2,227 2,227 3,899 3,899
19
0,662 1,396 1,733 5,272 3,890 5,157 0,000 0,000 1,396 5,272 1,733 3,890
20
0,796 1,982 2,529 5,099 3,899 8,890 8,890 0,000 1,982 5,099 3,899 3,899
21
0,716 1,733 3,449 3,890 3,899 5,157 5,157 0,000 1,733 3,890 3,899 3,899
22
0,566 3,899 3,529 3,899 3,529 0,000 0,000 0,000 3,899 3,899 3,529 3,529
c_hrany t_ij
zm
km
zp
kp
rc
rv
rn
tm_ii tp_ii
tm_jj tp_jj
23
0,632 3,529 3,223 3,529 3,223 0,000 0,000 0,000 3,529 3,529 3,223 3,223
24
0,557 3,223 4,093 3,223 4,093 0,000 0,000 0,000 3,223 3,223 4,093 4,093
25
0,623 4,093 5,010 4,093 5,010 0,000 0,000 0,000 4,093 4,093 5,010 5,010
26
0,596 0,832 1,166 12,729 10,382 8,890 0,000 0,000 0,832 0,832 1,166 10,382
102
0,623 0,957 1,960 3,396 3,899 3,872 3,872 0,000 0,957 3,396 3,899 3,899
Tab. 5.13: Výstupní parametry modelu PERT (směrodatná odchylka). c_hrany
t_ij
zm
km
zp
kp
rc
rv
rn
tm_ii
tp_ii
tm_jj
tp_jj
0
0,772 0,000 0,772 0,000 0,772 0,000 0,000 0,000 0,000 0,000 0,772 0,772
1
0,836 0,772 0,912 0,772 0,912 0,000 0,000 0,000 0,772 0,772 0,912 0,912
2
0,846 0,912 1,344 0,912 1,344 0,000 0,000 0,000 0,912 0,912 1,344 1,344
3
0,775 0,912 1,378 1,413 1,315 1,407 0,000 0,000 0,912 0,912 1,378 1,315
4
0,795 1,378 1,181 2,872 2,296 2,271 0,000 0,000 1,378 1,315 1,181 2,296
5
0,727 1,378 1,581 1,315 1,352 1,407 1,407 0,000 1,378 1,315 1,352 1,352
6
0,752 1,080 1,153 3,222 2,709 2,982 0,000 0,000 1,080 3,222 1,153 2,709
7
0,833 1,153 1,408 2,709 2,258 2,982 0,000 0,000 1,153 2,709 1,408 2,258
8
0,687 1,344 1,211 1,344 1,211 0,000 0,000 0,000 1,344 1,344 1,211 1,211
9
0,833 1,211 1,352 1,211 1,352 0,000 0,000 0,000 1,211 1,211 1,352 1,352
10
0,856 1,211 1,653 1,327 1,492 1,108 1,108 1,108 1,211 1,211 1,492 1,492
11
0,875 0,772 0,790 2,319 1,982 1,968 0,000 0,000 0,772 0,772 0,790 1,982
12
0,836 0,790 1,087 1,896 1,557 2,089 0,000 0,000 0,790 1,982 1,087 1,557
13
0,846 0,790 1,016 2,056 1,843 2,039 0,814 2,216 0,790 1,982 0,978 1,843
14
0,790 0,790 0,600 1,989 1,956 1,949 0,000 0,000 0,790 1,982 0,600 1,956
15
0,836 1,087 1,535 1,557 1,843 2,089 1,376 0,000 1,087 1,557 0,978 1,843
16
0,846 0,600 0,998 1,956 1,843 1,949 0,453 0,000 0,600 1,956 0,978 1,843
17
0,775 1,352 1,492 1,352 1,492 0,000 0,000 0,000 1,352 1,352 1,492 1,492
18
0,844 1,492 1,975 1,492 1,975 0,000 0,000 0,000 1,492 1,492 1,975 1,975
19
0,814 1,181 1,317 2,296 1,972 2,271 0,000 0,000 1,181 2,296 1,317 1,972
20
0,892 1,408 1,590 2,258 1,975 2,982 2,982 0,000 1,408 2,258 1,975 1,975
21
0,846 1,317 1,857 1,972 1,975 2,271 2,271 0,000 1,317 1,972 1,975 1,975
22
0,752 1,975 1,879 1,975 1,879 0,000 0,000 0,000 1,975 1,975 1,879 1,879
23
0,795 1,879 1,795 1,879 1,795 0,000 0,000 0,000 1,879 1,879 1,795 1,795
24
0,746 1,795 2,023 1,795 2,023 0,000 0,000 0,000 1,795 1,795 2,023 2,023
25
0,790 2,023 2,238 2,023 2,238 0,000 0,000 0,000 2,023 2,023 2,238 2,238
26
0,772 0,912 1,080 3,568 3,222 2,982 0,000 0,000 0,912 0,912 1,080 3,222
102
0,790 0,978 1,400 1,843 1,975 1,968 1,968 0,000 0,978 1,843 1,975 1,975
Řešení slouží jako základní část zdrojového kódu programů pro řízení projektů. Může sloužit zároveň i pro postoptimalizační analýzu a řízení neopakujících se činností.
5.2.4 Grafické řešení analýzy CPM Grafické znázornění sítě pro analýzu CPM vychází z obrázku Obr. 5.5. V tomto zobrazení hrany jsou popsány označením a ohodnocením. Uzly jsou označeny svým pořadovým číslem a dalšími parametry podle obrázku Obr. 5.4a. Jedná se o hodnotu nejdříve možného termínu realizace uzlu TM, uvedenou v levém dolním poli a hodnotu nejpozději možného termínu realizace uzlu TP uvedenou v pravém dolním poli symbolu uzlu. Pro označení charakteristik činnosti se v grafickém zobrazení používá grafických symbolů podle obrázku Obr. 5.4b.
ZMij
i TMi | TPi
tij
KMij
hij ZPij
a)
KPij
b)
Obr. 5.4: Označení a popis uzlu a hrany v zobrazení CPM. (označení charakteristik odpovídá předchozímu textu) Hledání kritické cesty se provádí ve dvou průchodech v síťovém grafu. Při přímém průchodu sítí získáme nejdříve možné začátky a nejdříve možné konce jednotlivých činností, při zpětném průchodu pak nejpozději přípustné začátky a konce. Pokud vztáhneme relativní čas ke konkrétní časové škále, získáme kalendářní plán provádění jednotlivých činností, a to je účel řešení. Ohodnocení j-tého uzlu při přímém průchodu vzniká podle Dantzigova vztahu, kdy postupujeme od počátečního uzlu k uzlu koncovému:
TM j = max (TM i + tij )
(5.1)
kde: TMj TMi ti;j
nejdříve možný termín realizace uzlu j nejdříve možný termín realizace počátečních uzlů i činností končících v uzlu j ohodnocení (doba trvání) činností končících v uzlu j
Parametry uzlu TMj je možno stanovit v okamžiku, kdy jsou k dispozici hodnoty KMi;j všech vstupujících činností do uzlu (konjunktivita uzlu). Po vypočtení parametrů uzlu vypočítáváme parametry ZMj;k a KMj;k pro všechny činnosti vycházející z tohoto uzlu. Analogický výpočet provádíme při zpětném průchodu sítí. V tomto případě postupujeme od koncového uzlu k uzlu počátečnímu. Pro koncový uzel k grafu platí:
TPk = TM k
(5.2)
pak pro nejpozději přípustný termín realizace uzlu j TPj platí:
TPj = min (TPk − t j ; k )
kde: TPj
nejpozději přípustný termín realizace uzlu j
(5.3)
nejpozději přípustný termín realizace koncových uzlů k činností začínajících v uzlu j ohodnocení (doba trvání) činností začínajících v uzlu j
TPk tj;k
Při takto ohodnocených uzlech je možné vyjádřit i jednotlivé rezervy jednotlivých činností. Celková rezerva RCi;j činnosti i; j se dá vyjádřit vztahem (5.10) Volná rezerva RVi;j činnosti i ;j je počet časových jednotek, o které je možné posunout nebo prodloužit činnost tak, aniž by se posunul nejdříve možný začátek všech bezprostředně následujících činností, tj. aniž by byla překročena hodnota TPj konečného uzlu činnosti. Stanoví se podle vztahu (5.11). Volná rezerva vzniká pouze v případě, kdy do některého uzlu ústí ještě alespoň jedna hrana. Nezávislá rezerva RNi;j činnosti i; j je počet časových jednotek, o které lze nejvýše prodloužit nebo posunout začátek činnosti, aniž se změní nejdříve možný začátek všech bezprostředně následujících činností a nejpozději přípustný konec činností, které bezprostředně předcházejí. Stanoví se podle vztahu (5.12). Pro výpočet kritické cesty je podstatná pouze celková rezerva, ostatní rezervy se využívají především při algoritmech přerozdělování a optimalizaci zdrojů na síťových grafech. Matematická formulace charakteristik CPM: Pro jednotlivé charakteristiky činností a uzlů využíváme následující vztahy: ZMi;j
nejdříve možný počátek činnosti (i,j) ZM1;2 = T0 = 0
pro činnost vycházející z prvého uzlu,
ZMi;j = max(KMh i)
pro ostatní činnosti, h označuje bezprostředně předcházející činnost
KMi;j
KPi;j
= min(ZPj;k)
pro ostatní činnosti pro všechny činnosti
TPj
(5.10)
(5.11)
nezávislá rezerva činnosti (i,j) RNi;j = max(TMj - TPi - ti;j ; 0) = max(max(KMj) – min(ZPi) - ti;j ; 0)
TMj
(5.9)
volná rezerva činnosti (i,j) RVi;j = TMj – TMi – ti;j = max(KMj) - max(KMi) - ti;j
RNi;j
(5.8)
celková rezerva činnosti (i,j) RCi;j = TPj – TMi - ti;j = KPi;j – KM i;j
RVi;j
(5.7)
nejpozději přípustný konec činnosti (i,j) ZPi;j = KPi;j – ti;j
RCi;j
(5.6)
nejpozději přípustný konec činnosti (i,j) KPi;j = Tn = max(KMj;k) pro činnost končící v posledním uzlu k,
ZPi;j
(5.5)
nejdříve možný konec činnosti (i,j) KMi;j = ZMi;j + ti;jpro všechny činnosti
KPi;j
(5.4)
(5.12)
nejdříve možný termín realizace uzlu j TMi = max(KMh;i)
(5.13)
TMj = max(Ki;j)
(5.14)
nejpozději možný termín realizace uzlu j TPi = min(ZPh;i)
(5.15)
TPj = min(ZPi;j)
(5.16)
Příklad řešení metodou CPM Úkolem příkladu je zpracovat analýzu pro provádění oprav ŽKV. Jedná se modelový příklad opravy podvozku hnacího vozidla. Tento projekt je rozdělen na jednotlivé činnosti, jejichž charakteristické vlastnosti jsou popsány. Ze specifikace zadání vyplývá jako nejvhodnější princip řešení použití síťové analýzy. Opravy vozidel jsou opakující se činností, proto pro analýzu je vhodné použít metodu CPM. Pro realizaci analýzy je nutno zpracovat vstupní informace v podobě hranově ohodnoceného síťového grafu. Informace má podobu tabulky, ve které jsou údaje potřebné pro řešení. Pro metodu CPM jsou to údaje podle tabulky Tab. 5.4.
Grafické zobrazení síťového grafu této analýzy je na obrázku Obr. 5.5.
11
14
19 10
4 5 4
21 8
5 6
10
3 4 1
0 1
2
3
1 2
2 3
9 9 5
17 12
9
8 9
13
10 11
26 3 11 12
18
18 11
22 7
19
23 6
20
24 5
21
25 4
22
20 9 6
6 7
7 12 13 14 15
8
13 14 12
102 2
15
7 8
17 15 14 16 13
16
Obr. 5.5: Síťový graf daného projektu. (horní část popisu činnosti charakterizuje označení činnosti, dolní hodnota popisuje dobu trvání ti;j)
Tab. 5.4: Vstupní údaje pro metodu CPM. c_hrany
pop_hrany
uz_vych uz_konc
t_ij
0
Uvolnění závěsů
1
2
1
1
Vývaz dvojkolí
2
3
2
2
Demont. nápr. převodovky
3
5
3
c_hrany
pop_hrany
uz_vych uz_konc
t_ij
3
Demont. lož. domků
3
4
4
4
Kont. ložisek
4
11
5
5
Kont. náprav
4
10
6
6
Kont. pružnic
6
8
7
7
Měření char. pružnic
8
15
8
8
Vývaz TM
5
9
9
9
Kont. TM
9
10
10
10
Kont. nápr . převodovek
9
13
11
11
Odstrojení brz. výstroje
2
7
12
12
Oprava mech. části brz.
7
12
13
13
Kont. vzd. potrubí
7
17
14
14
Oprava brz. válců
7
16
15
15
Mont. mech. části brzdy
12
17
14
16
Mont. brz. válců
16
17
13
17
Složení náprav a TM
10
13
12
18
Kompletace nápr.převodovek 13
18
11
19
Složení lož. domků
11
14
10
20
Mont. pružnic
15
18
9
21
Mont. lož. domků
14
18
8
22
Závaz dvojkolí
18
19
7
23
Mont. uchycení dvojkolí
19
20
6
24
Zkouška fce brzdy
20
21
5
25
Záběh podvozku
21
22
4
26
Demon. pružnic
3
6
3
102
Složení brz.
17
18
2
Vysvětlivky záhlaví: c_hrany číslo hrany pop_hrany popis hrany – činnost uz_vych číslo výchozího uzlu hrany
uz_konc t_ij
číslo koncového uzlu hrany doba trvání činnosti hrany
Postup stanovení parametrů při přímém průchodu pro několik vybraných uzlů a činností je zobrazen na obrázku Obr. 5.6. Charakteristiky jsou vypočteny následovně: Pro činnost 1 podle (5.7) a (5.6)
ZM 23 = max( KM i 2 ) = max (1) = 1 KM 23 = ZM 23 + t 23 = 1 + 2 = 3 Pro uzel 3 podle (5.13)
TM 3 = max (KM i 3 ) = max (3) = 3 Pro činnost 2 podle (5.2) a (5.6)
ZM 3;5 = max( KM i ;3 ) = max (3) = 3 KM 3;5 = ZM 3;5 + t3;5 = 3 + 3 = 6 Pro činnosti 26, 3, 8, 5, 9, 10 postupuje výpočet analogicky. Pro uzly 4, 5, 9 postupujeme podobně výpočtu pro uzel 3.. Postup výpočtu pro uzel 10 podle (5.13)
TM 10 = max (KM i;10 ) = max (13;25) = 25
Charakteristiky pro činnost 17 se stanoví podle (5.5) a (5.6)
ZM 10;13 = max( KM i;10 ) = max (13;25) = 25 KM 10;13 = ZM 10;13 + t10;13 = 25 + 12 = 37 Zpětný průchod se řeší analogicky k průchodu přímému. Postup stanovení parametrů při zpětném průchodu pro několik vybraných uzlů a činností je zobrazen na obrázku Obr. S.22. Postupujeme od koncového uzlu k uzlu počátečnímu (směr postupu je naznačen na obrázku šipkami). 7
5
12
4
7
6
13
5 3
4
7
25 4 7|_
3
12
15
10
10 25|__
25
37
9 1
2
37
17
3
11
18
1 3 3|_
3
5 6|_
9 15|__
13 37|__
3
26 3
3
6 15
2
11
10
6
9
15
8
Obr. 5.6: Postup výpočtu CPM – přímý krok.
Charakteristiky jsou vypočteny následovně: Pro činnost 18 podle vztahu (5.8):
ZP13;18 = KP13; j − t13;18 = 48 − 11 = 37 Pro uzel 13 se stanoví charakteristika TP podle vztahu (5.15):
TP13 = min (ZP13; j ) = min (37 ) = 37
Pro uzel 9 se stanoví charakteristika TP podle vztahu (5.15):
TP9 = min (ZP9; j ) = min (26;15) = 15
26
48
Pro činnosti 10, 9, 8, 5, 4, 3, 2, 26, 1 postupuje výpočet analogicky. Pro uzly 10, 5, 4, 3 postupujeme podobně.
7
5
12
4 25
30* 7
6
13
5 3
4
7
25
15
19
4 7 |19
3
12
17
19
25 15
10
37
10 25|25
25
37
9 1
2
3 15
25 37
3 3|3
3
3
3
11
5 6|6
48
18
1 1
37
25
9 15|15
48*
13 37|37
6
26 3
21
3
6
24*
15
2 3
11
26
10
6 26 6
9
37
15
8 6
15
Obr. 5.7: Postup výpočtu CPM – zpětný krok. Označené uzly a činnosti jsou součástí kritické cesty Hodnoty označené * jsou vypočteny ze zbylé části SG V dalším kroku pro všechny činnosti stanovíme jednotlivé rezervy podle vztahů (5.10) až (5.12). Ukázkový výpočet pro činnost 18 a 10 je následující: Pro činnost 18 se vypočítá:
RC13;18 = KP13;18 − KM 13;18 = 18 − 48 = 0 RV13;18 = TM 18 − TM 13 − t13;18 = 48 − 37 − 11 = 0
RN13;18 = max (TP18 − TP13 − t13;18 ;0) = max (48 − 37 − 11;0 ) = 0 Pro činnost 10 je výpočet rezerv následující:
RC9;13 = KP9;13 − KM 9;13 = 37 − 26 = 11 RV9;13 = TM 13 − TM 9 − t 9;13 = 37 − 15 − 11 = 11
RN 9;13 = max (TP13 − TP9 − t9;13 ;0 ) = max (37 − 15 − 11;0) = 11
Z výsledků výpočtů rezerv vyplývá, že činnost 18 je součástí kritické cesty, protože hodnota RC je rovna nule. U činnosti 10 je hodnota volné rezervy RC>0, proto tato činnost není součástí kritické cesty v tomto síťovém grafu. V obrázku Obr. 5.7 jsou uzly a činnosti, které jsou součástí kritické cesty, zvýrazněny. Hodnoty charakteristik pro ostatní uzly a činnosti jsou v tabulce Tab. 5.5. Tab. 5.5. Výsledky výpočtu charakteristik CPM metody.
hij
Popis činnosti
uzel uzel ti;j i
ZM KM ZP KP RC RV RN
j
0
Uvolnění závěsů
1
2
1
0
1
0
1
0
0
0
1
Vývaz dvojkolí
2
3
2
1
3
1
3
0
0
0
2
Demont. nápr. převodovky 3
5
3
3
6
3
6
0
0
0
3
Demont. lož. domků
3
4
4
3
7
15 19 12 0
0
4
Kont. ložisek
4
11
5
7
12 25 30 18 0
0
5
Kont. náprav
4
10
6
7
13 19 25 12 12 0
6
Kont. pružnic
6
8
7
6
13 24 31 18 0
0
7
Měření char. pružnic
8
15
8
13 21 31 39 18 0
0
8
Vývaz TM
5
9
9
6
15 0
0
0
9
Kont. TM
9
10
10
15 25 15 25 0
0
0
10
Kont. nápr . převodovek
9
13
11
15 26 26 37 11 11 11
11
Odstrojení brz. výstroje
2
7
12
1
18 5
0
0
12
Oprava mech. části brz.
7
12
13
13 26 19 32 6
0
0
13
Kont. vzd. potrubí
7
17
14
13 27 32 46 19 14 9
14
Oprava brz. válců
7
16
15
13 28 18 33 5
0
0
15
Mont. mech. části brzdy
12
17
14
26 40 32 46 6
1
0
16
Mont. brz. válců
16
17
13
28 41 33 46 5
0
0
17
Složení náprav a TM
10
13
12
25 37 25 37 0
0
0
18
Kompletace nápr.
13
18
11
37 48 37 48 0
0
0
0
15 6
13 6
převodovek 19
Složení lož. domků
11
14
10
12 22 30 40 18 0
20
Mont. pružnic
15
18
9
21 30 39 48 18 18 0
21
Mont. lož. domků
14
18
8
22 30 40 48 18 18 0
22
Závaz dvojkolí
18
19
7
48 55 48 55 0
0
0
23
Mont. uchycení dvojkolí
19
20
6
55 61 55 61 0
0
0
24
Zkouška fce brzdy
20
21
5
61 66 61 66 0
0
0
25
Záběh podvozku
21
22
4
66 70 66 70 0
0
0
26
Demont. pružnic
3
6
3
3
21 24 18 0
0
102
Složení brz.
17
18
2
41 43 46 48 5
6
5
0
Výsledek analýzy CPM je graficky zobrazen na obrázku Obr. 5.8. Celá kritická cesta je zvýrazněna.
4
19
11 12 30
4 7 19
14 22 40
5
21
3
26 11
6 6 24
7 13 18
20 6
8 13 31
7
15 21 39
13 12 14
12 26 32
15
102 17 41 46
16
16 28 33
Obr. 5.8: Výsledný síťový graf zpracovaný metodou CPM.
5.2.5 Metoda PERT Analýzu metodou PERT používáme tam, kde jsou činnosti neopakovatelné a nelze dobu trvání činnosti změřit předem. Nejčastěji se používá při řízení vývoje nového zařízení. Tato metoda pracuje s hranově definovaným síťovým grafem. Trvání činnosti se považuje za náhodnou veličinu s určeným rozdělením pravděpodobnosti. Tento typ analýzy se používá pro návrhy projektů, u kterých nejsme schopni deterministicky definovat ohodnocení činností. Při praktickém řešení se používá tří odhadů ohodnocení činnosti s označením: optimistický odhad (a) nejpravděpodobnější odhad (m) pesimistický odhad (b) Časovou analýzu typu PERT je možno provádět dvojím způsobem: n metodou Monte Carlo - modelováním realizací síťového grafu převodem pravděpodobnosti na model s hodnotami hodnocení činnosti určené náhodným výběrem z intervalu podle určeného pravděpodobnostního rozdělení. n převodem na deterministický model - činnostem přiřadíme ohodnocení popsané očekávanou dobou trvání to , používá se proložení polynomem 2. řádu:
to =
a + 4m + b , 6
(5.17)
pro rozptyl trvání platí: 2 ( a + b) D (t ij ) = ,
36
(5.18)
a směrodatná odchylka se vypočítá:
D (t ij ) =
b−a 6
a model běžně řešíme postupem známým pro CPM.
(5.19)
