Calculul și analiza graficelor de rețea. Data timpurie a evenimentului

Parametrii principali ai diagramei de rețea

Principalii parametri ai diagramei de rețea sunt:

traiectorie critică

Rezerve de timp pentru finalizarea evenimentelor

Rezerve de timp pentru efectuarea lucrărilor

cale - o succesiune de joburi în care evenimentul de sfârșit al unui job coincide cu evenimentul de început al altuia.

Calea plină - o cale, al cărei început este evenimentul inițial, iar sfârșitul este cel final.

Durata, lungimea traseului, este egală cu suma duratelor lucrării. Constituenții săi.

traiectorie critică - traseu complet. cea mai lungă dintre toate căile diagramei de rețea de la evenimentul inițial (I) până la cel final (C).

Lungimea traseului critic determină durata totală a întregului complex de lucrări. Calea critică vă permite să găsiți momentul evenimentului final.

Căile complete pot ieși în afara celei critice sau pot coincide parțial cu aceasta. Aceste călătorii mai scurte se numesc relaxat. Caracteristicile lor sunt. Că au rezerve de timp. Calea critică nu este. Pentru fiecare al-lea eveniment se determină:

tpi– debut precoce- timpul minim posibil de producere a acestui eveniment pentru o anumită durată de muncă.

t p i– data de sosire târzie- maximul momentului de producere a acestui eveniment, în care este încă posibilă efectuarea tuturor lucrărilor următoare, sub rezerva termenului stabilit pentru producerea evenimentului.

R i – slăbiciune pentru un eveniment- perioada de timp pentru care declanșarea acestui eveniment poate fi amânată fără a încălca timpul de dezvoltare a complexului planificat în ansamblu. Definit ca diferența dintre întârziere ( t p i) și devreme ( t p i) momentul finalizării acestui eveniment.

Rezervele unui eveniment pe calea critică sunt egale cu zero, deoarece pe acesta t p i =t p i

Pentru fiecare lucrare tij) este definit:

data de începere anticipată (t w.d. ij)- timpul minim posibil pentru începerea acestei lucrări.

data de încheiere anticipată (t p.o. ij)- termenul minim posibil pentru finalizarea acestei lucrări, pe o durată dată de lucru

data de începere întârziată (t b.s. ij)- maximul datelor admise pentru începerea acestei lucrări

data de încheiere târziu (t p.o. ij)- maximul termenelor admisibile pentru finalizarea acestei lucrări, la care mai sunt posibile executarea următoarelor lucrări cu respectarea termenului stabilit pentru producerea evenimentului final.

În mod evident, data de început devreme a activității coincide cu data devreme a debutului evenimentului său inițial, iar data de încheiere timpurie o depășește cu durata activității:

t r.n. ij = t p i

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

Data de încheiere tardivă a activității este aceeași cu data de întârziere a evenimentului de încheiere a acesteia, iar data de începere întârziată a activității este mai mică cu durata activității:

t p.o. ij = t p j

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

Timp de rezervă complet pentru finalizarea lucrării Rnij– perioada maximă de timp pentru care puteți întârzia începerea sau crește durata lucrării fără a modifica data stabilită pentru producerea evenimentului de sfârșit.

Timp liber pentru a lucra, care face parte din rezerva completă - perioada maximă de timp până la care puteți întârzia începerea sau crește durata lucrului, fără a modifica datele de început anticipate pentru lucrările ulterioare.

Locurile de muncă care se află pe calea critică nu au rezerve, deoarece toate rezervele sunt create datorită diferenței dintre duratele căilor critice și luate în considerare.

Un indicator relativ care caracterizează rezerva de timp pentru efectuarea muncii este coeficientul lor de tensiune, care este egal cu raportul dintre durata segmentelor de cale dintre aceleași evenimente, în plus, un segment face parte din calea de durată maximă din toate căile care trec prin această lucrare, iar celălalt segment face parte din calea critică.

3.Calculul modelelor de rețea

Parametrii de rețea pentru diagramele de rețea se calculează folosind o metodă grafică și tabelară, iar pentru cele complexe, o metodă matematică.

Grafic, metoda de calcul se realizează direct pe diagramă și este utilizată în cazurile în care numărul de evenimente este mic. Pentru a face acest lucru, fiecare cerc este împărțit în 4 sectoare.

Sectorul superior este rezerva de timp pentru producerea evenimentului R i

sectorul din stânga - data timpurie a evenimentului tpi

sector din dreapta - data tardivă a evenimentului t p i

jos - numărul evenimentului

Metoda de calcul a parametrilor

1) Momentul timpuriu al evenimentelor . Data timpurie a finalizării evenimentului inițial (primul sau zero) este considerată egală cu zero. Datele timpurii pentru finalizarea tuturor celorlalte evenimente sunt determinate într-o secvență strictă de un număr tot mai mare de evenimente. Pentru a determina data de finalizare anticipată a oricărui eveniment j, sunt luate în considerare toate locurile de muncă incluse în acest eveniment, pentru fiecare post data de finalizare anticipată a evenimentului final este determinată ca suma datei de încheiere anticipată a evenimentului inițial al lucrării și durata acestei lucrări tij, din valorile obţinute se selectează timpul maxim de finalizare timpurie a j-lea eveniment

