Într-o lecție practică, vom lua în considerare această cale și vom compara rezultatele simulării cu o soluție teoretică. Exemple de rezolvare a problemelor sistemelor de așteptare

Obiect matematic (abstract), ale cărui elemente sunt (Fig. 2.1):

• flux de intrare (intrat) de aplicații (cerințe) pentru serviciu;
• dispozitive de serviciu (canale);
• o coadă de aplicații care așteaptă serviciul;
• fluxul de ieșire (ieșire) al cererilor deservite;
• fluxul de cereri de îngrijire ulterioară după întreruperea serviciului;
• fluxul de cereri neservite.

Cerere(cerere, cerință, apel, client, mesaj, pachet) - un obiect care intră în QS și necesită service în dispozitiv. Setul de aplicații consecutive distribuite în formă de timp fluxul de intrare al aplicațiilor.

Orez. 2.1.

dispozitiv de service(dispozitiv, dispozitiv, canal, linie, unealtă, mașină, router etc.) - element QS, al cărui scop este de a deservi aplicațiile.

Serviciu- întârziere de ceva timp a solicitării în dispozitivul de service.

Durata serviciului- timpul de întârziere (serviciu) al aplicației în dispozitiv.

Dispozitiv de stocare(buffer, buffer de intrare, buffer de ieșire) - un set de locuri pentru așteptarea aplicațiilor în fața dispozitivului de servire. Numar locuri de asteptare - Capacitate de stocare.

O cerere primită de CMO poate fi în două stări:

• 1) serviciu(în dispozitiv);
• 2) așteptări(în acumulator), dacă toate dispozitivele sunt ocupate cu alte solicitări.

Revendicările din formularul acumulator și în așteptare de service întoarce aplicatii. Numărul de aplicații în acumulatorul care așteaptă serviciul - lungimea cozii.

Disciplina tampon(disciplina de coadă) - regula pentru introducerea aplicațiilor primite în unitate (buffer).

Disciplina de serviciu- regula de selectare a cererilor din coada pentru service în dispozitiv.

O prioritate- dreptul de preempțiune (de a capta resurse) de a intra în acumulator sau de a selecta din coadă pentru service în dispozitivele aplicațiilor dintr-o clasă în raport cu aplicațiile din alte clase.

Există multe sisteme de așteptare care diferă în ceea ce privește organizarea structurală și funcțională. În același timp, dezvoltarea metodelor analitice pentru calcularea indicatorilor de performanță QS implică în multe cazuri o serie de restricții și ipoteze care restrâng setul de QS-uri studiate. De aceea nu există un model analitic general pentru o structură complexă arbitrară QS.

Modelul analitic QS este un set de ecuații sau formule care permit determinarea probabilităților stărilor sistemului în cursul funcționării acestuia și a indicatorilor de performanță pe baza parametrilor cunoscuți ai fluxului de intrare și canalelor de servicii, disciplinelor de tamponare și servicii.

Modelarea analitică a QS-ului este mult facilitată dacă procesele care au loc în QS sunt markoviane (fluxul de aplicații este cel mai simplu, timpii de serviciu sunt distribuiti exponențial). În acest caz, toate procesele din QS pot fi descrise prin ecuații diferențiale obișnuite, iar în cazul limită - pentru stările staționare - prin ecuații algebrice liniare și, rezolvându-le prin orice metode disponibile în pachetele software matematice, se determină indicatorii de performanță selectați. .

În sistemele IM, la implementarea QS, sunt acceptate următoarele restricții și ipoteze:

• aplicație introdusă în sistem imediat intră în serviciu dacă nu există solicitări în coadă și dispozitivul este liber;
• în dispozitiv pentru întreținere în orice moment poate fi doar unu cerere;
• după încheierea serviciului oricărei solicitări din dispozitiv, următoarea solicitare este selectată din coadă pentru service instantaneu, adică dispozitivul nu inactivează dacă există cel puțin o aplicație în coadă;
• primirea aplicațiilor în QS și durata serviciului acestora nu depind de numărul de aplicații deja în sistem sau de alți factori;
• durata cererilor de deservire nu depinde de intensitatea cererilor care intră în sistem.

Să ne oprim asupra unor elemente ale QS mai detaliat.

Fluxul de intrare (intrat) al aplicațiilor. Fluxul evenimentelor se numește o succesiune de evenimente omogene care urmează unul după altul și care au loc în unele, în general, Aleatoriu puncte în timp. Dacă evenimentul constă în apariția unor pretenții, avem fluxul de aplicare. Pentru a descrie fluxul de aplicații în cazul general, este necesar să se stabilească intervalele de timp t = t k - t k-1între momentele adiacente t k _ kși t k primirea cererilor cu numere de serie la - 1 și la respectiv (la - 1, 2, ...; t 0 - 0 - momentul inițial de timp).

Principala caracteristică a fluxului de aplicare este sa intensitatea X- numărul mediu de aplicații care ajung la intrarea QS pe unitatea de timp. Valoarea t = 1/X defineste intervalul de timp mediu dintre două comenzi consecutive.

Fluxul este numit determinat dacă intervale de timp t laîntre aplicațiile adiacente iau anumite valori precunoscute. Dacă intervalele sunt aceleași (x la= t pentru toate k = 1, 2, ...), atunci fluxul este numit regulat. Pentru o descriere completă a fluxului obișnuit de cereri, este suficientă setarea intensității fluxului X sau valoarea intervalului t = 1/X.

Un flux în care intervale de timp x kîntre aplicațiile adiacente sunt variabile aleatoare, numite Aleatoriu. Pentru o descriere completă a unui flux aleator de aplicații în cazul general, este necesar să se stabilească legile de distribuție F fc (x fc) pentru fiecare dintre intervalele de timp. x k, k = 1,2,....

Flux aleatoriu în care toate intervalele de timp x b x 2,... între clienții consecutivi adiacenți sunt variabile aleatoare independente descrise de funcțiile de distribuție FjCij), F 2 (x 2), ... respectiv, se numește flux cu efect secundar limitat.

Se numește flux aleatoriu recurent, dacă toate intervalele de timp xb t 2 , ... distribuit între aplicații sub aceeasi lege F(t). Există multe fluxuri recurente. Fiecare lege de distribuție generează propriul flux recurent. Fluxurile recurente sunt altfel cunoscute sub denumirea de fluxuri Palm.

Dacă intensitatea X iar legea de distribuție F(t) a intervalelor dintre cererile succesive nu se modifică în timp, atunci fluxul de cereri se numește staționarÎn caz contrar, fluxul de aplicație este nestaționară.

Dacă în fiecare moment al timpului t k la intrarea QS poate apărea un singur client, apoi se apelează fluxul de clienți comun. Dacă mai multe aplicații pot apărea în orice moment, atunci fluxul de aplicații este extraordinar, sau grup.

Fluxul de cereri se numește flux nici un efect secundar, dacă se primesc cereri indiferent unul de altul, adică momentul primirii următoarei cereri nu depinde de când și câte cereri au fost primite înainte de acest moment.

Se numește un flux obișnuit staționar fără efect secundar cel mai simplu.

Intervalele de timp t dintre cereri în cel mai simplu flux sunt distribuite conform exponenţială (exemplar) lege: cu funcția de distribuție F(t) = 1 - e~ m; densitatea distribuţiei/(f) = Heh~"l, Unde X > 0 - parametru de distribuție - intensitatea fluxului de aplicații.

Cel mai simplu flux este adesea numit Poisson. Denumirea provine de la faptul că pentru acest flux probabilitatea P fc (At) de apariție exact la cereri pentru un anumit interval de timp At este determinat legea lui Poisson:

Trebuie remarcat faptul că fluxul Poisson, spre deosebire de cel mai simplu, poate fi:

• staționar, dacă intensitatea X nu se modifică în timp;
• nestaționar, dacă debitul depinde de timp: X= >.(t).

În același timp, cel mai simplu flux, prin definiție, este întotdeauna staționar.

Studiile analitice ale modelelor de așteptare sunt adesea efectuate sub ipoteza celui mai simplu flux de cereri, care se datorează unui număr de caracteristici remarcabile inerente acestuia.

1. Însumarea (unificarea) fluxurilor. Cel mai simplu flux din teoria QS este similar cu legea distribuției normale din teoria probabilității: trecerea la limita pentru un flux care este suma fluxurilor cu caracteristici arbitrare cu o creștere infinită a numărului de termeni și o scădere a intensității lor duce la cel mai simplu flux.

Sumă N fluxuri ordinare staţionare independente cu intensităţi x x x 2 ,..., X N formează cel mai simplu flux cu intensitate

X=Y,^i cu condiţia ca fluxurile adăugate să aibă mai mult sau

impact mai puțin la fel de mic asupra debitului total. În practică, debitul total este aproape de cel mai simplu la N > 5. Deci când se însumează cele mai simple fluxuri independente, debitul total va fi cel mai simplu pentru orice valoare N.

• 2. Rarefacția probabilistică a curgerii. probabilistică(dar nedeterminist) rarefiere cel mai simplu flux aplicații, în care orice aplicație la întâmplare cu o anumită probabilitate R este exclus din flux indiferent dacă alte aplicații sunt sau nu excluse, duce la formare cel mai simplu flux cu intensitate X* = pX, Unde X- intensitatea fluxului initial. Fluxul aplicațiilor excluse cu intensitate X** = (1 - p)X- de asemenea protozoar curgere.
• 3. Eficiență. Dacă canalele (dispozitivele) de servire sunt concepute pentru cel mai simplu flux de solicitări cu intensitate X, atunci deservirea altor tipuri de fluxuri (cu aceeași intensitate) va fi asigurată cu o eficiență nu mai mică.
• 4. Simplitate. Asumarea celui mai simplu flux de aplicații permite multor modele matematice să obțină într-o formă explicită dependența indicatorilor QS de parametri. Cel mai mare număr de rezultate analitice a fost obținut pentru cel mai simplu flux de cereri.

Analiza modelelor cu fluxuri de aplicații diferite de cele mai simple complică de obicei calculele matematice și nu permite întotdeauna obținerea unei soluții analitice explicite. Cel mai „simplu” flux și-a primit numele tocmai datorită acestei caracteristici.

Aplicațiile pot avea drepturi diferite pentru a începe serviciul. În acest caz, se spune că aplicațiile sunt eterogen. Avantajele unor fluxuri de aplicații față de altele la începutul serviciului sunt stabilite de priorități.

O caracteristică importantă a fluxului de intrare este coeficientul de variație

unde t int - așteptarea matematică a lungimii intervalului; despre- abaterea standard a lungimii intervalului x int (variabilă aleatoare) .

Pentru cel mai simplu flux (a = -, m = -) avem v = 1. Pentru majoritatea

fluxuri reale 0

Canale de servicii (dispozitive). Principala caracteristică a canalului este durata serviciului.

Durata serviciului- timpul petrecut de aplicație în dispozitiv - în cazul general, valoarea este aleatorie. În cazul unei încărcări neuniforme a QS, timpii de deservire pentru cereri de diferite clase pot diferi în funcție de legile de distribuție sau numai de valorile medii. În acest caz, se presupune de obicei că timpii de serviciu pentru cererile fiecărei clase sunt independente.

Adesea, practicienii presupun că durata cererilor de service este distribuită legea exponenţială ceea ce simplifică foarte mult calculele analitice. Acest lucru se datorează faptului că procesele care au loc în sistemele cu o distribuție exponențială a intervalelor de timp sunt Markov procese:

unde c - intensitatea serviciului, aici p = _--; t 0 bsl - matematică-

tic timp de așteptare pentru service.

Pe lângă distribuția exponențială, există distribuții Erlang /c, distribuții hiperexponențiale, distribuții triunghiulare și altele. Acest lucru nu trebuie să ne încurce, deoarece se arată că valoarea criteriilor de eficiență QS depinde puțin de forma legii distribuției timpului de serviciu.

În studiul QS, esența serviciului, calitatea serviciului, nu este luată în considerare.

Canalele pot fi absolut de incredere acestea. nu da gres. Mai degrabă, poate fi acceptat în studiu. Canalele pot avea fiabilitate supremă.În acest caz, modelul QS este mult mai complicat.

Eficiența QS depinde nu numai de parametrii fluxurilor de intrare și a canalelor de servicii, ci și de secvența în care cererile primite sunt deservite, de exemplu. de la moduri de a gestiona fluxul de aplicații atunci când acestea intră în sistem și sunt trimise pentru service.

Modalitățile de gestionare a fluxului de aplicații sunt determinate de discipline:

• tamponare;
• serviciu.

Disciplinele de tamponare și întreținere pot fi clasificate în funcție de următoarele criterii:

• disponibilitatea priorităților între aplicațiile de diferite clase;
• o metodă pentru împingerea aplicațiilor din coadă (pentru disciplinele de buffering) și atribuirea cererilor de servicii (pentru disciplinele de servicii);
• o regulă pentru anticiparea sau selectarea cererilor de servicii;
• capacitatea de a schimba prioritățile.

În fig. 2.2.

Depinzând de disponibilitate sau lipsa de prioritatiîntre aplicațiile de diferite clase, toate disciplinele de tamponare pot fi împărțite în două grupe: neprioritare și prioritare.

De metoda de a împinge aplicațiile din stocare se pot distinge următoarele clase de discipline tampon:

• fără excluderea cererilor - cererile care au intrat în sistem și au constatat că unitatea este complet umplută se pierd;
• odată cu deplasarea aplicării acestei clase, i.e. aceeași clasă ca și cererea primită;
• cu deplasarea aplicației din clasa cu cea mai mică prioritate;
• odată cu deplasarea aplicaţiei din grupul claselor cu prioritate scăzută.

Orez. 2.2.

Disciplinele de tamponare pot folosi următoarele reguli pentru eliminarea cererilor din acumulator:

• deplasare accidentală;
• excluderea ultimului ordin, i.e. a intrat în sistem mai târziu decât toate;
• excluderea unei comenzi „lungi”, de ex. situat în acumulator mai mult decât toate aplicațiile primite anterior.

Pe fig. 2.3 prezintă clasificarea disciplinelor pentru aplicațiile de service în conformitate cu aceleași caracteristici ca și pentru disciplinele de buffering.

Uneori capacitatea de stocare în modele este considerată nelimitată, deși într-un sistem real este limitată. O astfel de ipoteză este justificată atunci când probabilitatea de a pierde o comandă într-un sistem real din cauza depășirii capacității de stocare este mai mică de 10 _3 . În acest caz, disciplina nu are practic niciun efect asupra executării cererilor.

Depinzând de disponibilitate sau lipsa de prioritatiîntre cererile diferitelor clase, toate disciplinele de serviciu, precum și disciplinele tampon, pot fi împărțite în două grupe: neprioritare și prioritare.

De cum sunt atribuite biletele de serviciu disciplinele de servicii pot fi împărțite în discipline:

• mod unic;
• modul grup;
• modul combinat.

Orez. 2.3.

În disciplinele de serviciu mod unic serviciu de fiecare dată doar unul atribuit cerere, pentru care cozile sunt scanate după încheierea deservirii cererii anterioare.

În disciplinele de serviciu modul grup serviciu de fiecare dată este atribuit un grup de aplicații o singură coadă, pentru care cozile sunt scanate numai după ce toate solicitările din grupul atribuit anterior au fost deservite. Noul grup de bilete alocat poate include toate biletele din coada dată. Solicitări de grup atribuite selectate secvenţial din coadăși sunt deservite de dispozitiv, după care următorul grup de aplicații dintr-o altă coadă este alocat pentru service în conformitate cu disciplina de serviciu specificată.

Modul combinat- o combinație de moduri unice și de grup, când o parte din cozile de solicitare este procesată în modul unic, iar cealaltă parte - în modul de grup.

Disciplinele de servicii pot folosi următoarele reguli de selecție a cererilor de servicii.

Neprioritar(aplicațiile nu au privilegii de serviciu timpurii - captura de resurse):

• serviciu primul venit, primul servit FIFO (primul în - primul iesit, primul intrat - primul iesit)
• serviciu invers- aplicația este selectată din coada în modul LIFO (ultimul în - primul iesit, ultimul intrat, primul iesit)
• serviciu aleatoriu- aplicația este selectată din coada în modul RAND (Aleatoriu- aleatoriu);
• serviciu ciclic- aplicațiile sunt selectate în procesul de interogare ciclică a unităților în secvența 1, 2, H DIN H- numărul de unități), după care se repetă secvența specificată;

Prioritate(aplicațiile au privilegii pentru service timpuriu - captarea resurselor):

• Cu priorități relative- daca in cursul deservirii curente a unei cereri intra in sistem cereri cu prioritati mai mari, atunci deservirea cererii curente, chiar fara prioritate, nu este intrerupta, iar cererile primite sunt trimise in coada de asteptare; prioritățile relative joacă un rol doar la sfârșitul serviciului curent al aplicației atunci când o nouă cerere de serviciu este selectată din coadă.
• Cu priorități absolute- la primirea unei cereri cu prioritate mare se întrerupe deservirea unei cereri cu prioritate redusă, iar cererea primită este trimisă spre service; o aplicație întreruptă poate fi returnată la coadă sau eliminată din sistem; dacă aplicația este returnată la coadă, atunci serviciul său ulterioar poate fi efectuat din locul întrerupt sau din nou;
• co priorități mixte- restricțiile stricte privind timpul de așteptare în coadă pentru deservirea aplicațiilor individuale impun atribuirea de priorități absolute acestora; ca urmare, timpul de așteptare pentru aplicațiile cu priorități scăzute se poate dovedi a fi inacceptabil de mare, deși cererile individuale au o marjă de timp de așteptare; pentru a îndeplini restricții la toate tipurile de solicitări, alături de priorități absolute, unor solicitări li se pot atribui priorități relative, iar restul pot fi servite într-un mod neprioritario;
• Cu alternarea prioritatilor- un analog al priorităților relative, prioritatea este luată în considerare numai în momentele de finalizare a deservirii curente a unui grup de solicitări dintr-o coadă și atribuirea unui nou grup pentru deservire;
• Intretinere programata- revendicările de diferite clase (situate în depozite diferite) sunt selectate pentru service conform unui anumit program care specifică succesiunea de interogare a cozilor de aplicații, de exemplu, în cazul a trei clase de aplicații (magazine), programul poate arăta ca (2, 1, 3, 3, 1, 2) sau (1, 2, 3, 3, 2, 1).

În sistemele IM informatice, de regulă, disciplina este implementată implicit FIFO. Cu toate acestea, au instrumente care oferă utilizatorului posibilitatea de a organiza disciplinele de servicii de care are nevoie, inclusiv în funcție de program.

Aplicațiile primite de CMO sunt împărțite în clase. În QS, care este un model matematic abstract, aplicațiile aparțin unor clase diferiteîn cazul în care acestea diferă în sistemul real simulat prin cel puțin una dintre următoarele caracteristici:

• durata serviciului;
• priorități.

Dacă aplicațiile nu diferă în ceea ce privește durata și prioritățile serviciului, acestea pot fi reprezentate de aplicații din aceeași clasă, inclusiv atunci când provin din surse diferite.

Pentru o descriere matematică a disciplinelor de servicii cu priorități mixte, folosim matrice de prioritate, care este o matrice pătrată Q = (q, ;), i, j - 1,..., I, I - numărul de clase de aplicații care intră în sistem.

Element q(j matricea stabilește prioritatea cererilor de clasă iîn legătură cu aplicațiile de clasă; și poate lua următoarele valori:

• 0 - fără prioritate;
• 1 - prioritate relativă;
• 2 - prioritate absolută.

Elementele matricei de prioritate trebuie să satisfacă următoarele cerinte:

• q n= 0, deoarece nu pot fi setate priorități între cererile din aceeași clasă;
• dacă q (j = 1 sau 2 atunci q^ = 0, deoarece dacă aplicațiile de clasă i a avea prioritate asupra cererilor de curs j, atunci acestea din urmă nu pot avea prioritate față de revendicările de clasă i (i,j = 1, ..., I).

Depinzând de oportunități de a schimba prioritățileÎn timpul funcționării sistemului, disciplinele prioritare de buffering și service sunt împărțite în două clase:

• 1) cu priorități statice, care nu se schimbă în timp;
• 2) cu priorități dinamice, care se poate modifica în timpul funcționării sistemului în funcție de diverși factori, de exemplu, când se atinge o anumită valoare critică a lungimii cozii de aplicații dintr-o clasă care nu are prioritate sau are o prioritate scăzută, i se poate acorda o valoare mai mare. prioritate.

În sistemele informatice IM există neapărat un singur element (obiect) prin care, și numai prin intermediul acestuia, cererile sunt introduse în model. În mod implicit, toate aplicațiile introduse nu sunt prioritare. Există însă posibilități de atribuire a priorităților în secvența 1, 2, ..., inclusiv în timpul execuției modelului, adică. în dinamică.

Flux de ieșire este fluxul de cereri deservite care părăsesc QS. În sistemele reale, aplicațiile trec prin mai multe QS: comunicare de tranzit, conductă de producție etc. În acest caz, fluxul de ieșire este fluxul de intrare pentru următorul QS.

Fluxul de intrare al primului QS, care a trecut prin QS-urile ulterioare, este distorsionat, iar acest lucru complică modelarea analitică. Cu toate acestea, trebuie avut în vedere faptul că cu cel mai simplu flux de intrare și serviciu exponențial(acestea. în sistemele Markov) fluxul de ieșire este și cel mai simplu. Dacă timpul de serviciu are o distribuție non-exponențială, atunci fluxul de ieșire nu numai că nu este simplu, ci și nu este recurent.

Rețineți că intervalele de timp dintre cererile trimise nu sunt aceleași cu intervalele de service. La urma urmei, se poate dovedi că, după încheierea următorului serviciu, QS-ul este inactiv de ceva timp din cauza lipsei de aplicații. În acest caz, intervalul fluxului de ieșire constă din timpul inactiv al QS-ului și intervalul de service al primei solicitări care a sosit după timpul de oprire.

În QS, pe lângă fluxul de ieșire al cererilor deservite, pot exista fluxul de cereri neservite. Dacă un astfel de QS primește un flux recurent, iar serviciul este exponențial, atunci fluxul de clienți neserviți este și el recurent.

Cozile gratuite de canale. În QS multicanal, se pot forma cozi de canale libere. Numărul de canale gratuite este o valoare aleatorie. Cercetătorii pot fi interesați de diferite caracteristici ale acestei variabile aleatorii. De obicei, acesta este numărul mediu de canale ocupate de serviciu pe interval de sondaj și factorii lor de încărcare.

După cum am observat mai devreme, în obiectele reale, cererile sunt deservite secvenţial în mai multe QS-uri.

Se numește un set finit de QS-uri interconectate secvenţial care procesează aplicaţiile care circulă în ele rețea de așteptare (Semo) (Fig. 2.4, A).

Orez. 2.4.

Se mai numește și SEMO QS multifazic.

Vom lua în considerare un exemplu de construire a unui QEMO IM mai târziu.

Elementele principale ale QS sunt nodurile (U) și sursele (generatoare) de solicitări (G).

Nod rețelele sunt un sistem de așteptare.

Sursă- un generator de aplicații care intră în rețea și necesită anumite etape de serviciu în nodurile rețelei.

Un grafic este utilizat pentru o imagine simplificată a QEMO.

Contele Semo- un graf direcționat (digraf), ale cărui vârfuri corespund nodurilor QEM, iar arcele reprezintă tranzițiile aplicațiilor între noduri (Fig. 2.4, b).

Deci, am luat în considerare conceptele de bază ale QS. Însă în dezvoltarea sistemelor informatice pentru IM și îmbunătățirea acestora, se folosește în mod necesar și potențialul creativ enorm conținut în prezent în modelarea analitică a QS.

Pentru o mai bună percepție a acestui potențial creativ, ca o primă aproximare, să ne oprim asupra clasificării modelelor QS.

Imagine 0 - 2 Fluxuri de evenimente (a) și cel mai simplu flux (b)

10.5.2.1. staționaritate

Fluxul se numește staționar , dacă probabilitatea de a lovi unul sau altul număr de evenimente într-o perioadă elementară de timp lungime τ (

Figura 0-2 , A) depinde doar de lungimea secțiunii și nu depinde de locul exact pe ax t aceasta zona este situata.

Staționaritatea fluxului înseamnă uniformitatea acestuia în timp; caracteristicile probabilistice ale unui astfel de flux nu se modifică în timp. În special, așa-numita intensitate (sau „densitate”) a fluxului de evenimente, numărul mediu de evenimente pe unitatea de timp pentru un flux staționar, trebuie să rămână constantă. Acest lucru, desigur, nu înseamnă că numărul real de evenimente care apar pe unitatea de timp este constant; fluxul poate avea concentrații și rarefacții locale. Este important ca pentru un flux staționar aceste concentrații și rarefări să nu fie de natură obișnuită, iar numărul mediu de evenimente care se încadrează într-un singur interval de timp să rămână constant pentru întreaga perioadă luată în considerare.

În practică, există adesea fluxuri de evenimente care (cel puțin pentru o perioadă limitată de timp) pot fi considerate staționare. De exemplu, fluxul de apeluri care sosesc la centrala telefonică, să zicem, în intervalul de la 12 la 13 ore poate fi considerat staționar. Același flux nu va mai fi staționar pentru o zi întreagă (noaptea, intensitatea fluxului de apeluri este mult mai mică decât în ​​timpul zilei). Rețineți că același lucru este și cazul majorității proceselor fizice pe care le numim „staționare”, de fapt, acestea sunt staționare doar pentru o perioadă limitată de timp, iar extinderea acestei perioade la infinit este doar un truc convenabil folosit pentru simplificare.

10.5.2.2. Fără efect secundar

Fluxul evenimentelor se numește flux fără efecte secundare , dacă pentru orice interval de timp care nu se suprapun numărul de evenimente care se încadrează pe unul dintre ele nu depinde de câte evenimente au căzut pe celălalt (sau altele, dacă sunt luate în considerare mai mult de două secțiuni).

În astfel de fluxuri, evenimentele care formează fluxul apar în momente succesive în timp, independent unele de altele. De exemplu, fluxul de pasageri care intră în stația de metrou poate fi considerat un flux fără efecte secundare, deoarece motivele care au determinat sosirea unui pasager individual în acest moment particular și nu în altul, de regulă, nu sunt legate de motive similare. pentru alți pasageri. Dacă apare o astfel de dependență, condiția pentru absența unui efect secundar este încălcată.

Luați în considerare, de exemplu, fluxul de trenuri de marfă care circulă de-a lungul unei linii de cale ferată. Dacă, din motive de siguranță, aceștia nu pot să se succedă mai des decât la intervale de timp t0 , atunci există o dependență între evenimentele din flux și este încălcată condiția fără efect secundar. Cu toate acestea, dacă intervalul t0 este mic în comparație cu intervalul mediu dintre trenuri, atunci o astfel de încălcare este nesemnificativă.

Imagine 0 - 3 Distribuția Poisson

Luați în considerare pe axă t cel mai simplu flux de evenimente cu intensitatea λ. (Figura 0-2 b) . Ne va interesa un interval de timp aleator T între evenimentele adiacente din acest flux; găsiți legea distribuției sale. Mai întâi, să găsim funcția de distribuție:

F(t) = P(T ( 0-2)

adică probabilitatea ca valoarea lui T va avea o valoare mai mică decâtt. Lăsați deoparte de la începutul intervalului T (puncte t0) segmentul t și găsiți probabilitatea ca intervalul T va fi mai putin t . Pentru a face acest lucru, este necesar ca pentru o secțiune de lungime t , adiacent unui punct t0 , cel puțin un eveniment accesat de fir. Să calculăm probabilitatea acestui lucru F(t) prin probabilitatea evenimentului opus (pe segment t niciun eveniment din flux nu va atinge):

F (t) \u003d 1 - P 0

Probabilitate P 0 găsim prin formula (1), presupunândm = 0:

de unde funcția de distribuție a valorii T va fi:

(0-3)

Pentru a afla densitatea distribuției f(t) variabilă aleatorie T, este necesar să se diferenţieze expresia (0‑1) print:

0-4)

Legea distribuției cu densitatea (0-4) se numește exponențială (sau exponențial ). Valoarea λ se numește parametru lege exemplară.

Figura 0 - 4 Distribuție exponențială

Găsiți caracteristicile numerice ale unei variabile aleatorii T- așteptări matematice (valoare medie) M[t]=mt , şi dispersia D t . Avem

( 0-5)

(integrare pe părți).

Dispersia valorii lui T este:

(0-6)

Extragând rădăcina pătrată a varianței, găsim abaterea standard a variabilei aleatoare T.

Deci, pentru o distribuție exponențială, așteptarea matematică și abaterea standard sunt egale între ele și sunt inverse parametrului λ, unde λ. intensitatea curgerii.

Astfel, aspectul m evenimentele dintr-un interval de timp dat corespunde distribuției Poisson, iar probabilitatea ca intervalele de timp dintre evenimente să fie mai mici decât un număr predeterminat corespunde distribuției exponențiale. Toate acestea sunt doar descrieri diferite ale aceluiași proces stocastic.

QS Exemplul-1 .

Ca exemplu, luați în considerare un sistem bancar în timp real care deservește un număr mare de clienți. În timpul orelor de vârf, cererile de la casierii băncilor care lucrează cu clienții formează un flux Poisson și ajung în medie două la 1 s (λ = 2). Fluxul constă în cererile care ajung cu o rată de 2 cereri pe secundă.

Calculați probabilitatea P ( m ) apariții m mesaje în 1 s. Deoarece λ = 2, din formula anterioară avem

Inlocuind m = 0, 1, 2, 3, obținem următoarele valori (până la patruzecimale):

Figura 0 - 5 Cel mai simplu exemplu de flux

Mai mult de 9 mesaje în 1 s sunt, de asemenea, posibile, dar probabilitatea acestui lucru este foarte mică (aproximativ 0,000046).

Distribuția rezultată poate fi reprezentată ca histogramă (prezentată în figură).

Exemplu de CMO-2.

Un dispozitiv (server) care procesează trei mesaje în 1 secundă.

Să existe un echipament care poate procesa trei mesaje în 1 s (µ=3). În medie, două mesaje sunt primite în 1 secunde și în conformitate c Distribuția Poisson. Ce proporție dintre aceste mesaje va fi procesată imediat după primire?

Probabilitatea ca rata de sosire să fie mai mică sau egală cu 3 s este dată de

Dacă sistemul poate procesa maximum 3 mesaje în 1 s, atunci probabilitatea ca acesta să nu fie supraîncărcat este

Cu alte cuvinte, 85,71% dintre mesaje vor fi difuzate imediat și 14,29% cu o oarecare întârziere. După cum puteți vedea, o întârziere în procesarea unui mesaj pentru un timp mai mare decât timpul de procesare a 3 mesaje va apărea rar. Timpul de procesare a unui mesaj este în medie de 1/3 s. Prin urmare, o întârziere mai mare de 1 s va fi rară, ceea ce este destul de acceptabil pentru majoritatea sistemelor.

Exemplu de CMO 3

· Dacă un casier de bancă este ocupat în 80% din timpul său de lucru, iar restul timpului își petrece așteptarea clienților, atunci el poate fi considerat un dispozitiv cu un factor de utilizare de 0,8.

· Dacă canalul de comunicație este folosit pentru a transmite simboluri pe 8 biți la o rată de 2400 bps, adică maxim 2400/8 simboluri sunt transmise în 1 s și construim un sistem în care cantitatea totală de date este de 12000 simboluri trimise de la diferite dispozitive prin canal pe minut ocupat (inclusiv sincronizare, caractere de sfârșit de mesaj, caractere de control etc.), atunci rata de utilizare a echipamentului canalului de comunicație în acest minut este egală cu

· Dacă motorul de acces la fișiere în oră aglomerată realizează 9000 de accesări la fișiere, iar timpul per acces este în medie de 300 ms, atunci utilizarea hardware-ului motorului de acces în oră aglomerată este

Conceptul de utilizare a echipamentelor va fi folosit destul de des. Cu cât utilizarea echipamentului este mai aproape de 100%, cu atât întârzierea este mai mare și coada este mai lungă.

Folosind formula anterioară, puteți compila tabele cu valorile funcției Poisson, din care puteți determina probabilitatea de a primim sau mai multe mesaje într-o anumită perioadă de timp. De exemplu, dacă o medie de 3,1 mesaje pe secundă [i.e. e. λ = 3.1], atunci probabilitatea de a primi 5 sau mai multe mesaje într-o secundă dată este 0,2018 (pentrum = 5 în tabel). Sau sub formă analitică

Folosind această expresie, analistul de sisteme poate calcula probabilitatea ca sistemul să nu îndeplinească un anumit criteriu de încărcare.

Adesea, calculele inițiale pot fi făcute pentru valorile sarcinii echipamentului.

p ≤ 0,9

Aceste valori pot fi obținute folosind tabelele Poisson.

Fie din nou rata medie de sosire a mesajelor λ = 3,1 mesaje/s. Din tabele rezultă că probabilitatea de a primi 6 sau mai multe mesaje în 1 s este 0,0943. Prin urmare, acest număr poate fi luat ca un criteriu de încărcare pentru calculele inițiale.

10.6.2. Provocări de proiectare

Având în vedere natura aleatorie a sosirii mesajelor la dispozitiv, acesta din urmă petrece o parte din timp procesând sau deservind fiecare mesaj, rezultând formarea de cozi. Coada de la bancă așteaptă eliberarea casierului și a calculatorului său (terminal). Coada de mesaje din memoria tampon de intrare a computerului așteaptă să fie procesată de procesor. Coada de solicitări pentru matrice de date așteaptă eliberarea canalelor etc. Se pot forma cozi în toate blocajele sistemului.

Cu cât rata de utilizare a echipamentului este mai mare, cu atât cozile rezultate sunt mai lungi. După cum se va arăta mai jos, este posibil să se proiecteze un sistem care să funcționeze satisfăcător cu un factor de utilizare de ρ = 0,7, dar un factor mai mare de ρ > 0,9 poate duce la o calitate slabă a serviciului. Cu alte cuvinte, dacă o legătură de date în bloc are o încărcare de 20%, este puțin probabil să aibă o coadă pe el. Dacă se încarcă; este 0,9, atunci, de regulă, se vor forma cozi, uneori foarte mari.

Coeficientul de utilizare a echipamentului este egal cu raportul dintre sarcina pe echipament și sarcina maximă pe care o poate suporta acest echipament sau este egal cu raportul dintre timpul de ocupare a echipamentului și timpul total de funcționare a acestuia.

La proiectarea unui sistem, este obișnuit să se estimeze factorul de utilizare pentru diferite tipuri de echipamente; exemple relevante vor fi date în capitolele ulterioare. Cunoașterea acestor coeficienți vă permite să calculați cozile pentru echipamentul corespunzător.

· Care este lungimea cozii?

· Cât timp va dura?

Întrebările de acest tip pot fi răspunse folosind teoria cozilor.

10.6.3. Sisteme de așteptare, clasele și principalele caracteristici ale acestora

Pentru QS, fluxurile de evenimente sunt fluxuri de cereri, fluxuri de cereri de „serviciu” etc. Dacă aceste fluxuri nu sunt Poisson (procesul Markov), descrierea matematică a proceselor care au loc în QS devine incomparabil mai complexă și necesită un aparat mai greoi, aducerea lui la formule analitice este posibilă doar în cazurile cele mai simple.

Cu toate acestea, aparatul teoriei de așteptare „Markovian” poate fi util și în cazul în care procesul care are loc în QS este diferit de cel Markov; cu ajutorul acestuia, caracteristicile de eficiență QS pot fi estimate aproximativ. Trebuie remarcat faptul că, cu cât QS-ul este mai complex, cu cât conține mai multe canale de servicii, cu atât formulele aproximative obținute cu ajutorul teoriei Markov sunt mai precise. În plus, într-o serie de cazuri, pentru a lua decizii în cunoștință de cauză privind gestionarea funcționării QS, nu este deloc necesar să se cunoască exact toate caracteristicile acestuia, adesea destul de aproximative, orientative.

QS sunt clasificate în sisteme cu:

eșecuri (cu pierderi). În astfel de sisteme, o solicitare care sosește în momentul în care toate canalele sunt ocupate primește un „refuz”, părăsește QS și nu participă la procesul de service ulterioar.

aşteptare (cu coadă). În astfel de sisteme, o solicitare care sosește atunci când toate canalele sunt ocupate este pusă în coadă și așteaptă până când unul dintre canale devine liber. Când canalul este liber, una dintre aplicațiile din coadă este acceptată pentru service.

Serviciul (disciplina la coadă) într-un sistem de așteptare poate fi

ordonat (cererile sunt comunicate în ordinea primirii),

· dezordonat(cererile sunt depuse în ordine aleatorie) sau

grămadă (ultima aplicație este selectată prima din coadă).

Prioritate

o cu prioritate statica

o cu prioritate dinamică

(în acest din urmă caz ​​a priori tet poate crește, de exemplu, odată cu timpul de așteptare pentru cerere).

Sistemele cu o coadă sunt împărțite în sisteme

· cu așteptare nelimitată și

· cu limitat aşteptare.

În sistemele cu așteptare nelimitată, fiecare solicitare care sosește în momentul în care nu există canale libere intră în coadă și așteaptă „răbdător” eliberarea canalului care o va accepta pentru service. Orice cerere primită de CMO va fi comunicată mai devreme sau mai târziu.

În sistemele cu așteptare limitată, sunt impuse anumite restricții privind rămânerea aplicației în coadă. Aceste restricții se pot aplica

· lungimea cozii (numărul de aplicații simultan în sistemul de cozi cu o lungime limitată a cozii),

· timpul în care aplicația rămâne în coadă (după o anumită perioadă de așteptare, aplicația iese din coadă, iar sistemul pleacă cu un timp de așteptare limitat),

· timpul total petrecut de aplicație în QS

etc.

În funcție de tipul de QS, la evaluarea eficienței acestuia, pot fi utilizate anumite valori (indicatori de performanță). De exemplu, pentru un QS cu defecțiuni, una dintre cele mai importante caracteristici ale productivității sale este așa-numita lățime de bandă absolută numărul mediu de cereri pe care sistemul le poate deservi pe unitatea de timp.

Împreună cu absolutul este adesea considerat debit relativ CMO este ponderea medie a cererilor primite deservite de sistem (raportul dintre numărul mediu de cereri deservite de sistem pe unitatea de timp și numărul mediu de cereri primite în acest timp).

În plus față de debitele absolute și relative în analiza QS cu eșecuri, putem, în funcție de sarcina studiului, să fim interesați de alte caracteristici, de exemplu:

· numărul mediu de canale ocupate;

· timpul de nefuncționare relativ mediu al sistemului ca întreg și al unui canal individual

etc.

QS-urile așteptate au caracteristici ușor diferite. Evident, pentru un QS cu timp de așteptare nelimitat, atât debitul absolut cât și cel relativ își pierd sensul, deoarece fiecare revendicare ajunge mai devreme.sau mai târziu va fi servit. Pentru un astfel de QS, caracteristicile importante sunt:

· numărul mediu de aplicații din coadă;

· numărul mediu de aplicații din sistem (în coadă și în service);

· timpul mediu de așteptare pentru o aplicație în coadă;

· timpul mediu petrecut de o aplicație în sistem (în coadă și în service);

precum și alte caracteristici ale așteptării.

Pentru un QS cu așteptare limitată, ambele grupuri de caracteristici sunt de interes: atât debitul absolut și relativ, cât și caracteristicile de așteptare.

Pentru a analiza procesul care are loc în QS, este esențial să cunoașteți principalii parametri ai sistemului: numărul de canale P, intensitatea debitului de aplicareλ , performanța fiecărui canal (numărul mediu de cereri μ deservite de canal pe unitatea de timp), condițiile de formare a cozii (restricții, dacă există).

În funcție de valorile acestor parametri, sunt exprimate caracteristicile eficienței operațiunii QS.

10.6.4. Formule pentru calcularea caracteristicilor QS pentru cazul service-ului cu un singur dispozitiv

Figura 0 - 6 Modelul unui sistem de așteptare cu coadă

Astfel de cozi pot fi create prin mesaje la intrarea procesorului care așteaptă să fie procesate. Acestea pot apărea în timpul funcționării stațiilor de abonat conectate la un canal de comunicație multipunct. În mod similar, la benzinării se formează cozi de mașini. Totuși, dacă există mai multe intrări în serviciu, avem o coadă cu multe dispozitive și analiza devine mai complicată.

Luați în considerare cazul celui mai simplu flux de cereri de servicii.

Scopul teoriei de așteptare prezentată aici este de a aproxima dimensiunea medie a cozii de așteptare, precum și timpul mediu petrecut de mesajele care așteaptă în cozi. De asemenea, este de dorit să se estimeze cât de des coada depășește o anumită lungime. Aceste informații ne vor permite să calculăm, de exemplu, cantitatea necesară de memorie tampon pentru stocarea cozilor de mesaje și a programelor aferente, numărul necesar de linii de comunicație, dimensiunile tampon necesare pentru hub-uri etc. Va fi posibil să se estimeze timpii de răspuns.

Fiecare dintre caracteristici variază în funcție de mijloacele folosite.

Luați în considerare o coadă cu un singur server. La proiectarea unui sistem de calcul, majoritatea cozilor de acest tip sunt calculate folosind formulele de mai sus. factor de variație a timpului de serviciu

Formula Khinchin-Polachek este utilizată pentru a calcula lungimile cozilor în proiectarea sistemelor informaționale. Se aplică în cazul unei distribuții exponențiale a timpului de sosire pentru orice distribuție a timpului de serviciu și orice disciplină de control, atâta timp cât alegerea următorului mesaj pentru serviciu nu depinde de timpul de serviciu.

La proiectarea sistemelor, există astfel de situații când apar cozi când disciplina de control depinde, fără îndoială, de timpul de service. De exemplu, în unele cazuri, putem alege să folosim mai întâi mesaje mai scurte pentru serviciu, pentru a obține un timp mediu de serviciu mai rapid. Atunci când gestionați o linie de comunicație, este posibil să acordați o prioritate mai mare mesajelor de intrare decât mesajelor de ieșire, deoarece primele sunt mai scurte. În astfel de cazuri, nu mai este necesară utilizarea ecuației lui Khinchin

Majoritatea timpilor de service în sistemele informaționale se află undeva între aceste două cazuri. Perioadele de service care sunt constante sunt rare. Chiar și timpul de acces la hard disk nu este constant din cauza poziției diferite a matricelor de date pe suprafață. Un exemplu care ilustrează cazul timpului de serviciu constant este ocuparea liniei de comunicație pentru transmiterea mesajelor de lungime fixă.

Pe de altă parte, răspândirea timpului de serviciu nu este la fel de mare ca în cazul unei distribuții arbitrare sau exponențiale, adicăσs rar atinge valorit s. Acest caz este uneori considerat „cel mai rău caz” și, prin urmare, se folosesc formule care se referă la distribuția exponențială a timpilor de serviciu. Un astfel de calcul poate da dimensiuni oarecum supraestimate ale cozilor de așteptare și timpi de așteptare, dar această eroare nu este cel puțin periculoasă.

Distribuția exponențială a timpilor de serviciu nu este cu siguranță cel mai rău caz cu care trebuie să te confrunți în realitate. Totuși, dacă timpii de serviciu obținuți din calculul cozilor se dovedesc a fi mai prost repartizați decât timpii distribuiți exponențial, acesta este adesea un semnal de avertizare pentru dezvoltator. Dacă abaterea standard este mai mare decât valoarea medie, atunci este de obicei necesară corectarea calculelor.

Luați în considerare următorul exemplu. Există șase tipuri de mesaje cu timpi de serviciu de 15, 20, 25, 30, 35 și 300. Numărul de mesaje pentru fiecare tip este același. Abaterea standard a acestor timpi este ceva mai mare decât media lor. Valoarea ultimului timp de service este mult mai mare decât celelalte. Acest lucru va face ca mesajele să fie în coadă mult mai mult decât dacă timpii de service ar fi de aceeași ordine. În acest caz, la proiectare, este indicat să luați măsuri pentru a reduce lungimea cozii. De exemplu, dacă aceste numere sunt legate de lungimea mesajelor, atunci poate că mesajele foarte lungi ar trebui împărțite în părți.

10.6.6. Exemplu de calcul

La proiectarea unui sistem bancar, este de dorit să se cunoască numărul de clienți care vor trebui să stea la coadă pentru un casier în orele de vârf.

Timpul de răspuns al sistemului și abaterea sa standard sunt calculate luând în considerare timpul de introducere a datelor de la stația de lucru, imprimare și procesare a documentelor.

Acțiunile casieriei au fost cronometrate. Timpul de serviciu ts este egal cu timpul total petrecut de casier pe client. Rata de utilizare a casierului ρ este proporţională cu timpul angajării acestuia. Dacă λ este numărul de clienți în orele de vârf, atunci ρ pentru casier este

Să presupunem că sunt 30 de clienți pe oră în orele de vârf. În medie, un casier petrece 1,5 minute per client. Apoi

ρ = (1,5 * 30) / 60 = 0,75

adică casieria este folosită de 75%.

Numărul de oameni în rând poate fi estimat rapid folosind grafice. Din ele rezultă că dacă ρ = 0,75, atunci numărul mediu nq de oamenila linie la casă se află între 1,88 și 3,0 în funcție de abaterea standard pt t s .

Să presupunem că măsurarea abaterii standard pentru ts a dat o valoare de 0,5 min. Apoi

σ s = 0,33 t s

Din graficul din prima figură, constatăm că nq = 2,0, adică, în medie, doi clienți vor aștepta la casă.

Timpul total pe care un client îl petrece la casă poate fi găsit ca

t ∑ = t q + t s = 2,5 min + 1,5 min = 4 min

unde t s se calculează folosind formula Khinchin-Polachek.

10.6.7. factor de câștig

Analizând curbele din cifre, vedem că atunci când echipamentul care deservește coada este folosit mai mult de 80%, curbele încep să crească într-un ritm alarmant. Acest fapt este foarte important în proiectarea sistemelor de transmisie a datelor. Dacă proiectăm un sistem cu mai mult de 80% de utilizare a hardware-ului, atunci o ușoară creștere a traficului poate duce la o scădere drastică a performanței sistemului sau chiar la blocarea acestuia.

O creștere a traficului de intrare cu un număr mic de x%. duce la o creștere a dimensiunii cozii cu aproximativ

Dacă rata de utilizare a echipamentului este de 50%, atunci această creștere este egală cu 4ts% pentru distribuția exponențială a timpului de serviciu. Dar dacă utilizarea echipamentului este de 90%, atunci creșterea dimensiunii cozii este de 100%, adică de 25 de ori mai mult. O ușoară creștere a încărcăturii la utilizarea echipamentelor cu 90% duce la o creștere de 25 de ori a dimensiunilor cozilor de așteptare, comparativ cu cazul utilizării echipamentelor cu 50%.

În mod similar, timpul de coadă crește cu

Cu un timp de serviciu distribuit exponențial, această valoare are valoarea 4 t s2 pentru utilizarea echipamentului egală cu 50% și 100 t s2 pentru un coeficient de 90%, adică din nou de 25 de ori mai rău.

În plus, pentru factorii de utilizare a echipamentelor mici, efectul modificărilor σs asupra dimensiunii cozii este nesemnificativ. Cu toate acestea, pentru coeficienți mari, modificarea σ s afectează foarte mult dimensiunea cozii. Prin urmare, atunci când se proiectează sisteme cu utilizare ridicată a echipamentelor, este de dorit să se obțină informații precise despre parametruσ s. Inexactitatea ipotezei privind exponenţialitatea distribuţiei lui tseste cel mai vizibil la valori mari ale lui ρ. Mai mult, dacă timpul de serviciu crește brusc, ceea ce este posibil în canalele de comunicare la transmiterea mesajelor lungi, atunci în cazul unui ρ mare, se formează o coadă semnificativă.

Destul de des, atunci când analizăm sistemele economice, trebuie să rezolvi așa-numitele probleme de coadă care apar în următoarea situație. Să fie analizat sistemul de întreținere al autovehiculului format dintr-un anumit număr de stații de diferite capacități. La fiecare stație (element de sistem), pot apărea cel puțin două situații tipice:

1. numărul de aplicații este prea mare pentru această stație, sunt cozi și trebuie să plătești pentru întârzierile de service;
2. stația primește prea puține solicitări și acum este deja necesar să se țină cont de pierderile cauzate de oprirea stației.

Este clar că scopul analizei de sistem în acest caz este de a determina o relație între pierderile de venit datorate cozile si pierderi datorate doar eu statii.

Teoria cozilor– o secțiune specială a teoriei sistemelor este o secțiune a teoriei probabilităților în care sistemele de așteptare sunt studiate folosind modele matematice.

Sistem de așteptare (QS)- acesta este un model care include: 1) un flux aleator de cerințe, apeluri sau clienți care au nevoie de service; 2) algoritmul de implementare a acestui serviciu; 3) canale (dispozitive) pentru întreținere.

Exemple de CMO sunt casele de casă, benzinăriile, aeroporturile, vânzătorii, frizerii, medicii, centralele telefonice și alte facilități care deservesc anumite aplicații.

Problema teoriei cozilor constă în elaborarea de recomandări pentru construirea rațională a QS și organizarea rațională a muncii acestora pentru a asigura o eficiență ridicată a serviciului la costuri optime.

Principala caracteristică a problemelor acestei clase este dependența clară a rezultatelor analizei și a recomandărilor primite de doi factori externi: frecvența primirii și complexitatea comenzilor (și, prin urmare, timpul executării acestora).

Subiectul teoriei stării de așteptare este stabilirea unei relații între natura fluxului de aplicații, performanța unui canal de serviciu separat, numărul de canale și eficiența serviciului.

La fel de Caracteristicile QS considerat:

• procentul mediu de aplicații care sunt respinse și lasă sistemul neservit;
• timpul mediu de nefuncționare a canalelor individuale și a sistemului în ansamblu;
• timpul mediu de așteptare la coadă;
• probabilitatea ca cererea primită să fie deservită imediat;
• legea distribuției lungimii de coadă și altele.

Adăugăm că cererile (cerințele) intră în QS aleatoriu (în momente aleatorii), cu puncte de condensare și rarefacție. Timpul de serviciu al fiecărei cerințe este, de asemenea, aleatoriu, după care canalul de serviciu este eliberat și gata să îndeplinească următoarea cerință. Fiecare QS, în funcție de numărul de canale și de performanța acestora, are o anumită capacitate. Debitul SMO poate absolut(numărul mediu de cereri deservite pe unitatea de timp) și relativ(raportul mediu dintre numărul de cereri depuse și numărul de cereri depuse).

3.1 Modele de sisteme de așteptare.

Fiecare QS poate fi caracterizat prin expresia: (a/b/c): (d/e/f) , Unde

A - distribuția fluxului de intrare al aplicațiilor;

b - distribuția fluxului de ieșire al aplicațiilor;

c – configurarea mecanismului de service;

d – disciplina la coada;

e – bloc de așteptare;

f este capacitatea sursei.

Acum să aruncăm o privire mai atentă la fiecare caracteristică.

Flux de intrare de aplicații- numărul de cereri primite de sistem. Caracterizat prin intensitatea fluxului de intrare l.

Flux de ieșire al aplicațiilor– numărul de aplicații deservite de sistem. Caracterizat prin intensitatea debitului de ieșire m.

configurarea sistemului implică numărul total de canale și noduri de servicii. SMO poate conține:

1. un canal servicii (o pistă, un furnizor);
2. un canal de serviciu, inclusiv mai multe noduri seriale(cantina, clinica, transportor);
3. mai multe canale similare servicii conectate în paralel (benzinări, birou de informații, gară).

Astfel, se pot distinge QS cu un singur canal și cu mai multe canale.

Pe de altă parte, dacă toate canalele de servicii din QS sunt ocupate, atunci aplicația abordată poate rămâne în coadă sau poate părăsi sistemul (de exemplu, o casă de economii și o centrală telefonică). În acest caz, vorbim despre sisteme cu coadă (în așteptare) și sisteme cu defecțiuni.

Întoarce-te este un set de aplicații care au intrat în sistem pentru service și care așteaptă service. Coada se caracterizează prin lungimea cozii și disciplina ei.

Disciplina la coada este regula pentru deservirea cererilor din coadă. Principalele tipuri de cozi includ următoarele:

1. PERPPO (primul venit, primul servit) este cel mai comun tip;
2. POSPPO (ultimul venit - primul servit);
3. SOP (selecția aleatorie a aplicațiilor) - din banca de date.
4. PR - serviciu prioritar.

Lungimea cozii poate

• nelimitat - atunci se vorbește de un sistem cu așteptare pură;
• egal cu zero - atunci se vorbește despre un sistem cu defecțiuni;
• limitat în lungime (sistem de tip mixt).

bloc de așteptare– „capacitatea” sistemului - numărul total de aplicații din sistem (în coadă și în serviciu). În acest fel, e=c+d.

Capacitatea sursei care generează cereri de servicii este numărul maxim de cereri care pot intra în QS. De exemplu, la un aeroport, capacitatea sursă este limitată de numărul tuturor aeronavelor existente, iar capacitatea sursă a unei centrale telefonice este egală cu numărul de locuitori ai Pământului, de exemplu. poate fi considerat nelimitat.

Numărul de modele QS corespunde numărului de combinații posibile ale acestor componente.

3.2 Flux de intrare de cerințe.

Cu fiecare interval de timp A, A+ T ], să asociem o variabilă aleatoare X, egal cu numărul de solicitări primite de sistem în timpul respectiv T.

Fluxul de cereri este apelat staționar, dacă legea distribuției nu depinde de punctul inițial al intervalului A, dar depinde numai de lungimea intervalului dat T. De exemplu, fluxul de aplicații către centrala telefonică în timpul zilei ( T\u003d 24 de ore) nu poate fi considerat staționar, dar de la 13 la 14 ore ( T\u003d 60 de minute) - poți.

Fluxul este numit nici un efect secundar, dacă istoricul fluxului nu afectează primirea cerințelor în viitor, i.e. cerințele sunt independente unele de altele.

Fluxul este numit comun, dacă nu mai mult de o solicitare poate intra în sistem într-o perioadă foarte scurtă de timp. De exemplu, fluxul către coafor este obișnuit, dar nu către oficiul de stat. Dar dacă ca o variabilă aleatoare X luați în considerare perechi de aplicații care intră în oficiul registrului, atunci un astfel de flux va fi obișnuit (adică, uneori un flux extraordinar poate fi redus la unul obișnuit).

Fluxul este numit cel mai simplu, dacă este staționar, fără efecte secundare și obișnuit.

Teorema principală. Dacă debitul este cel mai simplu, atunci r.v. X [ a . un + T] este distribuit conform legii Poisson, i.e. .

Corolarul 1. Cel mai simplu flux se mai numește și flux Poisson.

Consecința 2. M(X)= M(X [ A , A + T ] )= lT, adică pe parcursul T lT aplicatii. Prin urmare, pentru o unitate de timp, sistemul primește în medie l aplicatii. Această valoare este numită intensitate flux de intrare.

Luați în considerare EXEMPLU .

Studioul primește în medie 3 cereri pe zi. Presupunând că fluxul este cel mai simplu, găsiți probabilitatea ca numărul de cereri să fie de cel puțin 5 în următoarele două zile.

Soluţie.

Conform sarcinii, l=3, T=2 zile, flux de intrare Poisson, n ³5. la rezolvare este convenabil să se introducă evenimentul opus, care constă în faptul că în timp T vor fi primite mai puțin de 5 cereri. Prin urmare, conform formulei Poisson, obținem

^

3.3 Starea sistemului. Matricea și graficul tranzițiilor.

Într-un moment aleator, QS-ul trece de la o stare la alta: se modifică numărul de canale ocupate, numărul de solicitări și cozi etc.. Astfel, QS-ul cu n canale și o lungime de coadă egală cu m, poate fi în una dintre următoarele stări:

E 0 – toate canalele sunt gratuite;

E 1 – un canal este ocupat;

E n– toate canalele sunt ocupate;

E n +1 – toate canalele sunt ocupate și o cerere este în coadă;

E n + m– toate canalele și toate locurile din coadă sunt ocupate.

Un sistem similar cu defecțiuni poate fi în state E 0 – E n .

Pentru un QS cu așteptare pură, există un set infinit de stări. În acest fel, condiție E n QS la timp t este cantitatea n aplicații (cerințe) care se află în sistem la un moment dat, adică n= n(t) - valoare aleatorie, E n (t) sunt rezultatele acestei variabile aleatoare și P n (t) este probabilitatea ca sistemul să fie în stare E n .

Suntem deja familiarizați cu starea sistemului. Rețineți că nu toate stările sistemului sunt echivalente. Se numește starea sistemului sursă dacă sistemul poate părăsi această stare dar nu poate reveni la ea. Se numește starea sistemului izolat, dacă sistemul nu poate ieși sau intra în această stare.

Pentru a vizualiza imaginile stărilor sistemului se folosesc diagrame (așa-numitele grafice de tranziție), în care săgețile indică posibilele tranziții ale sistemului de la o stare la alta, precum și probabilitățile unor astfel de tranziții.

Figura 3.1 - grafic de tranziție

Comp.	E 0	E 1	E 2
E 0	P 0,0	P 0,1	P 0,2
E 1	P 1.0	R 1.1	R 1,2
E 2	R 2,0	R 2,2	R 2,2

De asemenea, uneori este convenabil să folosiți matricea de tranziție. În acest caz, prima coloană înseamnă stările inițiale ale sistemului (curente), iar apoi sunt date probabilitățile de trecere de la aceste stări la altele.

Deoarece sistemul va trece neapărat de la unul

stare la alta, atunci suma probabilităților din fiecare rând este întotdeauna egală cu unu.

3.4 QS cu un singur canal.

3.4.1 QS cu un singur canal cu defecțiuni.

Vom lua în considerare sistemele care îndeplinesc cerințele:

(P/E/1):(–/1/¥) . Să presupunem, de asemenea, că timpul de service al unui client nu depinde de numărul de clienți care intră în sistem. Aici și mai jos, „P” înseamnă că fluxul de intrare este distribuit conform legii Poisson, adică. cel mai simplu, „E” înseamnă că fluxul de ieșire este distribuit exponențial. Tot aici și mai jos, formulele principale sunt date fără dovezi.

Pentru un astfel de sistem, sunt posibile două stări: E 0 - sistemul este gratuit și E 1 – sistemul este ocupat. Să creăm o matrice de tranziție. Hai sa luam Dt este o cantitate infinitezimală de timp. Fie evenimentul A să constea în faptul că în sistem pe parcursul timpului Dt a primit o cerere. Evenimentul B constă în faptul că pe parcursul timpului Dt o cerere a fost servită. Eveniment DAR i , k- pe parcursul Dt sistemul va trece de la stat E iîntr-o stare E k. pentru că l este intensitatea fluxului de intrare, apoi pe parcursul timpului Dt intră în sistem în medie l*Dt cerințe. Adică probabilitatea de a primi o cerere P(A)=l* Dt, și probabilitatea evenimentului opus Р(А)=1-l*Dt.P(B)=F(Dt)= P(b< D t)=1- e - m D t = m Dt- probabilitatea de a deservi cererea la timp Dt. Apoi A 00 - cererea nu va fi primită sau va fi primită, dar va fi comunicată. A 00 \u003d  + A * V. R 00 \u003d 1 - l*Dt. (am luat in calcul asta (Dt) 2 este o valoare infinitezimală)

A 01 - cererea va fi primită, dar nu va fi comunicată. A 01 = A * . R 01 = l*Dt.

Și 10 - cererea va fi servită și nu va mai fi una nouă. A 10 \u003d B * A. R 10 = m*Dt.

Și 11 - cererea nu va fi notificată sau va sosi una nouă care nu a fost încă deservită. A 11 = +V * A. R 01 = 1- m*Dt.

Astfel, obținem matricea de tranziție:

Comp.	E 0	E 1
E 0	1-l * Dt	l * Dt
E 1	m * Dt	1-m * Dt

Probabilitatea de oprire și defecțiune a sistemului.

Să găsim acum probabilitatea ca sistemul să fie în stare E 0 în orice moment al timpului t(acestea. R 0 ( t) ). Graficul funcției
prezentat în Figura 3.2.

Asimptota graficului este o linie dreaptă
.

Evident, de la un moment dat t,

1

Figura 3.2

În sfârșit înțelegem asta
și
, Unde R 1 (t) este probabilitatea ca la timp t sistemul este ocupat (adică este într-o stare E 1 ).

Este evident că la începutul operațiunii QS, procesul în desfășurare nu va fi staționar: va fi un mod „de tranziție”, non-staționar. După un timp (care depinde de intensitățile fluxurilor de intrare și de ieșire), acest proces se va stinge și sistemul va trece la o stare de funcționare staționară, iar caracteristicile probabilistice nu vor mai depinde de timp.

Mod de funcționare staționar și factor de încărcare a sistemului.

Dacă probabilitatea ca sistemul să fie într-o stare E k, adică R k (t), nu depinde de timp t, apoi spun că QS-ul a stabilit modul staționar muncă. În același timp, valoarea
numit factor de încărcare a sistemului(sau densitatea redusă a fluxului de aplicații). Apoi pentru probabilități R 0 (t) și R 1 (t) obținem următoarele formule:
,
. De asemenea, puteți concluziona: cu cât factorul de încărcare a sistemului este mai mare, cu atât este mai probabil ca sistemul să eșueze (adică, probabilitatea ca sistemul să fie ocupat).

Spalatoria auto are o unitate pentru intretinere. Mașinile ajung într-o distribuție Poisson cu o rată de 5 mașini/oră. Durata medie de service pentru o mașină este de 10 minute. Găsiți probabilitatea ca o mașină care se apropie să găsească sistemul ocupat dacă QS-ul este în modul staționar.

Soluţie. Conform sarcinii, l=5, m y =5/6. Trebuie să găsim probabilitatea R 1 este probabilitatea defecțiunii sistemului.
.

3.4.2 QS cu un singur canal cu lungime nelimitată la coadă.

Vom lua în considerare sisteme care îndeplinesc cerințele: (Р/Е/1):(d/¥/¥). Sistemul poate fi într-una din state E 0 , …, E k, … Analiza arată că după ceva timp un astfel de sistem începe să funcționeze în mod staționar dacă intensitatea debitului de ieșire depășește intensitatea debitului de intrare (adică, factorul de sarcină a sistemului este mai mic de unu). Ținând cont de această condiție, obținem sistemul de ecuații

rezolvând care găsim că . Astfel, cu condiția ca y<1, получим
In cele din urma,
și
este probabilitatea ca QS să fie în stare E k la un moment aleator în timp.

Caracteristicile medii ale sistemului.

Datorită primirii inegale a cerințelor în sistem și fluctuațiilor în timpul de serviciu, în sistem se formează o coadă. Pentru un astfel de sistem, puteți explora:

• n – numărul de cerințe în QS (în coadă și în serviciu);
• v – lungimea cozii;
• w – timpul de așteptare a începerii serviciului;
• w 0 este timpul total petrecut în sistem.

Vom fi interesați caracteristici medii(adică, luăm așteptările matematice ale variabilelor aleatoare considerate și ne amintim că y<1).

este numărul mediu de aplicații din sistem.

este lungimea medie a cozii.

este timpul mediu de așteptare pentru începerea serviciului, adică timp de așteptare la coadă.

- timpul mediu pe care aplicația îl petrece în sistem - în coadă și pentru service.

La spălătorie este un bloc pentru service și există loc pentru coadă. Mașinile ajung într-o distribuție Poisson cu o rată de 5 mașini/oră. Durata medie de service pentru o mașină este de 10 minute. Găsiți toate caracteristicile QS medii.

Soluţie. l=5, m=60min/10min = 6. Factor de sarcină y =5/6. Apoi numărul mediu de mașini din sistem
, lungime medie de coadă
, timpul mediu de așteptare pentru începerea serviciului
ore = 50 de minute și, în final, timpul mediu petrecut în sistem
ora.

3.4.3 QS cu un singur canal de tip mixt.

Să presupunem că lungimea cozii este m cerințe. Apoi, pentru orice s£ m, probabilitatea de a găsi QS în stare E 1+ s, se calculează prin formula
, adică o cerere este deservită și alta s aplicațiile sunt în coadă.

Probabilitatea de oprire a sistemului este
,

iar probabilitatea defecţiunii sistemului este
.

Sunt date trei sisteme cu un singur canal, pentru fiecare l=5, m =6. Dar primul sistem este cu eșecuri, al doilea este cu așteptare pură, iar al treilea este cu o lungime limitată de coadă, m=2. Găsiți și comparați probabilitățile de oprire a acestor trei sisteme.

Soluţie. Pentru toate sistemele factor de sarcină y=5/6. Pentru un sistem cu defecțiuni
. Pentru un sistem cu așteptări pure
. Pentru un sistem cu o lungime limitată la coadă
. Concluzia este evidentă: cu cât mai multe aplicații sunt în coadă, cu atât este mai mică probabilitatea ca sistemul să fie oprit.

3.5 QS multicanal.

3.5.1 QS multicanal cu defecțiuni.

Vom lua în considerare sistemele (Р/Е/s):(-/s/¥) în ipoteza că timpul de serviciu nu depinde de fluxul de intrare și toate liniile funcționează independent. Sistemele multicanal, pe lângă factorul de sarcină, pot fi caracterizate și prin coeficient
, Unde s– numărul de canale de servicii. Explorând QS multicanal, obținem următoarele formule (formule Erlang) pentru probabilitatea ca sistemul să fie în stare E k la timp aleatoriu:

, k=0, 1, …

funcția de cost.

Ca și în cazul sistemelor cu un singur canal, o creștere a factorului de sarcină duce la o creștere a probabilității de defecțiune a sistemului. Pe de altă parte, o creștere a numărului de linii de servicii duce la o creștere a probabilității de oprire a sistemului sau a canalelor individuale. Astfel, este necesar să se găsească numărul optim de canale de servicii pentru acest QS. Numărul mediu de linii de servicii gratuite poate fi găsit prin formulă
. Să introducem C( s) – funcția de cost QS in functie de Cu 1 – costul unui refuz (penalizare pentru o cerere neîndeplinită) și din Cu 2 - costul perioadei de nefuncționare a unei linii pe unitatea de timp.

Pentru a găsi opțiunea optimă, trebuie să găsiți (și acest lucru se poate face) valoarea minimă a funcției de cost: DIN(s) = cu 1* l * p s +c 2*, al cărui grafic este prezentat în Figura 3.3:

Figura 3.3

Căutarea valorii minime a funcției de cost este pentru care găsim mai întâi valorile acesteia s =1, apoi pentru s =2, apoi pentru s =3 etc. până când la un pas se ajunge la valoarea funcției С( s) nu va fi mai mare decât precedentul. Aceasta înseamnă că funcția a atins minimul și a început să crească. Răspunsul este numărul de canale de servicii (valoarea s) pentru care funcția de cost este minimă.

EXEMPLU .

Câte linii de service ar trebui să conțină QS cu defecțiuni, dacă l\u003d 2reb / ​​oră, m\u003d 1reb / ​​oră, penalitatea pentru fiecare eșec este de 7 mii de ruble, costul timpului de nefuncționare pentru o linie este de 2 mii de ruble. in ora?

Soluţie. y = 2/1=2. Cu 1 =7, Cu 2 =2.

Să presupunem că QS are două canale de servicii, adică. s =2. Apoi
. Prin urmare, C(2) = c 1 *l*p 2 +c 2 *(2- y*(1-p 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Să ne prefacem că s =3. Apoi
, C(3) = c 1 *l*p 3 +c 2 *
=5.79.

Să presupunem că există patru canale, adică s =4. Apoi
,
, C(4) = c 1 *l*p 4 +c 2 *
=5.71.

Să presupunem că QS are cinci canale de servicii, adică. s =5. Apoi
, C(5) = 6,7 - mai mult decât valoarea anterioară. Prin urmare, numărul optim de canale de servicii este de patru.

3.5.2 QS multicanal cu o coadă.

Vom lua în considerare sistemele (Р/Е/s):(d/d+s/¥) în ipoteza că timpul de serviciu nu depinde de fluxul de intrare și toate liniile funcționează independent. Vom spune că sistemul s-a instalat funcționare staționară, dacă numărul mediu de revendicări primite este mai mic decât numărul mediu de revendicări deservite pe toate liniile sistemului, i.e. l

P(w>0) este probabilitatea de a aștepta începerea serviciului,
.

Ultima caracteristică permite rezolvarea problemei determinării numărului optim de canale de serviciu în așa fel încât probabilitatea de așteptare a începerii serviciului să fie mai mică decât un număr dat. Pentru a face acest lucru, este suficient să se calculeze succesiv probabilitatea de așteptare pentru s =1, s =2, s=3 etc.

EXEMPLU .

SMO - o stație de ambulanță a unui mic microdistrict. l=3 apeluri pe oră și m= 4 apeluri pe oră pentru o echipă. Câte echipaje trebuie să fie în stație pentru ca probabilitatea de a aștepta o ieșire să fie mai mică de 0,01?

Soluţie. Factorul de încărcare a sistemului y =0,75. Să presupunem că există două echipe disponibile. Să găsim probabilitatea de a aștepta ca serviciul să înceapă la s =2.
,
.

Să presupunem că există trei brigăzi, adică. s=3. Conform formulelor, obținem asta R 0 =8/17, P(w>0)=0.04>0.01 .

Să presupunem că în stație sunt patru echipaje, adică. s=4. Atunci obținem asta R 0 =416/881, P(w>0)=0.0077<0.01 . Prin urmare, în stație ar trebui să existe patru brigăzi.

3.6 Întrebări pentru autocontrol

1. Subiectul și sarcinile teoriei cozilor.
2. QS, modelele și denumirile acestora.
3. Flux de intrare de cerințe. Intensitatea fluxului de intrare.
4. Starea sistemului. Matricea și graficul tranzițiilor.
5. QS cu un singur canal cu defecțiuni.
6. QS cu un singur canal cu o coadă. Caracteristici.
7. Mod de funcționare staționar. Factorul de încărcare a sistemului.
8. QS multicanal cu defecțiuni.
9. Optimizarea funcției de cost.
10. QS multicanal cu o coadă. Caracteristici.

3.7 Exerciții pentru muncă independentă

1. Snack barul de la benzinărie are un singur tejghea. Mașinile sosesc conform unei distribuții Poisson, cu o medie de 2 mașini la 5 minute. În medie, 1,5 minute sunt suficiente pentru a finaliza o comandă, deși durata serviciului este distribuită conform unei legi exponențiale. Aflați: a) probabilitatea ca blocul să fie inactiv; b) performanta medie; c) probabilitatea ca numărul de mașini care sosesc să fie de cel puțin 10.
2. Aparatul cu raze X vă permite să examinați în medie 7 persoane pe oră. Intensitatea vizitatorilor este de 5 persoane pe oră. Presupunând funcționarea staționară, determinați caracteristicile medii.
3. Timpul de serviciu în QS respectă o lege exponențială,
   m = 7 cerințe pe oră. Aflați probabilitatea ca a) timpul de serviciu să fie între 3 și 30 de minute; b) cererea va fi comunicată în termen de o oră. Utilizați tabelul cu valorile funcției e X .
4. Există o dană în portul fluvial, intensitatea debitului de intrare este de 5 nave pe zi. Intensitatea operațiunilor de încărcare și descărcare este de 6 nave pe zi. Ținând cont de modul de funcționare staționar, determinați toate caracteristicile medii ale sistemului.
5. l=3, m=2, penalizarea pentru fiecare defecțiune este 5, iar costul timpului de nefuncționare pe linie este 2?
6. Care este numărul optim de canale de servicii pe care ar trebui să le aibă un QS dacă l=3, m =1, penalizarea pentru fiecare defecțiune este 7, iar costul timpului de nefuncționare pe linie este 3?
7. Care este numărul optim de canale de servicii pe care ar trebui să le aibă un QS dacă l=4, m=2, penalizarea pentru fiecare defecțiune este 5, iar costul timpului de nefuncționare pe linie este 1?
8. Determinați numărul de piste pentru aeronave, cu condiția ca probabilitatea de așteptare să fie mai mică de 0,05. În același timp, intensitatea fluxului de intrare este de 27 de aeronave pe zi, iar intensitatea serviciului acestora este de 30 de aeronave pe zi.
9. Câte linii de transport independente echivalente ar trebui să aibă un atelier pentru a asigura un ritm de lucru la care probabilitatea de așteptare a prelucrării produselor să fie mai mică de 0,03 (fiecare produs este produs de o linie). Se știe că intensitatea de primire a comenzilor este de 30 de produse pe oră, iar intensitatea procesării unui produs într-o linie este de 36 de produse pe oră.
10. O variabilă aleatoare continuă X este distribuită după o lege exponențială cu parametrul l=5. Găsiți funcția de distribuție, caracteristicile și probabilitatea de a lovi r.v. X în intervalul de la 0,17 la 0,28.
11. Numărul mediu de apeluri care sosesc la PBX într-un minut este 3. Presupunând că fluxul este Poisson, găsiți probabilitatea ca în 2 minute să fie: a) două apeluri; b) mai puțin de două apeluri; c) cel puţin două apeluri.
12. Într-o cutie sunt 17 piese, dintre care 4 sunt defecte. Asamblatorul trage 5 piese la întâmplare. Găsiți probabilitatea ca a) toate părțile extrase să fie de înaltă calitate; b) dintre piesele extrase 3 defecte.
13. Câte canale ar trebui să aibă un QS cu defecțiuni dacă l\u003d 2reb / ​​oră, m\u003d 1reb / ​​oră, penalitatea pentru fiecare eșec este de 8 mii de ruble, costul timpului de nefuncționare pentru o linie este de 2 mii de ruble. in ora?

1. QS cu un singur canal cu defecțiuni.

Exemplu. Fie ca un QS cu un singur canal cu defecțiuni să reprezinte o stație de service zilnică (OD) pentru spălarea auto. Aplicația - o mașină care a sosit într-un moment în care poșta este ocupată - i se refuză serviciul.

Debitul vehiculului = 1,0 (vehicul pe oră).

Durata medie de service este de 1,8 ore.

Fluxul mașinii și fluxul de service sunt cele mai simple.

Necesar pentru a definiîn valori limită la starea de echilibru:

Lățimea de bandă relativă q;

Lățimea de bandă absolută DAR ;

Probabilități de eșec P deschis.

Trebuie comparat real Debit QS cu nominal, care ar fi dacă fiecare mașină ar fi deservită exact 1,8 ore și mașinile ar urma una după alta fără pauză.

2. QS cu un singur canal cu așteptare

Caracteristica sistemului

Ø SMO are un singur canal.

Ø Fluxul de intrare de cereri de serviciu este cel mai simplu flux cu intensitate.

Ø Intensitatea fluxului de servicii este egală cu m (adică, în medie, un canal continuu ocupat va emite m cereri deservite).

Ø Durata serviciului este o variabila aleatorie supusa unei legi de distributie exponentiala.

Ø Fluxul de servicii este cel mai simplu flux de evenimente Poisson.

Ø Solicitarea, primita in momentul in care canalul este ocupat, intra in coada si asteapta service.

Graficul de stat

Stările QS au următoarea interpretare:

S 0 - „canalul este liber”;

S 1 - „canalul este ocupat” (nu există coadă);

S 2 - „canalul este ocupat” (o aplicație este în coadă);

…………………………………………………….

sn- „canalul este ocupat” ( n-1 aplicații sunt în coadă);

SN- „canalul este ocupat” ( N- 1 aplicații sunt în coadă).

Procesul staționar din acest sistem este descris de următorul sistem de ecuații algebrice:

Soluția sistemului de ecuații este:

3. QS cu un singur canal cu o coadă limitată.

Lungimea cozii :( N - 1)

Caracteristicile sistemului:

1. Probabilitatea refuzului serviciului către sistem:

2. Debitul relativ al sistemului:

3. Debitul absolut al sistemului:

4. Numărul mediu de aplicații din sistem:

5. Timpul mediu de rezidență al unei aplicații în sistem:

6. Durata medie a șederii clientului (aplicației) în coadă:

7. Numărul mediu de aplicații (clienți) în coadă (lungimea cozii):

Exemplu.

Un post de diagnostic specializat este un QS cu un singur canal.

Numărul de parcări pentru mașinile care așteaptă diagnosticare este limitat și egal cu 3 [( N- 1) = 3]. Dacă toate parcările sunt ocupate, adică există deja trei mașini în coadă, atunci următoarea mașină care a sosit pentru diagnosticare nu intră în coada de service.

Fluxul de mașini care sosesc pentru diagnosticare este distribuit conform legii lui Poisson și are o intensitate de 0,85 (mașini pe oră).

Timpul de diagnosticare auto este distribuit conform legii exponențiale și este egal cu 1,05 ore în medie.

4. QS cu un singur canal cu așteptare

fără limită de lungime a cozii

Condițiile de funcționare a QS rămân neschimbate, ținând cont de faptul că N .

Modul staționar de funcționare al unui astfel de QS există:

pentru oricine n= 0, 1, 2, ... și când λ < μ .

Sistemul de ecuații care descrie funcționarea QS:

Rezolvarea sistemului de ecuații are forma:

2. Durata medie a șederii unui client în sistem:

3. Numărul mediu de clienți în coada de servicii:

4. Durata medie a șederii clientului în coadă:

Exemplu.

Un post de diagnostic specializat este un QS cu un singur canal. Numărul de parcări pentru mașinile care așteaptă diagnosticare nu este limitat. Fluxul de mașini care sosesc pentru diagnosticare este distribuit conform legii Poisson și are o intensitate de λ = 0,85 (mașini pe oră). Timpul de diagnosticare auto este distribuit conform legii exponențiale și este egal cu 1,05 ore în medie.

Este necesar să se determine caracteristicile probabilistice ale unui post de diagnostic care funcționează în mod staționar.

Ca urmare a rezolvării problemei, este necesar să se determine valorile finale ale următoarelor caracteristici probabilistice:

ü probabilitățile stărilor sistemului (post de diagnostic);

ü numărul mediu de mașini din sistem (în service și în coadă);

ü durata medie de ședere a mașinii în sistem (în service și în coadă);

ü numărul mediu de mașini în coada de service;

durata medie de timp pe care o mașină o petrece la coadă.

1. Parametrul debitului de serviciu și intensitatea redusă a debitului mașinii:

μ = 0,952; ψ = 0,893.

2. Limitarea probabilităților de stare a sistemului:

P 0 (t) determină proporția de timp în care postul de diagnosticare este forțat să fie inactiv (inactiv). În exemplu, această proporție este de 10,7%, deoarece P 0 (t) = 0,107.

3. Numărul mediu de mașini din sistem

(în serviciu și în linie):

4. Durata medie a șederii unui client în sistem

5. Numărul mediu de mașini în coada de service:

6. Durata medie de ședere a mașinii în coadă:

7. Debit relativ al sistemului:

q= 1, adică fiecare cerere care intră în sistem va fi deservită.

8. Lățimea de bandă absolută:

Designul de prezentare al materialului este prezentat în fișierul „TMO”

Întrebări și sarcini

(conform lui Afanasiev M.Yu.)

Intrebarea 1. Un muncitor întreține treizeci de războaie, asigurându-se că pornesc după o rupere a firului. Modelul unui astfel de sistem de așteptare poate fi caracterizat astfel:

1) multicanal monofazat cu o populație limitată;

2) monofazat monocanal cu o populație nelimitată;

3) multifazic monocanal cu o populație limitată;

4) monofazat monocanal cu o populație limitată;

5) multi-canal monofazat cu o populație nelimitată.

Intrebarea 2.În teoria stării de așteptare, pentru a descrie cel mai simplu flux de cereri care ajung la intrarea sistemului, se utilizează distribuția de probabilitate:

1) normal;

2) exponenţial;

3) Poisson;

4) binom;

Întrebarea 3.În teoria cozilor de așteptare, se presupune că numărul de clienți dintr-o populație este:

1) fix sau variabil;

2) limitat sau nelimitat;

3) cunoscut sau necunoscut;

4) aleatoriu sau determinist;

5) niciuna din cele de mai sus nu este adevărată.

Întrebarea 4. Cei doi parametri principali care determină configurația unui sistem de așteptare sunt:

1) rata de primire și rata de serviciu;

2) lungimea cozii și regula de serviciu;

3) distribuția timpului între aplicații și distribuția timpului de serviciu;

4) numărul de canale și numărul de faze de serviciu;

5) niciuna din cele de mai sus nu este adevărată.

Întrebarea 5.În teoria stării de așteptare, o distribuție de probabilitate este de obicei folosită pentru a descrie timpul petrecut cu cererile de service:

1) normal;

2) exponenţial;

3) Poisson;

4) binom;

5) niciuna din cele de mai sus nu este adevărată.

Întrebarea 6. Reparația calculatoarelor defecte de la Facultatea de Economie este efectuată de trei specialiști care lucrează simultan și independent unul de celălalt. Modelul unui astfel de sistem de așteptare poate fi caracterizat astfel:

1) multicanal cu o populație limitată;

2) monocanal cu populație nelimitată;

3) monocanal cu o populație limitată;

4) monocanal cu o coadă limitată;

5) multicanal cu populație nelimitată.

Răspunsuri la întrebări: 1 -4, 2 - 3, 3 -2, 4 -4, 5 -2, 6 -1.

PLANIFICAREA ȘI MANAGEMENTUL REȚELEI

Sistemele de planificare și management al rețelei (SPU) sunt un tip special de sisteme de management organizate concepute pentru a reglementa activitățile de producție ale echipelor. Ca și în alte sisteme din această clasă, „obiectul controlului” în sistemele STC este o echipă de executanți care dispun de anumite resurse: umane, materiale, financiare. Cu toate acestea, aceste sisteme au o serie de caracteristici, deoarece baza lor metodologică o constituie metodele de cercetare operațională, teoria graficelor direcționate și unele secțiuni de teoria probabilităților și statistica matematică. O proprietate necesară a sistemului de planificare și management este, de asemenea, capacitatea de a evalua starea actuală, de a prezice cursul ulterioară a activității și, astfel, de a influența cursul de pregătire și producție, astfel încât întreaga gamă de lucrări să fie finalizată la timp și la cel mai mic cost. .

În prezent, modelele și metodele STC sunt utilizate pe scară largă în planificarea și implementarea lucrărilor de construcție și instalare, planificarea activităților de tranzacționare, întocmirea rapoartelor contabile, elaborarea unui plan comercial și financiar etc.

Gama de aplicare a SPM este foarte largă: de la sarcini legate de activitățile persoanelor fizice, până la proiecte care implică sute de organizații și zeci de mii de oameni (de exemplu, dezvoltarea și crearea unui complex teritorial-industrial mare).

Pentru a întocmi un plan de lucru pentru implementarea unor proiecte mari și complexe, constând din mii de studii și operațiuni separate, este necesar să îl descriem folosind un model matematic. Un astfel de instrument pentru descrierea proiectelor (complexelor) este un model de rețea.