Wykonawcy: Data oddania prezentacji:

Dominika Percula 29.11.2013r.

Andrea Szczygieł

Rok II semestr I

Logistyka przedsiębiorstw przemysłowych

na wydziale Organizacji i Zarządzania

na Politechnice Śląskiej w Zabrzu

PREZENTACJA NR 28

„Metody ścieżki krytycznej.

Przykład 6.3”

Źródła:

„Metody badań operacyjnych.

Modelowanie optymalizacyjne.”

Tadeusz Trzaskalik

6.3. Metoda ścieżki krytycznej

Rozpatrzymy sytuację w której realizacją każdej czynności opisuje jeden parametr, charakteryzujący czas trwanie tej czynności.

Możemy sformułować następujące pytanie:

1. Jaki jest najkrótszy czas, w którym można zakończyć realizację projektu (czyli najkrótszy czas realizacji projektu)?

2. Jaki jest harmonogram realizacji projektu, określający najwcześniejsze i najpóźniejsze momenty rozpoczęcia i zakończenia czynności tak, aby dotrzymać najkrótszy czas realizacji projektu?

3. Które czynności są „krytyczne” i nie mogą być opóźnione, by nie opóźnić realizacji całego projektu?

4. W jakim stopniu czynności niekrytyczne mogą być opóźnione, by pomimo ich ewentualnego opóźnienia projekt został zrealizowany w najkrótszym możliwym czasie?

Odpowiedź na powyższe pytania można uzyskać za pomocą metody ścieżki krytycznej (CPM – Critical Path Method). Zdefiniujemy pojęcie niezbędne do określenie ścieżki krytycznej.

Ścieżką nazywamy dowolny ciąg czynności łączący dwa wybrane zdarzenia. Czasem przejścia ścieżki nazywamy sumę czasów wykonania czynności tworzących tę ścieżkę.

Rozpatrzmy wszystkie ścieżki łączące zdarzenie początkowe ze zdarzeniem końcowym, ponieważ wszystkie czynności wchodzące w skład przedsięwzięcia muszą zostać wykonane, czasem krytycznym nazywamy największy spośród czasów przejścia wszystkich ścieżek łączących te zdarzenia.

Wyznaczoną w ten sposób ścieżkę nazywamy ścieżka krytyczną.

Na rysunku 6.5 pod poszczególnymi łukami przedstawiono czasy trwania (w ustalonych jednostkach czasu) poszczególnych czynności przedsięwzięcia rozpatrywanego w przykładzie 6.1.

RYSUNEK !!!!!

Metoda ścieżki krytycznej składa się z dwóch kroków. Wykonując pierwszy z nich, zwany krokiem do przodu otrzymujemy najkrótszy czas realizacji przedsięwzięcia. Drugi, czyli krok do tyłu daje harmonogram realizacji przedsięwzięcia oraz powala na znalezienie rezerw czasowych dla poszczególnych czynności. Opiszemy sposób realizacji tych kroków.

Krok do przodu

Posługujemy się następującymi oznaczeniami:

ES - najwcześniejszy moment rozpoczęcia danej czynności

EF – najwcześniejszy moment zakończenia danej czynności

t – czas realizacji rozpatrywanej czynności

Zachodzi związek:

EF = ES + t

Zilustrujemy zastosowanie kroku do przodu korzystając z danych przykładu 6.1.

Umownym momentem rozpoczęcia projektu jest moment 0. Wykorzystując rys.6.5 obliczamy dla kolejnych czynności wartości ES i EF. Wartości te umieścimy na grafie ilustrującym rozpatrywaną w ramkach informacyjnych.

Czynność A rozpoczyna się w wierzchołku początkowym, stąd

ES = 0

EF = 0 + 5 = 5

Czynność B rozpoczyna się również w wierzchołku początkowym, więc

ES = 0

EF = 0 + 7 = 7

Czynność C może rozpocząć się dopiero po zakończeniu czynności A, tak więc

ES = 5

EF = 5 + 6 = 11

Czynność D może rozpocząć się po zakończeniu czynności A, stąd

ES = 5

EF= 5 + 8 = 13

Czynność E rozpoczynamy po zrealizowaniu czynności B, więc

ES = 7

EF = 7 + 3 = 10

Czynność F można rozpocząć po zakończeniu czynności C, czyli

ES = 11

EF = 11 + 4 = 15

Czynność G można rozpocząć po zakończeniu czynności C, więc

ES = 11

EF = 11 + 2 = 13

Czynność H może zostać rozpoczęta po zrealizowaniu czynności D, E i F, czyli moment jej rozpoczęcia nie może być wcześniejszy od najwcześniejszego momentu zakończenia każdej z nich, stąd

ES = max {10, 15, 13} = 15

EF = 15 + 5 = 20

Oznaczamy przez T najkrótszy czas realizacji przedsięwzięcia. Mamy dwie czynności kończące się w wierzchołku końcowym 6: G i H. Ukończenie obu tych czynności stanowi jednocześnie ukończenie realizacji projektu, tak więc

T = max {13, 20} = 20

Znalezione momenty ES oraz EF dla kolejnych czynności przedstawia rys. 6.6

RYSUNEK !!!

Krok do tyłu

Będziemy posługiwali się dodatkowo następującymi oznaczeniami:

LS - najpóźniejszy moment rozpoczęcia danej czynności

LF- najpóźniejszy moment zakończenia danej czynności.

Zachodzi związek:

LS = LF – t

Zilustrujemy zastosowanie kroku do tyłu korzystając ponownie z danych przykładu 6.1. Obliczenia rozpoczynamy od czynności H i G kończących się w wierzchołku 6. Oczywiście dla tych czynności mamy LF = T = 20.

Czynność H:

LF = 20

LS = 20 – 5 = 15

Czynność G:

LF = 20

LS = 20 – 5 = 18

Czynność F musi się zakończyć się najdalej w momencie 15. Gdyż jej późniejsze zakończenie spowodowałyby opóźnienie rozpoczęcie czynności H, co oznaczałoby jednocześnie opóźnienie realizacji całego projektu. Tak więc

LF = 15

LS = 15 – 4 = 11

Czynność E podobnie jak rozpatrywana uprzednio czynność F, nie ma zakończyć się później niż w momencie 15, by nie opóźnić czynności H, stąd

LF = 15

LS = 15 – 3 = 12

Czynność D również nie może opóźnić czynności H, czyli

LF = 15

LS = 15 – 8 = 7

Czynność C musi zostać zakończona tak, by nie opóźnić następującej po niej czynności F i G, stad

LF = min {11, 18} = 11

LS = 11 – 6 =5

Czynność B musi się zakończyć najdalej w momencie 12, by nie opóźnić po niej czynności E, czyli

LF = 12

LS = 12 – 7 = 5

Czynność A nie może opóźnić rozpoczęcia czynności D i C, następująco bezpośrednio po niej, stąd

LF = min {7, 5} = 5

LS = 5 – 5 = 0

Definiujemy rezerwę czynności jako długość odcinka czasu, dlatego możemy my opóźnić realizację czynności, by nie opóźnić realizacji całego kroku.

Zachodzi związek:

Rezerwa = LS – ES = LF – EF

Jeżeli dla danej czynności rezerwa jest równa zero oznacza to, że czynność ta nie może być opóźniona i wchodzi ona w skład ścieżki krytycznej.

Otrzymane dla przykładu 6.1 wyniki przedstawiamy tabelaryczne (tabl. 6.3) oraz graficznie (rys. 6.7). Na rysunku tym uzupełniamy rezultaty otrzymane w wyniku realizacji kroku do przodu.

RYSUNEK !!!

TABELA !!!

Obecnie możemy odpowiedzieć na pytania postawione na początku działu. Projekt, opisany w przykładzie 6.1 nie może zostać zrealizowany w czasie krótszym niż 20 jednostek. Harmonogram realizacji poszczególnych czynności określają wartości ES, EF, LS oraz LF, zamieszczone w tabl. 6.3. Mamy jedną ścieżkę krytyczną, w skład której wchodzą czynności A, C, F oraz H. Czynności B, F, D oraz G są niekrytyczne. Rezerwy, podane w tabl 6.3 pokazują, o ile czynności te mogą być opóźnione.