Obliczanie i analiza grafów sieciowych. Wczesna data wydarzenia

Główne parametry schematu sieci

Główne parametry schematu sieci to:

ścieżki krytycznej

Rezerwy czasu na realizację wydarzeń

Rezerwy czasu na wykonanie pracy

Ścieżka - sekwencja zadań, w której zdarzenie końcowe jednego zadania pokrywa się ze zdarzeniem początkowym innego.

Pełna ścieżka - ścieżka, której początek jest wydarzeniem początkowym, a końcem wydarzeniem końcowym.

Czas trwania, czyli długość ścieżki, jest równy sumie czasów trwania pracy. Jego składniki.

ścieżki krytycznej - Pełna ścieżka. najdłuższa ze wszystkich ścieżek diagramu sieci od zdarzenia początkowego (I) do zdarzenia końcowego (C).

Długość ścieżki krytycznej określa całkowity czas trwania całego kompleksu prac. Ścieżka krytyczna pozwala znaleźć czas ostatniego wydarzenia.

Pełne ścieżki mogą wyjść poza krytyczną lub częściowo się z nią pokrywać. Te krótsze podróże nazywają się zrelaksowany. Ich cechy są. Że mają rezerwy czasu. Ścieżka krytyczna nie jest. Dla każdego i-tego wydarzenia określa się:

tpi– wczesny początek- minimalny możliwy czas wystąpienia tego zdarzenia dla danego czasu pracy.

t p ja– późna data przyjazdu- maksymalny czas wystąpienia tego zdarzenia, w którym nadal możliwe jest wykonanie wszystkich następnych prac, z zastrzeżeniem ustalonego terminu wystąpienia zdarzenia.

R i – luz na imprezę- okres czasu, na który początek tego wydarzenia może zostać opóźniony bez naruszenia czasu realizacji planowanego kompleksu jako całości. Zdefiniowana jako różnica między późnym ( t p ja) i wcześnie ( t p ja) termin zakończenia tego wydarzenia.

Rezerwy zdarzenia na ścieżce krytycznej są równe zeru, ponieważ na nim t p i = t p i

Do każdej pracy tij) definiuje:

wczesna data rozpoczęcia (t w.d. ij)- minimalny możliwy czas na rozpoczęcie tej pracy.

wcześniejsza data zakończenia (t p.o. ij)- minimalny możliwy termin wykonania tej pracy, za dany okres pracy

późna data rozpoczęcia (t b.s. ij)- maksymalny dopuszczalny termin rozpoczęcia tej pracy

późna data zakończenia (t p.o. ij)- maksymalny z dopuszczalnych terminów zakończenia tych prac, w których można jeszcze wykonać następujące prace z zachowaniem ustalonego terminu wystąpienia zdarzenia końcowego.

Oczywiście wczesna data rozpoczęcia działania pokrywa się z wczesną datą rozpoczęcia jej początkowego wydarzenia, a wczesna data zakończenia przekracza ją o czas trwania działania:

t r.n. ij = tp i

t r.o. ij = tp i + t ij

Późna data zakończenia działania jest taka sama jak późna data jego zdarzenia końcowego, a późna data rozpoczęcia działania jest mniejsza o czas trwania działania:

sp. z o.o. ij = t p j

t a. s. ij = t p j – t ij

Pełna rezerwa czasu na wykonanie pracy Rnij– maksymalny okres czasu, na który można opóźnić rozpoczęcie lub wydłużyć czas pracy bez zmiany ustawionej daty wystąpienia zdarzenia końcowego.

Czas wolny na pracę, który jest częścią pełnej rezerwy - maksymalny okres czasu, o który można opóźnić rozpoczęcie lub wydłużyć czas pracy, nie zmieniając przy tym terminów wcześniejszego rozpoczęcia dla kolejnych prac.

Zadania leżące na ścieżce krytycznej nie mają rezerw, ponieważ wszystkie rezerwy są tworzone ze względu na różnicę w czasie trwania ścieżki krytycznej i rozważanej.

Względnym wskaźnikiem charakteryzującym rezerwę czasu na wykonywanie pracy jest ich współczynnik naprężenia, co jest równe stosunkowi czasu trwania segmentów ścieżki między tymi samymi zdarzeniami, ponadto jeden segment jest częścią ścieżki o maksymalnym czasie trwania ze wszystkich ścieżek przechodzących przez tę pracę, a drugi odcinek jest częścią ścieżki krytycznej.

3.Obliczanie modeli sieciowych

Parametry sieciowe dla diagramów sieciowych są obliczane metodą graficzną i tabelaryczną, a dla złożonych metodą matematyczną.

Graficznie metoda obliczeniowa realizowana jest bezpośrednio na wykresie i stosowana w przypadkach, gdy liczba zdarzeń jest niewielka. Aby to zrobić, każdy krąg jest podzielony na 4 sektory.

Górny sektor to rezerwa czasu na wystąpienie zdarzenia R i

sektor lewy - wczesna data wydarzenia tpi

prawy sektor - późna data zdarzenia t p i

dół - numer wydarzenia

Metoda obliczania parametrów

1) Wczesny termin wydarzeń . Przyjmuje się, że wczesna data zakończenia początkowego (pierwszego lub zerowego) zdarzenia jest równa zeru. Wczesne terminy zakończenia wszystkich innych wydarzeń są określane w ścisłej kolejności przez rosnącą liczbę wydarzeń. Aby określić datę wcześniejszego zakończenia dowolnego zdarzenia j, wszystkie prace uwzględnione w tym wydarzeniu są brane pod uwagę, dla każdej pracy data wcześniejszego zakończenia wydarzenia końcowego jest określana jako suma daty wcześniejszego zakończenia początkowego wydarzenia pracy i czas trwania tej pracy tij , z uzyskanych wartości wybiera się maksymalny czas wcześniejszego zakończenia j-tego zdarzenia

t pj = (t pi +t ij) max i jest rejestrowane na wykresie (lewy sektor zdarzenia)

2) Późne terminy wydarzeń . Późna data zakończenia finałowego wydarzenia jest równa jego wcześniejszej dacie. Obliczanie spóźnionych dat zakończenia wszystkich innych wydarzeń odbywa się w odwrotnej kolejności, zgodnie z malejącymi numerami wydarzeń. Przy ustalaniu późnego terminu zakończenia poprzedniego wydarzenia i uwzględnia się wszystkie prace wychodzące z i-tego wydarzenia. Dla każdej pracy obliczany jest spóźniony termin zakończenia wydarzenia początkowego t p ja , jako różnica między późnym terminem zakończenia ostatniego wydarzenia tej pracy t p j i czas trwania tej pracy tij Z uzyskanej wartości wybierz minimalny czas opóźnionego zakończenia i-tego zdarzenia: t p i = (t p j - t ij)min i jest rejestrowany w odpowiednim sektorze.

3) Długość ścieżki krytycznej jest równa wcześniejszej dacie zdarzenia końcowego.

4) Rezerwy czasu imprezy . Przy ustalaniu rezerw czasowych na wydarzenia należy od liczby zapisanej w prawym sektorze tego wydarzenia odjąć liczbę zapisaną w lewym sektorze i umieścić ją w górnym sektorze.

5) Ustalając łączny dodatek za pracę, odejmij od liczby odnotowanej w prawym sektorze zdarzenia końcowego, liczbę odnotowaną w lewym sektorze zdarzenia początkowego oraz czas trwania samej pracy.

6) Przy ustalaniu wolnej rezerwy na pracę odejmij od liczby zarejestrowanej w lewym sektorze zdarzenia końcowego, liczbę zarejestrowaną w lewym sektorze zdarzenia początkowego oraz czas trwania samej pracy.

Wstępne dane:

Metoda tabelaryczna

Kody zadań w tabeli są zapisane w indeksie rosnącym i.

Kolumny 2 i 3 są wypełnione danymi pomocniczymi: kodami poprzednich i kolejnych prac. Dane te będą potrzebne do obliczeń. Jeśli prace są początkowe, to znaczy nie ma wcześniejszych prac lub ostateczne, to znaczy nie ma kolejnych, to w odpowiednich kolumnach wstawia się myślniki. Może być kilka poprzednich i kolejnych zadań w zależności od liczby wektorów kończących się lub rozpoczynających w danym zdarzeniu./

Kolumna 4 zawiera wartości czasu pracy.

Kolumna 5 rozpoczyna obliczone dane. Obliczenie odbywa się w dwóch przejściach przez rzędy tabeli. Pierwsze przechodzą przez wiersze od góry do dołu, w których obliczane są najwcześniejsze daty pracy, a drugie przechodzą przez wiersze od dołu do góry, w których obliczane są daty późnej pracy.

Wczesne rozpoczęcie czynności, które nie mają poprzednich (w kolumnie 2 - myślnik) można przyjąć jako 0, jeśli nie określono innej wartości. Wcześniejsze zakończenie pracy określane jest według wzoru t r.o. ij = t pH ij + t ij i wpisano w kolumnie 6.

Wczesny początek odpoczynku można zdefiniować tak, jakby na przykład brana była pod uwagę praca 2.5, która ma zdarzenie początkowe 2, to jej wcześniejszy czas rozpoczęcia jest równy czasowi wcześniejszego zakończenia pracy 12, ponieważ ma zdarzenie końcowe z 2. Wartość z kolumny 6 jest przepisana w kolumnie 5 Kody wcześniejszych prac są wskazane w kolumnie 2. Wcześniejsze zakończenie jest również określane wzorem t r.o. ij = t pH ij + t ij

Jeżeli w kolumnie 2 wskazano, że określona praca jest poprzedzona więcej niż jedną pracą (praca 5.6 jest poprzedzona pracami 2.5 i 3.5), to należy wybrać wartość wczesnego startu z kilku opcji dla wartości (9 - do końca pracy 2,5 lub 13 - do końca pracy 3,5). Reguła wyboru odpowiada wzorowi t p .n. ij = (t pi + t ij) max , czyli wybrana jest wartość maksymalna (w przykładzie - 16). Wczesne zakończenia są zdefiniowane jak powyżej.

Maksymalna wartość wczesnego końca w kolumnie 6 odpowiada wartości czasu trwania ścieżki krytycznej (16).

Drugie przejście wzdłuż rzędów tabeli od pracy zarejestrowanej w ostatnim wierszu do pracy zarejestrowanej w pierwszym wierszu pozwala określić wartości późnych wskaźników wydajności. Dla zadań, które nie mają kolejnych zadań (w kolumnie 3 - myślnik, w przykładzie pracy 46, 5,6), wartość ścieżki krytycznej jest zapisywana w kolumnie opóźnionego zakończenia (8). W przypadku tych zadań wartość późnego rozpoczęcia obliczana jest ze wzoru t a. s. ij t przez ij - t ij

Opóźnione zakończenie odpoczynku można zdefiniować jako, jeśli na przykład rozważana jest praca 3.5, która ma zdarzenie końcowe 5, to jej późny czas zakończenia jest równy czasowi późnego rozpoczęcia pracy 5.6, ponieważ ma koniec zdarzenie 5. Wartość z kolumny 7 jest przepisana w kolumnie 8. Kody kolejnych prac są wskazane w kolumnie 3. Opóźniony start jest również określony wzorem t a. s. ij t przez ij - t ij .

Jeśli w kolumnie 3 wskazano, że po określonej pracy następuje więcej niż jedna praca (po pracy 0.1 następuje praca 1.2 i 1.3), wówczas konieczne jest wybranie wartości późnego zakończenia z kilku opcji wartości (3 - zgodnie z czasem rozpoczęcia pracy 1 ,3 lub 7 - zgodnie z czasem rozpoczęcia 1,2) wybierana jest wartość minimalna (w przykładzie - 3). Opóźniony start określa się jak powyżej wzorem t a. s. ij t przez ij - t ij .

Wartość całkowitego luzu (kolumna 9) oblicza się według wzoru

R nij = t przez ij - t pH ij - t ij.

Wartość wolnego luzu (kolumna 10) oblicza się ze wzoru

R z ij = t ро ij - t рр ij - t ij

Dowolna sekwencja działań sieciowych, w której zdarzenie końcowe każdego działania zbiega się ze zdarzeniem początkowym działania następującego po nim, nazywa się poprzez.

Ścieżka sieciowa, w której punkt początkowy jest taki sam jak zdarzenie początkowe, a punktem końcowym jest zdarzenie końcowe, nazywa się kompletny.

Ścieżka od pierwotnego wydarzenia do dowolnego podjętego poprzedzony wydarzenie. Ścieżka, która poprzedza zdarzenie i ma najdłuższą długość, nazywa się maksymalna poprzednia. Jest oznaczony przez L 1 (i), a jego czas trwania wynosi t.

Ścieżka łącząca dowolne zdarzenie z ostatnim nazywa się późniejszy droga. Ta najdłuższa ścieżka nazywa się w miarę możliwości kolejnych i jest oznaczony przez L 2 (i), a jego czas trwania wynosi t.

Pełna ścieżka o najdłuższej długości nazywa się krytyczny. Nazywa się ścieżki inne niż ścieżka krytyczna zrelaksowany. Mają rezerwy czasu.

Działania na ścieżce krytycznej są wyróżnione grubymi lub podwójnymi liniami. Czas trwania ścieżki krytycznej jest uważany za główny parametr wykresu.

Rozważ algorytm wyznaczania ścieżki krytycznej na diagramie sieci przy użyciu algorytmu metody programowania dynamicznego.

Posortujmy wierzchołki wykresu według rang i ponumerujmy je od końca do początku. Umożliwi to dopasowanie liczb rang do etapów ruchu wstecz podczas znajdowania warunkowo optymalnych elementów sterujących na ostatnim, ostatnich dwóch i tak dalej. gradacja. Znalezienie ścieżki krytycznej zostanie przeanalizowane na przykładzie diagramu sieci pokazanego na rys. 10.7.

Zgodnie z zasadą optymalności Bellmana, sterowanie optymalne na każdym etapie jest określone przez cel sterowania i stan na początku etapu. Stan systemu to wydarzenia, które leżą w szeregach. Do zaliczenia finałowego wydarzenia X 16 konieczne jest ukończenie poprzednich wydarzeń. Możliwe stany układu na początku ostatniego etapu pracy - wystąpienie zdarzeń X 14 i X 15. W kółeczkach w punktach X 14 i X 15 umieszczamy maksymalny czas pracy na ostatnim etapie: X 14 5 , X 15 7 . Znajdźmy maksymalny czas pracy na ostatnich dwóch etapach. Stan systemu na początku przedostatniego etapu jest spowodowany zdarzeniem X 13. Maksymalny czas trwania ścieżki prowadzącej z X 13 do X 16 wynosi .

Dlatego cyfrę 14 należy umieścić w okręgu w pobliżu zdarzenia X 13 i tak dalej. Przeprowadzając etapy od końca do początku, wyznaczamy długość ścieżki krytycznej t cr =96. Aby znaleźć samą ścieżkę krytyczną, przejdźmy przez proces obliczeń od początkowego zdarzenia X 1 do końcowego X 16 . Liczbę 96 otrzymaliśmy na pierwszym etapie (od początku) dodając 16 do liczby 80. Zatem ścieżka krytyczna na tym etapie będzie równa (X 1, X 3). Liczba 80 = 16 + 64. Dlatego ścieżka krytyczna w drugim etapie przechodzi przez pracę (X 3 , X 4) itd. Na wykresie zaznaczono go pogrubioną linią:

X 1 - X 3 - X 4 - X 7 - X 8 - X 10 - X 11 - X 12 - X 13 - X 15 - X 16 .

Wczesne i późne terminy zakończenia wydarzeń. Zwolnienie wydarzenia

Wszystkie ścieżki różniące się czasem trwania od ścieżki krytycznej mają rezerwy czasowe. Różnica między długością ścieżki krytycznej a jakąkolwiek ścieżką niekrytyczną nazywana jest całkowitym zapasem na danej ścieżce niekrytycznej i jest oznaczana przez: .

wczesny termin zakończenie zdarzenia nazywa się najwcześniejszym momentem, w którym cała praca poprzedzająca to zdarzenie jest zakończona, tj. zależy od czasu trwania maksymalnej trasy poprzedzającej wydarzenie, tj.:

lub

Aby znaleźć wczesną datę zdarzenia j , trzeba znać ścieżkę krytyczną kierowanego podgrafu, który składa się ze zbioru ścieżek poprzedzających dane zdarzenie j . Wczesny termin zdarzenia początkowego jest równy zero: t p (1)=0.

późny termin wydarzenie zwany najpóźniejszym punktem w czasie, po którym jest dokładnie tyle czasu, ile potrzeba na wykonanie wszystkich prac po tym wydarzeniu. Najpóźniejszy z dopuszczalnych terminów zakończenia imprezy, łącznie z czasem realizacji wszystkich kolejnych czynności, nie może przekroczyć długości ścieżki krytycznej. Spóźniony termin wydarzenia jest obliczany jako różnica między czasem trwania ścieżki krytycznej a czasem trwania maksymalnej ścieżki następującej po wydarzeniu:

W przypadku wydarzeń na ścieżce krytycznej wczesne i późne daty zakończenia tych wydarzeń są takie same.

Różnica między późnym i wczesnym terminem zakończenia imprezy to rezerwowy czas imprezy: . Przedział nazywa się przedziałem wolności zdarzeń. Zawieszenie wydarzenia pokazuje maksymalny dozwolony czas, przez który wydarzenie może zostać cofnięte bez zwiększania ścieżki krytycznej.

Ponieważ kwota określa czas trwania ścieżki o maksymalnej długości przechodzącej przez to zdarzenie, a następnie , tj. zapas czasu dowolnego zdarzenia jest równy pełnemu zapasowi maksymalnej drogi przez to wydarzenie.

Przy ręcznym obliczaniu parametrów czasowych wygodnie jest stosować metodę czterosektorową. Dzięki tej metodzie okrąg diagramu sieci oznaczający zdarzenie jest podzielony na cztery sektory. Numer wydarzenia umieszczany jest w górnym sektorze; po lewej - najwcześniejszy możliwy czas wydarzenia (); po prawej - najpóźniejszy z dopuszczalnego czasu imprezy; w dolnym sektorze - rezerwowy czas tego wydarzenia: .

Aby obliczyć najwcześniejszy termin dla wydarzeń: , zastosuj formułę , biorąc pod uwagę wydarzenia w porządku rosnącym liczb, od początkowego do końcowego, zgodnie z dziełami zawartymi w tym wydarzeniu.

Spóźniony termin zakończenia wydarzeń oblicza się według wzoru , począwszy od zdarzenia końcowego, dla którego ( - numer zdarzenia końcowego), zgodnie z zadaniami z niego wychodzącymi.

Zdarzenia krytyczne mają zerowy zapas. Określają działania krytyczne i ścieżkę krytyczną.

Przykład 10.2. Niech schemat sieci pokazany na ryc. 10.8.

Rozwiązanie. Oblicz wcześniejsze terminy zakończenia wydarzeń:

Tak więc wydarzenie końcowe może nastąpić dopiero 14 dnia od rozpoczęcia projektu. Jest to maksymalny czas, w którym można zakończyć wszystkie działania projektowe. Decyduje o tym najdłuższa ścieżka. Termin wcześniejszego zakończenia pracy 6 =14 pokrywa się z czasem krytycznym kp - całkowitym czasem trwania pracy leżącym na ścieżce krytycznej. Teraz możesz wyróżnić działania należące do ścieżki krytycznej, wracając od zdarzenia końcowego do pierwotnego. Spośród dwóch zadań uwzględnionych w zdarzeniu 6 , długość ścieżki krytycznej determinowała zadania (5, 6), ponieważ (5 + 56)=14. Dlatego praca (5, 6) jest krytyczna i tak dalej. Prace (1, 3), (3, 4), (4, 5), (5, 6) wyznaczyły ścieżkę krytyczną: cr = (1-3-4-5-6).

Teraz obliczamy późne daty zakończenia wydarzeń. Wynajmować . Użyjmy metody programowania dynamicznego. Wszystkie obliczenia będą prowadzone od wydarzenia finałowego do wydarzenia początkowego. Późne terminy zakończenia wydarzeń to:

Ponieważ po zdarzeniu 5, aby zakończyć projekt, praca (5, 6) musi trwać 3 dni. Z wydarzenia 4 wynikają dwie prace, a więc:

Luz w przypadku zdarzenia 2 to: . Rezerwy pozostałych wydarzeń są równe zeru, ponieważ te wydarzenia są krytyczne.

Wczesne i późne daty rozpoczęcia i zakończenia. Ustalenie rezerw czasu pracy. Pełna rezerwa czasu pracy.

Wydarzenie bezpośrednio poprzedzające tę pracę zostanie nazwane podstawowy i oznaczają , oraz zdarzenie bezpośrednio następujące po nim, - finał i wyznacz. Wtedy każda praca będzie oznaczona przez . Znając czas zakończenia wydarzeń, możesz określić parametry czasowe pracy.

Wczesny czas rozpoczęcia jest równa wcześniejszej dacie wydarzenia: .

Wcześniejszy koniec pracy równa się sumie wcześniejszej daty zakończenia wydarzenia początkowego i czasu trwania tej pracy: lub .

Późny koniec pracy zbiega się z późnym terminem zakończenia jego ostatniego wydarzenia: .

Późny czas rozpoczęcia jest równa różnicy między późnym terminem zakończenia jego końcowego wydarzenia a wartością tej pracy:

Ponieważ terminy wykonania prac mieszczą się w granicach określonych przez i , mogą posiadać różnego rodzaju rezerwy czasowe.

Pełna rezerwa czasu pracy - jest to maksymalny czas wymagany do wykonania dowolnej pracy bez przekraczania ścieżki krytycznej. Oblicza się ją jako różnicę między późnym zakończeniem a wczesnym czasem zakończenia samego dzieła: . Od tego czasu .

W ten sposób, pełna rezerwa czasu pracy to maksymalny czas, o jaki można wydłużyć jego czas trwania bez zmiany czasu trwania ścieżki krytycznej. Wszystkie zadania niekrytyczne mają niezerowy całkowity zapas czasu.

Bezpłatna rezerwa czasu pracy- jest to margines czasu, który może być dostępny podczas wykonywania tej pracy, pod warunkiem, że jej wydarzenia początkowe i końcowe nastąpią w ich najwcześniejszych terminach: .

Obliczenia wykresu sieci w sposób tabelaryczny dokonuje się według wzorów podanych wcześniej w rozdziale 4 (1-10). Przy wyznaczaniu parametrów modeli sieciowych w sposób analityczny obliczenia wykonywane są w formie tabeli. Rozważ cechy obliczania modeli sieci w ten sposób (Załącznik 1) na przykładzie obliczania parametrów schematu sieci przedstawionego w zadaniu do tego kursu (opcja 15).

Na początkowym etapie konieczne jest opisanie wstępnego modelu sieci. W tym przypadku szyfry wszystkich zadań i zależności są wprowadzane w pierwszej kolumnie tabeli, zaczynając od zadania wyłaniającego się z pierwszego zdarzenia. Kody zadań muszą być umieszczane w tabeli sekwencyjnie, dowolna kolejność umieszczania zadań i zależności w tabeli jest niedozwolona. Druga kolumna tabeli zawiera czas trwania wszystkich prac i zależności.

