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

Hlavné parametre sieťového diagramu

Hlavné parametre sieťového diagramu sú:

kritická cesta

Časové rezervy na dokončenie akcií

Časové rezervy na výkon práce

Cesta - postupnosť úloh, v ktorých sa koniec jednej úlohy zhoduje so začiatkom inej úlohy.

Úplná cesta - cesta, ktorej začiatok je počiatočná udalosť a koniec je konečná.

Trvanie, dĺžka cesty, sa rovná súčtu trvania práce. Jeho zložky.

kritická cesta - plná cesta. najdlhšia zo všetkých ciest sieťového diagramu od počiatočnej udalosti (I) po konečnú (C).

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

Úplné cesty môžu ísť 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. Kritická cesta nie je. Pre každú i-tu udalosť sa určuje:

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

t p i– neskorý dátum príchodu- maximum načasovania vzniku tejto udalosti, v ktorom je ešte možné vykonať všetky nasledujúce práce pri dodržaní stanoveného termínu vzniku udalosti.

RI – voľna na udalosť- časový úsek, o ktorý možno oddialiť začiatok tejto udalosti bez toho, aby sa narušil čas výstavby plánovaného komplexu ako celku. Definované ako rozdiel medzi neskoro ( t p i) a skoro ( t p i) načasovanie dokončenia tejto udalosti.

Rezervy udalosti na kritickej ceste sú rovné nule, pretože na nej t p i = t p i

Za každé dielo tij) je definovaný:

skorý dátum začiatku (t w.d. ij)- minimálny možný čas na začatie týchto prác.

dátum skorého ukončenia (t p.o. ij)- minimálny možný termín dokončenia tejto práce, na danú dobu trvania práce

neskorý dátum začiatku (t b.s. ij)- maximálny z prípustných termínov začatia týchto prác

neskorý dátum ukončenia (t p.o. ij)- maximálne prípustné termíny dokončenia tohto diela, pri ktorých je ešte možné vykonať nasledujúce práce pri dodržaní ustanoveného termínu vzniku záverečnej udalosti.

Je zrejmé, že dátum skorého začiatku aktivity sa zhoduje so skorým dátumom začiatku jej počiatočnej udalosti a dátum skorého ukončenia ho presahuje o trvanie aktivity:

t r.n. ij = t p i

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

Neskorý dátum ukončenia aktivity je rovnaký ako neskorý dátum jej ukončenia a neskorší dátum začatia aktivity je kratší o trvanie aktivity:

t p.o. ij = t p j

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

Plná rezerva času na dokončenie práce Rnij– maximálny časový úsek, o ktorý môžete odložiť začiatok alebo predĺžiť trvanie práce bez zmeny nastaveného dátumu vzniku udalosti ukončenia.

Voľný čas na prácu, ktorá je súčasťou plnej rezervy - maximálny časový úsek, o ktorý môžete odložiť začiatok alebo predĺžiť trvanie práce, pričom nemeníte dátumy skorého začatia ďalšej práce.

Úlohy, ktoré ležia na kritickej ceste, nemajú rezervy, pretože všetky rezervy sa vytvárajú v dôsledku rozdielu 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 segmentov cesty medzi rovnakými udalosťami, navyše jeden segment je súčasťou cesty maximálneho trvania zo všetkých ciest prechádzajúcich týmto dielom a druhý segment je súčasťou kritickej cesty.

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

Parametre siete pre sieťové diagramy sa počítajú pomocou grafickej a tabuľkovej metódy a pre komplexné matematickou metódou.

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 je časová rezerva pre výskyt udalosti RI

ľavý sektor - skorý termín akcie tpi

pravý sektor - neskorý dátum udalosti t p i

dole - číslo udalosti

Metóda výpočtu parametrov

1) Skoré načasovanie udalostí . Skorý dátum dokončenia počiatočnej (prvej alebo nulovej) udalosti sa rovná nule. Skoré dátumy dokončenia všetkých ostatných podujatí sa určujú v prísnom poradí narastajúcim počtom podujatí. Na určenie dátumu skorého dokončenia akejkoľvek udalosti j sa berú do úvahy všetky úlohy zahrnuté v tejto udalosti, pre každú úlohu sa dátum skorého dokončenia poslednej udalosti určí ako súčet dátumu skorého dokončenia počiatočnej udalosti diela a trvanie tejto práce tij, zo získaných hodnôt sa vyberie maximálny čas skorého ukončenia j-tej udalosti

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

2) Neskoré termíny podujatí . Neskorý dátum ukončenia záverečného podujatia sa berie rovnako ako jeho skorý dátum. Výpočet neskorých termínov dokončenia 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 ukončenia predchádzajúceho podujatia i sa berú do úvahy všetky práce pochádzajúce z i-tého podujatia. Pre každú zákazku sa počíta neskorý termín dokončenia úvodnej udalosti t p i, ako rozdiel medzi neskorým termínom dokončenia záverečnej udalosti tohto diela t p j a trvanie tejto práce tij.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) Dĺžka kritickej cesty sa rovná skorému dátumu ukončenia udalosti.

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

5) Pri určovaní celkovej rezervy na prácu odpočítajte od čísla zaznamenaného v pravom sektore záverečnej udalosti, počtu zaznamenaného v ľavom sektore počiatočnej udalosti a trvania samotnej práce.

6) Pri určovaní voľnej rezervy na prácu odpočítajte od čísla zaznamenaného v ľavom sektore záverečnej udalosti, čísla zaznamenané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é vzostupne i.

Stĺpce 2 a 3 sú vyplnené pomocnými údajmi: kódy predchádzajúcich a nasledujúcich prác. Tieto údaje budú potrebné pre výpočty. Ak sú diela 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 vložia pomlčky. Môže existovať niekoľko predchádzajúcich a nasledujúcich úloh podľa počtu vektorov končiacich alebo začínajúcich v danej udalosti./

Stĺpec 4 obsahuje hodnoty trvania práce.

Stĺpec 5 začína vypočítané údaje. Výpočet sa vykonáva v dvoch prechodoch cez riadky tabuľky. Prvý prechádza riadkami zhora nadol, v ktorých sa počítajú najskoršie pracovné dátumy, a druhý prechádza riadkami zdola nahor, v ktorých sa počítajú neskoršie pracovné dátumy.

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

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

Ak je v stĺpci 2 uvedené, že určitej práci predchádza viacero prác (práci 5.6 predchádzajú práce 2.5 a 3.5), potom je potrebné zvoliť hodnotu skorého štartu z viacerých možností hodnôt (9 - do konca práce 2,5 alebo 13 - do konca 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 skorého konca v stĺpci 6 zodpovedá hodnote trvania kritickej cesty (16).

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

Neskoré dokončenie zvyšku možno definovať tak, že ak sa napríklad uvažuje o práci 3.5, ktorá má koniec 5, potom sa jej neskorý čas ukončenia rovná neskoršiemu času začiatku práce 5.6, pretože má koniec udalosť z 5. Hodnota zo stĺpca 7 sa prepíše do stĺpca 8. Kódy nasledujúcich prác sú uvedené v stĺpci 3. Neskorý začiatok je tiež určený vzorcom t a.s. ij t podľa ij - t ij .

Ak je v stĺpci 3 uvedené, že po určitom zamestnaní nasleduje viac ako jedna práca (za úlohou 0,1 nasledujú úlohy 1,2 a 1,3), potom je potrebné zvoliť hodnotu neskorého ukončenia z viacerých možností (3 - podľa čas začiatku práce 1,3 alebo 7 - podľa času začiatku 1,2 sa zvolí minimálna hodnota (v príklade - 3). Neskorý začiatok je určený vyššie uvedeným vzorcom t a.s. ij t podľa ij - t ij .

Hodnota celkovej nevyužitosti (stĺpec 9) sa vypočíta podľa vzorca

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

Hodnota voľného uvoľnenia (stĺpec 10) sa vypočíta pomocou vzorca

R s ij = t ро ij - t рр ij - t ij

Akákoľvek postupnosť sieťových aktivít, v ktorých sa koncová udalosť každej aktivity zhoduje so štartovacou udalosťou aktivity, ktorá po nej nasleduje, sa nazýva cez.

Volá sa sieťová cesta, kde počiatočný bod je rovnaký ako počiatočná udalosť a koncový bod je koncová udalosť kompletný.

Cesta od pôvodnej udalosti k akejkoľvek uskutočnenej predchádzalo táto udalosť. Cesta, ktorá predchádza udalosti a má najdlhšiu dĺžku, sa nazýva maximálne predchádzajúce. Označuje sa L 1 (i) a jeho trvanie je t.

Cesta spájajúca danú udalosť s konečnou sa nazýva následné spôsobom. Táto najdlhšia cesta je tzv pokiaľ je to možné následne a označuje sa L 2 (i) a jeho trvanie je t.

Plná cesta s najdlhšou dĺžkou je tzv kritický. Nazývajú sa cesty iné ako kritická cesta uvoľnený. Majú časové rezervy.

Aktivity na kritickej ceste sú zvýraznené hrubými alebo dvojitými čiarami. Trvanie kritickej cesty sa považuje za hlavný parameter grafu.

Zvážte algoritmus na určenie kritickej cesty v sieťovom diagrame pomocou algoritmu metódy dynamického programovania.

Zoraďme vrcholy grafu podľa hodností a očíslujme ich od konca po začiatok. To umožní zosúladiť poradové čísla s fázami spätného pohybu pri hľadaní podmienene optimálnych ovládacích prvkov na poslednom z nich, na posledných dvoch atď. etapy. Nájdenie kritickej cesty bude analyzované 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ždej fáze určené cieľom kontroly a stavom na začiatku etapy. Stav systému sú udalosti, ktoré ležia na radoch. Na dokončenie 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 - výskyt 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 157. Nájdite maximálne trvanie práce v posledných dvoch fázach. Stav systému na začiatku predposlednej etapy je spôsobený udalosťou X 13. Maximálne trvanie cesty vedúcej z X 13 do X 16 je .

Preto by malo byť číslo 14 umiestnené v kruhu blízko udalosti X 13 atď. Vykonaním etáp od konca po začiatok zistíme dĺžku kritickej dráhy t cr =96. Aby sme našli samotnú kritickú cestu, prejdime si proces výpočtu od počiatočnej udalosti X 1 po konečnú 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 druhej fáze prechádza cez prácu (X 3 , X 4) atď. Na grafe je vyznačená hrubou čiarou:

X1-X3-X4-X7-X8-X10-X11-X12-X13-X15-X16.

Skoré a neskoré termíny ukončenia podujatí. Udalosť uvoľnená

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

skorý termín dokončenie udalosti sa nazýva najskorší časový bod, v ktorom sú dokonč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

Aby ste našli skorý dátum udalosti j , potrebujete poznať kritickú cestu smerovaného podgrafu, ktorý pozostáva z množiny ciest predchádzajúcich danej udalosti j . Skorý člen počiatočnej udalosti sa rovná nule: t p (1) = 0.

neskorý termín udalosť najneskorší bod v čase, po ktorom je presne toľko času, koľko je potrebné na dokončenie všetkých prác nasledujúcich po tejto udalosti. Najneskorší z prípustných termínov ukončenia akcie spolu s trvaním vykonania všetkých následných činností nesmie presiahnuť dĺžku kritickej cesty. Neskorý termín pre udalosť sa vypočíta ako rozdiel medzi trvaním kritickej cesty a trvaním maxima ciest nasledujúcich po udalosti:

Pre udalosti na kritickej ceste sú skoré a neskoré dátumy dokončenia týchto udalostí rovnaké.

Rozdiel medzi neskorým a skorým dátumom dokončenia podujatia je rezervný čas podujatia: . Interval sa nazýva interval voľnosti udalosti. Medzera udalosti ukazuje maximálne povolené množstvo času, počas ktorého môže byť udalosť posunutá späť bez zvýšenia kritickej cesty.

Od čiastky určuje trvanie cesty maximálnej dĺžky prechádzajúcej týmto dejom, potom , t.j. uvoľnenie akejkoľvek udalosti sa rovná úplnému uvoľneniu maximálnej cesty cez túto udalosť.

Pri manuálnom výpočte časových parametrov je vhodné použiť štvorsektorovú metódu. Pri tejto metóde sa kruh sieťového diagramu označujúci udalosť rozdelí na štyri sektory. Číslo udalosti je umiestnené v hornom sektore; vľavo - najskorší možný čas udalosti (); vpravo - posledný z prípustného času udalosti; v dolnom sektore - rezervný čas tejto udalosti: .

Na výpočet najskoršieho termínu pre udalosti: , 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 dokončenia udalostí sa vypočíta podľa vzorca , počnúc koncovou udalosťou, pre ktorú ( - číslo koncovej udalosti) podľa úloh, ktoré z nej vychádzajú.

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

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

Riešenie. Vypočítajte skoré dátumy dokončenia 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 projektové aktivity. Určuje sa podľa najdlhšej dráhy. Termín skorého ukončenia diela 6 =14 sa zhoduje s kritickým časom kp - celkovým trvaním diela ležiaceho na kritickej ceste. Teraz môžete zvýrazniť aktivity, ktoré patria do kritickej cesty, a vrátiť sa z koncovej udalosti na pôvodnú. 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: cr = (1-3-4-5-6).

Teraz vypočítame neskoré dátumy dokončenia udalostí. Nechajte . Využime metódu dynamického programovania. Všetky výpočty sa vykonajú od záverečnej udalosti po počiatočnú udalosť. Neskoré termíny ukončenia podujatí sú:

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

Časový limit pre udalosť 2 je: . Rezervy zostávajúcich udalostí sa rovnajú nule, pretože tieto udalosti sú kritické.

Skoré a neskoré dátumy začiatku a konca. Stanovenie rezerv pracovného času. Plná rezerva pracovného času.

Udalosť bezprostredne predchádzajúca tomuto dielu bude tzv primárny a označujú , a udalosť bezprostredne nasledujúcu za ním, - finálny, konečný a určiť. Potom bude každá úloha označená . Keď poznáte načasovanie dokončenia udalostí, môžete určiť časové parametre práce.

Čas skorého začiatku sa rovná skorému dátumu udalosti: .

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

Neskorý koniec práce sa zhoduje s neskorým dátumom ukončenia jeho záverečnej udalosti: .

Neskorý čas začiatku sa rovná rozdielu medzi neskorým dátumom dokončenia jeho poslednej udalosti a hodnotou 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á rezerva pracovného času - je to maximálny čas potrebný na dokončenie akejkoľvek práce bez prekročenia kritickej cesty. Vypočíta sa ako rozdiel medzi udalosťou neskorého konca a skorým časom dokončenia samotnej práce: . Odvtedy .

Touto cestou, plná prevádzková rezerva je maximálny čas, o ktorý možno predĺžiť jeho trvanie bez zmeny trvania kritickej cesty. Všetky nekritické úlohy majú nenulovú celkovú rezervu.

Voľná ​​rezerva pracovného času- toto je časová rezerva, 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 najskoršom dátume: .

Výpočet sieťového grafu tabuľkovým spôsobom sa vykoná podľa vzorcov uvedených vyššie v časti 4 (1-10). Pri stanovení parametrov sieťových modelov analytickým spôsobom sa výpočet vykonáva vo forme tabuľky. Zvážte vlastnosti výpočtu sieťových modelov týmto spôsobom (aplikácia 1) na príklade výpočtu parametrov sieťového diagramu uvedeného v zadaní tejto práce na kurze (možnosť 15).

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

Výpočet plánu siete začína určením hodnôt počiatočných parametrov 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 aktivít 2-6 a 2-7 (v súlade so vzorcom 3) sa rovná skorému ukončeniu aktivity 1-2.

Maximálna hodnota predčasného ukončenia práce 19-21, rovná 36, určuje trvanie kritickej cesty a teda aj celkové trvanie vykonávania všetkých činností 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ý koniec práce 15-20 (=), ktorý mu predchádza.

Ďalej sa výpočet neskorých parametrov vykonáva podobne, s výnimkou prípadov, keď má úloha niekoľko po sebe nasledujúcich úloh (napríklad úloha 6-9 má dve po sebe nasledujúce - 9-10 a 9-14). V tomto prípade sa v súlade so vzorcom 4 neskoré dokonč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ých a súkromných časových rezerv pre každú prácu a závislosti sieťového diagramu a zadať ich hodnoty do 7. a 8. stĺpca výpočtu. tabuľky, resp.

Celková rezerva pracovného času podľa vzorcov 8-9 sa určí ako rozdiel medzi neskorým a skorým dokončením alebo ako rozdiel medzi neskorým a skorým začiatkom zodpovedajúcej práce. Hodnotu celkovej nevyužitosti je užitočné určiť oboma spôsobmi, zhodu získaných hodnôt možno považovať za dodatočnú kontrolu. Napríklad pre prácu 6-7:

Čiastočná prestávka pracovného času podľa vzorca 10 je definovaná ako rozdiel medzi hodnotou predčasného začiatku nasledujúcej činnosti a hodnotou predčasného ukončenia pre túto činnosť. Napríklad pre prácu 6-7:

Kritická cesta je charakterizovaná nulovou vôľou. Porovnanie parametrov sieťového modelu získané sektorovými a tabuľkovými metódami by malo odhaliť ich úplnú identitu, prítomnosť nezrovnalostí poukazuje na chybnosť výpočtov.

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

Výpočet sieťového grafu grafickým spôsobom 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 grafu zahŕňa ich zaznamenanie priamo na modeli (Príloha 2). Každá udalosť (kruh) je rozdelená do štyroch sektorov. Označenie sektorov je znázornené na nasledujúcom obrázku:

Pre aktivity kritickej cesty sú hodnoty celkového a čiastočného uvoľnenia 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:

• * odhalila súvislú kritickú cestu;
• * vypočítané časové rezervy majú nezápornú hodnotu;
• * hodnota súkromnej nevyužitej kapacity pre všetky pracovné miesta je menšia alebo rovná hodnote celkovej nevyužitej kapacity pre tieto pracovné miesta;
• * aspoň jedna hodnota neskorého začiatku prác (prác) vychádzajúcich z prvej udalosti sa rovná nule.

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 možno vykonať nasledujúcim spôsobom.

• 1. Výpočet skorých dátumov:
  • ? skorý začiatok práce je určená dobou trvania najdlhšej cesty od iniciačnej udalosti po začiatok vykonávania tejto práce,
  • ? termíny skorého dokončenia- toto je najskorší možný termín ukončenia prác. Čas skorého ukončenia práce sa rovná súčtu času skorého začatia práce a trvania samotnej práce.
• 2.Výpočet kritickej cesty. Jeho trvanie je definované ako celkový čas činností na kritickej ceste, t.j. čas dokončenia 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 dokončenia 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 sa určujú z možností posunu limitu doprava po číselnej osi termínov ukončenia prác tak, aby sa nezmenil čas kritickej cesty. 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 oneskoreným dokončením 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 koncovej udalosti, a vypočíta sa ako rozdiel medzi kritickou cestou a maximálnou dobou trvania práce od koncovej udalosti siete po koncovú udalosť tejto práce.
• 4. Výpočet časových rezerv“.

japlná prevádzková rezerva je 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ý čas práce na kritickej ceste sa rovná nule,

• ? súkromné (voľné) časové rezervy“.
• 1)súkromného ochabnutia prvého druhu určená schopnosťou zmeniť čas neskorého začiatku ( ij) na skoršie termíny bez zmeny neskorých termínov na dokončenie bezprostredne predchádzajúcich prác,
• 2) privátna slabosť druhého druhu určená schopnosťou zmeniť skorý koniec prac (ij) v neskorších dátumoch bez zmeny skorých dátumov začatia bezprostredne nasledujúcich prác; je určená rozdielom medzi skorým začiatkom následnej činnosti a skorým ukončením tejto činnosti.

Uvažujme o postupe 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é zásoby práce (y) rovnaké, je potrebné a postačujúce, aby záverečná udalosť Y predmetnej práce bola udalosťou na kritickej ceste.
• 2. Ak je plná rezerva (Ja a] 1) niektorých prác sa rovná nule, potom súkromná rezerva druhého typu (g "f) sa tiež rovná nule. Medzi týmito rezervami je vždy pomer R(IJ) > r"ijy Celkové a súkromné ​​č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 p, t.j. p, potom sa dátum skorého začiatku následnej práce zvýši o hodnotu p - g" ("uu
• 5. Ak sa trvanie práce (y) zvýši o množstvo celkovej časovej rezervy na túto prácu, vytvorí sa nová kritická cesta, ktorej trvanie sa rovná trvaniu starej.
• 6. Celková rezerva pracovného času (y) sa rovná súčtu čiastkovej časovej rezervy druhého druhu tejto práce a minima celkovej rezervy všetkých bezprostredne nasledujúcich prác.

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

Tabuľka 7.1

	Trvanie	Skoré	podmienky, h	Neskoré termíny, h		Časové rezervy, h
	diela, h	Začiatky	koncovky	Začiatky	koncovky	Plný	zadarmo
	Kritická cesta, h		(práca 1-3

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

Po vytvorení sieťového grafu a vypočítaní jeho hlavných ukazovateľov ho začnú optimalizovať.

• 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 prác a faktor intenzity práce predposledného diela

Riešenie

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

Sieťový prvok	Názov parametra	Symbol parametra
Udalosť i	Predčasný dátum ukončenia podujatia
Neskorý termín ukončenia akcie
Udalosť uvoľnená
práca (i, j)	Pracovny cas
Čas skorého začiatku
Predčasný koniec práce
Neskorý čas začiatku
Neskorý koniec práce
Plná prevádzková rezerva
	Cestovný čas
Dĺžka kritickej cesty
Časová rezerva na cestu

Na určenie časových rezerv pre udalosti siete sa vypočítajú najskôr t p a najneskoršie t p dátumy ukončenia udalostí. Žiadna udalosť nemôže nastať skôr, než budú dokončené všetky udalosti, ktoré jej predchádzali, a všetky predchádzajúce práce neboli dokončené. 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 L ni je ľubovoľná cesta predchádzajúca i-tej udalosti, teda cesta od počiatočnej k i-tej udalosti siete.

Ak má udalosť j niekoľko predchádzajúcich ciest, a teda niekoľko predchádzajúcich udalostí i, potom je vhodné nájsť skorý dátum dokončenia udalosti j pomocou vzorca:

t p (j) = max (2)

Oneskorenie ukončenia podujatia i vo vzťahu k jeho skoršiemu termínu neovplyvní čas ukončenia záverečného podujatia (a teda ani čas ukončenia komplexu prác) až do súčtu času ukončenia tohto podujatia a trvanie (dĺžka) maxima trás, ktoré nasledujú, nepresahuje dĺžku kritickej cesty. Preto sa neskorý (alebo limitný) termín 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 možno pohodlne nájsť 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 ukončenia:

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

Medzera udalosti ukazuje, ako dlho môže byť udalosť odložená bez toho, aby to spôsobilo predĺženie trvania pracovného balíka.

Kritické udalosti nemajú čas, pretože akékoľvek oneskorenie v dokončení udalosti na kritickej ceste spôsobí rovnaké oneskorenie v dokončení poslednej udalosti. Po určení skorého termínu poslednej udalosti siete teda určíme dĺžku kritickej cesty.

Pri určovaní skorého načasovania udalostí tp(i) sa pohybujeme po sieťovom grafe 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(tp (2) + t(2,8);tp (6) + t(6,8);tp(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(tp(4) + t(4,10);tp(7) + t(7,10);tp(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á dátumu skorého dokončenia poslednej udalosti 11: t kp =tp(11)=44

Pri určovaní neskorých dátumov dokončenia 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 (posledná 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 udalostí

Číslo udalosti	Načasovanie udalosti: skoré tp(i)	Termíny konania: neskorý tp(i)	Časová rezerva, R(i)

Vyplnenie tabuľky 2.

Zoznam prác a ich trvanie sa presunie do druhého a tretieho stĺpca. V tomto prípade by sa práca mala zaznamenať v stĺpci 2 postupne: najprv od čísla 0, potom od čísla 1 atď.

Do druhého stĺpca uvádzame číslo, ktoré charakterizuje počet bezprostredne predchádzajúcich diel (KPR) udalosti, od ktorej dané dielo začína.

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

Stĺpec 4 sa získa 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 (celkový nedostatok R(ij)) sa rovná rozdielu medzi stĺpcami 6 a 4 alebo stĺpcami 7 a 5. Ak sa R(ij) rovná nule, 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 tijR.N.	Skoré dátumy: koniec tijР.О.	Neskoré dátumy: začiatok tijP.N.	Neskoré termíny: koniec tijP.O.	Časové rezervy: plný RijP	Samostatná časová rezerva Rij	Súkromná rezerva 1. druhu, Rij1	Súkromná rezerva typu II, RijC

Treba si uvedomiť, že okrem plnej rezervy prevádzkového času existujú ešte tri typy rezerv. Súkromná časová rezerva prvého typu R 1 - časť celkovej časovej medzery, o ktorú je možné predĺžiť trvanie práce bez zmeny neskorého dátumu jej počiatočnej udalosti. R1 nájdeme podľa vzorca:

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

Čiastočný voľný čas druhého typu alebo voľný čas práce Rc práce (i, j) je súčasťou celkového času práce, o ktorú možno predĺžiť dobu trvania práce bez zmeny skoršieho dátumu jej ukončenia. Rc sa nachádza podľa vzorca:

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

Hodnota voľného času behu označuje miesto uvoľnenia potrebného na optimalizáciu.

Samostatná časová rezerva Rn práce (i, j) je časť celkovej rezervy získanej pre prípad, keď sa všetky predchádzajúce práce skončia neskoro a všetky nasledujúce prá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 predposlednej práce. Keďže dĺžka kritickej cesty je 44, maximálna cesta cez prácu (1,10) je 32, potom

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

4. ISP v malom meste má 5 vyhradených servisných kanálov. Obsluha jedného klienta trvá v priemere 25 minút. Systém prijíma v priemere 6 aczas za hodinu. Ak neexistujú žiadne voľné kanály, nasleduje odmietnutie. Určte vlastnosti 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, pre ktoré 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:

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

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

Pravdepodobnosť, že služba:

kanál 1 obsadený:

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

2 kanály sú obsadené:

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

3 kanály sú obsadené:

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

4 kanály sú obsadené:

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

Obsadených je 5 kanálov:

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

Pravdepodobnosť zlyhania je zlomok zamietnuté žiadosti:

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

Pravdepodobnosť obsluhy prichádzajúcich požiadaviek-pravdepodobnosť, že klient bude obsluhovaný:

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

p otvorené + p obs = 1

Relatívna priepustnosť Q = p obs .

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

V dôsledku toho bude doručených 93 % prijatých žiadostí. Priemerný počet kanálov obsadených službou

n s \u003d s * p obs \u003d 2,5 * 0,93 \u003d 2,326 kanálov.

Priemerné nečinné kanály.

n pr \u003d n - n z \u003d 5 - 2,326 \u003d 2,7 kanálov.

Miera obsadenosti servisného kanála.

Preto je systém na 50 % vyťažený údržbou.

Absolútna šírka pásma

A \u003d pobs * l \u003d 0,93 * 6 \u003d 5,581 aplikácií za hodinu.

Priemerný čas nečinnosti QS.

t pr \u003d p otk * t obs \u003d 0,0697 * 0,417 \u003d 0,029 hodín.

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

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

Priemerný čas zotrvania žiadosti v SOT(Littleho vzorec).

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

Nominálny výkon QS: 5 / 0,417 = 12 002 aplikácií za hodinu.

Skutočný výkon SOT: 5,581 / 12,002 = 47 % nominálneho výkonu.

Určme 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é: