Metody programowania sieciowego w
zarządzaniu przedsięwzięciami
Programowanie sieciowe stanowi
specyficzną grupę zagadnień programowania
matematycznego.
Zagadnienia sieciowe - zagadnienia,
których ilustrację graficzną można przedstawić
w formie figury płaskiej zwanej grafem. Graf
składa się z wyróżnionych punktów zwanych
węzłami grafu i odcinków łączących
określone pary węzłów, zwanych łukami
grafu. Gdy każdemu łukowi grafu jest
przyporzÄ…dkowana pewna liczba nieujemna, to
taki graf nosi miano sieci.
Przedsięwzięcie wieloczynnościowe
Każdy zespół działań, których wykonanie
realizuje określone zadanie.
Przykłady:
- remont budynku,
- produkcja filmu,
1
- budowa obwodnicy Warszawy,
- prace organizacyjne.
Własność 1: Całe przedsięwzięcie daje się
rozłożyć na elementy prostsze zwane
czynnościami. Każda czynność jest procesem
wykonywania określonej części zadania
stanowiÄ…cego wynik realizacji danego
przedsięwzięcia.
Czynność zaznacza się na wykresie w postaci
strzałek (zwanych także łukami):
Niekiedy struktura logiczna sieci wymaga
wprowadzenia czynności pozornej, która
charakteryzuje się tym, iż nie zużywa czasu
(czas trwania równy zeru) oraz środków.
Graficznym obrazem czynności pozornej jest
przerywana strzałka:
Własność 2: Każda czynność trwa przez
pewien czas t zwany czasem trwania.
2
Własność 3: Zdarzenie - określa moment
rozpoczęcia lub zakończenia co najmniej
jednej czynności wchodzącej w skład
przedsięwzięcia. Zdarzenie nie zużywa
środków, ani czasu.
Przykład:
- zapoznanie się z dokumentacją - czynność,
- gotowanie wody - czynność,
- zakończenie malowania ścian - zdarzenie,
- rozpoczęcie budowy wiaduktu - zdarzenie,
- układanie parkietu - czynność,
- obwodnica wybudowana Jð - zdarzenie.
Własność 4: Każda czynność rozpoczyna się
pewnym zdarzeniem (początek czynności) i
kończy pewnym zdarzeniem (koniec
czynności). Postulat ten można spełnić poprzez
wprowadzenie czynności pozornej.
Dla dwóch różnych czynności ta sama para
zdarzeń nie może spełniać roli początku i
końca tych czynności.
3
Czynności łączą ze sobą zdarzenia. Zdarzenia
przedstawiane sÄ… na wykresie zazwyczaj w
postaci kółek (lub innych figur
geometrycznych):
Czynności i zdarzenia umieszcza się na
wykresie w sposób logiczny, sekwencyjny i
zintegrowany, co wymaga ustalenia: jednej lub
kilku czynności, które muszą być zakończone
przed rozpoczęciem rozpatrywanej, czynności,
które mogą się zacząć po zakończeniu
rozpatrywanej, czynności, które mogą być
wykonywane równolegle z rozpatrywaną. Przy
konstrukcji sieci obowiązują pewne reguły.
Zdarzenia i czynności muszą być
odpowiednio uporzÄ…dkowane. tzn. poprzednik
ma mieć mniejszy numer lub wcześniejszą
literÄ™. Ten postulat oznacza w praktyce
niewystępowania cyklu, a zatem sytuacji, gdy
wychodząc z jednego wierzchołka (zdarzenia)
i poruszając się po krawędziach (czynności)
można do tego wierzchołka powrócić, Dwa
4
zdarzenia muszą być powiązane wyłącznie
jedna czynnością; gdy kilka czynności
wykonywanych równolegle poprzedza jedna
wprowadza się czynność pozorną. Ostatni z
wymogów to nieprzecinanie się strzałek, co
oznacza, iż czynności nie mogą się krzyżować.
Własność 5: W przedsięwzięciu musi istnieć
jedno tylko zdarzenie, które jest wyłącznie
początkiem pewnych czynności - początek
przedsięwzięcia i inne tylko jedno, które jest
wyłącznie końcem pewnych czynności -
koniec przedsięwzięcia.
Droga (ścieżka) - taki ciąg czynności
przedsięwzięcia, że początek każdej czynności
jest jednocześnie końcem czynności
poprzedniej.
Własność 6: Każda czynność (a więc i każde
zdarzenie) musi należeć do co najmniej jednej
drogi łączącej początek z końcem
przedsięwzięcia, natomiast żadne zdarzenie
nie może być początkiem i jednocześnie
końcem tej samej drogi.
5
Własność 7: Dane zdarzenie występuje w
momencie najpóz
niej kończonej czynności
spośród wszystkich, których końcem jest to
zdarzenie.
Własność 8: Żadna czynność nie może
rozpocząć się przed wystąpieniem zdarzenia,
które jest jej początkiem.
Budowa sieci
1. Ustalenie listy czynności, z których składa
się przedsięwzięcie.
2. Ustalenie zdarzenia poczÄ…tkowego i
końcowego przedsięwzięcia.
3. Określenie dla każdej czynności:
·ð jednej lub kilku czynnoÅ›ci, które
muszą być zakończone przed
rozpoczęciem rozpatrywanej,
6
·ð czynnoÅ›ci, które mogÄ… siÄ™ zacząć po
zakończeniu rozpatrywanej,
·ð czynnoÅ›ci, które mogÄ… być
wykonywane równolegle z
rozpatrywanÄ….
4. Numeracja węzłów sieci - zdarzeń.
Do najbardziej rozpowszechnionych metod
zarządzania przedsięwzięciami należą metody
programowania sieciowego CPM i PERT.
Metoda ścieżki krytycznej CPM
(ang. Critical Path Method)
Ścieżka (droga) krytyczna wyznacza
najkrótszy z możliwych czas realizacji całego
przedsięwzięcia.
Wyznaczenie ścieżki krytycznej:
1. Termin zdarzenia rozpoczynajÄ…cego
przedsięwzięcie jest równy 0.
7
2. Wyznaczenie najwcześniejszych
Tjw
terminów zdarzeń.
Wyznaczenie najwcześniejszego terminu j-
tego jest związane z warunkiem zakończenia
wszystkich czynności poprzedzających to
zdarzenie. Termin ten jest więc określony
przez najdłuższy czas przejścia od zdarzenia
poczÄ…tkowego do j - tego zdarzenia:
Tjw =ð max Tiw +ð tij
(ð )ð
iÎðP( j)
gdzie:
Tiw
- najwcześniejszy termin wystąpienia i -
tego zdarzenia,
tij - czas trwania czynności rozpoczynającej się
zdarzeniem i, a kończącej się zdarzeniem j.
P(j) - zbiór zdarzeń bezpośrednio
poprzedzajÄ…cych zdarzenie j.
8
3. Najpóz
niejszy termin wystÄ…pienia zdarzenia
kończącego przedsięwzięcie jest równy
najwcześniejszemu terminowi wystąpienia
tego zdarzenia.
4. Wyznaczenie najpóz
niejszych terminów
Tjp
zdarzeń . Najpóz
niejszy termin zdarzenia i
- tego musi być wyznaczony w ten sposób, aby
nie powodować opóz
nienia zdarzenia
końcowego.
Tjp =ð min Tip -ð tji
(ð )ð
i ÎðN( j)
gdzie:
N(j) - zbiór zdarzeń następujących po zdarzeniu
j.
5. Wyznaczenie zdarzeń krytycznych.
Zdarzenie j jest zdarzeniem krytycznym
tylko wtedy gdy:
9
Tjp =ð Tjw
Tjp Tjw
Różnica między a nosi nazwę luzu
czasowego Lj:
Lj =ð Tjp -ð Tjw
6. Zapas na czynności:
zij =ð Tjp -ð Tiw -ð tij
czynność
Przykład: Przedsiębiorstwo rozważa
przeprowadzenie akcji reklamowej. Plan
przedsięwzięcia obejmuje następujące
czynności:
10
A (1 - 2) przygotowanie wzoru ulotki
reklamowej (czas trwania  w dniach - t12 = 1)
B (2  3) wysłanie wzoru do firmy
powielajÄ…cej ulotki (t23 = 1)
C (2  4) określenie miejsc, w których ulotki
będę rozdawane mieszkańcom miasta (t24 = 2)
D (2  5) rekrutacja osób rozdających ulotki
(t25 = 6)
E (3  4) odebranie ulotek od firmy
powielajÄ…cej (t34 = 3)
F (4  6) paczkowanie ulotek (t46 = 1)
G (5  6) szkolenie osób rozdających ulotki
(t56 = 1)
H (6  7) wręczenie ulotek osobom
rozdającym ulotki i przypisanie każdej osoby
do obszaru działania (t67 = 1)
3
A 1 C 2 F 1 H 1
2 4 6 7
1
5
11
Tjw =ð max Tiw +ð tij Tjp =ð min Tip -ð tji
(ð )ð (ð )ð
p
T1w =ð 0 T1 =ð 1-ð 1 =ð 0
w P
T2 =ð 0 +ð 1 =ð 1 T2 =ð 4 -ð 1 =ð 3
P
T2 =ð 7 -ð 2 =ð 5
P
T2 =ð 7 -ð 6 =ð 1MIN
w p
T3 =ð 1+ð 1 =ð 2 T3 =ð 7 +ð 3 =ð 4
w P
T4 =ð 1+ð 2 =ð 3 T4 =ð 8 -ð 1 =ð 7
w
T4 =ð 2 +ð 3 =ð 5MAX
w P
T5 =ð 1+ð 6 =ð 7 T5 =ð 8 -ð 1 =ð 7
P
w
T6 =ð 9 -ð 1 =ð 8
T6 =ð 5 +ð 1 =ð 6
w
T6 =ð 7 +ð 1 =ð 8MAX
w P
T7 =ð 8 +ð 1 =ð 9 T7 =ð 9
12
zij =ð Tjp -ð Tiw -ð tij
Lj =ð Tjp -ð Tjw
L1 =ð 0 -ð 0 =ð 0 z12 =ð 1-ð 0 -ð1=ð 0
A
L2 =ð 1-ð1=ð 0 z23 =ð 4 -ð1-ð1=ð 2
B
L3 =ð 4 -ð 2 =ð 2 z24 =ð 7 -ð1-ð 2 =ð 4
C
L4 =ð 7 -ð 5 =ð 2 z25 =ð 7 -ð1-ð 6 =ð 0
D
L5 =ð 7 -ð 7 =ð 0 z34 =ð 7 -ð 2 -ð 3 =ð 2
E
L6 =ð 8 -ð 8 =ð 0 z46 =ð 8 -ð 5 -ð1=ð 2
F
L7 =ð 9 -ð 9 =ð 0 z56 =ð 8 -ð 7 -ð1=ð 0
G
z67 =ð 9 -ð 8 -ð1=ð 0
H
3
2 4
2
1 F 1 H 1 7
A 1 6
2 C 2 4
0 0 5 7 8 8
9 9
1 1
0 2 0
z=2 z=0 0
z=0 0 z=4
5
7 7
0
13
Jak widać ścieżka krytyczna obejmuje
czynności A (1  2), D (2  5), G (5  6) oraz
H (6  7). Luzy na zdarzeniach tworzÄ…cych
ścieżkę krytyczną są równe zero. Podobnie
zapasy na czynnościach ścieżki krytycznej
mają wartość zero. Zatem najkrótszy czas
realizacji całego przedsięwzięcia
reklamowego to 9 dni.
Zastosowanie winqsb:
File
New Problem
14
Solve and
Analyze
Solve
Critical
Path
Results
Graphic
Activity
Analysis
15
Results
Show
Critical
Path
Results Gantt Chart
16
 Załóżmy, iż projekt jest realizowany 4 dni:
