algorytm.org

Metoda ścieżki krytycznej (CPM)



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Metoda ścieżki krytycznej (CPM)
Ocena użytkowników:***** / 56
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 01 sierpnia 2005 19:03

Metoda ścieżki krytycznej CPM (ang. Critical Path Method) dotyczy analizy czasowej sieci zadań w przpadku deterministycznym, tzn. przy znajomości wszystkich terminów zajść zdarzeń czasowych oraz czasów trwania zadań.
Dana jest sieć zadań (czynności) w notacji łukowej, tzn. wierzchołki sieci symbolizują zdarzenia czasowe typu "and" a łuki zadania. Zadanie na łuku (i,j) może zostać rozpoczęte dopiero po zakończeniu wszystkich zadań leżących na łukach dochodzących do wierzchołka i. W takiej sieci przyjmuje się uporządkowanie wierzchołka 1 do s (s- wierzchołek w sieci, z którego nie wychodzą już żadne łuki) takie, że zajście zdarzenia i jest niepóźniejsze niż zajście wierzchołka j, o ile i<j. Każde zadanie jest jednoznacznie określone przez zdarzenie czasowe i, w którym się zaczyna oraz przez zdarzenie j, w którym się kończy. Dlatego każde zadanie można opisać za pomocą uporządkowanej pary (i,j) o czasie trwania ti,j.
Oto przykładowa sieć zadań:
Image Z sieci wynika, że np. czas wykonania zadania (1,2) wynosi t1,2=5.
Zadanie (4,s) może się rozpocząć po zakończeniu zadań (2,4) oraz (1,4).
Poznamy teraz twa ważne terminy charakteryzujące każde zdarzenie:
1). Najwcześniejszy termin zajścia zdarzenia j oznaczamy przez tjw i wyznaczamy z wzoru:
   t1w=0: pierwsze zdarzenie może zajść najwcześniej w czasie t=0
   tjw=max{tiw+ti,j}, po i należącym do zbioru wierzchołków, w których rozpoczynają się zadania dochodzące do wierzchołka j. tjw jest więc długością najdłuższej ścieżki od wierzchołka 1 do j.
Przykładowo dla sieci widocznej na rysunku:
t1w=0, t2w=5, t3w=10, t4w=12, t2w=20

2). Najpóźniejszy termin zajścia zdarzenie i:
   tsp=tsw
   tip=max{tjp-ti,j}, po j należącym do zbioru zdarzeń, w których kończą się zadania rozpoczęte z wierzchołka i.
Przykład:
tsp=tsw=20, t4p=12, t3p=14, t2p=13, t1p=3

Na podstawie powyższych wartości można wyznaczyć najwcześniejsze i najpóźniejsze terminy rozpoczęcia i zakończenia zadań w sieci:
   tiw: najwcześniejszy termin rozpoczęcia zadań zaczynających się w wierzchołku i
   tiw+ti,j: najwcześniejszy termin zakończenia zadania (i,j)
   tjp-ti,j: najpóźniejszy termin rozpoczęcia zadania (i,j)
   tjp: najpóźniejszy termin zakończenia zadania kończącego się w wierzchołku j
Si,jc=tjp-tiw-ti,j: luz całkowity zadania (i,j).

Zajmiemy się teraz najważniejszą charakterystyką wynikającą z znalizy czasowej: ścieżką krytyczną: jest nią droga od zdarzenia 1 do s w sieci zadań o maksymalnej długości.
Ścieżka krytyczna jest jednoznacznie wyznaczona przez zadania, których luz całkowity jest równy 0.
Wyznaczenie ścieżki krytycznej w sieci zadań jest jednoznaczne z określeniem minimalnego czasu trwania projektu opisanego przez tą sieć. Otrzymujemy więc najkrótszy czas potrzebny do wykonania wszystkich zadań
Przykładowo długość ścieżki krytycznej z naszej sieci wynosi 20, tworzy ją ciąg wierzchołków: 1, 4, s.
Można sprawdzić, że luzy całkowite zadań (1, 4) i (4, s) są równe 0.
Wyznaczyć ścieżkę krytyczną można na podstawie opisanych wyżej terminów lub znajdując najdłuższą drogę w sieci za pomocą algorytmu znajdywania najkrótszej drogi w grafie (Algorytm Forda-Bellmana, Dijkstry lub Floyda). Graf dla takiego algorytmu otrzymujemy z sieci zadań poprzez zmienienie długości wykonania zadań na ujemne (zmieniając znak przy każdej wadze łuku na "-").

Poprawiony: 15 sierpnia 2005 23:56
Komentarze
photo
-4 # kether667 2010-10-03 22:26
wszystko super tylko w
2). Najpóźniejszy termin zajścia zdarzenie i:
tsp=tsw
tip=max{tjp-ti,j},
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # Decks 2013-02-10 13:02
w punkcie 2)
zamiast
tip=max{tjp-ti,j}
powinno być
tip=min{tjp-ti,j}
!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Help 2017-04-12 00:57
Brakuje złożoności algorytmu :(
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz