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.
t24
2
t12
4
5
1
t45
t13
t34
3
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.
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ść
tc
id
tc - czas trwania
id - oznaczenie czynności
czynność pozorna
zdarzenie
id
t
T
Z
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.
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ść
Osoby
Czynności
Czas trwania
czynności
poprzedzające
[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
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
Wybór miejsca
a
2008-02-21
Dokonanie rezerwacji
b
2008-02-23
Wysłanie zaliczki
c
2008-02-25
Zakup map i przewodników
d
2008-03-01
Przegląd sprzętu i serwis
e
2008-03-02
Przegląd samochodu
f
2008-03-03
Zakup winietek na autostrady
g
2008-03-05
Ustalenie listy zakupów
h
2008-03-05
Zakupy na wyjazd
Zało
i
2008-03-06
Ŝenie bagaŜnika na narty
Pakowanie rzeczy
j
2008-03-07
Pakowanie nart
k
2008-03-07
Naklejenie winietek
l
2008-03-07
WyjeŜdŜamy
m
2008-03-07
2008-02-20
2008-02-27
2008-03-05
n
2008-03-08
przedstawiono
model
sieciowy
planowanego
przedsięwzięcia
z
charakterystykami opracowanymi za pomocą metody CPM.
2
4
4
0
c
1
b 2
3
g
3
4,9
1
1,9
1
m
2
2
0
0,1
d
a
1
h
2
1
9
10
n
5
5
6
6
0
0
0
4
1
k
0
0
3
4,3
i
7
0
1,3
f
3,5 4,8
0,2
0,5
1,3
2
5
2
4,6
j
6
2,6
2,2 4,8
0,2
2,6
l
8
0,2
3
4,8
e
1,8
3
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ę t0 = 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ą: tj = maxi {ti + ti→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ę Tk = tk. 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ą:
Ti = minj {Tj - ti→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:
Zi = Ti - ti
4. Dla kaŜdej czynności wylicza się zapas czasu: Zi→j = (Tj - ti→j) - ti 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.
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:
to czas optymistyczny (czas trwania przy najbardziej sprzyjających warunkach)
tp czas pesymistyczny (czas trwania przy najmniej sprzyjających warunkach)
tm czas najbardziej prawdopodobny (typowy dla tej czynności) Te trzy wartości wyznaczają czas oczekiwany trwania czynności: t
+ t + 4
t
o
p
m
t
c =
6
oraz wariancję czasu oczekiwanego:
2
t -
t
2
p
o
σ =
6
Posługując się czasami oczekiwanymi (tc) 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 (Tr). Ten termin jest wielkością losową, a jego wariancja (
2
σ ) jest sumą wariancji czynności na ścieŜce krytycznej.
T
Spodziewana wielkość odchylenia od wyliczonego terminu (Tr) 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(Tr, σT) moŜna obliczyć prawdopodobieństwo zakończenia przedsięwzięcia w pewnym zadanym czasie tx.
t − T
t
T
t
T
t
T
r
x −
r
x −
r
x −
P( t ≤ t
P
P x
F
x ) =
≤
= ≤
=
r
σ
σ
σ
σ
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/