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