t pj = (t pi +t ij) max și este înregistrat pe diagramă (sectorul din stânga al evenimentului)

2) Întârzieri pentru evenimente . Data târzie a finalizării evenimentului final este considerată egală cu data sa devreme. Calculul termenelor de întârziere pentru finalizarea tuturor celorlalte evenimente se efectuează în ordine inversă, conform numerelor descrescătoare ale evenimentelor. Pentru a determina termenul de întârziere pentru finalizarea evenimentului anterior i, se iau în considerare toate lucrările care ies din evenimentul i-a. Pentru fiecare job, se calculează termenul de întârziere pentru finalizarea evenimentului inițial t p i , ca diferență între data de finalizare tardivă a evenimentului final al acestei lucrări t p jși durata acestei lucrări tij.Din valoarea obținută, alegeți timpul minim de finalizare cu întârziere a evenimentului i-a: t p i = (t p j - t ij)min si se inregistreaza in sectorul potrivit.

3) Lungimea traseului critic este egală cu data timpurie a evenimentului de sfârșit.

4) Rezerve de timp pentru eveniment . La determinarea rezervelor de timp pentru evenimente, trebuie scăzut din numărul scris în sectorul din dreapta al acestui eveniment, numărul scris în sectorul din stânga și să-l puneți în sectorul superior.

5) La determinarea timpului total de rezervă pentru muncă se scade din numărul înregistrat în sectorul din dreapta al evenimentului final, numărul înregistrat în sectorul din stânga evenimentului inițial și durata lucrării în sine.

6) La determinarea rezervei libere de muncă, se scade din numărul înregistrat în sectorul din stânga evenimentului final, numărul înregistrat în sectorul din stânga evenimentului inițial și durata lucrării în sine.

Date inițiale:

Metoda tabelară

Codurile locurilor de muncă din tabel sunt scrise în index crescător i.

Coloanele 2 și 3 sunt completate cu date auxiliare: coduri ale lucrărilor anterioare și ulterioare. Aceste date vor fi necesare pentru calcule. Dacă lucrările sunt inițiale, adică nu există lucrări anterioare, sau finale, adică nu există lucrări ulterioare, atunci se pun liniuțe în coloanele corespunzătoare. Pot exista mai multe joburi anterioare și ulterioare în funcție de numărul de vectori care se termină sau încep într-un anumit eveniment./

Coloana 4 conține valorile duratei de lucru.

Coloana 5 începe datele calculate. Calculul se efectuează în două treceri prin rândurile tabelului. Primul trece prin rândurile de sus în jos, în care se calculează cele mai vechi date de lucru, iar al doilea trece prin liniile de jos în sus, în care se calculează datele de lucru întârziate.

Începerea timpurie a activităților care nu au cele anterioare (în coloana 2 - o liniuță) poate fi luată ca 0 dacă nu este specificată altă valoare. Finalizarea timpurie a lucrărilor este determinată conform formulei t r.o. ij = t pH ij + t ij și înscris în coloana 6.

Începutul timpuriu al restului poate fi definit ca, dacă, de exemplu, se ia în considerare lucrarea 2.5, care are un eveniment inițial de 2, atunci timpul său de început timpuriu este egal cu timpul de sfârșit timpuriu al lucrării 12, deoarece are un sfârșit. eveniment de 2. Valoarea din coloana 6 se rescrie în coloana 5 Codurile lucrărilor anterioare sunt indicate în coloana 2. Finalizarea timpurie este determinată și de formula t r.o. ij = t pH ij + t ij

Dacă, în coloana 2, se indică faptul că o anumită lucrare este precedată de mai multe lucrări (lucrarea 5.6 este precedată de lucrările 2.5 și 3.5), atunci este necesar să alegeți valoarea începutului timpuriu dintre mai multe opțiuni de valoare (9 - până la sfârșitul lucrării 2 ,5 sau 13 - până la sfârșitul lucrării 3.5). Regula de selecție corespunde formulei t p .n. ij = (t pi + t ij) max , adică este selectată valoarea maximă (în exemplu - 16). Terminațiile timpurii sunt definite ca mai sus.

Valoarea maximă a capătului timpuriu din coloana 6 corespunde valorii duratei căii critice (16).

A doua trecere de-a lungul rândurilor tabelului de la munca înregistrată în ultima linie până la munca înregistrată în prima linie vă permite să determinați valorile indicatorilor de performanță întârziați. Pentru joburile care nu au joburi ulterioare (în coloana 3 - o liniuță, în exemplul lucrării 46, 5,6), valoarea căii critice este scrisă în coloana de finalizare târziu (8). Pentru aceste locuri de muncă, valoarea de pornire întârziată este calculată prin formulă t a.s. ij t prin ij - t ij

