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/