Rezumatul lecției „teoria sistemelor de așteptare”. Coadă cu așteptare (coadă) Coadă cu așteptare și coadă nelimitată

Subiect. Teoria sistemelor la coadă.

Fiecare QS constă dintr-un anumit număr de unități de serviciu, care sunt numitecanale de servicii (acestea sunt mașini, cărucioare de transport, roboți, linii de comunicare, casierii, vânzători etc.). Fiecare QS este conceput pentru a servi un fel defluxul de aplicații (cerințe) sosind la unele momente aleatorii în timp.

Clasificarea QS în funcție de metoda de procesare a fluxului de intrare al aplicațiilor.

Sisteme de așteptare

Cu refuzuri

(fără coadă)

Cu o coadă

Coadă nelimitată

Coadă limitată

Cu prioritate

Primul venit, primul servit

Prioritate relativă

Prioritate absolută

După timpul de service

După lungimea cozii

Clasificare după modul de funcționare:

deschis, adică fluxul de aplicații nu depinde de starea internă a QS;

închis, adică fluxul de intrare depinde de starea QS (un singur lucrător de reparații deservește toate canalele pe măsură ce eșuează).

QS multicanal cu așteptare

Sistem cu lungime limitată cozile. Să luăm în considerare canal QS cu așteptare, care primește un flux de solicitări cu o intensitate ; intensitatea serviciului (pentru un canal) ; numărul de locuri la coadă

Stările sistemului sunt numerotate în funcție de numărul de aplicații, conectate de sistem:

fara coada:

- toate canalele sunt gratuite;

- un canal este ocupat, restul sunt libere;

- ocupat -canale, nu altele;

- toată lumea este ocupată -nu exista canale gratuite;

exista o coada:

- toate canalele n sunt ocupate; o aplicație este în coadă;

- toate n-canalele, r-cererile din coada sunt ocupate;

- Toate n-canalele, r-cererile din coadă sunt ocupate.

GSP este prezentat în Fig. 9. Fiecare săgeată este marcată cu intensitățile corespunzătoare ale fluxurilor de evenimente. Sistemul este deplasat întotdeauna de-a lungul săgeților de la stânga la dreapta de același flux de aplicații cu intensitate , urmând săgețile de la dreapta la stânga, sistemul este transferat printr-un flux de serviciu, a cărui intensitate este egală cu , înmulțit cu numărul de canale ocupate.

Orez. 9. QS multicanal cu așteptare

Probabilitatea de eșec.

(29)

Debitul relativ completează probabilitatea de eșec la unul:

Debit absolut al QS:

(30)

Numărul mediu de canale ocupate.

Numărul mediu de cereri din coadă poate fi calculat direct ca așteptarea matematică a unei variabile aleatoare discrete:

(31)

Unde .

Din nou (expresia din paranteză) apare derivata sumei progresiei geometrice (vezi mai sus (23), (24) - (26)), folosind relația pentru aceasta, obținem:

Numărul mediu de aplicații în sistem:

Timp mediu de așteptare pentru o aplicație în coadă.

(32)

La fel ca și în cazul unui QS cu un singur canal cu așteptare, rețineți că această expresie diferă de expresia pentru lungimea medie a cozii numai în factor , adică

Timpul mediu de păstrare a unei cereri în sistem, la fel ca pentru un QS cu un singur canal .

Sisteme cu lungime nelimitată la coadă. Am revizuit canal QS cu așteptare, când nu pot fi în coadă mai mult de m-cereri în același timp.

La fel ca înainte, atunci când se analizează sisteme fără restricții, este necesar să se ia în considerare relațiile obținute pentru .

Probabilitatea de eșec

Obținem numărul mediu de aplicații din coadă la din (31):

iar timpul mediu de așteptare este de la (32): .

Numărul mediu de aplicații .

Exemplul 2. Benzinărie cu două coloane (n = 2) deservește fluxul de trafic cu intensitate =0,8 (mașini pe minut). Durata medie de service pe mașină:

Nu există altă benzinărie în zonă, așa că șirul de mașini din fața benzinăriei poate crește aproape nelimitat. Găsiți caracteristicile QS.

SMO cu timp limitat asteptari. Anterior, am considerat sisteme cu așteptare limitată doar de lungimea cozii (numărul de m-cereri simultan în coadă). Într-un astfel de QS, o aplicație care a crescut într-o coadă nu o părăsește până nu așteaptă service-ul. În practică, există și alte tipuri de QS în care o aplicație, după ce a așteptat ceva timp, poate părăsi coada (așa-numitele aplicații „nerăbdătoare”).

Să considerăm un QS de acest tip, presupunând că constrângerea timpului de așteptare este o variabilă aleatorie.

Poisson „flux de plecări” cu intensitate:

Dacă acest flux este Poisson, atunci procesul care are loc în QS va fi Markovian. Să găsim probabilitățile de stare pentru aceasta. Numerotarea stărilor sistemului este asociată cu numărul de aplicații din sistem - atât deservite, cât și de stat la coadă:

fara coada:

- toate canalele sunt gratuite;

- un canal este ocupat;

- două canale sunt ocupate;

- toate canalele n sunt ocupate;

exista o coada:

- toate canalele n sunt ocupate, o cerere este în coadă;

- Toate canalele n sunt ocupate, cererile r sunt în coadă etc.

Graficul stărilor și tranzițiilor sistemului este prezentat în Fig. 10.

Orez. 10. QS cu timp de așteptare limitat

Să marchem acest grafic ca înainte; toate săgețile care conduc de la stânga la dreapta vor indica intensitatea fluxului de aplicații . Pentru statele fără coadă, săgețile care duc de la ele de la dreapta la stânga vor indica, ca și înainte, intensitatea totală a fluxului care deservește toate canalele ocupate. În ceea ce privește statele cu o coadă, săgețile care duc de la ele de la dreapta la stânga vor indica intensitatea totală a fluxului de servicii al tuturor canalelor n plus intensitatea corespunzătoare a fluxului de plecări din coadă. Dacă există r-cereri în coadă, atunci intensitatea totală a fluxului de plecări va fi egală cu .

Numărul mediu de aplicații în coadă: (35)

Fiecare dintre aceste aplicații este supusă unui „flux de plecări” cu intensitatea . Deci, de la medie -în medie, aplicațiile din coadă vor pleca fără a aștepta serviciul, -aplicațiile pe unitate de timp și total pe unitate de timp vor fi deservite în medie - aplicatii. Capacitatea relativă a QS va fi:

Numărul mediu de canale ocupate mai obținem prin împărțirea capacității absolute a lui A la QS închis

Până acum am luat în considerare sisteme în care fluxul de intrare nu este în niciun fel legat de fluxul de ieșire. Astfel de sisteme se numesc buclă deschisă. În unele cazuri, solicitările deservite sunt din nou primite la intrare după o întârziere. Astfel de QS-uri sunt numite închise. O clinică care deservește o zonă dată, o echipă de muncitori repartizată unui grup de mașini, sunt exemple de sisteme închise.

Într-un QS închis circulă același număr finit de cerințe potențiale. Până când o cerință potențială a fost realizată ca cerere de serviciu, se consideră că se află într-un bloc de întârziere. În momentul implementării, acesta intră în sistem propriu-zis. De exemplu, lucrătorii întrețin un grup de mașini. Fiecare mașină este o cerință potențială, transformându-se într-una reală în momentul defecțiunii sale. În timp ce mașina funcționează, se află în blocul de întârziere, iar din momentul defecțiunii până la sfârșitul reparației, se află în sistemul propriu-zis. Fiecare lucrător este un canal de servicii. = =P 1 + 2 P 2 +…+(n- 1 )P n- 1 +n( 1 -P Intrarea unui QS cu trei canale cu defecțiuni primește un flux de solicitări cu o intensitate =4 solicitări pe minut, timp pentru deservirea unei cereri de către un canalt obsl=1/μ =0,5 min. Din punct de vedere al capacității QS, este profitabil să forțați toate cele trei canale să depună cereri de serviciu simultan, iar timpul mediu de service este redus de trei ori? Cum va afecta acest lucru timpul mediu petrecut de o aplicație în CMO?

Exemplul 2 . /μ=2, ρ/n =2/3<1.

Sarcina 3:

Doi muncitori operează un grup de patru mașini. Opririle unei mașini de lucru au loc în medie după 30 de minute. Timpul mediu de configurare este de 15 minute. Timpul de funcționare și de configurare este distribuit conform unei legi exponențiale.

Găsiți ponderea medie a timpului liber pentru fiecare lucrător și timpul mediu de funcționare al mașinii.

Găsiți aceleași caracteristici pentru un sistem în care:

a) fiecărui muncitor i se atribuie două utilaje;

b) doi muncitori întrețin întotdeauna mașina împreună, și cu intensitate dublă;

c) singura mașină defectă este întreținută de ambii muncitori simultan (cu intensitate dublă), iar când mai apare cel puțin o altă mașină defectă, aceștia încep să funcționeze separat, fiecare deservind câte o mașină (descrieți mai întâi sistemul din punct de vedere al proceselor de moartea şi naşterea).

Agenția Federală pentru Educație a Federației Ruse

FGOU SPO „Colegiul de construcții Perevozsky”

Lucrări de curs

la disciplina „Metode matematice”

pe tema „SMO cu timp de așteptare limitat. QS închis"

Introducere................................................. ....... ................................................. ............. ....... 2

1. Fundamentele teoriei cozilor de așteptare.................................................. ................ ...... 3

1.1 Conceptul de proces aleatoriu............................................. ......... ................. 3

1.2 Proces aleatoriu Markov.............................................. ...... ................ 4

1.3 Fluxuri de evenimente.................................................. ............................. ................................. ............. 6

1.4 Ecuații Kolmogorov pentru probabilități de stare. Probabilități de stare finală.................................................. ............................................................... ..................... ........ 9

1.5 Probleme ale teoriei cozilor de așteptare............................................. ....... .. 13

1.6 Clasificarea sistemelor de așteptare.................................................. ..... 15

2. Sisteme de așteptare cu așteptare.................................................. ........ 16

2.1 QS cu un singur canal cu așteptare............................................. ......... .......... 16

2.2 QS multicanal cu așteptare............................................. ......... ......... 25

3. QS închis.............................................. ...................................................... ... 37

Rezolvarea problemei.................................................................. ..... ................................................. 45

Concluzie................................................. .................................................. ...... .50

Referințe.................................................................. ....................................................... 51

În acest curs ne vom uita la diferite sisteme de așteptare (QS) și rețele de așteptare (Queuing).

Sistemul de așteptare (QS) este înțeles ca un sistem dinamic conceput pentru a deservi eficient fluxul de cereri (cerințe de serviciu) sub restricții asupra resurselor sistemului.

Modelele QS sunt convenabile pentru descrierea subsistemelor individuale ale sistemelor de calcul moderne, cum ar fi subsistemul procesorului - memoria principală, canalul de intrare-ieșire etc. Un sistem de calcul în ansamblu este un set de subsisteme interconectate, a căror interacțiune este probabilistică. O aplicație pentru rezolvarea unei anumite probleme de intrare într-un sistem de calcul parcurge o succesiune de etape de numărare, accesarea dispozitivelor de stocare externe și a dispozitivelor de intrare-ieșire. După finalizarea unei anumite secvențe de astfel de etape, numărul și durata cărora depind de complexitatea programului, cererea este considerată deservită și părăsește sistemul informatic. Astfel, sistemul de calcul în ansamblu poate fi reprezentat printr-un set de QS, fiecare dintre acestea reflectând procesul de funcționare a unui dispozitiv individual sau a unui grup de dispozitive similare care fac parte din sistem.

Un set de QS-uri interconectate se numește rețea de așteptare (rețea stocastică).

Pentru început, ne vom uita la elementele de bază ale teoriei QS, apoi vom trece la familiarizarea cu conținutul detaliat cu QS cu așteptare și QS închis. Cursul include și o parte practică, în care vom învăța în detaliu cum să aplicăm teoria în practică.

Teoria cozilor este una dintre ramurile teoriei probabilităților. Această teorie consideră probabilistică probleme și modele matematice (înainte de asta am considerat modele matematice deterministe). Să vă reamintim că:

Model matematic determinist reflectă comportamentul unui obiect (sistem, proces) din perspectivă certitudine deplinăîn prezent și viitor.

Model matematic probabilist ia în considerare influența factorilor aleatori asupra comportamentului unui obiect (sistem, proces) și, prin urmare, evaluează viitorul din punctul de vedere al probabilității anumitor evenimente.

Aceste. aici, ca, de exemplu, în teoria jocurilor sunt luate în considerare problemele in conditii incertitudine .

Să luăm în considerare mai întâi câteva concepte care caracterizează „incertitudinea stocastică”, atunci când factorii nesiguri incluși în problemă sunt variabile aleatoare (sau funcții aleatoare), ale căror caracteristici probabilistice fie sunt cunoscute, fie pot fi obținute din experiență. O astfel de incertitudine este numită și „favorabilă”, „benignă”.

Strict vorbind, tulburările aleatorii sunt inerente oricărui proces. Este mai ușor să dai exemple de proces aleatoriu decât un proces „nealeatoriu”. Chiar și, de exemplu, procesul de rulare a unui ceas (pare a fi o lucrare strict calibrată - „funcționează ca un ceas”) este supus unor modificări aleatorii (înainte, rămânere în urmă, oprire). Dar atâta timp cât aceste perturbări sunt nesemnificative și au un efect redus asupra parametrilor care ne interesează, le putem neglija și considera procesul ca fiind determinist, non-aleatoriu.

Să existe un sistem S(dispozitiv tehnic, grup de astfel de dispozitive, sistem tehnologic - mașină, șantier, atelier, întreprindere, industrie etc.). În sistem S scurgeri proces aleatoriu, dacă își schimbă starea în timp (trece de la o stare la alta), mai mult, într-o manieră aleatorie necunoscută anterior.

Exemple:

1. Sistem S– sistem tehnologic (sectiunea masini). Mașinile se defectează din când în când și sunt reparate. Procesul care are loc în acest sistem este aleatoriu.

2. Sistem S- o aeronavă care zboară la o altitudine dată de-a lungul unei anumite rute. Factori deranjanți - condițiile meteorologice, erorile echipajului etc., consecințe - accidentare, încălcarea programului de zbor etc.

Se numește un proces aleatoriu care are loc într-un sistem Markovsky, dacă pentru orice moment de timp t 0 caracteristicile probabilistice ale unui proces în viitor depind numai de starea acestuia în momentul de față t 0 și nu depind de când și cum a ajuns sistemul în această stare.

Fie ca sistemul să fie într-o anumită stare în momentul t 0 S 0 . Cunoaștem caracteristicile stării sistemului în prezent și tot ce s-a întâmplat în timpul t <t 0 (istoricul procesului). Putem prezice (prevaza) viitorul, de ex. ce se va întâmpla când t >t 0 ? Nu tocmai, dar unele caracteristici probabilistice ale procesului pot fi găsite în viitor. De exemplu, probabilitatea ca după ceva timp sistemul S va putea S 1 sau va rămâne în stare S 0, etc.

Exemplu. Sistem S- un grup de aeronave care participă la lupte aeriene. Lasă x– numărul de avioane „roșii”, y– numărul de aeronave „albastre”. Până când t 0 număr de aeronave supraviețuitoare (nu doborâte), respectiv – x 0 , y 0 . Ne interesează probabilitatea ca la un moment dat superioritatea numerică să fie de partea „roșiilor”. Această probabilitate depinde de starea în care se afla sistemul la momentul respectiv t 0, și nu când și în ce secvență cei doborâți au murit până în momentul de față t 0 avioane.

În practică, procesele Markov în forma lor pură nu sunt de obicei întâlnite. Dar există procese pentru care influența „preistoriei” poate fi neglijată. Și atunci când se studiază astfel de procese, pot fi folosite modele Markov (teoria cozilor de așteptare nu ia în considerare sistemele de așteptare Markov, dar aparatul matematic care le descrie este mult mai complex).

În cercetarea operațională, procesele aleatoare Markov cu stări discrete și timp continuu sunt de mare importanță.

Procesul este numit proces de stare discretă, dacă este posibil S 1 , S 2, ... poate fi determinat în prealabil, iar tranziția sistemului de la stare la stare are loc „într-un salt”, aproape instantaneu.

Procesul este numit proces în timp continuu, dacă momentele posibilelor tranziții de la stare la stare nu sunt fixate în prealabil, ci sunt incerte, aleatorii și pot apărea în orice moment.

Exemplu. Sistem tehnologic (secțiune) S este format din două mașini, fiecare dintre acestea putând defecta (eșua) la un moment aleator, după care începe imediat reparația unității, care continuă și pentru un timp necunoscut, aleatoriu. Sunt posibile următoarele stări ale sistemului:

S 0 - ambele mașini funcționează;

S 1 - prima mașină este în curs de reparare, a doua funcționează;

S 2 - a doua mașină este în curs de reparare, prima funcționează;

S 3 - ambele mașini sunt în curs de reparare.

Tranziții de sistem S de la stare la stare apar aproape instantaneu, în momente aleatorii când o anumită mașină eșuează sau o reparație este finalizată.

Când se analizează procese aleatoare cu stări discrete, este convenabil să se folosească o schemă geometrică - grafic de stare. Vârfurile graficului sunt stările sistemului. Arcele graficului sunt posibile tranziții de la stare la stare. Pentru exemplul nostru, graficul de stare este prezentat în Fig. 1.

Orez. 1. Graficul stării sistemului

Nota. Trecerea de la stat S 0 in S 3 nu este indicat în figură, deoarece se presupune că mașinile eșuează independent unele de altele. Neglijăm posibilitatea defecțiunii simultane a ambelor mașini.

Flux de evenimente– o succesiune de evenimente omogene care urmează unul după altul în anumite momente aleatorii în timp.

În exemplul anterior, acesta este un flux de eșecuri și un flux de restaurări. Alte exemple: fluxul de apeluri la o centrală telefonică, fluxul de clienți într-un magazin etc.

Fluxul evenimentelor poate fi reprezentat vizual printr-o serie de puncte de pe axa timpului O t- orez. 2.

Orez. 2. Imagine a fluxului de evenimente pe axa timpului

Poziția fiecărui punct este aleatorie și aici este descrisă o singură implementare a fluxului.

Intensitatea fluxului evenimentului ( ) este numărul mediu de evenimente pe unitatea de timp.

Să ne uităm la unele proprietăți (tipuri) de fluxuri de evenimente.

Fluxul de evenimente este numit staţionar, dacă caracteristicile sale probabilistice nu depind de timp.

În special, intensitatea fluxului staționar este constantă. Fluxul evenimentelor are inevitabil condensări sau rarefacții, dar acestea nu sunt de natură obișnuită, iar numărul mediu de evenimente pe unitatea de timp este constant și nu depinde de timp.

Fluxul de evenimente este numit curge fara consecinte, dacă pentru oricare două secțiuni de timp care nu se suprapun și (vezi Fig. 2) numărul de evenimente care cad pe una dintre ele nu depinde de câte evenimente cad pe celălalt. Cu alte cuvinte, aceasta înseamnă că evenimentele care formează fluxul apar în anumite momente în timp independent unul de altulși fiecare sunt cauzate de propriile sale cauze.

Fluxul de evenimente este numit comun, dacă evenimentele apar în el unul câte unul, și nu în grupuri de mai multe simultan.

Fluxul de evenimente este numit cel mai simplu (sau staționar Poisson), dacă are trei proprietăți simultan:

1) staționar;

2) obișnuit;

3) nu are consecințe.

Cel mai simplu flux are cea mai simplă descriere matematică. Ea joacă același rol special între fluxuri ca și legea distribuției normale între alte legi de distribuție. Și anume, la suprapunerea unui număr suficient de mare de fluxuri independente, staționare și obișnuite (comparabile între ele ca intensitate), se obține un flux apropiat de cel mai simplu.

Pentru cel mai simplu debit cu interval de intensitate Tîntre evenimente învecinate are o așa-numită distribuție exponențială cu densitate:

unde este parametrul legii exponenţiale.

