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 koniec ostatecznym.

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

ścieżki krytycznej - Pełna ścieżka. najdłuższa ze wszystkich ścieżek diagramu sieciowego 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 wystąpienia wydarzenia końcowego.

Pełne ścieżki mogą wychodzić poza krytyczną lub częściowo się z nią pokrywać. Te krótsze podróże nazywane są zrelaksowany. Ich cechy są. Że mają rezerwę czasu. Ścieżka krytyczna nie. Dla każdego i-tego zdarzenia wyznacza 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 zaistnienia tego zdarzenia, w którym możliwe jest jeszcze wykonanie wszystkich kolejnych prac, z zastrzeżeniem ustalonego terminu zaistnienia zdarzenia.

R ja – luzu na imprezę- okres czasu, o który można opóźnić wystąpienie tego zdarzenia bez naruszenia okresu rozwoju planowanego kompleksu jako całości. Zdefiniowany jako różnica między późnym ( t p ja) i wczesny ( t p ja) termin zakończenia tego wydarzenia.

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

Za każdą pracę tij) definiuje:

wczesna data rozpoczęcia (t w.d ij)- minimalny możliwy czas rozpoczęcia tych prac.

wcześniejsza data końcowa (t p.o. ij)- minimalny możliwy termin wykonania tej pracy, dla danego czasu trwania pracy

późna data rozpoczęcia (t b.s ij)- maksymalne dopuszczalne terminy rozpoczęcia tych prac

późna data końcowa (t p.o. ij)- maksymalne dopuszczalne terminy zakończenia tych prac, w których możliwe jest jeszcze wykonanie kolejnych prac z zachowaniem ustalonego terminu zaistnienia zdarzenia końcowego.

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

t r.n. ij = t p ja

t r.o. ij = t p ja + t ij

Data późnego zakończenia działania jest taka sama, jak późna data zdarzenia końcowego, a data późnego rozpoczęcia działania jest krótsza o czas trwania działania:

t po ij = t p jot

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

Pełna rezerwa czasu na wykonanie prac Rnij– maksymalny czas, o jaki można opóźnić rozpoczęcie lub wydłużyć czas pracy bez zmiany ustalonego terminu wystąpienia zdarzenia końcowego.

Czas wolny na pracę, wchodząca w skład rezerwy pełnej – to 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 kolejnych prac.

Zadania leżące na ścieżce krytycznej nie mają rezerw, ponieważ wszystkie rezerwy powstają w wyniku różnicy w czasie trwania ścieżki krytycznej i rozważanej.

Względnym wskaźnikiem charakteryzującym rezerwę czasu na wykonanie pracy jest ich współczynnik napięcia, który jest równy 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 segment jest częścią ścieżki krytycznej.

3.Obliczanie modeli sieci

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

Graficznie metoda obliczeniowa przeprowadzana jest bezpośrednio na wykresie i stosowana w przypadkach, gdy liczba zdarzeń jest niewielka. Aby to zrobić, każde koło jest podzielone na 4 sektory.

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

lewy sektor - wczesna data wydarzenia tpi

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

dół - numer zdarzenia

Metoda obliczania parametrów

1) Wczesny harmonogram wydarzeń . Za wcześniejszą datę zakończenia zdarzenia początkowego (pierwszego lub zerowego) przyjmuje się wartość równą zeru. Wczesne daty zakończenia wszystkich pozostałych wydarzeń są ustalane w ścisłej kolejności poprzez rosnącą liczbę wydarzeń. Aby określić datę wcześniejszego zakończenia dowolnego zdarzenia j, uwzględnia się wszystkie prace uwzględnione w tym zdarzeniu, dla każdego zadania datę wcześniejszego zakończenia zdarzenia końcowego określa się jako sumę daty wcześniejszego zakończenia zdarzenia początkowego robót i trwania tej pracy tij, z uzyskanych wartości wybierany jest maksymalny czas wcześniejszego zakończenia j-tego zdarzenia

t pj = (t pi +t ij) max i jest zapisywany na mapie (lewy sektor zdarzenia)

2) Późne daty wydarzeń . Za późną datę zakończenia zdarzenia końcowego przyjmuje się datę wcześniejszą. Obliczanie opóźnień zakończenia wszystkich pozostałych wydarzeń odbywa się w odwrotnej kolejności, według malejących numerów wydarzeń. Do ustalenia późnego terminu zakończenia poprzedniego wydarzenia i, uwzględniane są wszystkie prace powstałe w ramach i-tego wydarzenia. Dla każdego zadania obliczany jest ostateczny termin zakończenia zdarzenia początkowego t pi, jako różnica pomiędzy późną datą zakończenia ostatniego wydarzenia tej pracy t p j i czas trwania tej pracy tij.Z otrzymanej wartości wybierz minimalny czas opóźnienia zakończenia i-tego zdarzenia: t p ja = (t p jot - t ij)min i jest zarejestrowany w prawym sektorze.

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

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

5) Przy ustalaniu całkowitego zapasu czasu na pracę należy od liczby zapisanej w prawym sektorze zdarzenia końcowego odjąć liczbę zarejestrowaną w lewym sektorze zdarzenia początkowego i czas trwania samej pracy.

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

Wstępne dane:

Metoda tabelaryczna

Kody stanowisk w tabeli są zapisane w indeksie rosnącym I.

Kolumny 2 i 3 wypełniamy danymi pomocniczymi: kodami prac poprzednich i kolejnych. Dane te będą potrzebne do obliczeń. Jeżeli prace są wstępne, to znaczy nie ma prac wcześniejszych, lub końcowe, to znaczy nie ma prac kolejnych, wówczas w odpowiednich kolumnach umieszcza się myślniki. Może istnieć 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. Obliczenia przeprowadza się w dwóch przejściach przez wiersze tabeli. Pierwsza przechodzi przez rzędy od góry do dołu, w których wyliczane są najwcześniejsze daty pracy, a druga przechodzi przez linie od dołu do góry, w których wyliczane są późniejsze daty pracy.

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

Wcześniejszy początek odpoczynku można zdefiniować w ten sposób, że jeśli weźmiemy pod uwagę pracę 2.5, która ma zdarzenie początkowe 2, to jej wcześniejszy czas rozpoczęcia jest równy wcześniejszemu czasowi zakończenia pracy 12, ponieważ ma ona koniec zdarzenie 2. Wartość z kolumny 6 przepisuje się do kolumny 5. W kolumnie 2 podaje się kody prac poprzednich. Wcześniejsze zakończenie określa także wzór t r.o. ij = t pH ij + t ij

Jeżeli w kolumnie 2 wskazano, że daną pracę poprzedza więcej niż jedna praca (pracę 5.6 poprzedzają prace 2.5 i 3.5), wówczas należy wybrać wartość wcześniejszego rozpoczęcia spośród kilku opcji wartości (9 - do końca pracy 2,5 lub 13 - do końca pracy 3,5). Reguła wyboru odpowiada formule t p.n. ij = (t pi + t ij) maks , czyli wybierana 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ż wierszy tabeli od pracy zapisanej w ostatniej linii do pracy zapisanej w pierwszej linii pozwala określić wartości wskaźników późnej wydajności. Dla zadań, które nie mają kolejnych zadań (w kolumnie 3 - myślnik, na przykładzie pracy 46, 5,6) wartość ścieżki krytycznej wpisuje się w kolumnie późnego zakończenia (8). W przypadku tych zadań wartość późnego rozpoczęcia jest obliczana ze wzoru t a.s. ij t przez ij - t ij

Opóźnione zakończenie reszty można zdefiniować w ten sposób, że jeśli weźmiemy pod uwagę na przykład pracę 3.5, która ma zdarzenie końcowe 5, to czas jej późnego zakończenia jest równy opóźnionemu czasowi rozpoczęcia pracy 5.6, ponieważ ma ona koniec zdarzenie 5. Wartość z kolumny 7 przepisuje się w kolumnie 8. Kody kolejnych prac wskazane są w kolumnie 3. Późny start określa się także wzorem t a.s. ij t przez ij - t ij .

Jeżeli w kolumnie 3 wskazano, że po danym zadaniu następuje więcej niż jedno zadanie (po zadaniu 0.1 następują zadania 1.2 i 1.3), to należy wybrać wartość późnego zakończenia spośród kilku opcji (3 – wg. czas rozpoczęcia pracy 1,3 lub 7 - zgodnie z czasem rozpoczęcia 1,2), wybierana jest wartość minimalna (w przykładzie - 3). Późny start określa się według powyższego wzoru t a.s. ij t przez ij - t ij .

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

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

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

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

Wywoływana jest dowolna sekwencja działań sieciowych, w której zdarzenie końcowe każdego działania pokrywa się ze zdarzeniem rozpoczynającym następujące po nim działanie Poprzez.

Wywoływana jest ścieżka sieciowa, w której punkt początkowy jest taki sam jak zdarzenie początkowe, a punkt końcowy jest zdarzeniem końcowym kompletny.

Ścieżka od pierwotnego zdarzenia do dowolnego podjętego wydarzenia poprzedzone wydarzenie. Ścieżka, która poprzedza zdarzenie i ma najdłuższą długość, nazywana jest ścieżką maksymalnie poprzedni. Jest on oznaczony przez L 1 (i), a jego czas trwania wynosi t.

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

Nazywa się pełną ścieżkę o najdłuższej długości krytyczny. Nazywa się ścieżki inne niż ścieżka krytyczna zrelaksowany. Mają rezerwę czasu.

Działania na ścieżce krytycznej są wyróżnione grubymi lub podwójnymi liniami. Za główny parametr wykresu uważa się czas trwania ścieżki krytycznej.

Rozważmy algorytm wyznaczania ścieżki krytycznej na schemacie sieci z wykorzystaniem algorytmu metody programowania dynamicznego.

Posortujmy wierzchołki grafu według rang i ponumerujmy je od końca do początku. Umożliwi to dopasowanie numerów rang do etapów ruchu wstecz przy znajdowaniu warunkowo optymalnych kontroli na ostatnim, dwóch ostatnich i tak dalej. gradacja. Znalezienie ścieżki krytycznej będzie analizowane na przykładzie schematu sieci pokazanego na rys. 10.7.

Zgodnie z zasadą optymalności Bellmana o optymalnym sterowaniu na każdym etapie decyduje cel sterowania oraz stan na początku etapu. Stan systemu to zdarzenia leżące na szeregach. Aby ukończyć ostatnie wydarzenie 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 okręgach w punktach X 14 i X 15 podajemy maksymalny czas pracy na ostatnim etapie: X 14 5 , X 15 7 . Znajdźmy maksymalny czas pracy na dwóch ostatnich etapach. Stan układu na początku przedostatniego etapu wynika ze zdarzenia X 13. Maksymalny czas trwania ścieżki prowadzącej od X 13 do X 16 wynosi .

Dlatego liczbę 14 należy umieścić w okręgu obok zdarzenia X 13 i tak dalej. Realizując etapy od końca do początku, dowiadujemy się o długości ścieżki krytycznej t cr =96. Aby znaleźć samą ścieżkę krytyczną, przejdźmy przez proces obliczeń od zdarzenia początkowego X 1 do końcowego X 16 . Na pierwszym etapie (od początku) otrzymaliśmy liczbę 96, 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 to 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 daty zakończenia wydarzeń. Zastój w wydarzeniu

Wszystkie ścieżki różniące się czasem trwania od ścieżki krytycznej posiadają rezerwy czasu. Różnica między długością ścieżki krytycznej i dowolnej ścieżki niekrytycznej nazywana jest całkowitym luzem danej ścieżki niekrytycznej i jest oznaczana przez: .

wczesny termin zakończeniem zdarzenia nazywa się najwcześniejszy moment, w którym cała praca poprzedzająca to wydarzenie zostaje ukończona, tj. wyznaczany jest na podstawie czasu trwania maksymalnej ścieżki poprzedzającej zdarzenie, tj.:

Lub

Aby znaleźć wczesną datę zdarzenia j, należy znać ścieżkę krytyczną podgrafu skierowanego, na który składa się zbiór ścieżek poprzedzających dane zdarzenie j. Wczesny wyraz zdarzenia początkowego jest równy zeru: t p (1) = 0.

spóźniony termin wydarzenie zwany najpóźniejszym momentem w czasie, po upływie którego pozostaje dokładnie tyle czasu, ile jest konieczne do wykonania wszystkich prac następujących po tym zdarzeniu. Najpóźniejszy z dopuszczalnych terminów zakończenia wydarzenia, łącznie z czasem realizacji wszystkich kolejnych czynności, nie może przekraczać długości ścieżki krytycznej. Ostateczny termin zdarzenia oblicza się jako różnicę pomiędzy czasem trwania ścieżki krytycznej a czasem trwania maksimum ścieżek następujących po zdarzeniu:

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

