ANALIZA CZASOWO-KOSZTOWA
SIECI CPM-COST
Maciej Patan
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
WPROWADZENIE
W metodach CPM i PERT zwraca się uwagę jedynie na analizę ilościową
Równie ważne zagadnienie  aspekt ekonomiczny i możliwość modyfikacji
modelu poprzez zmianę struktury sieci ze względu na czas realizacji
przedsięwzięcia dla inwestora lub odbiorcy
Należy rozpatrzyć techniczne możliwości skrócenia terminu wykonania
całego przedsięwzięcia w taki sposób, aby koszty związane z jego realizacją
były jak najniższe
Określenie optymalnego terminu realizacji przedsięwzięcia  takie ułożenie
programu przyśpieszenia, aby największa akceleracja przypadła na te
czynności krytyczne, których koszty przyśpieszenia będą najmniejsze
UWAGA!
" każde przyspieszenie wiąże się ze zwiększeniem kosztów
" odbiorca oczekuje efektu przy minimum wzrostu kosztów
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 1
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
METODA CPM-COST
Niech
" tn  czas normalny czynności, przy którym koszty jej wykonania Kn są najniższe
" tgr  czas graniczny, najkrótszy możliwy ze względów technicznych i
technologicznych czas wykonania czynności przy koszcie granicznym Kgr
" K = f(t)  przebieg zależności kosztów wykonania czynności od czasu jej trwania
" S  średni gradient kosztu
Kgr - Kn
S = = tgÄ…
tn - tgr
Współczynnik S określa przyrost kosztów wykonania czynności spowo-
dowany skróceniem czasu wykonania czynności o jednostkę
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 2
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
Algorytm kompresji sieci
Krok 1. Zestawić czynności krytyczne, podać ich gradienty kosztów S oraz kosz-
ty graniczne tgr
Krok 2. Wyeliminować z zestawienia te czynności krytyczne, dla których średni
gradient kosztów nie istnieje, tzn. tn = tgr
Krok 3. Proces skracania rozpocząć od czynności krytycznej o najniższym gra-
diencie kosztów S
Krok 4. Przy skracaniu czasu trwania czynności należy starać się skrócić jej
czas o jak największą liczbę jednostek. W tym kroku algorytmu wystę-
pujÄ… dwa ograniczenia:
a) czas graniczny danej czynności
b) pojawienie się nowej ścieżki krytycznej
Nowa ścieżka pojawi się wtedy, gdy zaniknie zapas czasu w ciągu czyn-
ności niekrytycznych
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 3
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
Algorytm kompresji sieci - cd.
Krok 5. Przy istnieniu dwóch lub więcej ścieżek krytycznych w sieci należy skra-
cać czas o tą samą wielkość na wszystkich równoległych ścieżkach kry-
tycznych
Krok 6. Najkrótszy termin wykonania programu sieciowego uzyskuje się, gdy
wszystkie czynności leżące na którejkolwiek ścieżce krytycznej osiągają
czasy graniczne tgr. Dalsze skracanie czasu wykonania przedsięwzięcia
jest niemożliwe
Krok 7. Koszty przyspieszenia oblicza się mnożąc liczby jednostek czasu (dni),
o które dana czynność krytyczna została skrócona przez jej gradient
kosztów
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 4
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
Optymalizacja przedsięwzięcia polega na:
" wyodrębnieniu i zestawieniu wchodzących w jego skład czynności
" ocenie parametrów poszczególnych czynności i zdarzeń
" konstrukcji sieci zależności technologicznych
" wyznaczeniu podstawowych charakterystyk sieci dotyczÄ…cych
poszczególnych czynności, zdarzeń i całego projektu
" wyznaczeniu ścieżki krytycznej
Powyższy algorytm jest algorytmem uniwersalnym, pasuje za-
równo do sieci CPM jak i do sieci typu PERT
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 5
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
Przykład 8.1
Mając dane charakteryzujące przedsięwzięcie P (tabela) dokonać skrócenia
całkowitego czasu wykonania programu tak, aby koszt przyspieszenia terminu
ukończenia przedsięwzięcia był jak najmniejszy
(i, j) tn tgr Kn Kgr S
1, 2 8 6 280 400 60
"
1, 4 10 5 100 150 10
2, 3 6 4 300 400 50
3, 6 12 10 260 300 20
"
4, 5 15 15 150 150 -
"
5, 6 10 2 200 360 20
1290 1780
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 6
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
(9)
6
8 14
3
2
17 23
(9)
12
(9)
8
9 9
0
35
1 6
0
35
(0)
(0)
10 10
0
0
(0)
15
10 25
4
5
10
25
0
0
" ścieżka krytyczna: 1 - 4 - 5 - 6
" termin wykonania przedsięwzięcia: 35 dni
" zapas na ciągu czynności niekrytycznych: 9 dni
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 7
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
Etapy kompresji sieci
1. Czynność o najmniejszym współczynniku wzrostu kosztów  (1, 4)
" Czas trwania tej czynności można skrócić do 5 dni
" Czas realizacji przedsięwzięcia zostaje skrócony do 30 dni
" Wzrost kosztów: K1 = S · "t = 10 · (10 - 5) = 50
(4)
6
8 14
3
2
12 18
(4)
12
(4)
8
0
30
1 6
0
30
5 (0)
(0) 10
(0)
15
5 20
4
5
5
20
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 8
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
2. Kolejna czynność o najmniejszym współczynniku wzrostu kosztów  (5, 6)
" Czas trwania tej czynności można skrócić do 2 dni
" Ograniczeniem jest całkowity zapas ciągu czynności 1 - 2 - 3 - 6 (4 dni)
" Czynność (5, 6) można zatem skrócić do 6 dni
" Czas realizacji przedsięwzięcia skrócony zostaje do 26 dni
" Wzrost kosztów  K2 = S · "t = 20 · (10 - 6) = 20 · 4 = 80
(0)
6
8 14
3
2
8 14
(0)
12
(0)
8
0
26
1 6
0
26
(0)
6
5
(0)
(0)
15
5 20
4
5
5
20
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 9
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
" ścieżki krytyczne: 1 - 2 - 3 - 6 i 1 - 4 - 5 - 6
" czas realizacji przedsięwzięcia: 26 dni
" dalsza kompresja sieci jest możliwa
3. Kończymy skracanie czynności (5, 6)
" czas trwania czynności można skrócić do 2 dni
" czas realizacji przedsięwzięcia skraca się do 22 dni
" jednocześnie należy na drugiej ścieżce dokonać skrócenia także o 4 dni
" czynność (3, 6) skraca się do 10 dni  za mało!
" dodatkowo czynność (2, 3) skraca się o 2 dni
" osiągnięto bilans na obu ścieżkach
" koszty związane z tymi czynnościami są następujące:
dla (5, 6): 20 · (6 - 2) = 4 · 20 = 80
dla (3, 6): 20 · (12 - 10) = 20 · 2 = 40
dla (2, 3): 50 · (6 - 4) = 50 · 2 = 100
K3 = 80 + 40 + 100 = 220
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 10
Badania operacyjne Analiza czasowo-kosztowa
Sieci CPM-COST
4. Dalsze skracanie jest niemożliwe, gdyż wszystkie czynności leżące na ścieżce
krytycznej 1 - 4 - 5 - 6 osiągnęły wartości krytyczne
5. Końcowa sieć czynności
(0)
4
8 12
3
2
8 12
(0)
10
(0)
8
0
22
1 6
0
22
(0)
2
5
(0)
(0)
15
5 20
4
5
5
20
czas trwania przedsięwzięcia  22 dni
koszt związany ze skróceniem czasu wykonania przedsięwzięcia
K = K1 + K2 + K3 = 50 + 80 + 220 = 350
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski 11