Obliczanie harmonogramu sieci rozpoczyna się od określenia wartości wczesnych parametrów pracy. Wczesny początek pracy 1-2 jest równy zero (wzór 1), a jego wczesny koniec zgodnie ze wzorem 2.

Wczesny początek czynności 2-6 i 2-7 (zgodnie ze wzorem 3) jest równoznaczny z wczesnym zakończeniem czynności 1-2.

Maksymalna wartość wcześniejszego zakończenia pracy 19-21, równa 36, ​​określa czas trwania ścieżki krytycznej, a tym samym łączny czas wykonania wszystkich czynności w pierwotnym modelu sieci. Wynikowa wartość wcześniejszego zakończenia tej pracy 19-21 = 36 jest przenoszona do kolumny późnego zakończenia pracy końcowej 20-21.

Późne rozpoczęcie pracy 20-21 określa się według wzoru 5 (= 34)

Późne rozpoczęcie pracy 20-21 to późne zakończenie pracy 15-20 (=), które ją poprzedza.

Ponadto obliczanie późnych parametrów odbywa się podobnie, z wyjątkiem przypadków, gdy zadanie ma kilka kolejnych zadań (na przykład zadanie 6-9 ma dwa kolejne - 9-10 i 9-14). W tym przypadku, zgodnie ze wzorem 4, spóźnione zakończenie pracy 6-9 jest równe minimalnej wartości spóźnionego rozpoczęcia kolejnej pracy 9-10 i 9-14.

Aby znaleźć pozycję ścieżki krytycznej, konieczne jest określenie wartości całkowitych i prywatnych rezerw czasu dla każdej pracy oraz zależności schematu sieci i wprowadzenie ich wartości w 7 i 8 kolumnie obliczenia tabeli.

Całkowitą rezerwę czasu pracy, zgodnie ze wzorami 8-9, określa się jako różnicę między późnym a wczesnym zakończeniem lub jako różnicę między późnym a wczesnym rozpoczęciem odpowiedniej pracy. Przydatne jest określenie wartości całkowitego luzu w obie strony, zbieżność uzyskanych wartości można uznać za dodatkową kontrolę. Na przykład do pracy 6-7:

Częściowy brak czasu pracy, zgodnie ze wzorem 10, określa się jako różnicę między wartością wcześniejszego rozpoczęcia kolejnej czynności a wartością wcześniejszego zakończenia tej czynności. Na przykład do pracy 6-7:

Ścieżka krytyczna charakteryzuje się zerowym luzem. Porównanie parametrów modelu sieci uzyskanych metodami sektorowymi i tabelarycznymi powinno ujawnić ich pełną tożsamość, występowanie rozbieżności wskazuje na błędność obliczeń.

Graficzna metoda obliczania diagramów sieciowych

Obliczanie wykresu sieci w sposób graficzny odbywa się podobnie jak metodą tabelaryczną (wzory 1-10), jednak metoda graficzna lub sektorowa obliczania parametrów schematu sieci polega na ich zapisie bezpośrednio na modelu (Załącznik 2 ). Każde wydarzenie (koło) podzielone jest na cztery sektory. Oznaczenie sektorów pokazano na poniższym rysunku:

W przypadku działań na ścieżce krytycznej wartości całkowitego i częściowego luzu są równe zeru, co jest wyróżnione na schemacie sieci podwójną linią.

Aby sprawdzić poprawność wykonanych obliczeń należy upewnić się, że:

• * ujawnił ciągłą ścieżkę krytyczną;
• * naliczone rezerwy czasowe mają wartość nieujemną;
• * wartość luzu prywatnego dla wszystkich stanowisk jest mniejsza lub równa wartości luzu całkowitego dla tych stanowisk;
• * co najmniej jedna wartość późnego rozpoczęcia prac (prac) wychodzących z pierwszego zdarzenia jest równa zero.

Dwa są znane metoda obliczania parametrów grafu sieciowego”. obliczenia bezpośrednio na wykresie sieci; analityczny (tabelaryczny).

Obliczenie główne wskaźniki modelu sieci można to zrobić w następujący sposób.

• 1. Obliczanie wczesnych dat:
  • ? wczesne rozpoczęcie pracy określa czas trwania najdłuższej drogi od zdarzenia inicjującego do rozpoczęcia wykonywania tej pracy,
  • ? wcześniejsze terminy ukończenia- jest to najwcześniejszy możliwy termin zakończenia pracy. Czas wcześniejszego zakończenia pracy jest równy sumie czasu rozpoczęcia pracy i czasu trwania samej pracy.
• 2.Obliczanie ścieżki krytycznej. Jego czas trwania jest definiowany jako łączny czas działań na ścieżce krytycznej, czyli czas wykonania całego kompleksu robót przy największym zrównoleglaniu wszystkich robót. Ten czas jest równy największemu z najwcześniejszych czasów ukończenia grafu sieci. Ścieżka krytyczna przechodzi przez wydarzenia, które nie mają rezerw czasowych (poprzez działania krytyczne).
• 3.Obliczanie późnych dat rozpoczęcia i zakończenia wyznaczane są z możliwości przesunięcia limitu w prawo wzdłuż osi liczbowej terminów wykonania pracy tak, aby nie zmienił się czas ścieżki krytycznej. Dlatego logiczne jest przeprowadzenie obliczeń od ostatniego zdarzenia do pierwszego i najpierw określenie czasu późnego zakończenia pracy, a następnie obliczenie czasu późnego rozpoczęcia pracy:
  • ?późna data rozpoczęcia (ij) definiuje się jako różnicę między późnym zakończeniem pracy a czasem trwania samej pracy,
  • ? późna data ukończenia określana jest przez wartość ścieżki o minimalnym czasie trwania, która do niej prowadzi od zdarzenia końcowego i jest obliczana jako różnica między ścieżką krytyczną a maksymalnym czasem pracy od zdarzenia końcowego w sieci do zdarzenia końcowego tej pracy.
• 4. Obliczanie rezerw czasu”.

Ipełna rezerwa czasu pracy definiuje się jako różnicę między późnym i wczesnym startem lub między późnym i wczesnym zakończeniem. Należy zauważyć, że całkowity zastój czasu pracy na ścieżce krytycznej jest równy zero,

• ? prywatny (wolne) rezerwy czasu".
• 1)prywatny luz pierwszego rodzaju określana przez możliwość zmiany późnego czasu rozpoczęcia ( ij) do wcześniejszych terminów bez zmiany spóźnionych terminów wykonania bezpośrednio poprzedzających prac,
• 2) prywatny luz drugiego rodzaju uwarunkowana możliwością zmiany wcześniejszego zakończenia pracy (ij) w późniejszych terminach bez zmiany wcześniejszych terminów rozpoczęcia bezpośrednio późniejszej pracy; jest określana przez różnicę między wczesnym rozpoczęciem kolejnej czynności a wczesnym zakończeniem tej czynności.

Rozważmy procedurę obliczania parametrów na przykładzie. Schemat sieci pokazano na ryc. 7.5.

Ryż. 7.5.

Aby obliczyć parametry, użyjemy metody tabelarycznej, a aby uprościć percepcję, podsumujemy wszystko w jednej tabeli. 7.1.

Zasady wykorzystania rezerw czasowych w planowaniu sieci.

• 1. Aby całkowite i częściowe rezerwy pracy (y) były równe, konieczne i wystarczające jest, aby wydarzenie końcowe Y danej pracy było wydarzeniem na ścieżce krytycznej.
• 2. Jeśli pełna rezerwa (Ja i]1) części pracy jest równa zeru, to prywatna rezerwa drugiego rodzaju (g "f) jest również równy zero. Między tymi rezerwami zawsze jest stosunek R(IJ) > r”ijy Całkowite i prywatne rezerwy czasu są zawsze większe lub równe zeru.
• 3. Aby rezerwa częściowa czasu pracy (y) była równa zeru, konieczne i wystarczające jest, aby praca ta przebiegała na drodze o maksymalnej długości od pierwszego zdarzenia do zdarzenia y.
• 4. Jeżeli czas pracy (y) zostanie zwiększony o p, tj. p to wcześniejszy termin rozpoczęcia kolejnej pracy wzrośnie o wartość p - g” („uu
• 5. Jeżeli czas pracy (y) zostanie zwiększony o całkowitą rezerwę czasu na tę pracę, wówczas powstaje nowa ścieżka krytyczna, której czas trwania jest równy czasowi trwania starej.
• 6. Całkowita rezerwa czasu pracy (y) jest równa sumie częściowej rezerwy czasu drugiego rodzaju tej pracy oraz minimum całkowitej rezerwy wszystkich bezpośrednio kolejnych prac.

Wyniki obliczeń parametrów schematu sieci

Tabela 7.1

	Czas trwania	Wczesny	warunki, h	Późne daty, h		Rezerwy czasu, h
	działa, h	Początki	końcówki	Początki	końcówki	Pełny	Bezpłatny
	Ścieżka krytyczna, h		(działa 1-3

7. Jeżeli czas pracy (r /) zostanie zwiększony o p, pojawi się nowa ścieżka krytyczna, której czas trwania przekroczy czas trwania starej ścieżki krytycznej o p -

Po zbudowaniu wykresu sieci i obliczeniu jego głównych wskaźników zaczynają go optymalizować.

• 1. Wybierz ścieżkę krytyczną i znajdź jej długość;
• 2. Ustalić rezerwy czasowe na każde wydarzenie;
• 3. Określ rezerwy czasowe całej pracy i współczynnik intensywności pracy przedostatniej pracy

Rozwiązanie

Aby rozwiązać problem, stosujemy następującą notację.

Element sieci	Nazwa parametru	Symbol parametru
Wydarzenie i	Wcześniejszy termin zakończenia wydarzenia
Późna data zakończenia wydarzenia
Zwolnienie wydarzenia
Praca (i, j)	Czas pracy
Wczesny czas rozpoczęcia
Wcześniejszy koniec pracy
Późny czas rozpoczęcia
Późny koniec pracy
Pełna rezerwa czasu pracy
	Czas podróży
Długość ścieżki krytycznej
Rezerwa czasu podróży

Aby określić rezerwy czasowe na zdarzenia w sieci, obliczane są najwcześniejsze terminy tp i najpóźniejsze tp zakończenia zdarzeń. Żadne wydarzenie nie może wystąpić, zanim wszystkie poprzedzające je wydarzenia nie zostaną zakończone, a wszystkie poprzednie prace nie zostaną zakończone. Zatem wczesny (lub oczekiwany) czas tp(i) i-tego zdarzenia jest określony przez czas trwania maksymalnej ścieżki poprzedzającej to zdarzenie:

t p (i) = max(t(L ni)) (1)

gdzie L ni jest dowolną ścieżką poprzedzającą i-te zdarzenie, to jest ścieżką od początku do i-tego zdarzenia w sieci.

Jeśli zdarzenie j ma kilka poprzednich ścieżek, a co za tym idzie kilka poprzednich zdarzeń i, to wygodnie jest znaleźć wczesną datę zakończenia zdarzenia j według wzoru:

t p (j) = maks. (2)

Opóźnienie w realizacji imprezy i w stosunku do jej wcześniejszego terminu nie będzie miało wpływu na czas realizacji imprezy finałowej (a tym samym na czas realizacji kompleksu robót) do sumy czasu realizacji tego zdarzenia i czas trwania (długość) maksimum ścieżek po nim podążających nie przekracza długości ścieżki krytycznej. Zatem późny (lub graniczny) termin t p (i) zakończenia i-tego zdarzenia jest równy:

t p (i) = t kp - max(t(L ci)) (3)

gdzie Lci jest dowolną ścieżką po i-tym zdarzeniu, tj. ścieżka od i-tego do końcowego zdarzenia sieciowego.

Jeżeli zdarzenie i ma kilka kolejnych ścieżek, a więc kilka kolejnych zdarzeń j, to spóźnioną datę zakończenia zdarzenia i można wygodnie znaleźć za pomocą wzoru:

t p (i) = min

Rezerwa czasu R(i) i-tego wydarzenia jest definiowana jako różnica między późną i wcześniejszą datą jego zakończenia:

R(i) = tp(i) - tp(i)

Zawieszenie wydarzenia wskazuje, jak długo wydarzenie może zostać opóźnione bez powodowania wydłużenia czasu trwania pakietu roboczego.

Zdarzenia krytyczne nie mają luzu czasowego, ponieważ każde opóźnienie w zakończeniu zdarzenia znajdującego się na ścieżce krytycznej spowoduje takie samo opóźnienie w zakończeniu zdarzenia końcowego. Tak więc, po ustaleniu wczesnego terminu końcowego zdarzenia w sieci, określamy w ten sposób długość ścieżki krytycznej.

Określając wczesny czas zdarzeń tp(i), poruszamy się po wykresie sieci od lewej do prawej i korzystamy ze wzorów (1), (2).

Obliczanie czasu wydarzeń.

Dla i=0 (zdarzenie początkowe), oczywiście tp(0)=0.

i=1: tp (1) = tp (0) + t(0,1) = 0 + 0 = 0.

i=2: t p (2) = t p (1) + t (1,2) = 0 + 8 = 8.

i=3: t p (3) = t p (1) + t (1,3) = 0 + 3 = 3.

i=4: max(t p (2) + t(2,4);t p (3) + t(3,4)) = max(8 + 6;3 + 3) = 14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i=6: max(t p (4) + t(4,6);t p (5) + t(5,6)) = max(14 + 5;14 + 3) = 19.

i=7: tp (7) = tp (6) + t(6,7) = 19 + 9 = 28.

i=8: max(t p (2) + t(2,8);t p (6) + t(6.8);t p (7) + t(7.8)) = max(8 + 18;19 + 5; 28 + 4 ) = 32.

i=9: max(t p (5) + t(5,9);t p (7) + t(7,9)) = max(14 + 2;28 + 4) = 32.

i=10: max(t p (4) + t(4,10);t p (7) + t(7,10);t p (9) + t(9,10)) = max(14 + 4;28 + 2; 32 + 0) = 32.

i=11: max(t p (8) + t(8,11);t p (10) + t(10,11)) = max(32 + 12;32 + 4) = 44.

Długość ścieżki krytycznej jest równa dacie wcześniejszego zakończenia zdarzenia końcowego 11: t kp =tp(11)=44

Określając późne terminy zakończenia zdarzeń t p (i), poruszamy się po sieci w odwrotnym kierunku, czyli od prawej do lewej i korzystamy ze wzorów (3), (4).

Dla i=11 (zdarzenie końcowe), późna data zdarzenia musi być równa jego wczesnej dacie (w przeciwnym razie zmieni się długość ścieżki krytycznej): t p (11)= t p (11)=44

i=10: t p (10) = t p (11) - t(10,11) = 44 - 4 = 40.

i=9: tp (9) = tp (10) - t(9,10) = 40 - 0 = 40.

Wszystkie wiersze zaczynające się od numeru 8 są przeglądane.

i=8: t p (8) = t p (11) - t(8,11) = 44 - 12 = 32.

Wszystkie wiersze zaczynające się od numeru 7 są przeglądane.

i=7: min(t p (8) - t(7.8);t p (9) - t(7.9);t p (10) - t(7.10)) = min(32 - 4;40 - 4;40 - 2 ) = 28.

i=6: min(t p (7) - t(6.7);t p (8) - t(6.8)) = min(28 - 9; 32 - 5) = 19.

Wszystkie wiersze zaczynające się od numeru 5 są przeglądane.

i=5: min(t p (6) - t(5,6);t p (9) - t(5.9)) = min(19 - 3;40 - 2) = 16.

i=4: min(t p (5) - t(4.5);t p (6) - t(4.6);t p (10) - t(4.10)) = min(16 - 0;19 - 5;40 - 4 ) = 14.

Wszystkie wiersze zaczynające się od numeru 3 są przeglądane.

i=3: t p (3) = t p (4) - t(3,4) = 14 - 3 = 11.

i=2: min(t p (4) - t(2,4));t p (8) - t(2,8)) = min(14 - 6; 32 - 18) = 8.

i=1: min(t p (2) - t(1,2);t p (3) - t(1,3)) = min(8 - 8;11 - 3) = 0.

(0,1): 0 - 0 = 0;

Tabela 1 - Obliczanie rezerwy wydarzeń

Numer wydarzenia	Czas wydarzenia: wczesny tp(i)	Daty wydarzenia: późne tp(i)	Rezerwa czasu, R(i)

Wypełnienie tabeli 2.

Lista prac i czas ich trwania zostaną przeniesione do drugiej i trzeciej kolumny. W takim przypadku praca powinna być zapisywana w kolumnie 2 kolejno: najpierw zaczynając od numeru 0, potem od numeru 1 itd.

W drugiej kolumnie wpisujemy liczbę charakteryzującą liczbę bezpośrednio poprzedzających prac (KPR) do wydarzenia, którym rozpoczyna się dana praca.

Tak więc dla pracy (1,2) w kolumnie 1 wstawiamy liczbę 1, ponieważ numer 1 kończy 1 pracę: (0,1).

Kolumnę 4 uzyskano z tabeli 1 (t p (i)). Kolumnę 7 otrzymuje się z tabeli 1 (t p (i)).

Wartości w kolumnie 5 uzyskuje się sumując kolumny 3 i 4.

W kolumnie 6 późne rozpoczęcie pracy definiuje się jako różnicę między późnym zakończeniem tych prac a ich czasem trwania (dane w kolumnie 3 odejmuje się od wartości z kolumny 7);

Zawartość kolumny 8 (pełna rezerwa czasu R(ij)) jest równa różnicy między kolumnami 6 i 4 lub kolumną 7 i 5. Jeżeli R(ij) jest równe zero, to praca jest krytyczna

Tabela 2 - Analiza modelu sieci w czasie

Praca (i,j)	Liczba poprzednich prac	Czas trwania	Wczesne daty: początek tijR.N.	Wczesne daty: kończące się tijР.О.	Późne daty: początek tijP.N.	Późne terminy: koniec tijP.O.	Rezerwy czasu: pełne RijP	Niezależna rezerwa czasu Rij	Prywatna rezerwa pierwszego rodzaju, Rij1	Rezerwa prywatna typu II, RijC

Należy zauważyć, że oprócz pełnej rezerwy czasu pracy istnieją jeszcze trzy rodzaje rezerw. Prywatny luz czasu pierwszego typu R 1 - część łącznego luzu czasu, o którą można wydłużyć czas pracy bez zmiany późnej daty jej zdarzenia początkowego. R 1 znajduje się według wzoru:

R(i,j)= R p (i,j) - R(i)

Drugi rodzaj luzu częściowego, czyli luzu wolnego Rc pracy (i, j) to część luzu całkowitego, o którą można wydłużyć czas pracy bez zmiany wcześniejszej daty jej zakończenia. Rc znajduje się według wzoru:

R(i,j)= Rn(i,j) - R(j)

Wartość zapasu wolnego czasu wykonywania wskazuje lokalizację zapasu czasu wymaganego do optymalizacji.

Niezależna rezerwa czasu Rn pracy (i, j) jest częścią całkowitej rezerwy uzyskanej na wypadek, gdy wszystkie poprzednie prace kończą się z opóźnieniem, a wszystkie kolejne prace rozpoczynają się wcześniej. Rn znajduje się według wzoru:

R(i,j)= Rp(i,j) - R(i) - R(j)

ścieżki krytycznej: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Czas trwania ścieżki krytycznej: 44

Znajdźmy współczynnik intensywności pracy przedostatniej pracy. Ponieważ długość ścieżki krytycznej wynosi 44, maksymalna ścieżka przez pracę (1,10) wynosi 32, zatem

K(1,10)=(32-28)/(44-28)=0,296.

4. Dostawca usług internetowych w małym mieście ma 5 dedykowanych kanałów obsługi. Obsługa jednego klienta zajmuje średnio 25 minut. System otrzymuje średnio 6 aczasów na godzinę. Jeśli nie ma wolnych kanałów, następuje odmowa. Określ charakterystykę usługi: prawdopodobieństwo awarii, średnią liczbę linii komunikacyjnych zajmowanych przez usługę, przepustowość bezwzględną i względną, prawdopodobieństwo świadczenia usługi. Znajdź liczbę dedykowanych kanałów, dla których względna przepustowość systemu będzie wynosić co najmniej 0,95. Załóżmy, że przepływy żądań i usług są najprostsze

Intensywność przepływu usług:

Intensywność obciążenia:

c \u003d l * t obs \u003d 6 * 25/60 \u003d 2,5

Intensywność obciążenia c=2,5 pokazuje stopień spójności między wejściowymi i wyjściowymi przepływami żądań kanału obsługi i określa stabilność systemu kolejkowania.

Prawdopodobieństwo, że usługa:

kanał 1 zajęty:

p 1 = z 1 / 1! p 0 = 2,5 1/1! * 0,0857 = 0,214

Zajęte są 2 kanały:

p 2 \u003d c 2 / 2! p 0 = 2,5 2 /2! * 0,0857 = 0,268

Zajęte są 3 kanały:

p 3 \u003d c 3 / 3! p 0 = 2,5 3 /3! * 0,0857 = 0,223

Zajęte są 4 kanały:

p 4 = z 4 / 4! p 0 = 2,5 4 /4! * 0,0857 = 0,139

Zajętych jest 5 kanałów:

p 5 = z 5 / 5! p 0 = 2,5 5 /5! * 0,0857 = 0,0697

Prawdopodobieństwo niepowodzenia to ułamek odrzucone wnioski:

Oznacza to, że 7% otrzymanych wniosków nie jest przyjmowanych do obsługi.

Prawdopodobieństwo obsługi zgłoszeń przychodzących-prawdopodobieństwo, że klient zostanie obsłużony:

W systemach z awariami zdarzenia awarii i konserwacji stanowią kompletną grupę zdarzeń, a więc:

p otwarte + p obs = 1

Względna przepustowość Q = p obs .

p obs \u003d 1 - p otk \u003d 1 - 0,0697 \u003d 0,93

W konsekwencji 93% otrzymanych wniosków zostanie obsłużonych. Średnia liczba kanałów zajmowanych przez usługę

n s \u003d s * p obs \u003d 2,5 * 0,93 \u003d 2,326 kanałów.

Średnie bezczynne kanały.

n pr \u003d n - n z \u003d 5 - 2,326 \u003d 2,7 kanałów.

Wskaźnik obłożenia kanału usług.

Dlatego system jest w 50% zajęty konserwacją.

Bezwzględna przepustowość

A \u003d pobs * l \u003d 0,93 * 6 \u003d 5,581 aplikacji / godzinę.

Średni czas bezczynności QS.

t pr \u003d potk * t obs \u003d 0,0697 * 0,417 \u003d 0,029 godziny.

Średnia liczba obsłużonych żądań.

L obs \u003d s * Q \u003d 2,5 * 0,93 \u003d 2,326 jednostek.

Średni czas przebywania wniosku w CMO(Formuła Little'a).

Liczba żądań odrzuconych w ciągu godziny: l * p 1 = 0,418 żądań na godzinę.

Nominalna wydajność QS: 5 / 0,417 = 12,002 aplikacji na godzinę.

Rzeczywista wydajność CMO: 5,581 / 12,002 = 47% wydajności nominalnej.

Określmy liczbę kanałów wymaganych do zapewnienia działania systemu z prawdopodobieństwem P ? 0,95

Aby to zrobić, znajdujemy n z warunku:

Obliczmy prawdopodobieństwo, że jeśli w systemie jest 6 kanałów i wszystkie są zajęte: