Výpočet a analýza sieťových diagramov. Skorý dátum udalosti

Základné parametre sieťového diagramu

Medzi hlavné parametre sieťového diagramu patria:

Kritická cesta

Časové rezervy na akcie

Časové rezervy na dokončenie prác

Cesta – postupnosť úloh, v ktorých sa posledná udalosť jednej úlohy zhoduje s počiatočnou udalosťou inej.

Úplná cesta – cesta, ktorej začiatok je počiatočná udalosť a ktorej koniec je záverečná udalosť.

Trvanie, dĺžka cesty, sa rovná súčtu trvania prác. Jeho komponenty.

Kritická cesta - úplná cesta. najdlhšia zo všetkých ciest v sieťovom diagrame od počiatočnej udalosti (I) po konečnú (C).

Dĺžka kritickej cesty určuje celkové trvanie celého pracovného balíka. Kritická cesta vám umožňuje nájsť načasovanie poslednej udalosti.

Úplné cesty môžu prechádzať mimo kritickej cesty alebo sa s ňou čiastočne zhodovať. Tieto kratšie cesty sú tzv uvoľnený. Ich vlastnosti sú: Že majú časové rezervy. Ale kritická cesta nie je. Pre každú i-tú udalosť sa určuje nasledovné:

tpi– skorý nástup– minimálny možný čas vzniku tejto udalosti pri danom trvaní práce.

t p i– neskorý nástup– maximálny časový úsek pre vznik danej udalosti, v ktorom je ešte možné vykonať všetky nasledujúce práce pri dodržaní ustanoveného časového obdobia pre vznik udalosti.

RI – rezervujte si čas na podujatie– časový úsek, o ktorý je možné oddialiť nástup tejto udalosti bez narušenia doby rozvoja plánovaného komplexu ako celku. Definované ako rozdiel medzi neskorými ( t p i) a skoro ( t r i) načasovanie udalosti.

Rezervy pre udalosť kritickej cesty sa rovnajú nule, pretože na nej t p i = t p i

Pre každú prácu ( t ij) je určený:

skorý dátum začiatku (t р.н. ij)– minimálny možný dátum začatia tejto práce.

dátum skorého ukončenia (t p.o. ij)– minimálny možný termín dokončenia tejto práce počas daného trvania práce

neskorý dátum začiatku (t bp ij)– maximálny povolený dátum začatia tejto práce

neskorý dátum ukončenia (t p.o. ij)– maximálny prípustný termín dokončenia tohto diela, v ktorom je ešte možné vykonať nasledujúce práce pri dodržaní ustanoveného termínu ukončenia akcie.

Je zrejmé, že dátum skorého začatia úlohy sa zhoduje s dátumom skorého začatia jej počiatočnej udalosti a dátum skorého ukončenia ho presahuje o trvanie úlohy:

t р.н. ij = t r i

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

Neskorý dátum ukončenia úlohy sa zhoduje s neskorým dátumom jej ukončenia a neskorý dátum začatia úlohy je kratší ako trvanie úlohy:

t p.o. ij = t p j

t p.n. ij = t p j – t ij

Úplná časová rezerva na dokončenie práce R nij– maximálny časový úsek, o ktorý možno odložiť začiatok alebo predĺžiť trvanie prác bez zmeny stanoveného termínu ukončenia.

Voľná ​​časová rezerva na dokončenie prác, ktorá je súčasťou plnej rezervy - maximálny časový úsek, o ktorý je možné odložiť začiatok prác alebo predĺžiť trvanie prác bez toho, aby sa zmenili dátumy predčasného začatia následných prác.

Činnosti ležiace na kritickej ceste nemajú rezervy, pretože všetky rezervy sa vytvárajú z dôvodu rozdielov v trvaní kritických a uvažovaných ciest.

Relatívny ukazovateľ charakterizujúci časovú rezervu na výkon práce je ich koeficient napätia,čo sa rovná pomeru trvania úsekov cesty medzi rovnakými udalosťami, navyše jeden úsek je súčasťou cesty maximálneho trvania všetkých ciest prechádzajúcich daným dielom a druhý úsek je súčasťou kritickej cesty.

3.Výpočet sieťových modelov

Parametre siete pre sieťové diagramy sa počítajú grafickými a tabuľkovými metódami a pre komplexné matematickými metódami.

Graficky sa metóda výpočtu vykonáva priamo na grafe a používa sa v prípadoch, keď je počet udalostí malý. Na tento účel je každý kruh rozdelený na 4 sektory.

Horný sektor – rezerva času na uskutočnenie udalosti RI

ľavý sektor – skorý dátum vzniku udalosti tpi

pravý sektor – neskorý dátum vzniku udalosti t p i

nižšie – číslo udalosti

Spôsob výpočtu parametrov

1) Skoré načasovanie udalostí . Predpokladá sa, že skorý dátum dokončenia počiatočnej (prvej alebo nulovej) udalosti je nula. Skoré dátumy dokončenia všetkých ostatných podujatí sa určujú v prísnom poradí podľa narastajúceho počtu podujatí. Na určenie dátumu skorého dokončenia akejkoľvek udalosti j sa berie do úvahy všetka práca zahrnutá v tejto udalosti; pre každú úlohu sa dátum skorého dokončenia poslednej udalosti určuje ako súčet dátumu skorého dokončenia počiatočnej pracovnej udalosti a trvania. tohto diela t ij, Zo získaných hodnôt sa vyberie maximálny skorý čas j-tej udalosti

t pj = (t pi + t ij) max a je zaznamenané v grafe (ľavý sektor udalosti)

2) Neskoré načasovanie udalostí . Predpokladá sa, že neskorý dátum dokončenia záverečnej udalosti sa rovná jej skoršiemu dátumu. Výpočet posledných termínov na dokončenie všetkých ostatných podujatí sa vykonáva v opačnom poradí podľa zostupných čísel podujatí. Na určenie neskorého termínu dokončenia predchádzajúceho podujatia i sa zohľadňujú všetky práce vyplývajúce z i-tého podujatia. Pre každú úlohu sa vypočíta neskorý dátum dokončenia počiatočnej udalosti t p i, ako rozdiel medzi neskorým termínom dokončenia záverečnej akcie tohto diela t p j a trvanie tejto práce t ij.Zo získanej hodnoty vyberte minimálny čas neskorého dokončenia i-tej udalosti: t p i = (t p j - t ij) min a je zaznamenaný v pravom sektore.

3) Trvanie kritickej cesty rovná skorému dátumu ukončenia.

4) Časové rezervy podujatí . Pri určovaní časových rezerv na udalosti treba číslo napísané v ľavom sektore odpočítať od čísla napísaného v pravom sektore daného podujatia a umiestniť do horného sektora.

5) Pri určovaní celkovej rezervy času na prácu by ste mali odpočítať od čísla napísaného v pravom sektore záverečnej udalosti, čísla napísaného v ľavom sektore počiatočnej udalosti a trvania samotnej práce.

6) Pri určovaní voľnej rezervy na prácu by ste mali odpočítať od čísla napísaného v ľavom sektore záverečnej udalosti, čísla napísaného v ľavom sektore počiatočnej udalosti a trvania samotnej práce.

Počiatočné údaje:

Tabuľková metóda

Kódy úloh v tabuľke sú zapísané vo vzostupnom indexovom poradí i.

Stĺpce 2 a 3 sú vyplnené pomocnými údajmi: kódmi predchádzajúcej a následnej práce. Tieto údaje budú potrebné pre výpočty. Ak je dielo počiatočné, to znamená, že neexistujú žiadne predchádzajúce diela, alebo konečné, to znamená, že neexistujú žiadne následné diela, do príslušných stĺpcov sa umiestnia pomlčky. Môže existovať niekoľko predchádzajúcich a nasledujúcich diel v súlade s počtom vektorov končiacich alebo začínajúcich v danej udalosti./

Stĺpec 4 obsahuje hodnoty trvania práce.

Vypočítané údaje začínajú v stĺpci 5. Výpočet sa vykonáva v dvoch prechodoch cez riadky tabuľky. Prvý prechod po riadkoch zhora nadol, v ktorom sa počítajú skoré termíny prác, a druhý prechod po riadkoch zdola nahor, v ktorom sa počítajú neskoré termíny prác.

Skorý začiatok práce, ktorý nemá žiadne predchádzajúce (v stĺpci 2 - pomlčka), možno považovať za 0, pokiaľ nie je špecifikovaná iná hodnota. Predčasné dokončenie práce sa určuje podľa vzorca t p.o. ij = t pH ij + t ij a je zaznamenaný v stĺpci 6.

Skorý začiatok odpočinku možno definovať tak, že ak sa uvažuje napríklad o práci 2.5, ktorá má počiatočnú udalosť 2, potom sa čas jej skorého začiatku rovná času predčasného ukončenia práce 12, keďže má koncovú udalosť 2. Hodnota zo stĺpca 6 sa prepíše do stĺpca 5 Kódy predchádzajúcej práce sú uvedené v stĺpci 2. Predčasné ukončenie je tiež určené vzorcom t p.o. ij = t pH ij + t ij

Ak je v stĺpci 2 uvedené, že určitej úlohe predchádza viac ako jedna úloha (úlohám 5,6 predchádza úlohy 2,5 a 3,5), potom musíte vybrať hodnotu skorého spustenia z niekoľkých možností hodnôt (9 - podľa času ukončenia práce 2,5 alebo 13 - podľa času ukončenia práce 3,5). Pravidlo výberu zodpovedá vzorcu t p .n. ij = (t pi +t ij) max , to znamená, že je zvolená maximálna hodnota (v príklade - 16). Skoré konce sú definované ako vyššie.

Maximálna hodnota predčasného ukončenia v stĺpci 6 zodpovedá hodnote trvania kritickej cesty (16).

Druhý prechod po riadkoch tabuľky od práce zaznamenanej v poslednom riadku k práci zaznamenanej v prvom riadku vám umožňuje určiť hodnoty neskorších ukazovateľov činností. Pri úlohách, ktoré nemajú následné úlohy (v stĺpci 3 je pomlčka, v príklade úloh 46, 5,6), sa hodnota kritickej cesty zapíše do stĺpca neskorého dokončenia (8). Pre tieto úlohy sa hodnota neskorého začiatku vypočíta pomocou vzorca t p.n. ij t podľa ij - t ij

Neskoré ukončenie zvyšku je možné určiť tak, že ak sa uvažuje napríklad o práci 3.5, ktorá má ukončenie 5, potom sa čas jej neskorého ukončenia rovná času neskorého začiatku práce 5,6 , pretože má koncovú udalosť 5. Hodnota zo stĺpca 7 sa prepíše do stĺpca 8. Kódy pre následnú prácu sú uvedené v stĺpci 3. Neskorý začiatok je tiež určený vzorcom t p.n. ij t podľa ij - t ij .

Ak je v stĺpci 3 uvedené, že po určitej úlohe nasleduje viac ako jedna úloha (po práci 0,1 nasledujú úlohy 1,2 a 1,3), potom musíte vybrať hodnotu neskorého dokončenia z niekoľkých možností hodnôt (3 - podľa času začiatku práce 1 ,3 alebo 7 – podľa času začiatku práce 1,2) je zvolená minimálna hodnota (v príklade – 3). Neskorý nástup je určený vyššie uvedeným vzorcom t p.n. ij t podľa ij - t ij .

Hodnota celkového času uvoľnenia (stĺpec 9) sa vypočíta pomocou vzorca

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

Hodnota rezervy voľného času (stĺpec 10) sa vypočíta podľa vzorca

R с ij = t ро ij - t рр ij - t ij

Akákoľvek postupnosť aktivít v pláne siete, v ktorej sa koncová udalosť každej aktivity zhoduje so začiatočnou udalosťou aktivity, ktorá po nej nasleduje, sa nazýva podľa.

Sieťová cesta, v ktorej sa počiatočný bod zhoduje s počiatočnou udalosťou a koncový bod sa zhoduje s koncovou udalosťou, sa nazýva plný.

Cesta od pôvodnej udalosti k akejkoľvek zvolenej predchádzalo na túto udalosť. Najdlhšia cesta predchádzajúca udalosti sa nazýva maximálne predchádzajúce. Označuje sa L 1 (i) a jeho trvanie je t.

Cesta spájajúca akúkoľvek uskutočnenú udalosť s konečnou sa nazýva následné spôsobom. Cesta s najdlhšou dĺžkou je tzv maximálne následne a označuje sa L 2 (i) a jeho trvanie je t.

Úplná cesta s najväčšou dĺžkou sa nazýva kritický. Nazývajú sa cesty iné ako kritická cesta uvoľnený. Majú časové rezervy.

Aktivity kritickej cesty sú zvýraznené tučnými alebo dvojitými čiarami. Trvanie kritickej cesty sa považuje za hlavný parameter harmonogramu.

Uvažujme o algoritme na určenie kritickej cesty v sieťovom diagrame pomocou algoritmu metódy dynamického programovania.

Usporiadajme vrcholy grafu podľa poradia a očíslujme ich od konca po začiatok. To umožní kombinovať poradové čísla s fázami spätného pohybu pri hľadaní podmienene optimálnych ovládacích prvkov na poslednom, dvoch atď. etapy. Pozrime sa na nájdenie kritickej cesty pomocou príkladu sieťového diagramu znázorneného na obr. 10.7.

Podľa Bellmanovho princípu optimality je optimálne riadenie v každom štádiu určené cieľom riadenia a stavom na začiatku štádia. Stav systému sú udalosti ležiace na radoch. Na uskutočnenie záverečnej udalosti X 16 je potrebné dokončiť predchádzajúce udalosti. Možné stavy systému na začiatku poslednej etapy práce sú ukončenie udalostí X 14 a X 15. V kruhoch v bodoch X 14 a X 15 uvádzame maximálne trvanie práce na poslednej etape: X 14 5, X 15 7. Nájdite maximálne trvanie práce v posledných dvoch etapách. Stav systému na začiatku predposlednej etapy určuje udalosť X 13. Maximálne trvanie cesty vedúcej z X 13 do X 16 sa rovná .

Preto do kruhu vedľa udalosti X 13 musíte zadať číslo 14 atď. Vykonaním etáp od konca po začiatok zistíme dĺžku kritickej dráhy tcr =96. Aby sme našli samotnú kritickú cestu, prejdeme procesom výpočtu od počiatočnej udalosti X 1 po konečnú udalosť X 16. Číslo 96 sme dostali v prvej fáze (od začiatku) pripočítaním 16 k číslu 80. Preto sa kritická cesta v tejto fáze bude rovnať (X 1, X 3). Číslo 80 = 16 + 64. Preto kritická cesta v druhom štádiu prechádza prácou (X 3, X 4) atď. V grafe je zvýraznený hrubou čiarou:

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

Skoré a neskoré načasovanie udalostí. Časová rezerva podujatia

Všetky cesty, ktoré sa trvaním líšia od kritickej, majú časové rezervy. Rozdiel medzi dĺžkou kritickej cesty a akoukoľvek nekritickou cestou sa nazýva celkový čas uvoľnenia tejto nekritickej cesty a označuje sa: .

Skorý termín dokončenie udalosti sa nazýva najskorší časový bod, ktorým sú ukončené všetky práce predchádzajúce tejto udalosti, t.j. je určená dobou trvania maximálnej cesty pred udalosťou, t.j.

alebo

Ak chcete nájsť skorý dátum udalosti j, musíte poznať kritickú cestu smerovaného podgrafu pozostávajúceho zo súboru ciest predchádzajúcich tejto udalosti j. Skorý dátum počiatočnej udalosti je nula: t p (1) = 0.

Neskoro dokončenie udalosti je posledný časový bod, po ktorom zostáva presne toľko času, koľko je potrebné na dokončenie všetkých prác po tejto udalosti. Najneskorší prijateľný čas výskytu udalosti spolu s trvaním všetkých nasledujúcich prác nesmie presiahnuť dĺžku kritickej cesty. Neskorý dátum udalosti sa vypočíta ako rozdiel medzi trvaním kritickej cesty a trvaním maximálnej cesty po udalosti:

Pre udalosti ležiace na kritickej ceste sa skoré a neskoré dátumy dokončenia týchto udalostí zhodujú.

Rozdiel medzi neskorým a skorým dátumom podujatia predstavuje rezervačný čas podujatia: . Interval sa nazýva interval voľnosti udalosti. Čas nečinnosti udalosti ukazuje maximálny povolený čas, o ktorý možno posunúť moment jej výskytu bez zvýšenia kritickej cesty.

Od čiastky určuje trvanie dráhy maximálnej dĺžky prechádzajúcej týmto dejom, potom, t.j. Časová rezerva akéhokoľvek podujatia sa rovná plnej časovej rezerve maximálnej trasy prechádzajúcej týmto podujatím.

Pri manuálnom výpočte časových parametrov je vhodné použiť štvorsektorovú metódu. Pri tejto metóde je kruh sieťového diagramu označujúci udalosť rozdelený do štyroch sektorov. Horný sektor obsahuje číslo udalosti; vľavo - najskorší možný čas udalosti (); vpravo - posledný prípustný čas udalosti; v dolnom sektore - časová rezerva tohto podujatia: .

Na výpočet skorého dátumu udalostí: , použite vzorec , berúc do úvahy udalosti vo vzostupnom poradí čísel, od počiatočného po konečné, podľa diel zahrnutých v tejto udalosti.

Neskorý dátum udalostí sa vypočíta pomocou vzorca , počnúc záverečnou udalosťou, pre ktorú ( je číslo záverečnej udalosti) podľa diel, ktoré z nej vychádzajú.

Kritické udalosti majú nulovú rezervu. Definujú kritické činnosti a kritickú cestu.

Príklad 10.2. Nech je uvedený sieťový diagram znázornený na obr. 10.8.

Riešenie. Vypočítajme skoré dátumy udalostí:

Takže záverečná udalosť môže nastať až 14. deň od začiatku projektu. Toto je maximálny čas, za ktorý je možné dokončiť všetky práce na projekte. Určuje sa podľa najdlhšej dráhy. Skorý termín ukončenia prác 6 =14 sa zhoduje s kritickým časom kr - celkovým trvaním prác ležiacich na kritickej ceste. Teraz môžete zvýrazniť prácu, ktorá patrí do kritickej cesty, a vrátiť sa z koncovej udalosti do začiatočnej udalosti. Z dvoch úloh zahrnutých do udalosti 6 dĺžka kritickej cesty určila úlohy (5, 6), keďže (5 + 56)=14. Preto je kritická práca (5, 6) atď. Práce (1, 3), (3, 4), (4, 5), (5, 6) určili kritickú cestu: kr = (1-3-4-5-6).

Poďme teraz vypočítať neskoršie dátumy udalostí. Dajme tomu. Využime metódu dynamického programovania. Všetky výpočty sa vykonajú od záverečnej udalosti po počiatočnú udalosť. Najneskoršie dátumy konania podujatí sú:

Keďže po udalosti 5, na dokončenie projektu, musíte dokončiť prácu (5, 6) v trvaní 3 dní. Z udalosti 4 vychádzajú dve úlohy, takže:

Čas uvoľnenia pre udalosť 2 je: . Rezervy na zostávajúce udalosti sú nulové, pretože tieto udalosti sú kritické.

Skorý a neskorý dátum začiatku a konca práce. Stanovenie rezerv pracovného času. Plná rezerva pracovného času.

Udalosť bezprostredne predchádzajúca tomuto dielu bude tzv počiatočné a označujú , a udalosť, ktorá za ním bezprostredne nasleduje, je Konečný a určiť . Akékoľvek dielo potom označíme . Vďaka znalosti načasovania udalostí je možné určiť časové parametre práce.

Dátum skorého začiatku rovná skorému dátumu udalosti: .

Predčasný dátum dokončenia sa rovná súčtu skorého obdobia dokončenia počiatočnej udalosti a trvania tejto práce: alebo .

Neskorý termín ukončenia prác sa zhoduje s neskorým dátumom dokončenia jeho záverečnej udalosti: .

Neskorý dátum začiatku sa rovná rozdielu medzi neskorým dátumom dokončenia jeho poslednej udalosti a množstvom tejto práce:

Keďže termíny dokončenia prác sú v medziach určených a, môžu mať rôzne druhy časových rezerv.

Plná prevádzková časová rezerva - je to maximálny čas potrebný na dokončenie akejkoľvek úlohy bez prekročenia kritickej cesty. Vypočíta sa ako rozdiel medzi neskorým termínom dokončenia záverečnej akcie a skorým termínom dokončenia samotnej práce: . Odvtedy.

teda plná prevádzková časová rezerva je maximálny čas, o ktorý možno predĺžiť jeho trvanie bez zmeny trvania kritickej cesty. Každá práca, ktorá nie je kritická, má iný čas než nula.

Bezplatná rezerva pracovného času- toto je množstvo času, ktoré môže byť k dispozícii pri vykonávaní tejto práce za predpokladu, že jej počiatočné a konečné udalosti nastanú v ich najskoršom termíne: .

Sieťový diagram sa vypočítava tabuľkovým spôsobom pomocou vzorcov uvedených v časti 4 (1-10). Pri analytickom určovaní parametrov sieťových modelov sa výpočet vykonáva vo forme tabuľky. Uvažujme o vlastnostiach výpočtu sieťových modelov pomocou tejto metódy (aplikácia 1) na príklade výpočtu parametrov sieťového diagramu znázorneného v zadaní tejto seminárnej práce (možnosť 15).

V počiatočnej fáze je potrebné opísať počiatočný model siete. V tomto prípade sa kódy všetkých úloh a závislostí zadajú do prvého stĺpca tabuľky, počnúc úlohou pochádzajúcou z prvej udalosti. Kódy úloh musia byť do tabuľky zahrnuté postupne, ľubovoľné poradie zaraďovania úloh a závislostí do tabuľky je neprijateľné. Druhý stĺpec tabuľky obsahuje trvanie všetkých aktivít a závislostí.

Výpočet sieťového diagramu začína určením hodnôt parametrov ranej práce. Skorý začiatok práce 1-2 sa rovná nule (vzorec 1) a jej skorý koniec podľa vzorca 2.

Skorý začiatok prác 2-6 a 2-7 (v súlade so vzorcom 3) sa rovná skorému ukončeniu prác 1-2.

Maximálna hodnota skorého dokončenia úlohy 19-21, ktorá sa rovná 36, určuje trvanie kritickej cesty, a teda aj celkové trvanie vykonávania všetkých úloh v pôvodnom sieťovom modeli. Výsledná hodnota predčasného dokončenia tejto práce 19-21 = 36 sa prenesie do stĺpca neskoré ukončenie záverečnej práce 20-21.

Neskorý začiatok práce 20-21 sa určuje podľa vzorca 5 (= 34)

Neskorý začiatok práce 20-21 je neskorým ukončením predchádzajúcej práce 15-20 (=).

Ďalej sa výpočet neskorších parametrov vykonáva rovnakým spôsobom, s výnimkou prípadov, keď má úloha niekoľko nasledujúcich úloh (napríklad úloha 6-9 má dve nasledujúce - 9-10 a 9-14). V tomto prípade sa v súlade so vzorcom 4 neskoré ukončenie prác 6-9 rovná minimálnej hodnote neskorého začiatku nasledujúcich prác 9-10 a 9-14.

Na nájdenie polohy kritickej cesty je potrebné určiť hodnoty celkového a súkromného nevyužitého času pre každú úlohu a závislosť sieťového diagramu a zadať ich hodnoty do stĺpcov 7 a 8 výpočtovej tabuľky. .

Celková rezerva pracovného času podľa vzorcov 8-9 je definovaná ako rozdiel medzi neskorým a skorým ukončením alebo ako rozdiel medzi neskorým a skorým začiatkom príslušnej práce. Hodnotu celkovej nevyužitosti je užitočné určiť pomocou oboch metód, zhodu získaných hodnôt možno považovať za dodatočnú kontrolu. Napríklad pre prácu 6-7:

Čiastočná rezerva pracovného času podľa vzorca 10 je definovaná ako rozdiel medzi hodnotou skorého začiatku nasledujúcej práce a hodnotou skorého ukončenia tejto práce. Napríklad pre prácu 6-7:

Kritická dráha je charakterizovaná nulovým časom uvoľnenia. Porovnanie parametrov sieťového modelu získaných sektorovými a tabuľkovými metódami by malo odhaliť ich úplnú identitu, prítomnosť nezrovnalostí naznačuje, že výpočty sú chybné.

Grafická metóda na výpočet sieťových diagramov

Grafický výpočet sieťového diagramu sa vykonáva podobne ako tabuľková metóda (vzorce 1-10), avšak grafická alebo sektorová metóda výpočtu parametrov sieťového diagramu zahŕňa ich zaznamenanie priamo na modeli (Príloha 2). V tomto prípade je každá udalosť (kruh) rozdelená do štyroch sektorov. Označenie sektorov je znázornené na nasledujúcom obrázku:

Pre aktivity na kritickej ceste sú hodnoty celkového a súkromného floatingu rovné nule, na sieťovom diagrame je to zvýraznené dvojitou čiarou.

Ak chcete skontrolovať správnosť vykonaných výpočtov, mali by ste sa uistiť, že:

• * bola identifikovaná súvislá kritická cesta;
• * vypočítané časové rezervy majú nezápornú hodnotu;
• * hodnota súkromnej časovej rezervy pre všetky zamestnania je menšia alebo rovná hodnote všeobecnej časovej rezervy pre tieto zamestnania;
• * aspoň jedna hodnota neskorého začiatku úloh (úloh) pochádzajúcich z prvej udalosti je nula.

Známe sú dve metóda na výpočet parametrov sieťového grafu“. výpočet priamo na sieťovom grafe; analytické (tabuľkové).

Kalkulácia hlavné ukazovatele sieťového modelu môže vyrábať nasledovne.

• 1. Výpočet skorých dátumov:
  • ? skorý začiatok práce určená dĺžkou najdlhšej cesty od počiatočnej udalosti po začiatok tejto práce,
  • ? termíny skorého dokončenia- Toto je najskorší možný termín ukončenia prác. Čas skorého začiatku práce sa rovná súčtu času skorého začiatku práce a trvania samotnej práce.