Finalizarea cu întârziere a restului poate fi definită ca, dacă, de exemplu, se ia în considerare lucrarea 3.5, care are un eveniment de sfârșit de 5, atunci timpul său de sfârșit târziu este egal cu timpul de începere întârziat al lucrării 5.6, deoarece are un sfârșit. eveniment de 5. Valoarea din coloana 7 este rescrisă în coloana 8. Codurile lucrărilor ulterioare sunt indicate în coloana 3. Începutul târziu este determinat și de formula t a.s. ij t prin ij - t ij .

Dacă în coloana 3 se indică faptul că mai mult de un loc de muncă urmează un anumit loc de muncă (postul 0.1 este urmat de joburile 1.2 și 1.3), atunci este necesar să alegeți valoarea finisajului târziu dintre mai multe opțiuni (3 - conform ora de începere a lucrului 1 ,3 sau 7 - în funcție de ora de începere 1,2), este selectată valoarea minimă (în exemplu - 3). Pornirea târziu este determinată ca mai sus de formulă t a.s. ij t prin ij - t ij .

Valoarea jocului total (coloana 9) se calculează prin formula

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

Valoarea liberă a slăbiciunii (coloana 10) este calculată folosind formula

R cu ij = t ро ij - t рр ij - t ij

Orice succesiune de activități de rețea în care evenimentul de sfârșit al fiecărei activități coincide cu evenimentul de început al activității care urmează ei se numește prin.

Este apelată o cale de rețea în care punctul de pornire este același cu evenimentul de început și punctul final este evenimentul de final complet.

Calea de la evenimentul inițial la orice parcurs precedat acest eveniment. Se numește calea care precede evenimentul și are cea mai mare lungime maxim anterior. Se notează cu L 1 (i), iar durata sa este t.

Calea care leagă orice eveniment dat de cel final este numită ulterior cale. Această cale cea mai lungă se numește pe cât posibil ulteriorși este notat cu L 2 (i), iar durata sa este t.

Se numește calea completă cu cea mai mare lungime critic. Sunt numite alte căi decât calea critică relaxat. Au rezerve de timp.

Activitățile de pe calea critică sunt evidențiate cu linii groase sau linii duble. Durata căii critice este considerată parametrul principal al graficului.

Luați în considerare un algoritm pentru determinarea căii critice pe o diagramă de rețea folosind algoritmul metodei de programare dinamică.

Să sortăm vârfurile graficului după ranguri și să le numărăm de la sfârșit până la început. Acest lucru va face posibilă potrivirea numerelor de rang cu etapele de mișcare înapoi atunci când se găsesc controale optime condiționat pe ultimul, ultimele două și așa mai departe. etape. Găsirea căii critice va fi analizată folosind exemplul diagramei de rețea prezentată în Fig. 10.7.

Conform principiului optimității Bellman, controlul optim în fiecare etapă este determinat de scopul controlului și starea de la începutul etapei. Starea sistemului este evenimentele care se află pe rânduri. Pentru finalizarea evenimentului final X 16, este necesară finalizarea evenimentelor precedente. Stări posibile ale sistemului la începutul ultimei etape de lucru - apariția evenimentelor X 14 și X 15. În cercurile de la punctele X 14 și X 15 punem durata maximă de lucru în ultima etapă: X 14 5 , X 15 7 . Să găsim durata maximă de lucru în ultimele două etape. Starea sistemului la începutul penultimei etape se datorează evenimentului X 13. Durata maximă a căii care duce de la X 13 la X 16 este .

Prin urmare, numărul 14 ar trebui plasat în cerc lângă evenimentul X 13 și așa mai departe. Efectuând etapele de la final până la început, aflăm lungimea traseului critic t cr =96. Pentru a găsi calea critică în sine, să trecem prin procesul de calcul de la evenimentul inițial X 1 până la finalul X 16 . Am obținut numărul 96 la prima etapă (de la început) adăugând 16 la numărul 80. Prin urmare, calea critică în această etapă va fi egală cu (X 1, X 3). Numărul 80 = 16 + 64. Prin urmare, calea critică în a doua etapă trece prin lucrare (X 3 , X 4), etc. Pe grafic, este marcat cu o linie aldine:

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

Date anticipate și târzii pentru finalizarea evenimentelor. Slack eveniment

Toate căile care diferă ca durată de calea critică au rezerve de timp. Diferența dintre lungimea căii critice și orice cale non-critică se numește slăbirea totală a căii non-critice dată și este notă cu: .

termen timpuriu finalizarea unui eveniment se numește cel mai devreme moment în timp până la care toate lucrările premergătoare acestui eveniment sunt finalizate, adică este determinată de durata traseului maxim care precede evenimentul, adică:

sau

Pentru a găsi data timpurie a evenimentului j , trebuie să cunoașteți calea critică a subgrafului direcționat, care constă din setul de căi care preced evenimentul dat j . Termenul timpuriu al evenimentului inițial este egal cu zero: t p (1)=0.

termen întârziat eveniment numit cel mai recent moment în timp, după care există exact atât timp cât este necesar pentru a finaliza toate lucrările care urmează acestui eveniment. Ultimul dintre termenele admisibile pentru finalizarea evenimentului, în total cu durata de execuție a tuturor activităților ulterioare, nu trebuie să depășească lungimea traseului critic. Termenul de întârziere pentru un eveniment este calculat ca diferența dintre durata căii critice și durata maximului de căi care urmează evenimentului:

Pentru evenimentele pe calea critică, datele timpurii și cele târzii pentru finalizarea acestor evenimente sunt aceleași.

Diferența dintre datele târzii și cele devreme pentru finalizarea evenimentului este ora de rezervă a evenimentului: . Intervalul se numește interval de libertate a evenimentului. Slack-ul evenimentului arată perioada maximă de timp permisă în care un eveniment poate fi respins fără a crește calea critică.

Din moment ce suma determină durata traseului de lungime maximă care trece prin acest eveniment, apoi , i.e. slăbirea oricărui eveniment este egală cu slăbirea totală a căii maxime prin acest eveniment.

Când se calculează manual parametrii de timp, este convenabil să se folosească metoda celor patru sectoare. Cu această metodă, cercul diagramei de rețea care denotă evenimentul este împărțit în patru sectoare. Numărul evenimentului este pus în sectorul superior; în stânga - momentul cel mai devreme posibil al evenimentului (); în dreapta - cel mai târziu din timpul admisibil al evenimentului; în sectorul inferior - timpul de rezervă al acestui eveniment: .

Pentru a calcula cea mai devreme scadență pentru evenimente: , aplicați formula , având în vedere evenimentele în ordinea crescătoare a numerelor, de la inițial la final, conform lucrărilor cuprinse în acest eveniment.

Data de întârziere pentru finalizarea evenimentelor este calculată prin formula , incepand de la evenimentul final, pentru care ( - numarul evenimentului final), in functie de joburile care ies din acesta.

Evenimentele critice au un joc de zero. Ele definesc activitățile critice și calea critică.

Exemplul 10.2. Lăsați diagrama de rețea prezentată în fig. 10.8.

Soluţie. Calculați datele timpurii pentru finalizarea evenimentelor:

Deci, evenimentul final poate avea loc abia în a 14-a zi de la începerea proiectului. Acesta este timpul maxim în care pot fi finalizate toate activitățile proiectului. Este determinată de calea cea mai lungă. Data de finalizare timpurie a lucrării 6 =14 coincide cu timpul critic kp - durata totală a lucrării aflată pe calea critică. Acum puteți evidenția activitățile care aparțin căii critice, revenind de la evenimentul final la cel inițial. Dintre cele două locuri de muncă incluse în evenimentul 6 , , lungimea căii critice a determinat locurile de muncă (5, 6), întrucât (5 + 56)=14. Prin urmare, munca (5, 6) este critică și așa mai departe. Lucrările (1, 3), (3, 4), (4, 5), (5, 6) au determinat calea critică: cr = (1-3-4-5-6).

Acum calculăm datele târzii pentru finalizarea evenimentelor. Lăsa . Să folosim metoda de programare dinamică. Toate calculele vor fi efectuate de la evenimentul final până la evenimentul inițial. Datele tardive pentru finalizarea evenimentelor sunt:

Deoarece după evenimentul 5, pentru a finaliza proiectul, lucrarea (5, 6) trebuie finalizată timp de 3 zile. Din evenimentul 4 ies două locuri de muncă, deci:

Slack pentru evenimentul 2 este: . Rezervele evenimentelor rămase sunt egale cu zero, deoarece aceste evenimente sunt critice.

Date de început și de sfârșit devreme și târzie. Determinarea rezervelor de timp de lucru. Rezervă completă de timp de lucru.

Evenimentul imediat premergător acestei lucrări va fi convocat primarși notează , și evenimentul imediat care îl urmează, - finalși desemnează. Atunci orice loc de muncă va fi notat cu . Cunoscând momentul finalizării evenimentelor, puteți determina parametrii de timp ai lucrării.

Ora de pornire devreme este egală cu data timpurie a evenimentului: .

Sfârșitul timpuriu al lucrului este egală cu suma datei timpurii pentru finalizarea evenimentului inițial și a duratei acestei lucrări: sau .

Sfârșit târziu de lucru coincide cu data de finalizare tardivă a evenimentului său final: .

Ora de începere târziu este egală cu diferența dintre data târzie de finalizare a evenimentului său final și valoarea acestei lucrări:

Deoarece termenele de finalizare a lucrării se încadrează în limitele determinate de și , acestea pot avea diferite tipuri de rezerve de timp.

Rezerva intreaga de timp de lucru - este timpul maxim necesar pentru finalizarea oricărei lucrări fără a depăși calea critică. Se calculează ca diferența dintre evenimentul de sfârșit târziu și momentul timpuriu pentru finalizarea lucrării în sine: . De atunci .

În acest fel, rezervă completă de funcționare este timpul maxim în care durata sa poate fi mărită fără a modifica durata traseului critic. Toate joburile necritice au o slăbiciune totală diferită de zero.

Rezervare de timp de lucru gratuit- aceasta este marja de timp care poate fi disponibilă la efectuarea acestei lucrări, cu condiția ca evenimentele sale inițiale și finale să aibă loc la cele mai vechi date: .

Calculul graficului rețelei în mod tabelar se face conform formulelor menționate anterior în secțiunea 4 (1-10). La determinarea parametrilor modelelor de rețea într-un mod analitic, calculul se realizează sub forma unui tabel. Luați în considerare caracteristicile calculului modelelor de rețea în acest fel (aplicația 1) folosind exemplul de calcul al parametrilor diagramei de rețea prezentate în sarcina pentru acest lucru de curs (opțiunea 15).

În etapa inițială, este necesar să se descrie modelul de rețea inițial. În acest caz, cifrurile tuturor job-urilor și dependențelor sunt introduse în prima coloană a tabelului, începând cu jobul care iese din primul eveniment. Codurile de locuri de muncă trebuie incluse în tabel secvenţial, ordinea arbitrară de includere a locurilor de muncă şi a dependenţelor în tabel nu este permisă. A doua coloană a tabelului conține durata tuturor lucrărilor și dependențelor.

Calculul programului rețelei începe cu determinarea valorilor parametrilor timpurii ai lucrării. Începutul timpuriu al lucrării 1-2 este egal cu zero (formula 1), iar sfârșitul său timpuriu conform formulei 2.

Începutul timpuriu al activităților 2-6 și 2-7 (în conformitate cu formula 3) este egal cu sfârșitul timpuriu al activității 1-2.

Valoarea maximă de finalizare anticipată a lucrării 19-21, egală cu 36, determină durata căii critice și, prin urmare, durata totală a executării tuturor activităților din modelul original de rețea. Valoarea rezultată a finalizării timpurii a acestei lucrări 19-21 = 36 este transferată în coloana finalizării cu întârziere a lucrării finale 20-21.

Începutul tardiv al lucrărilor 20-21 se determină conform formulei 5 (= 34)

Începutul târziu al lucrării 20-21 este sfârșitul târziu al lucrării 15-20 (=) care îl precede.

În plus, calculul parametrilor de întârziere se efectuează în mod similar, cu excepția cazurilor în care jobul are mai multe joburi ulterioare (de exemplu, jobul 6-9 are două ulterioare - 9-10 și 9-14). În acest caz, în conformitate cu formula 4, finalizarea cu întârziere a lucrării 6-9 este egală cu valoarea minimă a începerii tardive a lucrărilor ulterioare 9-10 și 9-14.

Pentru a găsi poziția căii critice, este necesar să se determine valorile rezervelor de timp totale și private pentru fiecare lucrare și dependențele diagramei de rețea și să se introducă valorile lor în coloanele a 7-a și a 8-a ale calculului. tabel, respectiv.

Rezerva totală de timp de muncă, conform formulelor 8-9, se determină ca diferență dintre finalizarea tardivă și cea anticipată sau ca diferența dintre începutul târziu și începutul lucrării corespunzătoare. Este util să se determine valoarea jocului total în ambele moduri, coincidența valorilor obținute poate fi considerată o verificare suplimentară. De exemplu, pentru munca 6-7:

Leziunea parțială a timpului de lucru, conform formulei 10, este definită ca diferența dintre valoarea începerii timpurii a activității ulterioare și valoarea încheierii timpurii pentru această activitate. De exemplu, pentru munca 6-7:

Calea critică este caracterizată de slăbire zero. Compararea parametrilor modelului de rețea obținut prin sector și metodele tabelare ar trebui să dezvăluie identitatea lor completă, prezența discrepanțelor indică eronarea calculelor.

Metodă grafică pentru calculul diagramelor de rețea

Calculul grafic al rețelei în mod grafic se realizează în mod similar cu metoda tabulară (formulele 1-10), însă metoda grafică sau sectorială de calculare a parametrilor graficului rețelei presupune înregistrarea lor direct pe model (Anexa 2). Fiecare eveniment (cerc) este împărțit în patru sectoare. Desemnarea sectoarelor este prezentată în următoarea figură:

Pentru activitățile pe calea critică, valorile slăbirii totale și parțiale sunt egale cu zero; este evidențiată pe diagrama de rețea cu o linie dublă.

Pentru a verifica corectitudinea calculelor efectuate, trebuie să vă asigurați că:

• * a dezvăluit o cale critică continuă;
• * rezervele de timp calculate au o valoare nenegativă;
• * valoarea slack-ului privat pentru toate locurile de muncă este mai mică sau egală cu valoarea slack-ului total pentru aceste locuri de muncă;
• * cel puțin o valoare a începerii tardive a lucrărilor (lucrărilor) care iese din primul eveniment este egală cu zero.

Două sunt cunoscute metoda de calcul al parametrilor graficului de rețea”. calcul direct pe graficul rețelei; analitice (tabulare).

Calcul principalii indicatori ai modelului de rețea se poate face în felul următor.

• 1. Calcularea datelor timpurii:
  • ? începerea timpurie a muncii este determinată de durata celei mai lungi trasee de la evenimentul inițial până la începerea execuției acestei lucrări,
  • ? datele de finalizare anticipate- aceasta este cea mai devreme dată posibilă de finalizare a lucrării. Ora de încheiere timpurie a lucrării este egală cu suma timpului de începere timpuriu a lucrării și a duratei lucrării în sine.
• 2.Calculul drumului critic. Durata sa este definită ca timpul total al activităților pe calea critică, adică. timpul de finalizare a întregului complex de lucrări cu cea mai mare paralelizare a tuturor lucrărilor. Acest timp este egal cu cel mai mare timp de finalizare timpurie a completărilor graficului de rețea. Calea critică trece prin evenimente care nu au rezerve de timp (prin activități critice).
• 3.Calculul termenelor de începere și de sfârșit cu întârziere sunt determinate din posibilitățile de deplasare a limită la dreapta de-a lungul axei numerice a termenelor de finalizare a lucrărilor astfel încât timpul traseului critic să nu fie modificat. Prin urmare, este logic să se efectueze calcule de la ultimul eveniment până la primul și să se determine mai întâi momentul încheierii cu întârziere a lucrărilor, apoi să se calculeze ora începerii tardive a lucrărilor:
  • ?data de începere întârziată (ij) este definită ca diferența dintre finalizarea cu întârziere a lucrării și durata lucrării în sine,
  • ? data de finalizare tardiva este determinată de valoarea traseului de durată minimă care duce la acesta de la evenimentul final și se calculează ca diferență între calea critică și durata maximă de lucru de la evenimentul final al rețelei până la evenimentul final al acestei lucrări.
• 4. Calculul rezervelor de timp”.

eurezervă completă de funcționare este definită ca diferența dintre începutul târziu și începutul timpuriu sau între terminarea târziu și terminarea timpurie. Trebuie remarcat faptul că durata totală a timpului de lucru pe calea critică este egală cu zero,

• ? privat (liber) rezerve de timp”.
• 1)slăbiciunea privată de primul fel determinat de capacitatea de a schimba ora de pornire târziu ( ij) la date anterioare, fără a modifica termenele de întârziere pentru finalizarea lucrărilor imediat precedente,
• 2) slăbire privată de al doilea fel determinat de capacitatea de a schimba sfârşitul timpuriu al muncii (ij) la date ulterioare, fără a modifica datele timpurii pentru începerea lucrărilor imediat ulterioare; este determinată de diferența dintre începutul timpuriu al activității ulterioare și încheierea timpurie a acestei activități.

Să luăm în considerare procedura de calcul a parametrilor folosind un exemplu. Schema rețelei este prezentată în fig. 7.5.

Orez. 7.5.

Pentru a calcula parametrii, vom folosi metoda tabulară, iar pentru a simplifica percepția, vom rezuma totul într-un singur tabel. 7.1.

Reguli de utilizare a rezervelor de timp în planificarea rețelei.

• 1. Pentru ca rezervele totale și parțiale de muncă (y) să fie egale, este necesar și suficient ca evenimentul final Y al lucrării în cauză să fie un eveniment pe calea critică.
• 2. Dacă rezervă completă (Eu și]1) a unor lucrări este egală cu zero, apoi rezerva privată de al doilea tip (g "f) este de asemenea egal cu zero. Între aceste rezerve există întotdeauna un raport R(IJ) > r"ijy Rezervele de timp totale și private sunt întotdeauna mai mari sau egale cu zero.
• 3. Pentru ca rezerva parțială de timp de lucru (y) să fie egală cu zero, este necesar și suficient ca această muncă să se afle pe traseul de lungime maximă de la primul eveniment la evenimentul y.
• 4. Dacă durata muncii (y) este mărită cu p, i.e. p atunci data de începere anticipată a lucrării ulterioare va crește cu valoarea p - g" ("uu
• 5. Dacă durata muncii (y) este mărită cu suma rezervei totale de timp pentru această lucrare, atunci se formează o nouă cale critică, a cărei durată este egală cu durata celei vechi.
• 6. Rezerva totală de timp de lucru (y) este egală cu suma rezervei parțiale de timp a celui de-al doilea tip al acestei lucrări și minimul rezervei totale a tuturor lucrărilor imediat ulterioare.

Rezultatele calculării parametrilor diagramei de rețea

Tabelul 7.1

	Durată	Din timp	termeni, h	Întâlniri târzii, h		Rezerve de timp, h
	lucrări, h	Începuturile	terminatii	Începuturile	terminatii	Deplin	Gratuit
	Calea critică, h		(lucrările 1-3

7. Dacă durata de lucru (r /) este mărită cu p, atunci va apărea o nouă cale critică, a cărei durată va depăși durata vechiului drum critic cu p -

După ce se construiește graficul rețelei și se calculează principalii indicatori, aceștia încep să-l optimizeze.

• 1. Selectați calea critică și găsiți lungimea acesteia;
• 2. Stabiliți rezervele de timp pentru fiecare eveniment;
• 3. Determinați rezervele de timp ale întregii lucrări și factorul de intensitate al muncii penultimei lucrări

Soluţie

Pentru a rezolva problema, aplicăm următoarea notație.

Element de rețea	Nume parametru	Simbol parametru
Evenimentul i	Data de finalizare anticipată a evenimentului
Data de finalizare cu întârziere a evenimentului
Slack eveniment
Lucrare (i, j)	Timpul de lucru
Ora de pornire devreme
Sfârșitul timpuriu al lucrului
Ora de începere târziu
Sfârșit târziu de lucru
Rezervă completă de funcționare
	Timp de calatorie
Lungimea traseului critic
Rezervare timp de călătorie

Pentru a determina rezervele de timp pentru evenimentele rețelei, se calculează cele mai vechi t p și cele mai recente t p date pentru finalizarea evenimentelor. Orice eveniment nu poate avea loc înainte ca toate evenimentele anterioare să fi fost finalizate și toate lucrările anterioare nu au fost finalizate. Prin urmare, timpul timpuriu (sau așteptat) tp(i) al i-lea eveniment este determinat de durata căii maxime care precedă acest eveniment:

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

unde L ni este orice cale care precede evenimentul i, adică calea de la evenimentul inițial la i-lea al rețelei.

Dacă evenimentul j are mai multe căi anterioare și, prin urmare, mai multe evenimente anterioare i, atunci este convenabil să găsiți data timpurie pentru finalizarea evenimentului j folosind formula:

t p (j) = max (2)

Întârzierea finalizării evenimentului i în raport cu data sa devreme nu va afecta timpul de finalizare a evenimentului final (și, prin urmare, timpul de finalizare a complexului de lucrări) până la suma timpului de finalizare a acestui eveniment și durata (lungimea) maximului traseelor ​​care îl urmează nu depăşeşte lungimea drumului critic. Prin urmare, termenul târziu (sau limită) t p (i) al finalizării celui de-al i-lea eveniment este egal cu:

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

unde Lci este orice cale care urmează evenimentului i, adică. calea de la i-lea la evenimentul final al rețelei.

Dacă evenimentul i are mai multe căi ulterioare și, prin urmare, mai multe evenimente ulterioare j, atunci data de finalizare târzie a evenimentului i poate fi găsită convenabil folosind formula:

t p (i) = min

Rezerva de timp R(i) a celui de-al i-lea eveniment este definită ca diferența dintre datele târzii și cele timpurii ale finalizării acestuia:

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

Slack-ul unui eveniment arată cât de mult poate fi amânat evenimentul fără a provoca o creștere a duratei pachetului de lucru.

Evenimentele critice nu au slăbire, deoarece orice întârziere în finalizarea unui eveniment pe calea critică va provoca aceeași întârziere în finalizarea evenimentului final. Astfel, după ce am determinat termenul timpuriu al evenimentului final al rețelei, determinăm astfel lungimea căii critice.

Când determinăm momentul timpuriu al evenimentelor tp(i), ne deplasăm de-a lungul graficului rețelei de la stânga la dreapta și folosim formulele (1), (2).

Calculul calendarului evenimentelor.

Pentru i=0 (eveniment inițial), evident 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.

Lungimea căii critice este egală cu data finalizării timpurii a evenimentului final 11: t kp =tp(11)=44

Când determinăm datele târzii pentru finalizarea evenimentelor t p (i), ne deplasăm prin rețea în direcția opusă, adică de la dreapta la stânga, și folosim formulele (3), (4).

Pentru i=11 (evenimentul final), data târzie a evenimentului trebuie să fie egală cu data sa devreme (în caz contrar, lungimea căii critice se va modifica): 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.

Toate liniile care încep cu numărul 8 sunt examinate.

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

Toate liniile care încep cu numărul 7 sunt examinate.

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.

Toate liniile care încep cu numărul 5 sunt examinate.

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.

Toate liniile care încep cu numărul 3 sunt examinate.

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;

Tabelul 1 - Calculul rezervei de evenimente

Numărul evenimentului	Momentul evenimentului: tp(i) devreme	Datele evenimentului: tp(i) târziu	Rezervă de timp, R(i)

Completarea tabelului 2.

Lista lucrărilor și durata acestora vor fi transferate în coloana a doua și a treia. În acest caz, lucrarea trebuie înregistrată în coloana 2 secvenţial: mai întâi, începând de la numărul 0, apoi de la numărul 1 etc.

În a doua coloană, punem un număr care caracterizează numărul lucrărilor imediat precedente (KPR) evenimentului de la care începe lucrarea în cauză.

Deci, pentru lucrarea (1,2) din coloana 1 punem cifra 1, deoarece numărul 1 se termină cu 1 lucrare: (0,1).

Coloana 4 este obținută din tabelul 1 (t p (i)). Coloana 7 este obținută din tabelul 1 (t p (i)).

Valorile din coloana 5 se obțin prin însumarea coloanelor 3 și 4.

În coloana 6, începerea tardivă a lucrărilor este definită ca diferența dintre finalizarea cu întârziere a acestor lucrări și durata acestora (datele din coloana 3 sunt scăzute din valorile coloanei 7);

Conținutul coloanei 8 (slăbire totală R(ij)) este egal cu diferența dintre coloanele 6 și 4 sau coloanele 7 și 5. Dacă R(ij) este egal cu zero, atunci munca este critică

Tabelul 2 - Analiza modelului de rețea în timp

Lucru (i,j)	Numărul lucrărilor anterioare	Durata tij	Date timpurii: începutul tijR.N.	Date timpurii: sfârșitul tijР.О.	Date tardive: începutul tijP.N.	Date tardive: sfârșitul tijP.O.	Rezerve de timp: RijP complet	Rezervă independentă de timp Rij	Rezervație privată de primul fel, Rij1	Rezervă privată de tip II, RijC

De remarcat faptul că, pe lângă rezerva completă de timp de funcționare, există încă trei tipuri de rezerve. Slack-ul privat al primului tip R 1 - parte din timpul total, prin care durata muncii poate fi mărită fără a modifica data târzie a evenimentului său inițial. R 1 se găsește prin formula:

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

Slăbirea parțială de al doilea tip, sau slăbirea liberă Rc de lucru (i, j) este o parte din slăbirea totală, prin care durata muncii poate fi mărită fără a modifica data timpurie a evenimentului său de sfârșit. Rc se găsește prin formula:

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

Valoarea slack-ului de rulare liberă indică locația slack-ului necesară pentru optimizare.

Rezerva de timp independentă Rn de muncă (i, j) este o parte din rezerva totală obținută pentru cazul în care toate lucrările anterioare se termină cu întârziere, iar toate lucrările ulterioare încep devreme. Rn se găsește prin formula:

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

traiectorie critică: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Durata traseului critic: 44

Să găsim coeficientul de intensitate a muncii penultimei lucrări. Deoarece lungimea căii critice este 44, calea maximă prin lucru (1,10) este 32, atunci

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

4. Un ISP dintr-un oraș mic are 5 canale de servicii dedicate. În medie, durează 25 de minute pentru a servi un client. Sistemul primește în medie 6 aczas pe oră. Dacă nu există canale gratuite, urmează un refuz. Determinați caracteristicile serviciului: probabilitatea de defecțiune, numărul mediu de linii de comunicație ocupate de serviciu, debitul absolut și relativ, probabilitatea de serviciu. Găsiți numărul de canale dedicate pentru care debitul relativ al sistemului va fi de cel puțin 0,95. Să presupunem că fluxurile de cereri și servicii sunt cele mai simple

Intensitatea fluxului de serviciu:

Intensitatea sarcinii:

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

Intensitatea încărcăturii c=2,5 arată gradul de consistență dintre fluxurile de intrare și de ieșire ale cererilor de canal de serviciu și determină stabilitatea sistemului de așteptare.

Probabilitatea ca serviciul:

canalul 1 ocupat:

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

Sunt ocupate 2 canale:

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

Sunt ocupate 3 canale:

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

Sunt ocupate 4 canale:

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

Sunt ocupate 5 canale:

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

Probabilitatea de eșec este o fracțiune cereri respinse:

Aceasta înseamnă că 7% din cererile primite nu sunt acceptate pentru serviciu.

Probabilitatea de a deservi cererile primite-probabilitatea ca clientul să fie servit:

În sistemele cu defecțiuni, evenimentele de defecțiune și întreținere constituie un grup complet de evenimente, deci:

p deschis + p obs = 1

Debit relativ Q = p obs .

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

În consecință, 93% din cererile primite vor fi deservite. Numărul mediu de canale ocupate de serviciu

n s \u003d s * p obs \u003d 2,5 * 0,93 \u003d 2,326 canale.

Canale inactiv medii.

n pr \u003d n - n z \u003d 5 - 2.326 \u003d 2.7 canale.

Rata de ocupare a canalului de servicii.

Prin urmare, sistemul este ocupat în proporție de 50% cu întreținere.

Lățimea de bandă absolută

A \u003d pobs * l \u003d 0,93 * 6 \u003d 5,581 aplicații / oră.

Timpul mediu de inactivitate al QS.

t pr \u003d p otk * t obs \u003d 0,0697 * 0,417 \u003d 0,029 ore.

Numărul mediu de solicitări servite.

L obs \u003d s * Q \u003d 2,5 * 0,93 \u003d 2,326 unități.

Timpul mediu de rezidență al unei cereri în CMO(Formula lui Little).

Numărul de cereri respinse în decurs de o oră: l * p 1 = 0,418 cereri pe oră.

Performanță QS nominală: 5 / 0,417 = 12,002 aplicații pe oră.

Performanța reală a CMO: 5.581 / 12.002 = 47% din performanța nominală.

Să determinăm numărul de canale necesare pentru a asigura operabilitatea sistemului cu probabilitatea P ? 0,95

Pentru a face acest lucru, găsim n din condiția:

Să găsim probabilitatea ca dacă există 6 canale în sistem și toate sunt ocupate: