A. Ogólne sformułowanie problemu

Programowanie sieciowe to zestaw technik planowania przedsięwzięć zapewniający

sprawny przebieg ich wykonania. Przedsięwzięcie to zorganizowane działania, mające swój
początek i zmierzające do określonego celu w skończonym czasie. Działania te mają
wyróżniony początek i koniec, korzystają ze skończonej ilości zasobów osobowych,
rzeczowych, finansowych i informacyjnych.

Na przedsięwzięcie składa się ciąg czynności wzajemnie ze sobą powiązanych.

Czynność to dowolnie wyodrębniona część przedsięwzięcia, która charakteryzuje się czasem
trwania i zużywaniem zasobów. Niektóre z tych czynności muszą być wykonywane w ściśle
określonej kolejności, niektóre mogę być wykonywane równolegle.

W trakcie realizacji przedsięwzięcia wyróżnia się zdarzenia. Zdarzenie to osiągnięcie

określonego stanu zaawansowania prac (celu cząstkowego). Pierwszym sformalizowanym
przedstawieniem planu przedsięwzięcia był opracowany w 1917 roku wykres Gantta.
Znacznie bardziej zaawansowanym podejściem pozwalającym na prezentację zależności
pomiędzy zdarzeniami i czynnościami są opracowane w 1958 (w firmie DuPont) modele
sieciowe.

Wykres Gantta obrazuje rozłożenie w czasie i następstwo czynności, a także osoby

zaangażowane w daną czynność.

Sporządzenie wykresu Gantta planowanego przedsięwzięcia wymaga wykonania

kolejno następujących kroków:

rozłożenie przedsięwzięcia na czynności,

ustalenie czasu trwania przedsięwzięcia i określenie czasów poszczególnych czynności,

ustalenie kolejności realizacji czynności oraz wyznaczenie terminów ich rozpoczęcia i

zakończenia,

określenie miejsca, w którym czynności te mają być zrealizowane,

określenie osób, zaangażowanych w te czynności ,

wyrażenie w postaci graficznej wszystkich wyróżnionych czynności.

Struktura logiczna modelu sieciowego jest wyznaczona przez zależności pomiędzy

zdarzeniami i czynnościami.

W trakcie rozwoju metod programowania sieciowego wypracowano dwa podstawowe

typy struktur logicznych modeli sieciowych:

zdeterminowaną (DAN - Deterministic Analysis Network), jeśli w trakcie realizacji

przedsięwzięcia wszystkie czynności przedstawione w sieci będą zrealizowane

CPM (Critical Path Method) - zakłada, że czas trwania czynności jest określony

jednoznacznie

PERT (Programm Evaluation and Review Technique) - uwzględnia losowość w czasie

trwania czynności

stochastyczną (GAN - Generalized Analysis Network), jeśli czynnościom przypisane są

prawdopodobieństwa i w trakcie realizacji przedsięwzięcia biorą udział tylko niektóre z nich.

1

2

3

4

5

t

12

t

13

t

34

t

24

t

45

Przygotowanie modelu sieciowego planowanego przedsięwzięcia wymaga wykonania

kolejno następujących kroków:

1. Lista czynności.

W pierwszej kolejności należy przygotować listę czynności, z

których składa się przedsięwzięcie, należy ustalić zależności pomiędzy nimi (kolejność
wykonywania) oraz ich czasy ich trwania.

2. Wykres sieciowy.

Następnie przedsięwzięcie przedstawia się w postaci wykresu

sieciowego, obrazującego zależności pomiędzy czynnościami i zdarzeniami. Z przyczyn
formalnych wprowadza się czynności pozorne - nie zużywające czasu ani zasobów, ich
zadaniem jest przedstawienie sekwencji zdarzeń.

czynność

t

c

- czas trwania

id - oznaczenie czynności

czynność pozorna

zdarzenie

id - oznaczenie zdarzenia

t

-

najwcześniejszy możliwy moment zaistnienia zdarzenia

T - najpóźniejszy dopuszczalny moment zaistnienia zdarzenia

Z - zapas czasu

Przy konstruowaniu sieci należy kierować następującymi zasadami:

1. musi istnieć dokładnie jedno zdarzenie początkowe i jedno zdarzenia końcowe

2. zdarzenia i czynności muszą być uporządkowane - zdarzenie wcześniejsze

musi mieć mniejszy numer

3. dwa zdarzenia mogą być połączone tylko jedną czynnością

4. łuki przedstawiające czynności nie mogą się przecinać.

3. Wyznaczanie charakterystyk sieci.

Dla wszystkich zdarzeń zostają wyliczone

najwcześniejsze możliwe momenty zaistnienia, najpóźniejsze dopuszczalne momenty
zaistnienia oraz zapasy czasu.

4. Wyznaczanie ścieżki krytycznej.

Określa się najwcześniejszy możliwy termin

ukończenia przedsięwzięcia.

id

t

c

Z

id

t

T

B. Przykład.

Zaplanować przygotowania do rodzinnego wyjazdu własnym samochodem na narty w

Alpy. Zaangażowane osoby (zasoby): mama (M), tata (T), syn (S), córka (C). Przedstawić
plan wyjazdu za pomocą wykresu Gantta oraz wyznaczyć charakterystyki modelu sieciowego
metodą CPM.

Id
czynności

Czynność

Osoby

Czynności
poprzedzające

Czas trwania
[dni]

a

Wybór miejsca

M T S C

2

b

Dokonanie rezerwacji

T

a

2

c

Wysłanie zaliczki

T

b

1

d

Zakup map i przewodników

M

a

1

e

Przegląd sprzętu i serwis

T S C

3

f

Przegląd samochodu

T

2

g

Zakup winietek na autostrady

M

a

1

h

Ustalenie listy zakupów

M T S C a

1

i

Zakupy na wyjazd

M

h

0.5

j

Założenie bagażnika na narty

T

f

0.2

k

Pakowanie rzeczy

M C

d i j

0.2

l

Pakowanie nart

T S

e j

0.2

m

Naklejenie winietek

M

g

0.1

n

Wyjeżdżamy

M T S C c k l m

1

C. Rozwiązanie.

Przedstawienie planu tego przedsięwzięcia za pomocą wykresu Gantta wymaga

dodatkowo uprzedniego zaplanowania czasów rozpoczęcia poszczególnych czynności.
Poniżej przedstawiono wykres Gantta wygenerowany za pomocą kreatora wykresów MS
EXCEL

Czynno

ść

Pocz

ą

tek

a

2008-02-21

b

2008-02-23

c

2008-02-25

d

2008-03-01

e

2008-03-02

f

2008-03-03

g

2008-03-05

h

2008-03-05

i

2008-03-06

j

2008-03-07

k

2008-03-07

l

2008-03-07

m

2008-03-07

n

2008-03-08

2008-02-20

2008-02-27

2008-03-05

Wybór miejsca

Dokonanie rezerwacji

Wysłanie zaliczki

Zakup map i przewodników

Przegl

ą

d sprz

ę

tu i serwis

Przegl

ą

d samochodu

Zakup winietek na autostrady

Ustalenie listy zakupów

Zakupy na wyjazd

Zało

ż

enie baga

ż

nika na narty

Pakowanie rzeczy

Pakowanie nart

Naklejenie winietek

Wyje

ż

d

ż

amy

Poniżej

przedstawiono

model

sieciowy

planowanego

przedsięwzięcia

z

charakterystykami opracowanymi za pomocą metody CPM.

W analizowanym za pomocą metody CPM modelu każdej czynności przypisuje się

ustalony czasu jej trwania. Kolejne etapy analizy polegają na:

1. Dla każdego zdarzenia oblicza się najwcześniejszy możliwy moment zaistnienia (t).

Zdarzeniu początkowemu przypisuje się t

0

= 0. Dla kolejnych zdarzeń

najwcześniejszy możliwy moment zaistnienia jest sumą czasu trwania prowadzącej do
niego czynności oraz najwcześniejszego możliwego momentu zaistnienia zdarzenia
poprzedniego. Przy kilku czynnościach wybiera się wielkość maksymalną:

t

j

= max

i

{t

i

+ t

i

→

j

}

2. Dla każdego zdarzenia, poczynając od zdarzenia końcowego oblicza się

najpóźniejszy dopuszczalny moment zaistnienia zdarzenia. Dla zdarzenia
końcowego przyjmuje się T

k

= t

k

. Dla poprzednich zdarzeń najpóźniejszy

dopuszczalny moment zaistnienia zdarzenia jest równy różnicy najpóźniejszego
dopuszczalnego momentu zaistnienia zdarzenia następnego i czasu trwania
prowadzącej do niego czynności. Przy kilku czynnościach wybiera się wielkość
minimalną:

T

i

= min

j

{T

j

- t

i

→

j

}

3. Dla każdego zdarzenia wylicza się zapas czasu jako różnicę najpóźniejszego

dopuszczalnego momentu zaistnienia i najwcześniejszego możliwego momentu
zaistnienia zdarzenia:

Z

i

= T

i

- t

i

4. Dla każdej czynności wylicza się zapas czasu: Z

i

→

j

= (T

j

- t

i

→

j

) - t

i

5. Wyznaczenie ścieżki krytycznej: wybranie ciągu zdarzeń i czynności od zdarzenia

początkowego do zdarzenia końcowego, którego czas wykonania jest najdłuższy.
Czynności i zdarzenia leżące na ścieżce krytycznej mają zerowe zapasy czasu.

0

0

0

0

0

1

2

2

a

2

b

0

2

4

4

2

c

1

g

1

1,9

3

3

4,9

0

9

5

5

1,3

7

3,5

4,8

0

10

6

6

1,3

4

3

4,3

1,8

8

3

4,8

e

3

d

1

h

1

2,6

5

2

4,6

f

2

i

0,5

j

0,2

k

2,6

6

2,2

4,8

l

n

m

0,2

0,2

1

0,1

W odróżnieniu od metody CPM, gdzie czasy trwania czynności były ustalone

jednoznacznie metoda PERT zakłada losowość parametrów opisujących czynności. Czasy
trwania poszczególnych czynności są zmiennymi losowymi: każdej czynności przypisuje się
trzy oceny czasu jej trwania:

t

o

czas optymistyczny (czas trwania przy najbardziej sprzyjających warunkach)

t

p

czas pesymistyczny (czas trwania przy najmniej sprzyjających warunkach)

t

m

czas najbardziej prawdopodobny (typowy dla tej czynności)

Te trzy wartości wyznaczają czas oczekiwany trwania czynności:

6

4t

t

t

m

p

o

+

+

=

c

t

oraz wariancję czasu oczekiwanego:

2

o

p

2

6

t

-

t













=

σ

Posługując się czasami oczekiwanymi (t

c

) dla poszczególnych czynności wyznacza się

charakterystyki modelu sieciowego według takich samych reguł jak dla metody CPM, wśród
nich termin oczekiwany realizacji całego przedsięwzięcia (T

r

). Ten termin jest wielkością

losową, a jego wariancja (

2

T

σ

) jest sumą wariancji czynności na ścieżce krytycznej.

Spodziewana wielkość odchylenia od wyliczonego terminu (T

r

) jest zatem równa

pierwiastkowi z tej wariancji.

Zakładając, że zmienna losowa, jaką jest termin realizacji całego przedsięwzięcia

podlega rozkładowi normalnemu N(T

r

,

σ

T

) można obliczyć prawdopodobieństwo

zakończenia przedsięwzięcia w pewnym zadanym czasie t

x

.

(

)













−

=













−

≤

=













−

≤

−

=

≤

σ

σ

σ

σ

r

x

r

x

r

x

r

x

T

t

F

T

t

x

P

T

t

T

t

P

t

t

P

D. Przebieg ćwiczenia.

1. Sporządzić wykres Gantta za pomocą MS EXCEL

2. Przygotować plan przedsięwzięcia za pomocą GanttProject 2.0

3. Wskazać w przygotowanym planie ścieżkę krytyczną.

Program GanttProject 2.0 można pobrać ze strony

http://ganttproject.org/