• 2.Výpočet kritickej cesty. Jeho trvanie je definované ako celkový čas činností ležiacich na kritickej ceste, t.j. čas na dokončenie celého komplexu prác s najväčšou paralelizáciou všetkých prác. Tento čas sa rovná najväčšiemu z časov skorého dokončenia vypnutí sieťového grafu. Kritická cesta prechádza cez udalosti, ktoré nemajú časové rezervy (cez kritické činnosti).
• 3.Výpočet neskorých dátumov začiatku a konca práce sa určujú z možností obmedzujúceho posunu doprava po číselnej osi termínov prác tak, aby sa nezmenil čas kritickej dráhy. Preto je logické vykonať výpočty od poslednej udalosti po prvú a najskôr určiť čas neskorého dokončenia práce a potom vypočítať čas neskorého začiatku práce:
  • ?neskorý dátum začiatku (ij) je definovaný ako rozdiel medzi neskorým termínom dokončenia diela a dobou trvania samotného diela,
  • ? neskorý termín dokončenia je určená hodnotou cesty minimálneho trvania, ktorá k nej vedie od záverečnej udalosti, a vypočíta sa ako rozdiel medzi kritickou cestou a maximálnym trvaním práce od poslednej udalosti plánu siete po záverečnú udalosť tejto práce .
• 4. Výpočet časových rezerv“.

japlná prevádzková časová rezerva definovaný ako rozdiel medzi neskorým začiatkom a skorým začiatkom alebo medzi neskorým a skorým ukončením. Je potrebné poznamenať, že celkové časové rezervy pre činnosti ležiace na kritickej ceste sú rovné nule,

• ? súkromné (voľné) časové rezervy“.
• 1)súkromná časová rezerva prvého typu určená schopnosťou zmeniť neskorý začiatok práce ( ij) na skoršie dátumy bez zmeny neskorších dátumov dokončenia bezprostredne predchádzajúcej práce,
• 2) súkromný rezervný čas druhého typu určená schopnosťou zmeniť skorý koniec prac (ij) k neskoršiemu dátumu bez zmeny skorých dátumov začatia bezprostredne nasledujúcich prác; je určená rozdielom medzi skorým začiatkom ďalšej práce a skorým ukončením tejto práce.

Pozrime sa na postup výpočtu parametrov na príklade. Schéma siete je znázornená na obr. 7.5.

Ryža. 7.5.

Na výpočet parametrov použijeme tabuľkovú metódu a pre zjednodušenie vnímania všetko zhrnieme do jednej tabuľky. 7.1.

Pravidlá využívania časových rezerv pri plánovaní siete.

• 1. Aby boli celkové a čiastočné rezervy práce (y) rovnaké, je potrebné a postačujúce, aby posledná udalosť Y predmetnej práce bola udalosťou na kritickej ceste.
• 2. Ak je plná rezerva (Ja a] 1) nejaká práca je nulová, potom súkromná rezerva druhého typu (g"f) je tiež nula. Medzi týmito rezervami je vždy vzťah R(IJ) > r" ijy Celkové a čiastočné časové rezervy sú vždy väčšie alebo rovné nule.
• 3. Aby sa čiastočná rezerva pracovného času (y) rovnala nule, je potrebné a postačujúce, aby táto práca ležala na dráhe maximálnej dĺžky od prvej udalosti k udalosti y.
• 4. Ak sa doba trvania práce (y) zvýši o sumu p, t.j. p, potom sa dátum skorého začiatku následnej práce zvýši o sumu p - g" ("yy
• 5. Ak sa trvanie práce (y) zvýši o množstvo celkového času rezervy tejto práce, vytvorí sa nová kritická cesta, ktorej trvanie sa rovná trvaniu starej.
• 6. Celková rezerva pracovného času (y) sa rovná súčtu súkromnej časovej rezervy druhého druhu tejto práce a minima celkových rezerv všetkých bezprostredne nasledujúcich prác.

Výsledky výpočtu parametrov sieťového diagramu

Tabuľka 7.1

	Trvanie	Skoré	termíny, hodiny	Neskoré termíny, h		Časové rezervy, h
	práca, h	Začiatky	Koncovky	Začiatky	Koncovky	Plný	K dispozícii
	Kritická cesta, h		(práca 1-3

7. Ak sa trvanie práce (g/) zvýši o hodnotu p, objaví sa nová kritická cesta, ktorej trvanie prekročí trvanie starej kritickej cesty o hodnotu p -

Po zostrojení sieťového diagramu a výpočte jeho hlavných ukazovateľov začneme s jeho optimalizáciou.

• 1. Vyberte kritickú cestu a nájdite jej dĺžku;
• 2. Stanovte časové rezervy pre každú udalosť;
• 3. Určte časové rezervy všetkých zamestnaní a koeficient náročnosti práce predposledného zamestnania

Riešenie

Na vyriešenie problému používame nasledujúci zápis.

Sieťový prvok	Názov parametra	Symbol parametra
Udalosť i	Skorý dátum udalosti
Neskorý dátum ukončenia akcie
Časová rezerva podujatia
práca (i, j)	Trvanie práce
Dátum skorého začiatku
Predčasný dátum dokončenia
Neskorý dátum začiatku
Neskorý termín ukončenia prác
Plná prevádzková časová rezerva
	Trvanie cesty
Trvanie kritickej cesty
Časová rezerva na cestu

Na určenie časovej rezervy pre sieťové udalosti sa vypočítajú najskorší t p a posledný t p dátumy udalostí. Žiadna udalosť nemôže nastať skôr, ako sa vyskytnú všetky udalosti, ktoré jej predchádzali, a kým nebola dokončená všetka predchádzajúca práca. Preto skorý (alebo očakávaný) čas tp(i) i-tej udalosti je určený trvaním maximálnej cesty predchádzajúcej tejto udalosti:

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

kde Lni je akákoľvek cesta predchádzajúca i-tej udalosti, to znamená cesta od počiatočnej k i-tej sieťovej udalosti.

Ak udalosť j má niekoľko predchádzajúcich ciest, a teda niekoľko predchádzajúcich udalostí i, potom skorý dátum udalosti j sa dá pohodlne nájsť pomocou vzorca:

t p (j) = max (2)

Oneskorenie dokončenia podujatia i v porovnaní s jeho skorším dátumom neovplyvní dátum dokončenia záverečného podujatia (a teda obdobie dokončenia pracovného balíka), až kým sa nezíska súčet obdobia dokončenia tohto podujatia a trvania (dĺžka ) z maxima nasledujúcich ciest nepresahuje dĺžku kritickej cesty. Preto sa neskorý (alebo konečný) dátum t p (i) dokončenia i-tej udalosti rovná:

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

kde Lci je ľubovoľná cesta nasledujúca po i-tej udalosti, t.j. cesta od i-tej po záverečnú sieťovú udalosť.

Ak má udalosť i niekoľko následných ciest, a teda niekoľko následných udalostí j, neskorší dátum dokončenia udalosti i sa pohodlne nájde pomocou vzorca:

tp(i) = min

Časová rezerva R(i) i-tej udalosti je definovaná ako rozdiel medzi neskorým a skorým dátumom jej výskytu:

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

Rezervný čas udalosti ukazuje, o aké prijateľné časové obdobie môže byť výskyt tejto udalosti oneskorený bez toho, aby došlo k predĺženiu doby dokončenia pracovného balíka.

Kritické udalosti nemajú časové rezervy, pretože akékoľvek oneskorenie dokončenia udalosti ležiacej na kritickej ceste spôsobí rovnaké oneskorenie dokončenia poslednej udalosti. Stanovením skorého dátumu poslednej udalosti siete teda určíme dĺžku kritickej cesty.

Pri určovaní skorých dátumov udalostí tp(i) sa pohybujeme po sieťovom diagrame zľava doprava a používame vzorce (1), (2).

Výpočet načasovania udalostí.

Pre i=0 (počiatočná udalosť), samozrejme tp(0)=0.

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

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

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

i=4: max(tp(2) + t(2,4);tp(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(tp(4) + t(4,6);tp(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(tp(5) + t(5,9);tp(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(tp(8) + t(8,11); tp(10) + t(10,11)) = max(32 + 12;32 + 4) = 44.

Dĺžka kritickej cesty sa rovná skorému dátumu dokončenia poslednej udalosti 11: t kp =tp(11)=44

Pri určovaní neskorých dátumov udalostí t p (i) sa pohybujeme po sieti v opačnom smere, teda sprava doľava a používame vzorce (3), (4).

Pre i=11 (konečná udalosť) sa neskorý dátum udalosti musí rovnať jej skoršiemu dátumu (inak sa dĺžka kritickej cesty zmení): t p (11)= t p (11)=44

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

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

Všetky riadky začínajúce číslom 8 sú prezreté.

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

Všetky riadky začínajúce číslom 7 sú prezreté.

i=7: min(tp(8) -t(7,8);tp(9)-t(7,9);tp(10)-t(7,10)) = min(32-4;40-4;40-2 ) = 28.

i=6: min(tp(7)-t(6,7);tp(8)-t(6,8)) = min(28-9;32-5) = 19.

Všetky riadky začínajúce číslom 5 sú prezreté.

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

i=4: min(tp(5)-t(4,5);tp(6)-t(4,6);tp(10)-t(4,10)) = min(16-0;19-5;40-4 ) = 14.

Všetky riadky začínajúce číslom 3 sú prezreté.

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

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

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

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

Tabuľka 1 - Výpočet rezervy na udalosti

Číslo udalosti	Načasovanie udalosti: skoré tp(i)	Načasovanie udalosti: neskoro tп(i)	Časová rezerva, R(i)

Vyplnenie tabuľky 2.

Zoznam diel a ich trvanie presunieme do druhého a tretieho stĺpca. V tomto prípade by sa práca mala zapísať do stĺpca 2 postupne: najskôr od čísla 0, potom od čísla 1 atď.

Do druhého stĺpca uvedieme číslo charakterizujúce počet bezprostredne predchádzajúcich diel (CPR) udalosti, od ktorej dané dielo začína.

Takže pre prácu (1,2) v stĺpci 1 dáme číslo 1, pretože číslo 1 končí 1 úlohami: (0,1).

Stĺpec 4 je získaný z tabuľky 1 (tp(i)). Stĺpec 7 sa získa z tabuľky 1 (tp(i)).

Hodnoty v stĺpci 5 sa získajú súčtom stĺpcov 3 a 4.

V stĺpci 6 je neskorý začiatok prác definovaný ako rozdiel medzi neskorým dokončením týchto prác a ich trvaním (údaje v stĺpci 3 sa odpočítajú od hodnôt stĺpca 7);

Obsah stĺpca 8 (čas plnej rezervy R(ij)) sa rovná rozdielu medzi stĺpcami 6 a 4 alebo stĺpcami 7 a 5. Ak je R(ij) nula, potom je práca kritická

Tabuľka 2 – Analýza modelu siete v čase

práca (i,j)	Počet predchádzajúcich diel	Trvanie tij	Skoré dátumy: začiatok tijР.Н.	Skoré dátumy: koniec tijР.О.	Neskoré dátumy: začiatok tijP.N.	Neskoré termíny: koniec tijP.O.	Časové rezervy: plný RijП	Samostatná časová rezerva RijН	Súkromná rezervácia prvého druhu, Rij1	Súkromná rezerva typu II, RijC

Treba si uvedomiť, že okrem plnej prevádzkovej časovej rezervy existujú ešte tri druhy rezerv. Čiastková časová rezerva prvého typu R 1 je súčasťou celkovej časovej rezervy, o ktorú možno predĺžiť trvanie práce bez zmeny neskorého termínu jej počiatočnej udalosti. R1 nájdeme podľa vzorca:

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

Súkromná časová rezerva druhého typu alebo voľná časová rezerva Rc práce (i, j) je súčasťou celkovej časovej rezervy, o ktorú možno predĺžiť trvanie práce bez zmeny skoršieho termínu jej záverečnej akcie. . Rc sa nachádza podľa vzorca:

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

Hodnota voľnej prevádzkovej časovej rezervy udáva umiestnenie rezerv potrebných na optimalizáciu.

Samostatná časová rezerva Rн práca (i, j) - časť celkovej rezervy získanej pre prípad, že všetky predchádzajúce práce skončia neskoro a všetky nasledujúce začnú skôr. Rn sa zistí podľa vzorca:

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

Kritická cesta: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Trvanie kritickej cesty: 44

Nájdite koeficient náročnosti práce predposledného zamestnania. Keďže dĺžka kritickej cesty je 44, maximálna cesta prechádzajúca úlohou (1.10) je 32, potom

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

4. Poskytovateľ internetu v malom meste má 5 vyhradených servisných kanálov. Obsluha jedného klienta trvá v priemere 25 minút. V priemere systém dostane 6 akzas za hodinu. Ak neexistujú žiadne voľné kanály, nasleduje odmietnutie. Určte charakteristiky služby: pravdepodobnosť zlyhania, priemerný počet komunikačných liniek obsadených službou, absolútnu a relatívnu priepustnosť, pravdepodobnosť služby. Nájdite počet vyhradených kanálov, pri ktorých bude relatívna priepustnosť systému aspoň 0,95. Predpokladajme, že toky požiadaviek a služieb sú najjednoduchšie

Intenzita servisného toku:

Intenzita zaťaženia:

s = l * t obs = 6 * 25/60 = 2,5

Intenzita zaťaženia c = 2,5 ukazuje stupeň konzistencie vstupných a výstupných tokov požiadaviek obslužného kanála a určuje stabilitu systému radenia.

Pravdepodobnosť, že služba:

1 kanál je obsadený:

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

2 kanály sú obsadené:

p2 = c2/2! p0 = 2,5 2/2! * 0,0857 = 0,268

3 kanály sú obsadené:

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

4 kanály sú obsadené:

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

Kanál 5 je obsadený:

p 5 = c 5 / 5! p0 = 2,55/5! * 0,0857 = 0,0697

Pravdepodobnosť zlyhania je zlomok zamietnuté žiadosti:

To znamená, že 7 % prijatých žiadostí nie je prijatých do služby.

Pravdepodobnosť obsluhy prichádzajúcich požiadaviek-pravdepodobnosť, že zákazník bude obsluhovaný:

V systémoch s poruchami tvoria poruchy a udalosti údržby kompletnú skupinu udalostí, preto:

p otvorené + p obs = 1

Relatívna kapacita Q = p obs .

p obs = 1 - p otvorené = 1 - 0,0697 = 0,93

Následne bude obsluhovaných 93 % prijatých žiadostí. Priemerný počet kanálov obsadených službou

nh = c * p obs = 2,5 * 0,93 = 2,326 kanálov.

Priemerný počet nečinných kanálov.

n pr = n - nh = 5 - 2,326 = 2,7 kanálov.

Miera obsadenosti servisného kanála.

V dôsledku toho je systém na 50 % vyťažený údržbou.

Absolútna priepustnosť

A = pobs * l = 0,93 * 6 = 5,581 požiadaviek/hod.

Priemerný prestoj QS.

t pr = p otvorené * t obs = 0,0697 * 0,417 = 0,029 hodiny.

Priemerný počet doručených žiadostí.

L obs = s * Q = 2,5 * 0,93 = 2,326 jednotiek.

Priemerný čas, počas ktorého aplikácia zostáva v SOT(Littleho vzorec).

Počet žiadostí zamietnutých do hodiny: l * p 1 = 0,418 žiadostí za hodinu.

Nominálna produktivita QS: 5 / 0,417 = 12 002 aplikácií za hodinu.

Skutočný výkon SMO: 5,581 / 12,002 = 47 % nominálnej kapacity.

Poďme určiť počet kanálov potrebných na zabezpečenie prevádzkyschopnosti systému s pravdepodobnosťou P ? 0,95

Aby sme to dosiahli, nájdeme n z podmienky:

Nájdite pravdepodobnosť, že ak je v systéme 6 kanálov a všetky sú obsadené: