2014-01-10
Badania operacyjne w
logistyce
Wykład 4:
Wykład 4:
Metody sieciowego planowania przedsięwzięć
Metody sieciowego planowania przedsięwzięć
Opracowała: Izabela Dziaduch
Podział metod programowania sieciowego
Podział metod programowania sieciowego
ID,2013/2014
1
2014-01-10
Podział metod programowania sieciowego
Podział metod programowania sieciowego
Metody deterministyczne  metody o ustalonej
strukturze sieci, w której czasy trwania czynności
są stałe i znane lub mają charakter
probabilistyczny
Metody stochastyczne  metody o
niezdeterminowanej strukturze logicznej sieci, w
której czasy trwania czynności można określić
tylko z pewnym prawdopodobieństwem.
ID,2013/2014
Podstawowe pojęcia
Podstawowe pojęcia
Przedsięwzięcie
Przedsięwzięcie
Zespół połączonych ze sobą czynności
wykonywanych w celu uzyskania określonego
celu, zwykle w ramach ograniczeń: czasu,
zasobów i kosztu.
wykresu sieciowego
Modelowane jest w postaci wykresu sieciowego
(sieci zależności, sieci czynności).
graf skierowany spójny
Sieć czynności to graf skierowany spójny
acykliczny, opisany ilościowo;
acykliczny, opisany ilościowo; graf, który ma jeden
wierzchołek początkowy i jeden wierzchołek
końcowy.
ID,2013/2014
2
2014-01-10
Podstawowe pojęcia
Podstawowe pojęcia
Graf
Graf
Graf to struktura składająca się z węzłów
(wierzchołków) wzajemnie połączonych za pomocą
krawędzi (łuków).
Grafy dzielimy na grafy skierowane i nieskierowane.
Graf skierowany
Graf nieskierowany
ID,2013/2014
Podstawowe pojęcia
Podstawowe pojęcia
Spójność grafu
Spójność grafu
Graf jest spójny, jeśli każde dwa wierzchołki
można połączyć ścieżką.
Graf niespójny
Graf spójny
ID,2013/2014
3
2014-01-10
Podstawowe pojęcia
Podstawowe pojęcia
Cykl w grafie
Cykl w grafie
Cykl to do droga zamknięta, czyli taka, która
kończy się w początkowym wierzchołku drogi w
grafie.
Graf nie zawierajÄ…cy cykli nazywamy acyklicznym.
<1,2,4,3,4,1> - cykl
<1,2,3,1> - cykl
<1,2,4,1> - cykl prosty
<2,2> - pętla
ID,2013/2014
Podstawowe pojęcia
Podstawowe pojęcia
Graf ważony
Graf ważony
Graf, w którym każdej krawędzi (każdemu łukowi)
jest przyporządkowana określona wartość
liczbowa. Wartość ta niesie ze sobą określoną
informację np. o odległości, czasie, koszcie itp.
26
26
ID,2013/2014
4
2014-01-10
Podstawowe pojęcia
Podstawowe pojęcia
Sieć czynności
Sieć czynności
zdarzenia i
Elementy składowe przedsięwzięcia: zdarzenia i
czynności
czynności.
Krawędzie sieci reprezentują czynności,
wierzchołki zaś zdarzenia.
Oznaczenie Planowanie Teoria grafów
symboliczne sieciowe
czynność łuk, krawędz

zdarzenie wierzchołek
ID,2013/2014
Podstawowe pojęcia
Podstawowe pojęcia
Czynności
Czynności
OdwzorowujÄ… wykonywanie dowolnego zadania
czÄ…stkowego.
procesem trwajÄ…cym w czasie. Proces ten
SÄ… procesem trwajÄ…cym w czasie. Proces ten
"zużywa nie tylko czas, ale również środki,
"zużywa nie tylko czas, ale również środki,
pociÄ…ga koszty zwiÄ…zane z jego realizacjÄ…
pociÄ…ga koszty zwiÄ…zane z jego realizacjÄ…, itp.
Obrazem graficznym czynności jest strzałka
(łuk). Kierunek strzałki wskazuje kierunek
przebiegu czynności w czasie (kolejność ich
wykonywania):
A=19
A=19
ID,2013/2014
5
2014-01-10
Podstawowe pojęcia
Podstawowe pojęcia
Czynności pozorne (fikcyjne)
Czynności pozorne (fikcyjne)
Wprowadzane do sieci w celu zaznaczenia
kolejności występowania innych czynności.
Nie zużywają czasu (ich czas trwania jest równy
zeru) ani środków.
Obrazem graficznym czynności pozornej jest
strzałka przerywana:
ID,2013/2014
Podstawowe pojęcia
Podstawowe pojęcia
Czynności  cd.
Czynności  cd.
Czynność charakteryzuje para wskaz
ników i-j,
gdzie i jest numerem zdarzenia, w którym
czynność się rozpoczyna, a j  numerem
zdarzenia w którym czynność się kończy.
Ciąg czynności
Ciąg czynności to kolejno, następujące po sobie
czynności, dla których zdarzenie końcowe pewnej
czynności jest jednocześnie zdarzeniem
początkowym dla czynności następnej.
ID,2013/2014
6
2014-01-10
Podstawowe pojęcia
Podstawowe pojęcia
Zdarzenie
Zdarzenie
Osiągnięcie stanu zaawansowania pracy przy
realizacji projektu.
Moment rozpoczęcia lub zakończenia (jednej lub
więcej) czynności.
Nie pochłania żadnych kosztów i nie jest rozłożone
w czasie.
Zdarzenia przedstawia siÄ™ graficznie za pomocÄ…
figur geometrycznych np. kół, prostokątów.
ID,2013/2014
Podstawowe pojęcia
Podstawowe pojęcia
Zdarzenie - cd.
Zdarzenie - cd.
Każde ze zdarzeń ma w sieci swoją etykietę 
numer
numer. Numeracja zdarzeń powinna być
 rosnąca , tj. że dla każdej czynności
rozpoczynajÄ…cej siÄ™ w zdarzeniu o numerze i a
kończącym w zdarzeniu o numerze j zachodzi iZdarzenie zaszło jeżeli zakończone zostały
Zdarzenie zaszło
wszystkie czynności, dla których to zdarzenie jest
zdarzeniem końcowym.
ID,2013/2014
7
2014-01-10
Podstawowe pojęcia
Podstawowe pojęcia
Zdarzenie - cd.
Zdarzenie - cd.
Zdarzenie poczÄ…tkowe -
Zdarzenie początkowe zdarzenie, które nie jest
końcem żadnej czynności.
Zdarzenie końcowe
Zdarzenie końcowe - zdarzenie, które nie jest
początkiem żadnej czynności.
W modelu sieciowym występuje jeden wierzchołek
jeden wierzchołek
(zdarzenie) początkowy i jeden wierzchołek
(zdarzenie) początkowy i jeden wierzchołek
końcowy.
końcowy.
ID,2013/2014
Zasady konstruowania sieci czynności
Zasady konstruowania sieci czynności
Zdarzenie początkowe nie ma czynności
poprzedzajÄ…cych
Zdarzenie końcowe nie ma czynności
następujących po nich
ID,2013/2014
8
2014-01-10
Zasady konstruowania sieci czynności
Zasady konstruowania sieci czynności
Wykres sieciowy może kilka końcowych zdarzeń i
wówczas łączy się je czynnościami pozornymi w
jedno zdarzenie końcowe.
ID,2013/2014
Zasady konstruowania sieci czynności
Zasady konstruowania sieci czynności
Dane zdarzenie nie może nastąpić, dopóki nie
zakończą się wszystkie czynności prowadzące do
niego i warunkujące zajście tego zdarzenia.
Żadna kolejna czynność nie może się rozpocząć,
dopóki nie zaistnieje zdarzenie kończące czynności
poprzedzajÄ…ce.
Wektory (łuki) czynności powinny być skierowane z
lewej strony do prawej
ID,2013/2014
9
2014-01-10
Zasady konstruowania sieci czynności
Zasady konstruowania sieci czynności
Wykres sieciowy nie
może mieć obiegów
zamkniętych (cyklu), tj.
pętli łączących
dwukrotnie te same
zdarzenia.
Strzałki obrazujące
czynności nie mogą się
przecinać.
ID,2013/2014
Zasady konstruowania sieci czynności
Zasady konstruowania sieci czynności
Dwa zdarzenia mogą być połączone tylko jedną
czynnością. Jeżeli kilka czynności wykonywanych
jest równolegle pomiędzy dwoma zdarzeniami to
należy wprowadzić czynności pozorne.
ID,2013/2014
10
2014-01-10
Zasady konstruowania sieci czynności
Zasady konstruowania sieci czynności
Zdarzenia i czynności powinny być odpowiednio
uporządkowane, tzn. każdy poprzednik ma mieć
mniejszy numer lub wcześniejszą literę od
następnika (zatem numerując zdarzenia należy
zwracać uwagę na to, by zdarzenie wcześniejsze
miało mniejszy numer i < j). Wymóg ten wyklucza
wystÄ…pienie cyklu (tzn. sytuacji, gdy wychodzÄ…c z
jednego wierzchołka i poruszając się po
krawędziach, można do tego samego wierzchołka
wrócić).
ID,2013/2014
Etapy tworzenia wykresu sieciowego
Etapy tworzenia wykresu sieciowego
1. Ustalenie listy czynności wchodzących w skład
przedsięwzięcia,
2. Ustalenie zdarzenia początkowego i końcowego
przedsięwzięcia,
3. Określenie kolejności wykonywania czynności.
4. Numeracja węzłów w sieci.
ID,2013/2014
11
2014-01-10
Przykład 1
Przykład 1
Firma produkująca sprzęt RTV zamierza
urządzić wystawę w celu wypromowania firmy
na rynku.
ID,2013/2014
Przykład 1
Przykład 1
1. Ustalenie listy czynności
1. Ustalenie listy czynności
A 
A  wybór lokalizacji wystawy,
B 
B  przygotowanie eksponatów,
C 
C  przygotowanie terenu wystawy,
D 
D  przygotowanie stoisk,
E 
E  dostawa eksponatów,
F 
F  przygotowanie obsługi stoisk (ustalenie składu
osobowego i szkolenie),
G 
G  urzÄ…dzenie stoisk wystawowych,
H 
H  otwarcie wystawy.
ID,2013/2014
12
2014-01-10
Przykład 1
Przykład 1
2. Ustalenie zdarzenia początkowego i końcowego
2. Ustalenie zdarzenia początkowego i końcowego
przedsięwzięcia
przedsięwzięcia
Zdarzeniem poczÄ…tkowym jest &
 podjęcie decyzji o urządzeniu wystawy ,
a zdarzeniem końcowym &
 otwarcie wystawy .
ID,2013/2014
Przykład 1
Przykład 1
3. Określenie kolejności wykonywania czynności
3. Określenie kolejności wykonywania czynności
Dla każdej czynności należy ustalić:
czynności poprzedzające
czynności poprzedzające, czyli te, które
powinny być zakończone przed rozpoczęciem
danej czynności;
czynności równoległe
czynności równoległe, tzn. te, które mogą być
wykonywane jednocześnie z czynnością
rozpatrywanÄ…;
czynności następujące
czynności następujące, tzn. te, które powinny
się rozpocząć po zakończeniu rozpatrywanej
czynności.
ID,2013/2014
13
2014-01-10
Przykład 1
Przykład 1
3. Określenie kolejności wykonywania czynności
3. Określenie kolejności wykonywania czynności
Czynności bezpośrednio:
Czynności
A 
A  wybór lokalizacji wystawy
poprzedzające następujące
B 
B  przygotowanie
eksponatów
A - C, F
C 
C  przygotowanie terenu
B - E
wystawy
C A D
D 
D  przygotowanie stoisk
D C G
E 
E  dostawa eksponatów
E B G
F 
F  przygotowanie obsługi
F A H
stoisk
G E, D H
G 
G  urzÄ…dzenie stoisk
H F, G -
wystawowych
H 
H  otwarcie wystawy
ID,2013/2014
Przykład 1
Przykład 1
Sieć czynności
Sieć czynności
E
B D
G
A C
H
F
ID,2013/2014
14
2014-01-10
Przykład 1
Przykład 1
4. Numeracja węzłów w sieci
4. Numeracja węzłów w sieci
Zdarzenia i czynności powinny być odpowiednio
uporządkowane, tzn. każdy poprzednik ma mieć
mniejszy numer lub wcześniejszą literę od
następnika (zatem numerując zdarzenia należy
zwracać uwagę na to, by zdarzenie wcześniejsze
miało mniejszy numer i < j). Wymóg ten wyklucza
wystÄ…pienie cyklu (tzn. sytuacji, gdy wychodzÄ…c z
jednego wierzchołka i poruszając się po
krawędziach, można do tego samego wierzchołka
wrócić).
ID,2013/2014
Przykład 1
Przykład 1
4. Numeracja węzłów w sieci
4. Numeracja węzłów w sieci
E 5
3
B D
1
G
4
A C
7
2 H
F
6
ID,2013/2014
15
2014-01-10
Przykład 2
Przykład 2
Firma X planuje wprowadzenie nowego
produktu na rynek. Przedsięwzięcie składa
się z czynności dotyczących sfery
projektowania produkcji, jak również działań
zwiÄ…zanych z badaniem rynku.
ID,2013/2014
Przykład 2
Przykład 2
1. Ustalenie listy czynności
1. Ustalenie listy czynności
A -
A - Nabycie surowców na prototypy
B -
B - Produkcja prototypów i ich ocena
C -
C - Badanie rynku
D -
D - Analiza kosztów (bez pakowania)
E -
E - Decyzje o podjęciu produkcji
F -
F - Nabycie surowców do produkcji
G -
G - Produkcja
H -
H - Wybór opakowania
I -
I - Nabycie opakowań
J -
J - Pakowanie
K -
K - Reklama i zbieranie zamówień
L -
L - Wysyłka do sklepów
ID,2013/2014
16
2014-01-10
Przykład 2
Przykład 2
2. Ustalenie zdarzenia początkowego i końcowego
2. Ustalenie zdarzenia początkowego i końcowego
przedsięwzięcia
przedsięwzięcia
Zdarzeniem poczÄ…tkowym jest &
 pojawienie się pomysłu na nowy wyrób ,
a zdarzeniem końcowym
&  dystrybucja wyrobów .
ID,2013/2014
Przykład 2
Przykład 2
3. Określenie kolejności wykonywania czynności
3. Określenie kolejności wykonywania czynności
Czynności bezpośrednio:
Czynności
poprzedzające następujące
A -
A - Nabycie surowców na prototypy
A - B
B -
B - Produkcja prototypów i ich ocena
B A D,H
C -
C - Badanie rynku
C - D,H
D -
D - Analiza kosztów produkcji
D B,C E
E -
E - Decyzje o podjęciu produkcji
E D F,I,K
F -
F - Nabycie surowców do produkcji
F E G
G -
G - Produkcja
G F J
H -
H - Wybór opakowania
H B,C I
I -
I - Nabycie opakowań
I H,E J
J 
J  Pakowanie
J G,I L
K -
K - Reklama i zbieranie zamówień
K E L
L -
L - Wysyłka do sklepów
L J,K -
ID,2013/2014
17
2014-01-10
Przykład 2
Przykład 2
Sieć czynności
Sieć czynności
I
A
J
G
B
L
H
C K
F
E
D
ID,2013/2014
Przykład 2
Przykład 2
4. Numeracja węzłów w sieci
4. Numeracja węzłów w sieci
8
2
I
A
J
G
1 7
B
L
H
6 9 10
C K
F
E
D
3
4 5
ID,2013/2014
18
2014-01-10
Metoda CPM - ścieżki krytycznej
(z ang. Critical Path Method)
ID,2013/2014
Metoda CPM
Metoda CPM
Informacje ogólne
Informacje ogólne
Deterministyczna analiza czasowa przedsięwzięcia
Metoda ta pozwala na wyznaczenie
najwcześniejszego możliwego terminu
zakończenia przedsięwzięcia, gdy znane są czasy
czasy
trwania oraz relacje kolejności wykonania
trwania relacje kolejności wykonania
poszczególnych zadań wchodzących w skład tego
poszczególnych zadań
przedsięwzięcia. Relacje kolejności najczęściej są
odwzorowywane przy pomocy sieci powiązań lub
poprzez określenie poprzedników (następników)
dla każdego zadania.
ID,2013/2014
19
2014-01-10
Metoda CPM
Metoda CPM
Interpretacja sieciowa terminów
Interpretacja sieciowa terminów
i j
tij
ti Ti tj Tj
Li Lj
gdzie:
i - numer zdarzenia (i=1,2,& )
j - numer zdarzenia (j=2,3& )
ti - najwcześniejszy możliwy moment zaistnienia zdarzenia i
tj - najwcześniejszy możliwy moment zaistnienia zdarzenia j
Ti - najpóz
niejszy dopuszczalny moment zaistnienia zdarzenia i
Tj  najpóz
niejszy dopuszczalny moment zaistnienia zdarzenia j
Li - zapas czasu dla zdarzenia i
Lj - zapas czasu dla zdarzenia j
 czynność o zdarzeniu początkowym i oraz końcowym j
tij  czas trwania czynności
ID,2013/2014
Metoda CPM
Metoda CPM
1 2
11
0 11
Etapy analizy
Etapy analizy
t2 = 0+11=11
Etap 1. Wyznaczanie najwcześniejszych możliwych
Etap 1. Wyznaczanie najwcześniejszych możliwych
momentów zaistnienia zdarzeń (t)
momentów zaistnienia zdarzeń (t)
t1 = 0
dla zdarzenia poczÄ…tkowego
j = 2 ,3 ,... n
t = ti + tij
dla zdarzenia następnego (j)
j
w przypadku, gdy do zdarzenia dochodzi więcej niż jedna
czynność, najwcześniejszy możliwy moment zaistnienia
tego zdarzenia jest równy maksymalnej z tak obliczonych
wielkości, czyli:
t = max{ti + tij}
j
i:i< j
n
t = ti
Dla zdarzenia końcowego
n "
i =1
ID,2013/2014
20
2014-01-10
11
Metoda CPM
Metoda CPM 1 2
0 11
5 16
T1 =16-11= 5
Etapy analizy
Etapy analizy
Wyznaczanie najpóz
niejszych dopuszczalnych
Etap 2. Wyznaczanie najpóz
niejszych dopuszczalnych
momentów zaistnienia zdarzeń (T)
momentów zaistnienia zdarzeń (T)
T
dla zdarzenia końcowego n =tn
j = n
Ti = Tj - tij - 1, n - 2,...1
dla zdarzenia poprzedniego (i)
w przypadku gdy do zdarzenia dochodzi więcej niż jedna
czynność, wybieramy wielkość najmniejszą, czyli
Ti = min{Tj - tij}
j:i< j
UWAGA:
Najwcześniejszy i najpóz
niejszy termin zdarzenia końcowego
są sobie równe, gdyż zdarzenie to nie ma następników
ID,2013/2014
Metoda CPM
Metoda CPM
Etapy analizy
Etapy analizy
Wyznaczanie luzów (zapasów) czasowych dla
Etap 3. Wyznaczanie luzów (zapasów) czasowych dla
zdarzeń (L)
zdarzeń (L)
Li = Ti - ti Lj = Tj - t
j
11
1 2
0 11
5 16
L1 = 5-0 = 5
5 5
L2 =16-11= 5
UWAGA:
Luz czasowy zdarzenia wskazuje, o ile jednostek czasu można opóz
nić termin
zaistnienia danego zdarzenia bez wpływu na termin zakończenia realizacji projektu
ID,2013/2014
21
2014-01-10
Metoda CPM
Metoda CPM
Etapy analizy
Etapy analizy
Etap 4. Wyznaczanie zapasów czasu dla czynności
Etap 4. Wyznaczanie zapasów czasu dla czynności
zapas całkowity
zcij = Tj - ti - tij
11
1 2
0 11
5 16
z12 =16-0-11= 5
5 5
UWAGA:
Zapas czasu dla czynności stanowi rezerwę czasu, który może być
wykorzystany dodatkowo na wykonanie danej czynności, bez wpływu
na termin realizacji projektu.
ID,2013/2014
Metoda CPM
Metoda CPM
Etapy analizy
Etapy analizy
Wyznaczanie zapasów czasu dla czynności
Etap 4. Wyznaczanie zapasów czasu dla czynności
zapas swobodny
zsij = t -ti -tij
j
11
1 2
0 11
5 16
5 5
z12 =11-0-11= 0
UWAGA:
Wykorzystanie tego zapasu nie ma wpływu na zapasy związane z
czynnościami należącymi do danej ścieżki.
ID,2013/2014
22
2014-01-10
Metoda CPM
Metoda CPM
Etapy analizy
Etapy analizy
Wyznaczanie zapasów czasu dla czynności
Etap 4. Wyznaczanie zapasów czasu dla czynności
zapas warunkowy
zwij = Tj -Ti - tij
11
1 2
0 11
5 16
5 5
z12 =16-5-11= 0
UWAGA:
Ta rezerwa czasu może być wykorzystana bez zmniejszenia zapasów
poprzednich, określonych dla danej ścieżki.
ID,2013/2014
Metoda CPM
Metoda CPM
Etapy analizy
Etapy analizy
Wyznaczenie harmonogramu przedsięwzięcia
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia
Najwcześniejszy możliwy termin rozpoczęcia czynności
NWRij = ti
Najpóz
niejszy dopuszczalny termin rozpoczęcia czynności
NPRij = Tj - tij
Najwcześniejszy możliwy termin zakończenia czynności
NWZij = ti + tij
Najpóz
niejszy dopuszczalny termin zakończenia czynności
NPZij = Tj
ID,2013/2014
23
2014-01-10
Metoda CPM
Metoda CPM
Etapy analizy
Etapy analizy
Etap 6. Określanie ścieżki (drogi) krytycznej przedsięwzięcia
Ścieżka krytyczna to nieprzerwany ciąg czynności, prowadzący
Ścieżka krytyczna
od zdarzenia początkowego do zdarzenia końcowego,
posiadający najdłuższy czas trwania. Warunkuje najkrótszy czas
wykonania przedsięwzięcia.
czynności krytycznych, w przypadku realizacji
Składa się z czynności krytycznych
których zapas czasu jest równy zeru
równy zeru.
również zerowe
Zdarzenia
Zdarzenia leżące na ścieżce krytycznej mają również zerowe
zapasy czasu.
zapasy czasu.
Przekroczenie terminu zakończenia którejkolwiek czynności
krytycznej powoduje opóz
nienie wykonania całego projektu.
może występować więcej niż jedna ścieżka
W sieciach może występować więcej niż jedna ścieżka
krytyczna
krytyczna.
ID,2013/2014
Przykład 2
Przykład 2
Czynności bezpośrednio:
Czas trwania
Czynność Opis czynności
(dni)
poprzedzające następujące
A Nabycie surowców na prototypy - B 5
B Produkcja prototypów i ich ocena A D,H 20
C Badanie rynku - D,H 35
D Analiza kosztów produkcji B,C E 10
E Decyzje o podjęciu produkcji D F,I,K 1
F Nabycie surowców do produkcji E G 15
G Produkcja F J 30
H Wybór opakowania B,C I 2
I Nabycie opakowań H,E J 10
J Pakowanie G,I L 5
K Reklama i zbieranie zamówień E L 20
L Wysyłka do sklepów J,K - 10
ID,2013/2014
24
2014-01-10
Przykład 2
Przykład 2
Etap 1. Wyznaczenie najwcześniejszych możliwych momentów
Etap 1. Wyznaczenie najwcześniejszych możliwych momentów
zaistnienia zdarzeń (t)
zaistnienia zdarzeń (t)
2
5
8
A=5
91
I=10
56
91
7
1
J=5
B=20 G=30
46
0
96
37 6
46 10
H=2 61 9 L=10
106
96
C=35 F=15
25
K=20
35
3 4 E=1 5
66
D=10
35 45 46
Najkrótszy czas realizacji całego przedsięwzięcia 106 dni ID,2013/2014
Przykład 2
Przykład 2
Etap 1. Wyznaczenie najpóz
niejszych dopuszczalnych
Etap 1. Wyznaczenie najpóz
niejszych dopuszczalnych
momentów zaistnienia zdarzeń (T)
momentów zaistnienia zdarzeń (T)
2
15
5
8
A=5
91 91
I=10
10
7
1
J=5
B=20 G=30
0 46 81
0
6
10
0 H=2 61 61 9 L=10
106 106
96 96
C=35 79 F=15
81
46 K=20
3 4 E=1 5
D=10
35 35 45 45 46 46
76
35
ID,2013/2014
25
2014-01-10
Przykład 2
Przykład 2
Etap 3. Wyznaczenie zapasów czasowych dla zdarzeń (L)
Etap 3. Wyznaczenie zapasów czasowych dla zdarzeń (L)
2
15
5
10
8
A=5
91 91
I=10
0
7
1
J=5
B=20 G=30
0 46 81
0
0 35
6
10
H=2 61 61 9 L=10
0 106 106
96 96
C=35 F=15
0
0
K=20
3 4 E=1 5
D=10
35 35 45 45 46 46
0 0 0
ID,2013/2014
Przykład 2
Przykład 2
Etap 4. Wyznaczenie całkowitych zapasów czasu dla czynności
Etap 4. Wyznaczenie całkowitych zapasów czasu dla czynności
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia
Czynność tij NWRij NPRij NWZij NPZij zcij
A <1,2> 5 0 10 5 15 10
B <2,3> 20 5 15 25 35 10
C <1,3> 35 0 0 35 35 0
D <3,4> 10 35 35 45 45 0
E <4,5> 1 45 45 46 46 0
F <5,6> 15 46 46 61 61 0
G <6,8> 30 61 61 91 91 0
H <3,7> 2 35 79 37 81 44
I <7,8> 10 46 81 56 91 35
J <8,9> 5 91 91 96 96 0
K <5,9> 20 46 76 66 96 30
L <9,10> 10 96 96 106 106 0
ID,2013/2014
26
2014-01-10
Przykład 2
Przykład 2
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia  wykres
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia  wykres
Gantta (wg NWRij)
Gantta (wg NWRij)
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110
A 5
B 20
C 35
D 10
E 1
F 15
G 30
H 2
I 10
J 5
K 20
L 10
ID,2013/2014
Przykład 2
Przykład 2
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia  wykres
Etap 5. Wyznaczenie harmonogramu przedsięwzięcia  wykres
Gantta
Gantta
5,7
8 9 10
1 2 3 4 6
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110
A 5
B 20
C 35
D 10
E 1
F 15
G 30
H 2
I 10
J 5
K 20
L 10
ID,2013/2014
27
2014-01-10
Przykład 2
Przykład 2
Etap 6. Wyznaczenie ścieżki krytycznej przedsięwzięcia
Etap 6. Wyznaczenie ścieżki krytycznej przedsięwzięcia
2
15
5
10
8
A=5
91 91
I=10
0
7
1
J=5
B=20 G=30
0 46 81
0
0 35
6
10
H=2 61 61 9 L=10
0 106 106
96 96
C=35 F=15
0
0
K=20
3 4 E=1 5
D=10
35 35 45 45 46 46
0 0 0
Najkrótszy czas realizacji całego przedsięwzięcia wyznaczony został przez ścieżkę: C-D-E-F-G-J-L
ID,2013/2014
Metoda CPM - COST
ID,2013/2014
28
2014-01-10
Metoda CPM-COST
Metoda CPM-COST
Informacje ogólne
Informacje ogólne
CechÄ… metody CPM-COST jest rozpatrywanie
możliwości skrócenia czasu trwania
poszczególnych czynności, przy czym każde
skrócenie pociąga za sobą odpowiednie koszty.
Celem jest wyznaczenie takiego terminu
zakończenia przedsięwzięcia przy którym całkowity
koszt realizacji jest minimalny.
W CPM-COST zakłada się, że zależność pomiędzy
kosztem skrócenia danej czynności a liczbą
jednostek czasu, o które zostanie ona skrócona ma
charakter liniowy.
ID,2013/2014
Metoda CPM-COST
Metoda CPM-COST
Interpretacja określeń i oznaczeń
Interpretacja określeń i oznaczeń
tn  normalny czas trwania czynności, któremu
odpowiadają najniższe koszty wykonania czynności
kn (koszt normalny)
tgr - czas graniczny, najkrótszy możliwy ze względów
technicznych i technologicznych czas wykonania
czynności przy koszcie granicznym kgr
ID,2013/2014
29
2014-01-10
Metoda CPM-COST
Metoda CPM-COST
Interpretacja określeń i oznaczeń
Interpretacja określeń i oznaczeń
S  średni gradient kosztu
k
k - k
gr n
S =
tn - t
gr
kgr
S - określa wzrost kosztu związany ze
skróceniem czasu trwania czynności o
jednostkÄ™.
kn
tgr tn t
ID,2013/2014
Metoda CPM-COST
Metoda CPM-COST
Etapy analizy
Etapy analizy
Etap 1. Wyznaczenie terminu końcowego i ścieżki
krytycznej na sieci zależności (na podstawie
normalnych czasów trwania czynności).
Etap 2. Zestawienie czynności krytycznych i
obliczenie dla nich gradientów kosztów S.
Etap 3. Wyeliminowanie z zestawienia tych
czynności krytycznych, dla których średni gradient
kosztów nie istnieje, tzn.
tn = tgr
ID,2013/2014
30
2014-01-10
Metoda CPM-COST
Metoda CPM-COST
Etapy analizy
Etapy analizy
Etap 4. Proces skracania rozpoczynamy od
czynności krytycznej o najniższym gradiencie
kosztów S.
Etap 5. Przy skracaniu czasu trwania czynności
należy starać się skrócić jej czas o jak największą
największą
liczbę jednostek czasu. Występują tu jednak dwa
ograniczenia:
czas graniczny danej czynności tgr,
pojawienie się nowej ścieżki krytycznej.
ID,2013/2014
Metoda CPM-COST
Metoda CPM-COST
Etapy analizy
Etapy analizy
Nowa ścieżka pojawi się wtedy, gdy zaniknie zapas
czasu w ciągu czynności niekrytycznych.
Etap 6. Przy istnieniu dwóch lub więcej ścieżek
krytycznych w sieci należy skracać czas o tę samą
wielkość na wszystkich równoległych ścieżkach
krytycznych.
Etap 7. Najkrótszy termin wykonania
przedsięwzięcia uzyskuje się, gdy wszystkie
czynności leżące na którejkolwiek ścieżce
krytycznej osiÄ…gnÄ… czasy graniczne tgr. Dalsze
skracanie czasu wykonania przedsięwzięcia jest
ID,2013/2014
niemożliwe.
31
2014-01-10
Metoda CPM-COST
Metoda CPM-COST
Etapy analizy
Etapy analizy
Etap 8. Koszty przyspieszenia na każdym etapie
oblicza się jako iloczyn gradientu kosztów (S) dla
danej czynności i liczby jednostek czasu, o które
dana czynność krytyczna została skrócona.
A
ączne koszty przyspieszenia są sumą kosztów
poniesionych na poszczególnych etapach.
ID,2013/2014
Przykład 3
Przykład 3
Przedsięwzięcie składa się z 9 czynności, dla których podano
czasy normalne (tn), czasy graniczne (tgr) w dniach oraz koszty
normalne (Kn) i koszty graniczne (Kgr) w zł.
i-j tn tgr Kn Kgr S
1-2 10 7 100 250 50
1-3 12 6 120 240 20
1-4 8 4 250 290 10
2-7 12 10 330 390 30
3-5 6 6 400 400 -
4-6 4 2 230 260 15
5-8 15 10 300 400 20
6-8 10 6 400 440 10
7-8 8 5 300 390 30
Wykreślić siatkę zależności oraz wyznaczyć najwcześniejszy możliwy termin
zakończenia przedsięwzięcia.
Do jakiego terminu można skrócić czas realizacji przedsięwzięcia? Jakie z tym
wiążą się koszty?
ID,2013/2014
32
2014-01-10
Przykład 3
Przykład 3
Etap 1. Wyznaczenie terminu końcowego i ścieżki krytycznej na
Etap 1. Wyznaczenie terminu końcowego i ścieżki krytycznej na
sieci zależności
sieci zależności
a)
i-j zcij
2 12 7
13
10 22 25 1-2 3
3
3
10 1-3 0
8
1-4 11
3 5
2-7 3
1 6 8
12 15
12 12 18
18
0
33 33
0
3-5 0
0
0
0
0
4-6 11
10
8
5-8 0
4 4 6
6-8 11
8 12 23
19
11
7-8 3
11
Najkrótszy czas realizacji całego przedsięwzięcia wynosi 33 dni
i wyznaczony jest przez ścieżkę: 1-3-5-8
ID,2013/2014
Przykład 3
Przykład 3
Etap 2. Zestawienie czynności krytycznych i obliczenie dla nich
Etap 2. Zestawienie czynności krytycznych i obliczenie dla nich
gradientów kosztów S.
gradientów kosztów S.
Etap 3. Wyeliminowanie z zestawienia tych czynności krytycznych,
Etap 3. Wyeliminowanie z zestawienia tych czynności krytycznych,
dla których średni gradient kosztów nie istnieje
dla których średni gradient kosztów nie istnieje
b)
i-j tn tgr Kn Kgr S
1-2 10 7 100 250 50
1-3 12 6 120 240 20
1-4 8 4 250 290 10
2-7 12 10 330 390 30
3-5 6 6 400 400 -
4-6 4 2 230 260 15
5-8 15 10 300 400 20
6-8 10 6 400 440 10
7-8 8 5 300 390 30
ID,2013/2014
33
2014-01-10
Przykład 3
Przykład 3
Etap 4. Proces skracania rozpoczynamy od czynności
Etap 4. Proces skracania rozpoczynamy od czynności
krytycznej o najniższym gradiencie kosztów S
krytycznej o najniższym gradiencie kosztów S
1 faza skracania
b)
i-j tn tgr Kn Kgr S
1-2 10 7 100 250 50
1-3 12 6 120 240 20
1-4 8 4 250 290 10
2-7 12 10 330 390 30
3-5 6 6 400 400 -
4-6 4 2 230 260 15
5-8 15 10 300 400 20
6-8 10 6 400 440 10
7-8 8 5 300 390 30
ID,2013/2014
Przykład 3
Przykład 3
Etap 5. Skracanie czasu trwania czynności krytycznych
Etap 5. Skracanie czasu trwania czynności krytycznych
1 faza skracania
b)
2 12 7
10
10 22 22
0
0
10
8
3 5
1 6 8
9 15
9 9 15
15
0
30 30
0
0
0
0
0
10
8
4 4 6
8 12 20
16
8
8
Koszt przyspieszenia czynnoÅ›ci <1-3>: 20·3=60 jedn. pieniężnych
Dwie ścieżki krytyczne: 1-3-5-8 oraz 1-2-7-8 ID,2013/2014
34
2014-01-10
Przykład 3
Przykład 3
Etap 4. Proces skracania rozpoczynamy od czynności
Etap 4. Proces skracania rozpoczynamy od czynności
krytycznej o najniższym gradiencie kosztów S
krytycznej o najniższym gradiencie kosztów S
2 faza skracania
b)
i-j tn tgr Kn Kgr S
1-2 10 7 100 250 50
9
1-3 12 6 120 240 20
1-4 8 4 250 290 10
2-7 12 10 330 390 30
3-5 6 6 400 400 -
4-6 4 2 230 260 15
5-8 15 10 300 400 20
6-8 10 6 400 440 10
7-8 8 5 300 390 30
Dwie ścieżki krytyczne: 1-3-5-8 oraz 1-2-7-8 ID,2013/2014
Przykład 3
Przykład 3
Etap 6. Dwie ścieżki krytyczne  skracamy czas o tą samą
Etap 6. Dwie ścieżki krytyczne  skracamy czas o tą samą
wielkość na wszystkich równoległych ścieżkach krytycznych
wielkość na wszystkich równoległych ścieżkach krytycznych
2 faza skracania
b)
2 10 7
7
7 17 17
0
0
7
5
3 5
1 6 8
6 10
6 6 12
12
0
22 22
0
0
0
0
0
8 10
4 4 6
Trzy ścieżki krytyczne: 1-3-
8 12 12
8
0 0 5-8, 1-2-7-8 i 1-4-6-8
Koszt przyspieszenia czynnoÅ›ci <1-3>: 20·3=60 jedn. pieniężnych
Koszt przyspieszenia czynnoÅ›ci <4-8>: 20·5=100 jedn. pieniężnych
460 jedn.pieniężnych
Koszt przyspieszenia czynnoÅ›ci <2-7>: 30·2=60 jedn. pieniężnych
Koszt przyspieszenia czynnoÅ›ci <7-8>: 30·3=90 jedn. pieniężnych
Koszt przyspieszenia czynnoÅ›ci <1-2>: 50·3=150 jedn. pieniężnych
ID,2013/2014
35
2014-01-10
Przykład 3
Przykład 3
Etap 7. Najkrótszy termin wykonania programu sieciowego
Etap 7. Najkrótszy termin wykonania programu sieciowego
Wszystkie czynności leżące na ścieżce krytycznej
1-3-5-8 oraz 1-2-7-8 osiągnęły czasy graniczne tgr.
Dalsze skracanie czasu wykonania
przedsięwzięcia jest niemożliwe.
Najkrótszy termin wykonania projektu to & 22 dni.
ID,2013/2014
Przykład 3
Przykład 3
Etap 8. A
Ä…czne koszty przyspieszenia
Etap 8. A
Ä…czne koszty przyspieszenia
A
ączne koszty przyspieszenia są sumą kosztów
poniesionych na poszczególnych etapach.
Skrócenie czasu trwania przedsięwzięcia z 33 do
22 dni kosztuje 520 jedn. pieniężnych.
ID,2013/2014
36
2014-01-10
Dziękuję za uwagę
37