Różnica pomiędzy późnym i wczesnym terminem zakończenia wydarzenia stanowi czas rezerwowy wydarzenia: . Przedział ten nazywany jest przedziałem swobody zdarzeń. Zapas zdarzenia pokazuje maksymalny dopuszczalny czas, o jaki zdarzenie może zostać przesunięte bez zwiększania ścieżki krytycznej.

Od kwoty określa czas trwania ścieżki o maksymalnej długości przechodzącej przez to zdarzenie, a następnie , tj. luz dowolnego zdarzenia jest równy pełnemu luzowi maksymalnej ścieżki przechodzącej przez to zdarzenie.

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

Aby obliczyć najwcześniejszy termin zdarzeń: , zastosuj formułę , biorąc pod uwagę wydarzenia w kolejności rosnącej liczbowo, od początkowej do końcowej, zgodnie z utworami objętymi tym wydarzeniem.

Opóźniony termin zakończenia zdarzeń oblicza się ze wzoru , zaczynając od zdarzenia końcowego, dla którego ( - numer zdarzenia końcowego), zgodnie z wynikającymi z niego zadaniami.

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

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

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

Zatem 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. Jest ona określana na podstawie najdłuższej ścieżki. Termin wcześniejszego zakończenia prac 6 =14 pokrywa się z czasem krytycznym kp – całkowitym czasem trwania prac leżących 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. Z dwóch zadań zawartych w zdarzeniu 6 , , o zadaniach (5, 6) determinowała długość ścieżki krytycznej, gdyż (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).

Obliczamy teraz późne daty zakończenia wydarzeń. Pozwalać . Zastosujmy metodę programowania dynamicznego. Wszystkie obliczenia zostaną przeprowadzone od zdarzenia końcowego do zdarzenia początkowego. Późne daty zakończenia wydarzeń to:

Ponieważ po zdarzeniu 5, aby ukończyć projekt, praca (5, 6) musi zostać ukończona przez 3 dni. Ze zdarzenia 4 wynikają dwa zadania, więc:

Zapas dla zdarzenia 2 to: . Rezerwy pozostałych zdarzeń są równe zeru, ponieważ zdarzenia te są krytyczne.

Daty wczesnego i późnego rozpoczęcia i zakończenia. Ustalanie rezerw czasu pracy. Pełna rezerwa czasu pracy.

Wydarzenie bezpośrednio poprzedzające tę pracę zostanie wywołane podstawowy i oznacz , oraz zdarzenie bezpośrednio po nim, - finał i wyznaczyć. Wtedy każda praca będzie oznaczona przez . Znając termin zakończenia zdarzeń, można określić parametry czasowe pracy.

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

Wczesny koniec pracy jest równa sumie wcześniejszego terminu zakończenia zdarzenia początkowego i czasu trwania tej pracy: Lub .

Późny koniec pracy zbiega się z późną datą zakończenia ostatniego wydarzenia: .

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

Ponieważ terminy wykonania prac mieszczą się w granicach określonych przez i , mogą posiadać różne rodzaje rezerw czasu.

Pełna rezerwa czasu pracy - jest to maksymalny czas potrzebny na wykonanie dowolnej pracy bez przekroczenia ścieżki krytycznej. Oblicza się go jako różnicę między późnym momentem końcowym a wczesnym czasem ukończenia samej pracy: . Skoro więc .

Zatem, 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 luz całkowity.

Rezerwa wolnego czasu pracy- jest to margines czasu, jakim można dysponować przy wykonywaniu tej pracy, pod warunkiem, że jej początkowe i końcowe zdarzenia wystąpią w najwcześniejszym terminie: .

Obliczenia wykresu sieci w sposób tabelaryczny dokonuje się według wzorów podanych wcześniej w ust. 4 (1-10). Przy wyznaczaniu parametrów modeli sieci w sposób analityczny obliczenia przeprowadza się w formie tabeli. Rozważ cechy obliczania modeli sieci w ten sposób (aplikacja 1) na przykładzie obliczania parametrów schematu sieci pokazanego w zadaniu z tego kursu (opcja 15).

Na początkowym etapie należy opisać wstępny model sieci. W tym przypadku szyfry wszystkich zadań i zależności wpisuje się w pierwszej kolumnie tabeli, zaczynając od zadania powstałego z pierwszego zdarzenia. Kody zadań należy umieszczać w tabeli sekwencyjnie, nie jest dozwolona dowolna kolejność umieszczania zadań i zależności w tabeli. 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 zeru (wzór 1), a jego wczesny koniec według wzoru 2.

Wcześniejsze rozpoczęcie działań 2-6 i 2-7 (zgodnie ze wzorem 3) jest równoznaczne z wcześniejszym zakończeniem działania 1-2.

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

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

Późne rozpoczęcie pracy 20-21 jest późnym zakończeniem pracy 15-20 (=), która ją poprzedza.

Ponadto obliczenia późnych parametrów przeprowadza 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, opóźnienie zakończenia prac 6-9 jest równe minimalnej wartości opóźnionego rozpoczęcia kolejnych prac 9-10 i 9-14.

Aby znaleźć położenie ścieżki krytycznej, należy określić wartości całkowitych i prywatnych rezerw czasu dla każdej pracy oraz zależności schematu sieci i wpisać ich wartości w 7. i 8. kolumnie obliczeń stół, odpowiednio.

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

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

Ścieżka krytyczna charakteryzuje się zerowym luzem. Porównanie parametrów modelu sieci uzyskanych metodą sektorową i tabelaryczną powinno wykazać ich pełną identyczność, obecność rozbieżności wskazuje na błędność obliczeń.

Graficzna metoda obliczania diagramów sieciowych

Obliczenia wykresu sieci w sposób graficzny przeprowadza się analogicznie do metody tabelarycznej (wzory 1-10), z tym że graficzna lub sektorowa metoda obliczania parametrów wykresu sieci polega na zapisaniu ich bezpośrednio na modelu (Załącznik 2). Każde wydarzenie (okrąg) jest podzielone na cztery sektory. Oznaczenie sektorów pokazano na poniższym rysunku:

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

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

• * ujawnił ciągłą ścieżkę krytyczną;
• * obliczone rezerwy czasu mają wartość nieujemną;
• * wartość zapasu prywatnego dla wszystkich stanowisk jest mniejsza lub równa wartości zapasu całkowitego dla tych stanowisk;
• * co najmniej jedna wartość opóźnienia rozpoczęcia prac (prac) wynikająca z pierwszego zdarzenia jest równa zeru.

Znane są dwa metoda obliczania parametrów wykresu sieciowego”. obliczenia bezpośrednio na wykresie sieci; analityczne (tabelaryczne).

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 wyznacza się czas trwania najdłuższej ścieżki od zdarzenia inicjującego do rozpoczęcia realizacji tej pracy,
  • ? wcześniejsze terminy zakończenia- jest to najwcześniejszy możliwy termin zakończenia prac. Czas wcześniejszego zakończenia pracy jest równy sumie czasu wcześniejszego rozpoczęcia pracy i czasu trwania samej pracy.
• 2.Obliczanie ścieżki krytycznej. Jego czas trwania definiuje się jako całkowity czas czynności na ścieżce krytycznej, tj. czas zakończenia całego kompleksu prac przy największej zbieżności wszystkich prac. Czas ten jest równy największemu z czasów wczesnego zakończenia uzupełniania grafu sieci. Ścieżka krytyczna przebiega przez zdarzenia, które nie mają rezerwy czasu (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 zakończenia prac, tak aby czas ścieżki krytycznej nie uległ zmianie. Dlatego logiczne jest przeprowadzenie obliczeń od ostatniego zdarzenia do pierwszego i najpierw określenie czasu spóźnionego zakończenia pracy, a następnie obliczenie czasu późnego rozpoczęcia pracy:
  • ?późna data rozpoczęcia (ja) definiuje się jako różnicę pomiędzy opóźnieniem w wykonaniu pracy a czasem trwania samej pracy,
  • ? późny termin zakończenia jest określany przez wartość ścieżki minimalnego czasu trwania prowadzącej do niej od zdarzenia końcowego i jest obliczany jako różnica między ścieżką krytyczną a maksymalnym czasem trwania pracy od zdarzenia końcowego diagramu sieciowego do końcowego zdarzenia tej pracy .
• 4. Obliczanie rezerw czasu”.

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

• ? prywatny (wolne) rezerwy czasu”.
• 1)prywatny luz pierwszego rodzaju określony przez możliwość zmiany czasu późnego startu ( ja) na terminy wcześniejsze bez zmiany przeterminowanych terminów wykonania bezpośrednio poprzedzających prac,
• 2) prywatny luz drugiego rodzaju zdeterminowana możliwością zmiany wcześniejszego zakończenia pracy (ij) w terminach późniejszych, bez zmiany wcześniejszych terminów rozpoczęcia bezpośrednio kolejnych prac; określa się na podstawie różnicy pomię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.

