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 ˛e uwag ˛e jedynie na analiz˛e ilo´sciow ˛
a
ã Równie wa˙zne zagadnienie – aspekt ekonomiczny i mo˙zliwo´s´c modyfikacji
modelu poprzez zmian ˛e struktury sieci ze wzgl ˛edu na czas realizacji
przedsi ˛ewzi ˛ecia dla inwestora lub odbiorcy
ã Nale˙zy rozpatrzy´c techniczne mo˙zliwo´sci skrócenia terminu wykonania
całego przedsi ˛ewzi ˛ecia w taki sposób, aby koszty zwi ˛
azane z jego realizacj ˛
a
były jak najni˙zsze
ã Okre´slenie optymalnego terminu realizacji przedsi ˛ewzi ˛ecia – takie uło˙zenie
programu przy´spieszenia, aby najwi ˛eksza akceleracja przypadła na te
czynno´sci krytyczne, których koszty przy´spieszenia b ˛ed ˛
a najmniejsze
UWAGA!
• ka˙zde przyspieszenie wi ˛
a˙ze si ˛e ze zwi ˛ekszeniem 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
• t
n
– czas normalny czynno´sci, przy którym koszty jej wykonania K
n
s ˛
a najni˙zsze
• t
gr
– czas graniczny, najkrótszy mo˙zliwy ze wzgl ˛edów technicznych i
technologicznych czas wykonania czynno´sci przy koszcie granicznym K
gr
• K = f (t) – przebieg zale˙zno´sci kosztów wykonania czynno´sci od czasu jej trwania
• S – ´sredni gradient kosztu
S =
K
gr
− K
n
t
n
− t
gr
= tgα
Współczynnik S okre´sla przyrost kosztów wykonania czynno´sci spowo-
dowany skróceniem czasu wykonania czynno´sci o jednostk˛e
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
2
Badania operacyjne
Analiza czasowo-kosztowa
Sieci CPM-COST
Algorytm kompresji sieci
Krok 1. Zestawi´c czynno´sci krytyczne, poda´c ich gradienty kosztów S oraz kosz-
ty graniczne t
gr
Krok 2. Wyeliminowa´c z zestawienia te czynno´sci krytyczne, dla których ´sredni
gradient kosztów nie istnieje, tzn. t
n
= t
gr
Krok 3. Proces skracania rozpocz ˛
a´c od czynno´sci krytycznej o najni˙zszym gra-
diencie kosztów S
Krok 4. Przy skracaniu czasu trwania czynno´sci nale˙zy stara´c si ˛e skróci´c jej
czas o jak najwi ˛eksz ˛
a liczb ˛e jednostek. W tym kroku algorytmu wyst ˛e-
puj ˛
a dwa ograniczenia:
a) czas graniczny danej czynno´sci
b) pojawienie si ˛e nowej ´scie˙zki krytycznej
Nowa ´scie˙zka pojawi si ˛e wtedy, gdy zaniknie zapas czasu w ci ˛
agu czyn-
no´sci 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 ˛ecej ´scie˙zek krytycznych w sieci nale˙zy skra-
ca´c czas o t ˛
a sam ˛
a wielko´s´c na wszystkich równoległych ´scie˙zkach kry-
tycznych
Krok 6. Najkrótszy termin wykonania programu sieciowego uzyskuje si ˛e, gdy
wszystkie czynno´sci le˙z ˛
ace na którejkolwiek ´scie˙zce krytycznej osi ˛
agaj ˛
a
czasy graniczne t
gr
. Dalsze skracanie czasu wykonania przedsi ˛ewzi ˛ecia
jest niemo˙zliwe
Krok 7. Koszty przyspieszenia oblicza si ˛e mno˙z ˛
ac liczby jednostek czasu (dni),
o które dana czynno´s´c 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 ˛ewzi ˛ecia polega na
:
• wyodr ˛ebnieniu i zestawieniu wchodz ˛
acych w jego skład czynno´sci
• ocenie parametrów poszczególnych czynno´sci i zdarze ´n
• konstrukcji sieci zale˙zno´sci technologicznych
• wyznaczeniu podstawowych charakterystyk sieci dotycz ˛
acych
poszczególnych czynno´sci, zdarze ´n i całego projektu
• wyznaczeniu ´scie˙zki krytycznej
Powy˙zszy 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 ˛
ac dane charakteryzuj ˛
ace przedsi ˛ewzi ˛ecie P (tabela) dokona´c skrócenia
całkowitego czasu wykonania programu tak, aby koszt przyspieszenia terminu
uko ´nczenia przedsi ˛ewzi ˛ecia był jak najmniejszy
(i, j)
t
n
t
gr
K
n
K
gr
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
1
0
0
4 10
10
2
8
17
3
14
23
5
25
25
6
35
35
0
9
9
0
0
0
10
15
10
(0)
(0)
(0)
8 (9)
6 (9)
12 (9)
• ´scie˙zka krytyczna: 1 − 4 − 5 − 6
• termin wykonania przedsi ˛ewzi ˛ecia: 35 dni
• zapas na ci ˛
agu czynno´sci 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´s´c o najmniejszym współczynniku wzrostu kosztów – (1, 4)
• Czas trwania tej czynno´sci mo˙zna skróci´c do 5 dni
• Czas realizacji przedsi ˛ewzi ˛ecia zostaje skrócony do 30 dni
• Wzrost kosztów: K
1
= S · ∆t = 10 · (10 − 5) = 50
1
0
0
4 5
5
2
8
12
3
14
18
5
20
20
6
30
30
5
15
10
(0)
(0)
(0)
8 (4)
6 (4)
12 (4)
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
8
Badania operacyjne
Analiza czasowo-kosztowa
Sieci CPM-COST
2. Kolejna czynno´s´c o najmniejszym współczynniku wzrostu kosztów – (5, 6)
• Czas trwania tej czynno´sci mo˙zna skróci´c do 2 dni
• Ograniczeniem jest całkowity zapas ci ˛
agu czynno´sci 1 − 2 − 3 − 6 (4 dni)
• Czynno´s´c (5, 6) mo˙zna zatem skróci´c do 6 dni
• Czas realizacji przedsi ˛ewzi ˛ecia skrócony zostaje do 26 dni
• Wzrost kosztów – K
2
= S · ∆t = 20 · (10 − 6) = 20 · 4 = 80
1
0
0
4 5
5
2
8
8
3
14
14
5
20
20
6
26
26
5
15
6
(0)
(0)
(0)
8 (0)
6 (0)
12 (0)
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
9
Badania operacyjne
Analiza czasowo-kosztowa
Sieci CPM-COST
• ´scie˙zki krytyczne: 1 − 2 − 3 − 6 i 1 − 4 − 5 − 6
• czas realizacji przedsi ˛ewzi ˛ecia: 26 dni
• dalsza kompresja sieci jest mo˙zliwa
3. Ko ´nczymy skracanie czynno´sci (5, 6)
• czas trwania czynno´sci mo˙zna skróci´c do 2 dni
• czas realizacji przedsi ˛ewzi ˛ecia skraca si ˛e do 22 dni
• jednocze´snie nale˙zy na drugiej ´scie˙zce dokona´c skrócenia tak˙ze o 4 dni
• czynno´s´c (3, 6) skraca si ˛e do 10 dni – za mało!
• dodatkowo czynno´s´c (2, 3) skraca si ˛e o 2 dni
• osi ˛
agni ˛eto bilans na obu ´scie˙zkach
• koszty zwi ˛
azane z tymi czynno´sciami s ˛
a nast ˛epuj ˛
ace:
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
K
3
= 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˙zliwe, gdy˙z wszystkie czynno´sci le˙z ˛
ace na ´scie˙zce
krytycznej 1 − 4 − 5 − 6 osi ˛
agn ˛eły warto´sci krytyczne
5. Ko ´ncowa sie´c czynno´sci
1
0
0
4 5
5
2
8
8
3
12
12
5
20
20
6
22
22
5
15
2
(0)
(0)
(0)
8 (0)
4 (0)
10 (0)
czas trwania przedsi ˛ewzi ˛ecia – 22 dni
koszt zwi ˛
azany ze skróceniem czasu wykonania przedsi ˛ewzi ˛ecia
K = K
1
+ K
2
+ K
3
= 50 + 80 + 220 = 350
Instytut Sterowania i Systemów Informatycznych
Uniwersytet Zielonogórski
11