Pentru o variabilă aleatorie T, care are o distribuție exponențială, așteptarea matematică este reciproca parametrului, iar abaterea standard este egală cu așteptarea matematică:

Luând în considerare procesele Markov cu stări discrete și timp continuu, se presupune că toate tranzițiile sistemului S de la stare la stare apar sub influența fluxurilor de evenimente simple (fluxuri de apel, fluxuri de defecțiuni, fluxuri de recuperare etc.). Dacă toate fluxurile de evenimente transferă sistemul S de la starea la starea cea mai simplă, atunci procesul care are loc în sistem va fi Markovian.

Deci, un sistem în stare este afectat de un simplu flux de evenimente. De îndată ce apare primul eveniment al acestui flux, sistemul „sare” de la o stare la alta (pe graficul de stare de-a lungul săgeții).

Pentru claritate, pe graficul stării sistemului, pentru fiecare arc, este indicată intensitatea fluxului de evenimente care mișcă sistemul de-a lungul acestui arc (săgeată). - intensitatea fluxului de evenimente care transferă sistemul din stare în . Un astfel de grafic se numește marcat. Pentru exemplul nostru, graficul etichetat este prezentat în Fig. 3.

Orez. 3. Graficul de stare a sistemului etichetat

În această figură - intensitatea fluxului de defecțiune; - intensitatea fluxului de recuperare.

Presupunem că timpul mediu de reparare a unei mașini nu depinde de faptul dacă o mașină este reparată sau ambele simultan. Aceste. Fiecare mașină este reparată de un specialist separat.

Lăsați sistemul să fie în stat S 0 . În stare S 1 se traduce prin fluxul de defecțiuni ale primei mașini. Intensitatea sa este egală cu:

unde este timpul mediu de funcționare fără defecțiuni a primei mașini.

De la stat S 1 in S 0 sistemul este transferat prin fluxul de „finalizări de reparații” al primei mașini. Intensitatea sa este egală cu:

unde este timpul mediu de reparație pentru prima mașină.

Intensitățile fluxurilor de evenimente care transferă sistemul de-a lungul tuturor arcelor graficului sunt calculate într-un mod similar. Având la dispoziție un grafic etichetat al stărilor sistemului, construim model matematic a acestui proces.

Lăsați sistemul luat în considerare S are -stări posibile. Probabilitatea celei de-a-a stări este probabilitatea ca în momentul de timp, sistemul să fie în starea. Este evident că pentru orice moment în timp suma tuturor probabilităților de stare este egală cu unu:

Pentru a găsi toate probabilitățile stărilor în funcție de timp, compuneți și rezolvați Ecuații Kolmogorov– un tip special de ecuație în care funcțiile necunoscute sunt probabilitățile stărilor. Regula pentru alcătuirea acestor ecuații este prezentată aici fără dovezi. Dar înainte de a o introduce, să explicăm conceptul probabilitatea finală de stare .

Ce se va întâmpla cu probabilitățile de stare la? Se vor strădui ei pentru vreo limită? Dacă aceste limite există și nu depind de starea inițială a sistemului, atunci ele sunt numite probabilitățile de stare finală .

unde este numărul finit de stări ale sistemului.

Probabilități de stare finală– acestea nu mai sunt cantități variabile (funcții ale timpului), ci numere constante. Este evident că:

Probabilitatea de stare finală este în esență timpul relativ mediu în care sistemul rămâne în această stare.

De exemplu, sistemul S are trei stări S 1 , S 2 și S 3. Probabilitățile lor finale sunt, respectiv, 0,2; 0,3 și 0,5. Aceasta înseamnă că un sistem în stare limită staționară își petrece în medie 2/10 din timpul său în stat S 1, 3/10 – capabil S 2 și 5/10 – capabil S 3 .

Regula pentru alcătuirea sistemului de ecuații Kolmogorov: în fiecare ecuație a sistemului pe partea stângă este probabilitatea finală a unei stări date, înmulțită cu intensitatea totală a tuturor fluxurilor, conducând din această stare, A în dreptul lui piese– suma produselor intensităților tuturor fluxurilor, incluse în -a stare, asupra probabilităţilor stărilor din care provin aceste fluxuri.

Folosind această regulă, scriem un sistem de ecuații pentru exemplul nostru :

Acest sistem de patru ecuații cu patru necunoscute, s-ar părea, poate fi rezolvat complet. Dar aceste ecuații sunt omogene (nu au termen liber) și, prin urmare, determină necunoscutele doar până la un factor arbitrar. Cu toate acestea, puteți utiliza condiția de normalizare: și folosiți-l pentru a rezolva sistemul. În acest caz, una (oricare) ecuații poate fi aruncată (urmează ca o consecință a celorlalte).

Continuarea exemplului. Fie intensitățile debitului egale cu: .

Renunțăm la a patra ecuație și adăugăm în schimb o condiție de normalizare:

Aceste. în modul de limitare, staționar sistemul Sîn medie 40% din timp va fi petrecut în stare de S 0 (ambele utilaje sunt operaționale), 20% - în stare bună S 1 (prima mașină este în curs de reparare, a doua funcționează), 27% - în stare S 2 (a doua mașină este în curs de reparare, prima funcționează), 13% - în stare S 3 (ambele utilaje sunt în curs de reparare). Cunoașterea acestor probabilități finale poate ajuta la estimarea eficienței medii a sistemului și a volumului de muncă al organelor de reparare.

Lasă sistemul S capabil S 0 (complet operațional) aduce un venit de 8 unități convenționale pe unitatea de timp, capabil S 1 – venit 3 unitati conventionale, capabil S 2 – venit 5 unitati conventionale, capabil S 3 – nu generează venituri. Apoi, în modul limitativ, staționar, venitul mediu pe unitatea de timp va fi egal cu: unități convenționale.

Mașina 1 este reparată într-o fracțiune de timp egală cu: . Mașina 2 este reparată într-o fracțiune de timp egală cu: . Apare problema de optimizare. Chiar dacă putem reduce timpul mediu de reparare a primei sau a doua mașini (sau ambelor), ne va costa o anumită sumă. Întrebarea este: veniturile crescute asociate cu reparațiile mai rapide vor plăti costurile crescute de reparații? Va trebui să rezolvați un sistem de patru ecuații cu patru necunoscute.

Exemple de sisteme de așteptare (QS): centrale telefonice, ateliere de reparații, case de bilete, birouri de informații, mașini-unelte și alte sisteme tehnologice, sisteme de control ale sistemelor flexibile de producție etc.

Fiecare QS constă dintr-un anumit număr de unități de serviciu, care sunt numite canale de servicii(acestea sunt mașini, cărucioare de transport, roboți, linii de comunicare, casierii, vânzători etc.). Fiecare QS este conceput pentru a servi un fel de fluxul de aplicații(cerințe) sosind la unele momente aleatorii în timp.

Servirea cererii continuă pentru un timp, în general, aleatoriu, după care canalul este eliberat și gata să primească următoarea solicitare. Natura aleatorie a fluxului de aplicații și a timpului de service duce la faptul că, în anumite perioade de timp, la intrarea QS-ului se acumulează un număr excesiv de mare de aplicații (fie pun la coadă, fie lasă QS-ul neservit). În alte perioade, sistemul va funcționa cu subîncărcare sau va fi complet inactiv.

Procesul de operare QS este un proces aleatoriu cu stări discrete și timp continuu. Starea QS-ului se schimbă brusc atunci când apar anumite evenimente (sosirea unei noi aplicații, încetarea serviciului, momentul în care o aplicație obosită de așteptare iese din coadă).

Subiectul teoriei cozilor– construirea de modele matematice care conectează condițiile de funcționare date ale QS (numărul de canale, productivitatea acestora, regulile de funcționare, natura fluxului de solicitări) cu caracteristicile care ne interesează - indicatori ai eficacității QS. Acești indicatori descriu capacitatea CMO de a face față fluxului de aplicații. Acestea pot fi: numărul mediu de aplicații deservite de QS pe unitatea de timp; numărul mediu de canale ocupate; numărul mediu de aplicații în coadă; timpul mediu de așteptare pentru serviciu etc.

Analiza matematică a muncii unui QS este mult facilitată dacă procesul acestei lucrări este Markovian, adică. fluxurile de evenimente care transferă sistemul de la stat la stat sunt cele mai simple. În caz contrar, descrierea matematică a procesului devine foarte complicată și rareori este posibil să o aducem la dependențe analitice specifice. În practică, procesele non-Markov sunt reduse la procese Markov cu aproximare. Următorul aparat matematic descrie procesele Markov.

Prima diviziune (pe baza prezenței cozilor):

1. QS cu defecțiuni;

2. Coadă cu o coadă.

În QS cu eșecuri o aplicație primită într-un moment în care toate canalele sunt ocupate este respinsă, părăsește QS și nu este deservită în viitor.

În SMO cu o coadă o aplicație care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci se pune la coadă și așteaptă să fie servită oportunitatea.

QS cu cozi sunt subdivizateîn diferite tipuri, în funcție de modul în care este organizată coada - limitat sau nelimitat. Restricțiile pot viza atât lungimea cozii, cât și timpul de așteptare, „disciplina de serviciu”.

Deci, de exemplu, sunt luate în considerare următoarele QS:

· CMO cu cereri nerăbdătoare (lungimea cozii și timpul de service sunt limitate);

· QS cu serviciu prioritar, de ex. unele cereri sunt procesate în afara rândului etc.

În plus, QS-urile sunt împărțite în QS-uri deschise și QS-uri închise.

Într-un QS deschis caracteristicile fluxului de aplicații nu depind de starea QS-ului în sine (cate canale sunt ocupate). Într-un QS închis– depind. De exemplu, dacă un lucrător deservește un grup de mașini care necesită ajustare din când în când, atunci intensitatea fluxului de „cereri” de la mașini depinde de câte dintre ele sunt deja operaționale și așteaptă ajustarea.

Clasificarea SMO este departe de a fi limitată la soiurile de mai sus, dar acest lucru este suficient.

Să considerăm cel mai simplu QS cu așteptare - un sistem cu un singur canal (n - 1), care primește un flux de solicitări cu intensitate; intensitatea serviciului (adică, în medie, un canal ocupat continuu va emite solicitări deservite pe unitate (de timp). O solicitare primită la un moment în care canalul este ocupat este pusă în coadă și așteaptă serviciul.

Sistem cu lungime limitată la coadă. Să presupunem mai întâi că numărul de locuri din coadă este limitat de numărul m, adică. dacă o aplicație ajunge într-un moment în care există deja m-aplicații în coadă, ea lasă sistemul neservit. În viitor, prin direcționarea m către infinit, vom obține caracteristicile unui QS cu un singur canal fără restricții privind lungimea cozii.

Vom numerota stările QS-ului în funcție de numărul de aplicații din sistem (atât în curs de service, cât și în așteptare):

Canalul este gratuit;

Canalul este ocupat, nu există coadă;

Canalul este ocupat, o cerere este în coadă;

Canalul este ocupat, aplicațiile k-1 sunt în coadă;

Canalul este ocupat, aplicațiile sunt la coadă.

GSP este prezentat în Fig. 4. Toate intensitățile fluxurilor de evenimente care se deplasează în sistem de-a lungul săgeților de la stânga la dreapta sunt egale cu și de la dreapta la stânga - . Într-adevăr, fluxul de solicitări mută sistemul de-a lungul săgeților de la stânga la dreapta (de îndată ce sosește o solicitare, sistemul trece la următoarea stare), de la dreapta la stânga - fluxul de „eliberări” ale unui canal ocupat, care are o intensitate (de îndată ce următoarea solicitare este deservită, canalul fie va deveni liber, fie va reduce numărul de aplicații din coadă).

Orez. 4. QS cu un singur canal cu așteptare

Arată în Fig. Diagrama 4 este o diagramă a reproducerii și a morții. Să scriem expresii pentru probabilitățile limită ale stărilor:

(5)

sau folosind: :

(6)

Ultima linie din (6) conține o progresie geometrică cu primul termen 1 și numitorul p, din care obținem:

(7)

în legătură cu care probabilitățile limitative iau forma:

(8).

Expresia (7) este valabilă numai pentru< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:

Să determinăm caracteristicile QS: probabilitatea de eșec, debitul relativ q, debitul absolut A, lungimea medie a cozii, numărul mediu de aplicații asociate sistemului, timpul mediu de așteptare în coadă, timpul mediu petrecut de o aplicație în QS .

Probabilitatea de eșec. Evident, aplicația este respinsă doar dacă canalul este ocupat și toate locurile t din coadă sunt de asemenea ocupate:

(9).

Lățime de bandă relativă:

(10).

Lungimea medie a cozii. Să găsim numărul mediu de aplicații din coadă ca așteptarea matematică a unei variabile aleatoare discrete R-număr de aplicații din coadă:

Cu probabilitate există o aplicație în coadă, cu probabilitate sunt două aplicații, în general cu probabilitate sunt k-1 aplicații în coadă etc., din care:

(11).

Deoarece , suma din (11) poate fi interpretată ca o derivată a sumei progresiei geometrice:

Înlocuind această expresie în (11) și folosind din (8), obținem în final:

(12).

Numărul mediu de aplicații din sistem. În continuare, obținem o formulă pentru numărul mediu de solicitări asociate sistemului (atât în coadă, cât și deservite). Deoarece , unde este numărul mediu de aplicații aflate în serviciu și k este cunoscut, rămâne de determinat . Deoarece există un singur canal, numărul de cereri deservite poate fi 0 (cu probabilitate ) sau 1 (cu probabilitate 1 - ), din care:

iar numărul mediu de aplicații asociate cu QS este:

(13).

Timp mediu de așteptare pentru o aplicație în coadă. Să o notăm; dacă o solicitare intră în sistem la un moment dat, atunci cu probabilitate canalul de serviciu nu va fi ocupat și nu va trebui să aștepte la coadă (timpul de așteptare este zero). Cel mai probabil, ea va intra în sistem în timp ce o cerere este servită, dar nu va fi nicio coadă în fața ei, iar cererea va aștepta începerea deservirii acesteia pentru o perioadă de timp (timpul mediu de deservire a uneia cerere). Există probabilitatea ca o altă aplicație să fie în coadă înainte de aplicația luată în considerare, iar timpul mediu de așteptare va fi egal cu , etc.

Dacă k=m+1, adică. când o cerere nou sosită găsește canalul de serviciu ocupat și m-cereri în coadă (probabilitatea acestui lucru), atunci în acest caz cererea nu se află în coadă (și nu este servită), deci timpul de așteptare este zero. Timpul mediu de așteptare va fi:

dacă substituim expresii pentru probabilitățile (8) aici, obținem:

(14).

Aici folosim relațiile (11), (12) (derivată a unei progresii geometrice), precum și din (8). Comparând această expresie cu (12), observăm că, cu alte cuvinte, timpul mediu de așteptare este egal cu numărul mediu de cereri din coadă împărțit la intensitatea fluxului de aplicații.

(15).

Timpul mediu de păstrare a unei aplicații în sistem. Să notăm așteptarea matematică a unei variabile aleatoare ca timpul în care o cerere rămâne în QS, care este suma timpului mediu de așteptare în coadă și timpul mediu de serviciu. Dacă încărcarea sistemului este de 100%, evident, în caz contrar:

Exemplul 1. O benzinărie (benzinărie) este o stație de benzină cu un canal de serviciu (o pompă).

Zona de la stație permite nu mai mult de trei mașini să fie la rând pentru realimentare în același timp (m = 3). Dacă sunt deja trei mașini în coadă, următorul vagon care sosește în stație nu se alătură la coadă. Fluxul de mașini care sosesc pentru realimentare are o intensitate = 1 (mașină pe minut). Procesul de realimentare durează în medie 1,25 minute.

Defini:

probabilitatea de eșec;

capacitatea relativă și absolută a benzinăriilor;

numărul mediu de mașini care așteaptă să realimenteze;

numărul mediu de mașini la o benzinărie (inclusiv cele deservite);

timpul mediu de așteptare pentru o mașină la coadă;

timpul mediu pe care îl petrece o mașină la o benzinărie (inclusiv service).

Cu alte cuvinte, timpul mediu de așteptare este egal cu numărul mediu de cereri din coadă împărțit la intensitatea fluxului de aplicații.

Găsim mai întâi intensitatea redusă a fluxului de aplicații: =1/1,25=0,8; =1/0,8=1,25.

Conform formulelor (8):

Probabilitatea de eșec este de 0,297.

Capacitatea relativă a QS: q=1-=0,703.

Debit absolut al QS: A==0,703 mașini pe minut.

Găsim numărul mediu de mașini din coadă folosind formula (12):

aceste. Numărul mediu de mașini care așteaptă la coadă pentru a umple benzinăria este de 1,56.

Adăugând la această valoare numărul mediu de vehicule în service:

obținem numărul mediu de mașini asociate unei benzinării.

Timp mediu de așteptare pentru o mașină la coadă conform formulei (15):

Adăugând la această valoare, obținem timpul mediu pe care îl petrece o mașină la o benzinărie:

Sisteme cu așteptare nelimitată. În astfel de sisteme, valoarea lui m nu este limitată și, prin urmare, caracteristicile principale pot fi obținute prin trecerea la limită în expresiile obținute anterior (5), (6) etc.

Rețineți că numitorul din ultima formulă (6) este suma unui număr infinit de termeni ai progresiei geometrice. Această sumă converge atunci când progresia este în scădere infinită, adică. la<1.

Se poate dovedi că<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.

Dacă, atunci relațiile (8) iau forma:

(16).

Dacă nu există restricții privind lungimea cozii, fiecare aplicație care intră în sistem va fi deservită, deci q=1, .

Obținem numărul mediu de aplicații din coadă de la (12) la:

Numărul mediu de aplicații în sistem conform formulei (13) la:

Timpul mediu de așteptare se obține din formula (14) cu:

În cele din urmă, timpul mediu pe care o aplicație rămâne în QS este:

Sistem cu lungime limitată la coadă. Să considerăm un canal QS cu așteptare, care primește un flux de solicitări cu intensitate; intensitatea serviciului (pentru un canal); numărul de locuri în coadă.

Stările sistemului sunt numerotate în funcție de numărul de solicitări asociate sistemului:

fara coada:

Toate canalele sunt gratuite;

Un canal este ocupat, restul sunt libere;

-canale sunt ocupate, restul nu;

Toate canalele sunt ocupate, nu există canale libere;

exista o coada:

Toate canalele n sunt ocupate; o aplicație este în coadă;

Toate n-canalele, r-cererile din coada sunt ocupate;

Toate n-canalele, r-cererile din coadă sunt ocupate.

GSP este prezentat în Fig. 17. Fiecare săgeată este marcată cu intensitățile corespunzătoare ale fluxurilor de evenimente. De-a lungul săgeților de la stânga la dreapta, sistemul este întotdeauna transferat de același flux de cereri cu o intensitate de

Orez. 17. QS multicanal cu așteptare

Graficul este tipic pentru procesele de reproducere și moarte, pentru care soluția a fost obținută anterior. Să scriem expresii pentru probabilitățile limită ale stărilor folosind notația: (aici folosim expresia pentru suma unei progresii geometrice cu numitor).

Astfel, au fost găsite toate probabilitățile de stare.

Să determinăm caracteristicile de performanță ale sistemului.

Probabilitatea de eșec. O solicitare primită este respinsă dacă toate canalele n și toate locurile m din coadă sunt ocupate:

(18)

Debitul relativ completează probabilitatea de eșec la unul:

Debit absolut al QS:

(19)

Numărul mediu de canale ocupate. Pentru QS cu refuzuri, acesta a coincis cu numărul mediu de cereri din sistem. Pentru un QS cu o coadă, numărul mediu de canale ocupate nu coincide cu numărul mediu de aplicații din sistem: ultima valoare diferă de prima prin numărul mediu de aplicații din coadă.

Să notăm numărul mediu de canale ocupate cu . Fiecare canal ocupat servește în medie revendicări A pe unitatea de timp, iar QS în ansamblu servește în medie cereri A pe unitatea de timp. Împărțind unul la altul, obținem:

Numărul mediu de cereri din coadă poate fi calculat direct ca așteptarea matematică a unei variabile aleatoare discrete:

(20)

Din nou (expresia dintre paranteze) apare derivata sumei progresiei geometrice (vezi mai sus (11), (12) - (14)), folosind relația pentru aceasta, obținem:

Numărul mediu de aplicații în sistem:

Timp mediu de așteptare pentru o aplicație în coadă. Să luăm în considerare o serie de situații care diferă în funcție de starea în care o cerere nou sosită va găsi sistemul și de cât timp va trebui să aștepte pentru service.

Dacă o solicitare nu găsește toate canalele ocupate, nu va trebui să aștepte deloc (termenii corespunzători din așteptarea matematică sunt egali cu zero). Dacă o solicitare sosește într-un moment în care toate n-canalele sunt ocupate și nu există coadă, va trebui să aștepte în medie un timp egal cu (deoarece „fluxul de lansare” al -canalelor are o intensitate de ). Dacă o solicitare găsește toate canalele ocupate și o solicitare în fața ei în coadă, va trebui să aștepte în medie o perioadă de timp (pentru fiecare cerere din față), etc. Dacă o solicitare se găsește într-o coadă de - cereri, va trebui să aștepte în medie timp Dacă o cerere nou sosită găsește m-cereri deja în coadă, atunci nu va aștepta deloc (dar nu va fi servită). Găsim timpul mediu de așteptare înmulțind fiecare dintre aceste valori cu probabilitățile corespunzătoare:

(21)

La fel ca și în cazul unui QS cu un singur canal cu așteptare, observăm că această expresie diferă de expresia pentru lungimea medie a cozii (20) doar prin factorul , i.e.

Timpul mediu pe care o cerere rămâne în sistem, precum și pentru un QS cu un singur canal, diferă de timpul mediu de așteptare cu timpul mediu de serviciu înmulțit cu debitul relativ:

Sisteme cu lungime nelimitată la coadă. Am considerat un canal QS cu așteptare, când nu pot fi în coadă mai mult de m-cereri în același timp.

La fel ca înainte, atunci când se analizează sisteme fără restricții, este necesar să se ia în considerare relațiile obținute pentru .

Obținem probabilitățile stărilor din formule trecând la limită (la ). Rețineți că suma progresiei geometrice corespunzătoare converge la și diverge la >1. Presupunând că<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Probabilitatea de eșec, debit relativ și absolut. Deoarece fiecare cerere va fi deservită mai devreme sau mai târziu, caracteristicile debitului QS vor fi:

Numărul mediu de aplicații din coadă se obține din (20):

iar timpul mediu de așteptare este de la (21):

Numărul mediu de canale ocupate, ca și înainte, este determinat prin debitul absolut:

Numărul mediu de aplicații asociate cu QS este definit ca numărul mediu de aplicații din coadă plus numărul mediu de aplicații aflate în serviciu (numărul mediu de canale ocupate):

Exemplul 2. O benzinărie cu două pompe (n = 2) deservește un flux de mașini cu o intensitate de =0,8 (mașini pe minut). Durata medie de service pe mașină:

Nu există altă benzinărie în zonă, așa că șirul de mașini din fața benzinăriei poate crește aproape nelimitat. Găsiți caracteristicile QS.

Din moment ce<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

etc.

Vom găsi numărul mediu de canale ocupate împărțind capacitatea absolută a QS A = = 0,8 la intensitatea serviciului = 0,5:

Probabilitatea să nu fie coadă la o benzinărie va fi:

Numărul mediu de mașini în coadă:

Numărul mediu de mașini la benzinării:

Timp mediu de așteptare la coadă:

Timpul mediu pe care îl petrece o mașină la o benzinărie:

QS cu timp de așteptare limitat. Anterior, am considerat sisteme cu așteptare limitată doar de lungimea cozii (numărul de m-cereri simultan în coadă). Într-un astfel de QS, o aplicație care a crescut într-o coadă nu o părăsește până nu așteaptă service-ul. În practică, există și alte tipuri de QS în care o aplicație, după ce a așteptat ceva timp, poate părăsi coada (așa-numitele aplicații „nerăbdătoare”).

Să considerăm un QS de acest tip, presupunând că constrângerea timpului de așteptare este o variabilă aleatorie.

Să presupunem că există un QS de așteptare pe canale n în care numărul de locuri în coadă este nelimitat, dar timpul în care o cerere rămâne în coadă este o variabilă aleatorie cu o valoare medie, astfel, fiecare cerere din coadă este supus unui fel de „flux de îngrijire” Poisson cu intensitate:

fara coada:

Toate canalele sunt gratuite;

Un canal este ocupat;

Două canale sunt ocupate;

Toate canalele n sunt ocupate;

exista o coada:

Toate canalele n sunt ocupate, o cerere este în coadă;

Toate canalele n sunt ocupate, cererile r sunt în coadă etc.

Graficul stărilor și tranzițiilor sistemului este prezentat în Fig. 23.

Orez. 23. QS cu timp de așteptare limitat

Să marchem acest grafic ca înainte; toate săgețile care conduc de la stânga la dreapta vor indica intensitatea fluxului de aplicații. Pentru statele fără coadă, săgețile care duc de la ele de la dreapta la stânga vor indica, ca și înainte, intensitatea totală a fluxului care deservește toate canalele ocupate. În ceea ce privește stările cu coadă, săgețile care duc de la ele de la dreapta la stânga vor avea intensitatea totală a fluxului de serviciu al tuturor canalelor n plus intensitatea corespunzătoare a fluxului de plecări din coadă. Dacă în coadă există aplicații r, atunci intensitatea totală a fluxului de plecări va fi egală cu .

După cum se poate observa din grafic, există un model de reproducere și moarte; folosind expresii generale pentru probabilitățile limită ale stărilor din această schemă (folosind notații abreviate, scriem:

(24)

Să notăm câteva caracteristici ale unui QS cu așteptare limitată în comparație cu QS-ul considerat anterior cu cereri „pacient”.

Dacă lungimea cozii nu este limitată și cererile sunt „răbdătoare” (nu părăsiți coada), atunci regimul limită staționar există doar în cazul (la progresia geometrică infinită corespunzătoare diverge, ceea ce corespunde fizic creșterii nelimitate al cozii de la ).

Dimpotrivă, într-un QS cu cereri „nerăbdătoare” care părăsesc coada mai devreme sau mai târziu, se realizează întotdeauna modul de service stabilit la, indiferent de intensitatea redusă a fluxului de cereri. Aceasta rezultă din faptul că seria pentru în numitorul formulei (24) converge pentru orice valori pozitive ale și .

Pentru un QS cu cereri „nerăbdătoare”, conceptul de „probabilitate de eșec” nu are sens - fiecare solicitare este în linie, dar poate să nu aștepte serviciul, plecând din timp.

Debit relativ, numărul mediu de cereri din coadă. Capacitatea relativă q a unui astfel de QS poate fi calculată după cum urmează. Evident, toate aplicațiile vor fi deservite, cu excepția celor care părăsesc coada înainte de program. Să calculăm numărul mediu de aplicații care părăsesc coada mai devreme. Pentru a face acest lucru, calculăm numărul mediu de aplicații din coadă:

Fiecare dintre aceste aplicații este supusă unui „flux de plecări” cu o intensitate de . Aceasta înseamnă că din numărul mediu de -aplicații din coadă, în medie, -aplicațiile vor pleca fără a aștepta serviciul, -aplicațiile pe unitatea de timp și în total pe unitatea de timp, în medie -aplicațiile vor fi servite. Capacitatea relativă a QS va fi:

Obținem în continuare numărul mediu de canale ocupate împărțind lățimea de bandă absolută A la:

(26)

Numărul mediu de aplicații în coadă. Relația (26) vă permite să calculați numărul mediu de aplicații din coadă fără să însumați seria infinită (25). Din (26) obținem:

iar numărul mediu de canale ocupate incluse în această formulă poate fi găsit ca așteptarea matematică a unei variabile aleatoare Z, luând valori 0, 1, 2,..., n cu probabilități ,:

În concluzie, observăm că dacă în formulele (24) mergem la limita la (sau, ceea ce este același, la ), atunci se vor obține formulele (22), adică aplicațiile „nerăbdătoare” vor deveni „răbdătoare”.

Lasă n- numărul de canale de servicii, s- numărul de aplicații potențiale, n <s , - intensitatea fluxului de aplicații pentru fiecare cerință potențială, μ - intensitatea serviciului:

Probabilitatea de oprire a sistemului este determinată de formulă

R 0 = .

Probabilitățile finale ale stărilor sistemului:

Pk= la k = la .

Numărul mediu de canale ocupate este exprimat prin aceste probabilități

=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) sau

=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).

Folosind aceasta găsim debitul absolut al sistemului:

precum și numărul mediu de aplicații din sistem

M=s- =s- .

Exemplul 1. Intrarea unui QS cu trei canale cu defecțiuni primește un flux de solicitări cu o intensitate =4 solicitări pe minut, timp pentru deservirea unei cereri de către un canal t obs =1/μ =0,5 min. Din punct de vedere al capacității QS, este profitabil să forțați toate cele trei canale să depună cereri de serviciu simultan, iar timpul mediu de service este redus de trei ori? Cum va afecta acest lucru timpul mediu petrecut de o aplicație în CMO?

Soluţie. Găsim probabilitatea de oprire a unui QS cu trei canale folosind formula

ρ = /μ =4/2=2, n=3,

P 0 = = = 0,158.

Probabilitatea de eșec este determinată de formula:

P deschis = P n ==

P deschis = 0,21.

Debit relativ al sistemului:

R obsl = 1-R deschis 1-0,21=0,79.

Debitul absolut al sistemului:

A= P obsl 3,16.

Numărul mediu de canale ocupate este determinat de formula:

1.58, cota de canale ocupate de service,

q = 0,53.

Timpul mediu pe care o aplicație rămâne în QS se găsește ca probabilitatea ca cererea să fie acceptată pentru serviciu, înmulțită cu timpul mediu de serviciu: t SMO 0,395 min.

Combinând toate cele trei canale într-unul singur, obținem un sistem cu un singur canal cu parametri μ= 6, ρ= 2/3. Pentru un sistem cu un singur canal, probabilitatea de oprire este:

R 0 = = =0,6,

probabilitatea de eșec:

P deschis =ρ P 0 = = 0,4,

debit relativ:

R obsl = 1-R deschis =0,6,

debit absolut:

A=P obs =2,4.

t SMO =P obsl= =0,1 min.

Ca urmare a combinării canalelor într-unul singur, debitul sistemului a scăzut pe măsură ce a crescut probabilitatea de defecțiune. Timpul mediu petrecut de o aplicație în sistem a scăzut.

Exemplul 2. Intrarea unui QS cu trei canale cu o coadă nelimitată primește un flux de solicitări cu o intensitate =4 aplicații pe oră, timp mediu de service pentru o aplicație t=1/μ=0,5 h Găsiți indicatorii de performanță a sistemului.

Pentru sistemul luat în considerare n =3, =4, μ=1/0,5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:

P= .

P 0 = =1/9.

Găsim numărul mediu de aplicații din coadă folosind formula:

L =.

L = = .

Calculăm timpul mediu de așteptare pentru o aplicație în coadă folosind formula:

t= = 0,22 ore.

Timpul mediu de păstrare a unei aplicații în sistem:

T=t+ 0,22+0,5=0,72.

Exemplul 3. În salonul de coafură lucrează 3 coafori, iar în sala de așteptare sunt 3 scaune. Fluxul de clienți este intens =12 clienți pe oră. Timp mediu de service t obsl =20 min. Determinați debitul relativ și absolut al sistemului, numărul mediu de scaune ocupate, lungimea medie a cozii, timpul mediu pe care clientul îl petrece la coafor.

Pentru această sarcină n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. Probabilitatea de oprire este determinată de formula:

R 0 =.

P 0 = 0,012.

Probabilitatea de refuz al serviciului este determinată de formulă

P deschis =P n+m = .

P deschide =P n + m 0,307.

Capacitatea relativă a sistemului, adică probabilitate de serviciu:

P obsl =1-P deschis 1-0,307=0,693.

Debit absolut:

A= P obsl 12 .

Numărul mediu de canale ocupate:

.

Lungimea medie a cozii este determinată de formula:

L =

L= 1,56.

Timp mediu de așteptare pentru serviciul la coadă:

t= h.

Numărul mediu de cereri către CMO:

M=L + .

Timpul mediu pe care o aplicație rămâne în CMO:

T=M/ 0,36 ore

Exemplul 4. Un muncitor operează 4 mașini. Fiecare mașină eșuează cu intensitate =0,5 defecțiuni pe oră, timp mediu de reparație t rem=1/μ=0,8 h. Determinați debitul sistemului.

Această problemă consideră un QS închis, μ =1,25, ρ=0,5/1,25=0,4. Probabilitatea de oprire a lucrătorului este determinată de formula:

R 0 =.

P 0 = .

Probabilitatea angajării lucrătorilor R zan = 1-P 0 . A=( 1-P 0 )μ =0,85μ mașini pe oră.

Sarcină:

Doi muncitori operează un grup de patru mașini. Opririle unei mașini de lucru au loc în medie după 30 de minute. Timpul mediu de configurare este de 15 minute. Timpul de funcționare și de configurare este distribuit conform unei legi exponențiale.

Găsiți ponderea medie a timpului liber pentru fiecare lucrător și timpul mediu de funcționare al mașinii.

Găsiți aceleași caracteristici pentru un sistem în care:

a) fiecărui muncitor i se atribuie două utilaje;

b) doi muncitori întrețin întotdeauna mașina împreună, și cu intensitate dublă;

c) singura mașină defectă este întreținută de ambii muncitori simultan (cu intensitate dublă), iar când mai apare cel puțin o altă mașină defectă, aceștia încep să funcționeze separat, fiecare deservind câte o mașină (descrieți mai întâi sistemul din punct de vedere al proceselor de moartea şi naşterea).

Soluţie:

Următoarele stări ale sistemului S sunt posibile:

S 0 – toate mașinile sunt operaționale;

S 1 – 1 utilaj este in reparatie, restul sunt in stare buna de functionare;

S 2 – 2 utilaj este în reparație, restul sunt în stare de funcționare;

Mașina S 3 – 3 este în curs de reparație, restul sunt în stare de funcționare;

Mașina S 4 – 4 este în curs de reparație, restul sunt în stare bună de funcționare;

S 5 – (1, 2) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;

S 6 – (1, 3) utilajele sunt în curs de reparare, restul sunt în stare de funcționare;

S 7 – (1, 4) utilajele sunt în reparație, restul sunt în stare de funcționare;

S 8 – (2, 3) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;

S 9 – (2, 4) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;

S 10 – (3, 4) utilajele sunt în curs de reparare, restul sunt în stare bună de funcționare;

S 11 – (1, 2, 3) utilaje sunt în curs de reparare, 4 utilaj este în funcțiune;

S 12 – (1, 2, 4) utilaje sunt în curs de reparare, 3 utilaj este în funcțiune;

S 13 – (1, 3, 4) utilajele sunt în curs de reparare, utilajul 2 este în funcțiune;

S 14 – (2, 3, 4) utilaje sunt în curs de reparare, 1 utilaj este în funcțiune;

S 15 – toate utilajele sunt reparate.

Graficul stării sistemului...

Acest sistem S este un exemplu de sistem închis, deoarece fiecare mașină este o cerință potențială, transformându-se într-una reală în momentul defecțiunii sale. În timp ce mașina funcționează, se află în blocul de întârziere, iar din momentul defecțiunii până la sfârșitul reparației, se află în sistemul propriu-zis. Fiecare lucrător este un canal de servicii.

Dacă un muncitor este ocupat, el instalează μ-mașini pe unitate de timp, capacitatea sistemului:

Răspuns:

Ponderea medie a timpului liber pentru fiecare lucrător este ≈ 0,09.

Timp mediu de funcționare a mașinii ≈ 3,64.

a) Fiecărui lucrător i se atribuie două utilaje.

Probabilitatea de oprire a lucrătorului este determinată de formula:

Probabilitatea angajării lucrătorului:

Dacă un muncitor este ocupat, el instalează μ-mașini pe unitate de timp, capacitatea sistemului:

Răspuns:

Ponderea medie a timpului liber pentru fiecare lucrător este ≈ 0,62.

Timp mediu de funcționare a mașinii ≈ 1,52.

b) Doi lucrători întrețin întotdeauna mașina împreună și cu intensitate dublă.

c) Singura mașină defectă este întreținută de ambii muncitori deodată (cu intensitate dublă), iar când mai apare cel puțin o altă mașină defectă, aceștia încep să lucreze separat, fiecare deservind câte o mașină (descrieți mai întâi sistemul din punct de vedere al proceselor de moartea şi naşterea).

Comparație a 5 răspunsuri:

Cea mai eficientă modalitate de a organiza lucrătorii la mașini va fi versiunea inițială a sarcinii.

Exemple ale celor mai simple sisteme de așteptare (QS) au fost discutate mai sus. Termenul „protozoare” nu înseamnă „elementar”. Modelele matematice ale acestor sisteme sunt aplicabile și utilizate cu succes în calculele practice.

Posibilitatea aplicării teoriei deciziei în sistemele de așteptare este determinată de următorii factori:

1. Numărul de aplicații din sistem (care este considerat un QS) trebuie să fie destul de mare (masiv).

2. Toate cererile primite la intrarea QS trebuie să fie de același tip.

3. Pentru a calcula folosind formule, trebuie să cunoașteți legile care determină primirea cererilor și intensitatea procesării acestora. Mai mult, fluxurile de ordine trebuie să fie Poisson.

4. Structura QS, i.e. setul de cerințe de intrare și succesiunea procesării cererii trebuie să fie strict fixate.

5. Este necesar să se excludă subiecții din sistem sau să le descrie ca cerințe cu o intensitate constantă de procesare.

La restricțiile enumerate mai sus, mai putem adăuga una, care are un impact puternic asupra dimensiunii și complexității modelului matematic.

6. Numărul de priorități utilizate ar trebui să fie minim. Prioritățile aplicațiilor trebuie să fie constante, adică nu se pot schimba în timpul procesării în cadrul QS.

În cursul lucrării, obiectivul principal a fost atins - a fost studiat materialul principal de „QS cu timp de așteptare limitat” și „Closed QS”, care a fost stabilit de profesorul disciplinei academice. Ne-am familiarizat și cu aplicarea în practică a cunoștințelor dobândite, adică. consolidat materialul acoperit.

1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http://revoluție..

5) Fomin G.P. Metode și modele matematice în activități comerciale. M: Finanțe și Statistică, 2001.

6) Gmurman V.E. Teoria probabilității și statistica matematică. M: Liceu, 2001.

7) Sovetov B.A., Yakovlev S.A. Modelarea sistemelor. M: Liceu, 1985.

8) Lifshits A.L. Modelarea statistică a QS. M., 1978.

9) Ventzel E.S. Cercetare operațională. M: Nauka, 1980.

10) Ventzel E.S., Ovcharov L.A. Teoria probabilității și aplicațiile sale de inginerie. M: Nauka, 1988.

În activitățile comerciale, QS cu așteptare (în coadă) este mai frecventă.

Să considerăm un QS simplu cu un singur canal cu o coadă limitată, în care numărul de locuri din coada m este o valoare fixă. În consecință, o aplicație primită într-un moment în care toate locurile din coadă sunt ocupate nu este acceptată pentru service, nu se înscrie în coadă și părăsește sistemul.

Graficul acestui QS este prezentat în Fig. 3.4 și coincide cu graficul din fig. 2.1 descriind procesul „naștere-moarte”, cu diferența că în prezența unui singur canal.

Graficul etichetat al procesului de serviciu „naștere - moarte” toate intensitățile fluxurilor de servicii sunt egale

Stările QS pot fi reprezentate după cum urmează:

S0 - canalul de servicii este gratuit,

S, - canalul de servicii este ocupat, dar nu există coadă,

S2 - canalul de serviciu este ocupat, există o solicitare în coadă,

S3 - canalul de serviciu este ocupat, există două solicitări în coadă,

Sm+1 - canalul de serviciu este ocupat, toate cele m locuri din coadă sunt ocupate, orice cerere ulterioară este respinsă.

Pentru a descrie procesul QS aleatoriu, puteți utiliza regulile și formulele menționate anterior. Să scriem expresii care determină probabilitățile limită ale stărilor:

Expresia pentru p0 poate fi scrisă într-un mod mai simplu în acest caz, folosind faptul că numitorul conține o progresie geometrică relativ la p, apoi după transformări corespunzătoare obținem:

c= (1-s)

Această formulă este valabilă pentru toate p, altele decât 1, dar dacă p = 1, atunci p0 = 1/(m + 2), iar toate celelalte probabilități sunt, de asemenea, egale cu 1/(m + 2).

Dacă presupunem m = 0, atunci trecem de la considerarea unui QS cu un singur canal cu așteptare la QS deja considerat cu un singur canal cu refuzuri de serviciu.

Într-adevăr, expresia probabilității marginale p0 în cazul m = 0 are forma:

po = m / (l+m)

Și în cazul l = m are valoarea p0 = 1 / 2.

Să determinăm principalele caracteristici ale unui QS cu un singur canal cu așteptare: debit relativ și absolut, probabilitatea de eșec, precum și lungimea medie a cozii și timpul mediu de așteptare pentru o aplicație în coadă.

O aplicație este respinsă dacă ajunge într-un moment în care QS-ul este deja în starea Sm+1 și, prin urmare, toate locurile din coadă sunt ocupate și un canal deservește

Prin urmare, probabilitatea de eșec este determinată de probabilitatea de apariție

Sm+1 afirmă:

Ptk = pm+1 = сm+1 * p0

Debitul relativ, sau ponderea cererilor deservite care sosesc pe unitatea de timp, este determinată de expresie

Q = 1- rotk = 1- cm+1 * p0

debitul absolut este:

Numărul mediu de aplicații L din coada de serviciu este determinat de așteptarea matematică a variabilei aleatoare k - numărul de aplicații din coadă

Variabila aleatorie k ia doar următoarele valori întregi:

1 - există o aplicație în coadă,

2 - există două aplicații în coadă,

t-toate locurile din coada sunt ocupate

Probabilitățile acestor valori sunt determinate de probabilitățile corespunzătoare de stări, începând cu starea S2. Legea distribuției unei variabile aleatoare discrete k este prezentată după cum urmează:

Tabelul 1. Legea distribuției unei variabile aleatoare discrete

Așteptările matematice ale acestei variabile aleatoare sunt:

Loch = 1* p2 +2* p3 +...+ m* pm+1

În cazul general, pentru p ? 1, această sumă poate fi transformată, folosind modele de progresie geometrică, într-o formă mai convenabilă:

Loch = p2 * 1-pm * (l-m*p+1)* p0

În cazul special când p = 1, când toate probabilitățile pk sunt egale, puteți folosi expresia pentru suma termenilor seriei numerice

1+2+3+ m = m(m+1)

Apoi obținem formula

L"och= m(m+1)* p0 = m(m+1)(p=1).

Folosind raționamente și transformări similare, se poate demonstra că timpul mediu de așteptare pentru deservirea unei cereri într-o coadă este determinat de formulele lui Little.

Punctul = Loch/A (la p? 1) și T1och= L"och/A (la p = 1).

Acest rezultat, când se dovedește că Toc ~ 1/l, poate părea ciudat: odată cu creșterea intensității fluxului de aplicații, lungimea cozii pare să crească, iar timpul mediu de așteptare scade. Cu toate acestea, trebuie avut în vedere faptul că, în primul rând, valoarea lui Loch este o funcție de l și m și, în al doilea rând, QS-ul luat în considerare are o lungime limitată a cozii de cel mult m aplicații.

O aplicație primită de QS într-un moment în care toate canalele sunt ocupate este respinsă și, prin urmare, timpul său de „așteptare” în QS este zero. Acest lucru duce în cazul general (pentru p? 1) la o scădere a Tochromost l, deoarece ponderea unor astfel de solicitări crește odată cu creșterea l.

Dacă renunțăm la restricția privind lungimea cozii, i.e. direct m--> >?, apoi cazurile p< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

Când k este suficient de mare, probabilitatea pk tinde spre zero. Prin urmare, debitul relativ va fi Q = 1, iar debitul absolut va fi egal cu A --l Q -- l Prin urmare, toate cererile primite sunt deservite, iar lungimea medie a cozii va fi egală cu:

Loch = p2 1-p

și timpul mediu de așteptare conform formulei lui Little

Punctul = Loch/A

În limita p<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Probabilitățile limită ale stărilor nu pot fi deci determinate: la Q = 1 ele sunt egale cu zero. De fapt, CMO nu își îndeplinește funcțiile, deoarece nu este capabil să deservească toate aplicațiile primite.

Este ușor de determinat că ponderea aplicațiilor deservite și, respectiv, debitul absolut, medii c și m, cu toate acestea, o creștere nelimitată a cozii și, prin urmare, timpul de așteptare în ea, duce la faptul că, după un anumit timp, încep aplicațiile să se acumuleze în coadă pentru o perioadă nedeterminată de timp.

Ca una dintre caracteristicile QS, se utilizează timpul mediu Tsmo al șederii unei aplicații în QS, inclusiv timpul mediu petrecut în coadă și timpul mediu de service. Această valoare este calculată folosind formulele lui Little: dacă lungimea cozii este limitată, numărul mediu de aplicații din coadă este egal cu:

Lsmo= m+1;2

Tsmo= Lsmo; la p?1

Și apoi, timpul mediu pe care o cerere rămâne în sistemul de așteptare (atât în coadă, cât și în serviciu) este egal cu:

Tsmo= m+1 la p ?1 2m

În practică, destul de des există servicii medicale cu un singur canal cu o coadă (un medic care deservește pacienții; un telefon public cu o singură cabină; un computer care îndeplinește comenzile utilizatorilor). În teoria stării de așteptare, QS-ul cu un singur canal cu o coadă ocupă de asemenea un loc special (majoritatea formulelor analitice obținute până acum pentru sistemele non-Markov aparțin unui astfel de QS). Prin urmare, ne vom concentra pe un QS cu un singur canal cu o coadă atenție deosebită.
Să existe un QS cu un singur canal cu o coadă la care nu se impun restricții (nici asupra lungimii cozii, nici asupra timpului de așteptare). Acest QS primește un flux de aplicații cu intensitatea X; fluxul de servicii are o intensitate inversă timpului mediu de deservire a unei cereri. Este necesar să se găsească probabilitățile finale ale stărilor QS, precum și caracteristicile eficacității acesteia:
Numărul mediu de aplicații în sistem,
Timpul mediu pe care o aplicație rămâne în sistem,
Numărul mediu de aplicații în coadă,
Timpul mediu pe care o aplicație îl petrece în coadă,
Probabilitatea ca canalul să fie ocupat (încărcare canal).

În ceea ce privește debitul absolut A și Q relativ, nu este nevoie să le calculați: datorită faptului că coada este nelimitată, fiecare solicitare va fi deservită mai devreme sau mai târziu, deci din același motiv
Soluţie. Ca și înainte, vom numerota stările sistemului în funcție de numărul de aplicații din QS:
Canalul este gratuit
Canalul este ocupat (deservește o solicitare), nu există coadă,
Canalul este ocupat, o solicitare este în coadă,
Canalul este ocupat, aplicațiile sunt în coadă,
Teoretic, numărul de stări este nelimitat (infinit). Graficul de stare are forma prezentată în Fig. 20.2. Aceasta este o schemă de moarte și reproducere, dar cu un număr infinit de stări. De-a lungul tuturor săgeților, un flux de solicitări cu intensitate A mută sistemul de la stânga la dreapta și de la dreapta la stânga - un flux de servicii cu intensitate
În primul rând, să ne întrebăm, există probabilități finale în acest caz? La urma urmei, numărul de stări ale sistemului este infinit și, în principiu, coada poate crește fără limită! Da, așa este: probabilitățile finale pentru un astfel de QS nu există întotdeauna, ci doar atunci când sistemul nu este supraîncărcat. Se poate dovedi că dacă este strict mai mică de unu, atunci probabilitățile finale există, iar atunci când coada la crește fără limită. Acest fapt pare mai ales „de neînțeles” atunci când s-ar părea că nu sunt impuse cerințe imposibile sistemului: în timpul deservirii unei aplicații, ajunge în medie o aplicație și totul ar trebui să fie în ordine, dar în realitate nu este așa.

Cu QS, face față fluxului de solicitări doar dacă acest flux este regulat, iar timpul de serviciu nu este, de asemenea, aleatoriu, egal cu intervalul dintre solicitări. În acest caz „ideal”, nu va exista deloc coadă, canalul va fi continuu ocupat și va emite în mod regulat solicitări deservite. Dar de îndată ce fluxul de aplicații sau fluxul de servicii devine chiar puțin aleatoriu, coada va crește la infinit. În practică, acest lucru nu se întâmplă doar pentru că „un număr infinit de aplicații în coadă” este o abstractizare. Acestea sunt erorile grosolane care pot rezulta din înlocuirea variabilelor aleatoare cu așteptările lor matematice!
Dar să revenim la QS-ul nostru cu un singur canal cu o coadă nelimitată. Strict vorbind, am derivat formule pentru probabilitățile finale în schema morții și reproducerii numai pentru cazul unui număr finit de stări, dar să ne luăm libertatea de a le folosi pentru un număr infinit de stări. Să calculăm probabilitățile finale ale stărilor folosind formulele (19.8), (19.7). În cazul nostru, numărul de termeni din formula (19.8) va fi infinit. Obținem o expresie pentru
Seria din formula (20.11) este o progresie geometrică. Știm că seria converge - este o progresie geometrică infinit descrescătoare cu un numitor . La , seria diverge (care este o dovadă indirectă, deși nu strictă, că probabilitățile finale ale stărilor există doar la ). Acum să presupunem că această condiție este îndeplinită și însumând progresia în (20.11), avem
(20.12)
Probabilitățile se găsesc folosind formulele:

de unde, ținând cont de (20.12), găsim în final:
După cum puteți vedea, probabilitățile formează o progresie geometrică cu numitorul . Destul de ciudat, maximul dintre ele este probabilitatea ca canalul să fie liber. Indiferent cât de încărcat este sistemul cu o coadă, dacă poate face față fluxului de aplicații, cel mai probabil numărul de aplicații din sistem va fi 0.
Să găsim numărul mediu de aplicații către CMO. Aici va trebui să mânuiești puțin. Variabila aleatoare Z - numărul de aplicații din sistem - are valori posibile cu probabilități
Așteptările sale matematice sunt
(20.14)
(suma nu se ia de la 0 la, ci de la 1 la, deoarece termenul zero este egal cu zero).
Să substituim în formula (20.14) expresia pentru
Acum să scoatem semnul sumei:
Aici vom aplica din nou un „mic truc”: nu există nimic mai mult decât derivatul porului din expresia înseamnă,
Inversand operatiile de diferentiere si insumare obtinem:

Dar suma din formula (20.15) nu este altceva decât suma unei progresii geometrice infinit descrescătoare cu primul termen și numitorul; această sumă este egală cu și derivata ei. Înlocuind această expresie în (20.15), obținem:
(20.16)
Ei bine, acum să aplicăm formula lui Little (19.12) și să găsim timpul mediu în care o aplicație rămâne în sistem:
Să găsim numărul mediu de aplicații din coadă Vom raționa astfel: numărul de aplicații din coadă este egal cu numărul de aplicații din sistem minus numărul de aplicații aflate în serviciu. Aceasta înseamnă (conform regulii de adăugare a așteptărilor matematice), numărul mediu de aplicații din coadă este egal cu numărul mediu de aplicații din sistem minus numărul mediu de aplicații aflate în serviciu. Numărul de solicitări în serviciu poate fi fie zero (dacă canalul este liber), fie unul (dacă este ocupat). Așteptarea matematică a unei astfel de variabile aleatoare este egală cu probabilitatea ca canalul să fie ocupat (l-am notat ). Evident, este egal cu unu minus probabilitatea ca canalul să fie liber;
Prin urmare, numărul mediu de cereri aflate în deservire este

În practică, destul de des există servicii medicale cu un singur canal cu o coadă (un medic care deservește pacienții; un telefon public cu o singură cabină; un computer care îndeplinește comenzile utilizatorilor). În teoria stării de așteptare, QS-ul cu un singur canal cu o coadă ocupă de asemenea un loc special (majoritatea formulelor analitice obținute până acum pentru sistemele non-Markov aparțin unui astfel de QS). Prin urmare, vom acorda o atenție deosebită QS-ului cu un singur canal cu o coadă.

Să existe un QS cu un singur canal cu o coadă la care nu se impun restricții (nici asupra lungimii cozii, nici asupra timpului de așteptare). Acest QS primește un flux de cereri cu intensitatea λ; fluxul de servicii are o intensitate μ, care este inversa timpului mediu de deservire a cererii tob. Este necesar să se găsească probabilitățile finale ale stărilor QS, precum și caracteristicile eficacității sale:

Lsyst - numărul mediu de aplicații din sistem,

Wsyst este timpul mediu pe care o cerere rămâne în sistem,

Loch - numărul mediu de aplicații în coadă,

Woch - timpul mediu în care o aplicație rămâne în coadă,

Rzan este probabilitatea ca canalul să fie ocupat (gradul de încărcare a canalului).

În ceea ce privește debitul absolut A și Q relativ, nu este nevoie să le calculați: datorită faptului că coada este nelimitată, fiecare cerere va fi deservită mai devreme sau mai târziu, deci A = λ, din același motiv Q = 1.

Soluţie. Ca și înainte, vom numerota stările sistemului în funcție de numărul de aplicații din QS:

S0 - canalul este gratuit,

S1 - canalul este ocupat (deservește o solicitare), nu există coadă,

S2 - canalul este ocupat, o cerere este în coadă,

Sk - canalul este ocupat, k - 1 aplicații sunt în coadă.

Teoretic, numărul de stări este nelimitat (infinit). Graficul de stare are forma prezentată în Fig. 4.11. Aceasta este o schemă de moarte și reproducere, dar cu un număr infinit de stări. De-a lungul tuturor săgeților, fluxul de cereri cu intensitatea λ mișcă sistemul de la stânga la dreapta și de la dreapta la stânga - fluxul de servicii cu intensitatea μ.

Orez. 4.11. Graficul de stări al unui QS sub forma unei scheme de moarte și reproducere cu un număr infinit de stări

În primul rând, să ne întrebăm, există probabilități finale în acest caz? La urma urmei, numărul de stări ale sistemului este infinit și, în principiu, pe măsură ce t→∞ coada poate crește la infinit! Da, așa este: probabilitățile finale pentru un astfel de QS nu există întotdeauna, ci doar atunci când sistemul nu este supraîncărcat. Se poate dovedi că dacă p este strict mai mic decât unu (p<1), то финальные вероятности существуют, а при р ≥ 1 очередь при t →∞ растет неограниченно. Особенно «непонятным» кажется этот факт при р = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При р = 1 СМО справляется с потоком заявок, только если поток этот - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом «идеальном» случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживаний стать хотя бы немного случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что «бесконечное число заявок в очереди» - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!

Dar să revenim la QS-ul nostru cu un singur canal cu o coadă nelimitată. Strict vorbind, am derivat formule pentru probabilitățile finale în schema morții și reproducerii numai pentru cazul unui număr finit de stări, dar le vom folosi pentru un număr infinit de stări. Să calculăm probabilitățile finale ale stărilor folosind formulele (4.21), (4.20). În cazul nostru, numărul de termeni din formula (4.21) va fi infinit. Obținem o expresie pentru p0:
unde
Probabilitățile p1, p2, ..., pk, ... se găsesc după formulele:

de unde, ținând cont de (4.38), găsim în final:

p 1 = ρ(1 - ρ), = ρ2(1- ρ), . . ., pk= ρ4(1- ρ), . . . (4,39)

După cum puteți vedea, probabilitățile p0, p1, ..., pk, ... formează o progresie geometrică cu numitorul p. Destul de ciudat, maximul dintre ele p0 este probabilitatea ca canalul să fie complet liber. Indiferent cât de încărcat este un sistem cu o coadă, dacă poate face față fluxului de aplicații (p<1), самое вероятное число заявок в системе будет 0.

Să găsim numărul mediu de aplicații în sistemul QS L. Variabila aleatoare Z - numărul de aplicații din sistem - are valori posibile 0, 1, 2, ..., k, ... cu probabilități p0, p1, p2, ..., pk, ... Așteptările sale matematice sunt

(suma nu se ia de la 0 la ∞, ci de la 1 la ∞, deoarece termenul zero este egal cu zero).

Să înlocuim expresia pentru рk (4.39) în formula (4.40):

Acum să luăm p (1 - p) din semnul sumei:

Aici aplicăm din nou un „mic truc”: kpk-1 nu este altceva decât derivata față de p din expresia pk; Mijloace,

Inversand operatiile de diferentiere si insumare obtinem:

Ei bine, acum aplicăm formula lui Little (4.25) și găsim timpul mediu în care o solicitare rămâne în sistem:

Să găsim numărul mediu de aplicații din coada Loch. Vom raționa astfel: numărul de aplicații din coadă este egal cu numărul de aplicații din sistem minus numărul de aplicații aflate în service. Aceasta înseamnă (conform regulii de adăugare a așteptărilor matematice), numărul mediu de aplicații din coada Loch este egal cu numărul mediu de aplicații din sistemul Lsyst minus numărul mediu de aplicații aflate în serviciu. Numărul de solicitări în serviciu poate fi fie zero (dacă canalul este liber), fie unul (dacă este ocupat). Așteptarea matematică a unei astfel de variabile aleatoare este egală cu probabilitatea ca canalul să fie ocupat (l-am notat Rzan). Evident, Pzan este egal cu unu minus probabilitatea p0 ca canalul să fie liber:

si in sfarsit

Astfel, au fost găsite toate caracteristicile eficacității QS.

Să invităm cititorul să rezolve singur un exemplu: un QS cu un singur canal este o stație de triaj feroviar, care primește cel mai simplu flux de trenuri cu o intensitate de λ = 2 (trenuri pe oră). Întreținerea (desființarea) trenului durează un timp (indicativ) aleatoriu cu o valoare medie de tob = 20 (min.). Parcul de sosire al stației are două șine pe care trenurile care sosesc pot aștepta serviciul; dacă ambele linii sunt ocupate, trenurile sunt forțate să aștepte pe șinele exterioare. Este necesar să se găsească (pentru modul de limitare, staționar de funcționare al stației): numărul mediu de trenuri Lsistemul asociat cu stația, timpul mediu Wsistem în care trenul rămâne în gară (pe șine interne, pe șine externe și sub serviciu), numărul mediu de trenuri Lof care așteaptă la coadă pentru desființare (nu contează ce linii), timpul mediu în care trenul rămâne în linie. În plus, încercați să găsiți numărul mediu de trenuri care așteaptă să fie desființate pe liniile externe Lext și timpul mediu al acestei așteptări Wext (ultimele două valori sunt legate prin formula lui Little). În cele din urmă, găsiți amenda zilnică totală Sh pe care gara va trebui să o plătească pentru timpul de oprire a trenului pe șinele externe, dacă stația plătește o amendă de (ruble) pentru o oră de oprire a unui tren. Pentru orice eventualitate, raportăm răspunsurile: Lcist = 2 (tren), Wsyst = i (oră), Loch = 4/3 (tren), Woch = 2/3 (ore), Lext = 16/27 (tren), Wext = 8 /27 ≈ 0,297 (ore). Amenda medie zilnică Ш pentru așteptarea trenurilor pe șine externe se obține prin înmulțirea numărului mediu de trenuri care sosesc în gară pe zi, a timpului mediu de așteptare a trenurilor pe șinele externe și a amenda orară а: Ш ≈ 14,2а.