Do obliczenia parametrów użyjemy metody tabelarycznej, a aby uprościć postrzeganie, podsumujemy wszystko w jednej tabeli. 7.1.

Zasady wykorzystania rezerw czasu w planowaniu sieci.

• 1. Aby całkowite i częściowe rezerwy pracy (y) były równe, konieczne i wystarczające jest, aby zdarzenie końcowe Y danego dzieła było zdarzeniem na ścieżce krytycznej.
• 2. Jeśli pełna rezerwa (Ja i]1) części pracy jest równa zeru, wówczas rezerwa prywatna drugiego rodzaju (g „f) jest również równa zeru. Pomiędzy tymi rezerwami zawsze jest stosunek R(IJ) > r"ijy Rezerwy czasu całkowitego i prywatnego są zawsze większe lub równe zeru.
• 3. Aby częściowa rezerwa czasu pracy (y) była równa zeru, konieczne i wystarczające jest, aby praca ta leżała na ścieżce o maksymalnej długości od pierwszego zdarzenia do zdarzenia y.
• 4. Jeżeli czas pracy (y) zostanie zwiększony o p, tj. p wówczas wcześniejszy termin rozpoczęcia kolejnych prac wzrośnie o wartość p - g” („uu
• 5. Jeżeli czas trwania pracy (y) zostanie powiększony o kwotę całkowitej rezerwy 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 i minimum całkowitej rezerwy wszystkich bezpośrednio następujących po sobie prac.

Wyniki obliczeń parametrów schematu sieci

Tabela 7.1

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

7. Jeśli 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 rozpoczyna się jego optymalizację.

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

Rozwiązanie

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

Element sieciowy	Nazwa parametru	Symbol parametru
Wydarzenie I	Wcześniejszy termin zakończenia wydarzenia
Późny termin zakończenia wydarzenia
Zastój w wydarzeniu
Praca (i, j)	Czas pracy
Wczesny czas rozpoczęcia
Wczesny 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 czasu na zdarzenia sieci, obliczane są najwcześniejsze daty t p i najpóźniejsze daty t p zakończenia zdarzeń. Żadne zdarzenie nie może nastąpić, zanim nie zakończą się wszystkie poprzedzające je zdarzenia i nie zostaną zakończone wszystkie poprzednie prace. Zatem wczesny (lub oczekiwany) czas tp(i) i-tego zdarzenia wyznaczany jest 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, czyli ścieżką od początkowego do i-tego zdarzenia w sieci.

Jeżeli zdarzenie j ma kilka poprzednich ścieżek, a co za tym idzie kilka poprzednich zdarzeń i, to wygodnie jest znaleźć wcześniejszą datę zakończenia zdarzenia j, korzystając ze wzoru:

t p (j) = maks. (2)

Opóźnienie w ukończeniu wydarzenia i w stosunku do jego wcześniejszego terminu nie będzie miało wpływu na czas zakończenia wydarzenia końcowego (a co za tym idzie na czas zakończenia kompleksu robót) aż do sumy czasu zakończenia tego wydarzenia i czas trwania (długość) maksimum następujących po niej ścieżek 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ą następującą po i-tym zdarzeniu, tj. ścieżka od i-tego do ostatniego zdarzenia sieciowego.

Jeżeli zdarzenie i ma kilka kolejnych ścieżek, a co za tym idzie kilka kolejnych zdarzeń j, to datę późnego zakończenia zdarzenia i można wygodnie znaleźć korzystając ze wzoru:

t p (i) = min

Rezerwę czasu R(i) i-tego zdarzenia definiuje się jako różnicę pomiędzy późnym i wczesnym terminem jego zakończenia:

R(i) = t p (i) - t p (i)

Zapas wydarzenia pokazuje, jak długo można opóźnić wydarzenie, nie powodując wydłużenia czasu trwania pakietu pracy.

Zdarzenia krytyczne nie mają luzu, gdyż każde opóźnienie w ukończeniu zdarzenia na ścieżce krytycznej spowoduje takie samo opóźnienie w zakończeniu zdarzenia końcowego. Zatem, po ustaleniu wczesnego terminu końcowego zdarzenia w sieci, określamy w ten sposób długość ścieżki krytycznej.

Wyznaczając wczesny moment zdarzeń tp(i), poruszamy się po wykresie sieci od lewej do prawej, korzystając ze wzorów (1), (2).

Obliczanie czasu zdarzeń.

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

i=1: t p (1) = t p (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: t p (7) = t p (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

Przy ustalaniu późnych dat zakończenia zdarzeń t p (i) poruszamy się po sieci w odwrotnym kierunku, czyli od prawej do lewej, korzystając 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: t p (9) = t p (10) - t(9,10) = 40 - 0 = 40.

Przeglądane są wszystkie linie zaczynające się od cyfry 8.

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

Przeglądane są wszystkie linie zaczynające się od cyfry 7.

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.

Przeglądane są wszystkie linie zaczynające się od cyfry 5.

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.

Przeglądane są wszystkie linie zaczynające się od cyfry 3.

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 zdarzeń

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

Wypełnianie tabeli 2.

Lista prac i czas ich trwania zostaną przeniesione do drugiej i trzeciej kolumny. W takim przypadku pracę należy wpisać w kolumnie 2 kolejno: najpierw zaczynając od cyfry 0, potem od cyfry 1 itd.

W drugiej kolumnie wpisujemy liczbę charakteryzującą liczbę utworów bezpośrednio poprzedzających wydarzenie, od którego rozpoczyna się dane dzieło.

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

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

Wartości w kolumnie 5 uzyskuje się poprzez zsumowanie kolumn 3 i 4.

W kolumnie 6 opóźnienie rozpoczęcia prac definiuje się jako różnicę pomiędzy opóźnieniem zakończenia tych prac a czasem ich trwania (dane w kolumnie 3 odejmuje się od wartości z kolumny 7);

Zawartość kolumny 8 (luz całkowity R(ij)) jest równa różnicy pomię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 tij	Wczesne daty: początek tijR.N.	Wczesne daty: zakończenie tijР.О.	Daty późne: początek tijP.N.	Późne daty: koniec tijP.O.	Rezerwy czasu: pełne RijP	Samodzielna rezerwa czasu Rij	Rezerwat prywatny I rodzaju, Rij1	Rezerwat prywatny typu II, RijC

Należy zauważyć, że oprócz pełnej rezerwy czasu pracy istnieją jeszcze trzy rodzaje rezerw. Przerwa czasowa prywatna pierwszego rodzaju R 1 – część całkowitego luzu czasowego, o który można wydłużyć czas pracy bez zmiany późniejszej daty jej zdarzenia początkowego. R 1 można znaleźć według wzoru:

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

Zapas częściowy drugiego rodzaju, czyli wolny luz 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 oblicza się ze wzoru:

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

Wartość wolnego czasu działania wskazuje lokalizację luzu wymaganą do optymalizacji.

Niezależna rezerwa czasu Rn pracy (i, j) stanowi część całkowitej rezerwy uzyskanej w przypadku, gdy cała poprzednia praca kończy się z opóźnieniem, a każda kolejna rozpoczyna się wcześniej. Rn oblicza się ze wzoru:

R(i,j)= Rο(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 pracy (1,10) wynosi 32, zatem

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

4. Dostawca usług internetowych w małym miasteczku ma 5 dedykowanych kanałów usług. Obsługa jednego klienta zajmuje średnio 25 minut. System otrzymuje średnio 6 aczasów na godzinę. W przypadku braku bezpłatnych 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 usługi. Znajdź liczbę kanałów dedykowanych, 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 pomiędzy przepływami wejściowymi i wyjściowymi żądań kanałów usługowych oraz określa stabilność systemu kolejkowego.

Prawdopodobieństwo, że usługa:

kanał 1 zajęty:

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

2 kanały są zajęte:

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

5 kanałów jest zajętych:

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

Prawdopodobieństwo niepowodzenia jest ułamkiem odrzucone wnioski:

Oznacza to, że 7% otrzymanych wniosków nie zostaje przyjętych do obsługi.

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

W systemach z awariami zdarzenia awaryjno-obsługowe 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 rezultacie 93% otrzymanych wniosków zostanie zrealizowanych. Średnia liczba kanałów zajętych przez usługę

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

Średnie nieaktywne kanały.

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

Wskaźnik wykorzystania 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 p otk * 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 jednostki.

Średni czas przebywania wniosku w CMO(wzór Little’a).

Liczba wniosków odrzuconych w ciągu godziny: l * p 1 = 0,418 wniosków 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 sprawności systemu z prawdopodobieństwem P ? 0,95

Aby to zrobić, znajdujemy n z warunku:

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