Results
Project
Completion
Analysis
Zadania do rozwiÄ…zania
Zadanie 1. Na pewne przedsięwzięcie składają się czynności
podane jak poniżej wraz z czasem ich trwania:
Czas Czas Czas
Czynność Czynność Czynność
trwania trwania trwania
A 1-2 25 I 4-12 8 Q 9-14 20
B 1-3 30 J 5-8 15 R 10-14 40
17
C 1-7 50 K 6-7 6 S 11-14 6
D 2-4 12 L 6-10 27 T 12-13 10
E 2-5 12 M 6-11 19 U 12-15 60
F 3-6 19 N 7-9 20 V 13-14 12
G 3-8 18 O 7-10 30 W 14-15 50
H 4-5 6 P 8-11 20
Narysować graf. Wyznaczyć ścieżkę krytyczną oraz
najwcześniejszy termin zakończenia przedsięwzięcia. Jak
wpłynie na termin końcowy:
a) wydłużenie czasu trwania czynności T o 10 dni,
b) wydłużenie czasu trwania czynności F o 7 dni, przy
warunkach wyjściowych,
c) skrócenie czasu trwania czynności U o 1/6, przy
warunkach wyjściowych,
d) skrócenie czasu trwania czynności W o 20 %, przy
warunkach wyjściowych,
e) wydłużenie czynności P o 42 dni, przy warunkach
wyjściowych,
f) wydłużenie czynności P o 41 dni, przy warunkach
wyjściowych?
Rozwiązanie: ścieżka B-F-K-O-R-W czas trwania
przedsięwzięcia 175 dni, a) ścieżka krytyczna B-F-K-O-R-W
czas trwania przedsięwzięcia 175 dni, b) ścieżka B-F-K-R-W
czas trwania przedsięwzięcia 182 dni, c) ścieżka B-F-K-R-W
czas trwania przedsięwzięcia 175 dni, d) ścieżka B-F-K-O-R-
W czas trwania przedsięwzięcia 165 dni , e) nowa ścieżka
krytyczna A-D-H-J-P-S-W czas trwania przedsięwzięcia 176
18
dni, f) dwie ścieżki krytyczne B-F-K-O-R-W oraz A-D-H-J-
P-S-W czas trwania przedsięwzięcia 175 dni.
Zadanie 2. Narysować sieć przedsięwzięcia składającego się z
czynności od A do M wiedząc, że:
Należy wykonać
Przed czynnością: Czas trwania
czynność:
A - 8
B - 6
C - 4
D A 2
E B 4
F C 4
G C 10
H A 3
I D,E,F 5
J D,E,F 5
K H,I 3
L J,G 4
M K,L 10
Narysować graf. Obliczyć najkrótszy czas realizacji
przedsięwzięcia. Ustalić zapasy na czynnościach D,E,F.
Rozwiązanie: 2 ścieżki krytyczne A-D-J-L-M oraz B-E-J-L-
M; czas trwania przedsięwzięcia 29 dni. Zapasy na
czynnościach zD=0, zE=0, zF=2.
19