Acasă
Să luăm în considerare un sistem de așteptare cu un singur canal cu așteptare.
Vom presupune că fluxul de intrare de cereri de serviciu este cel mai simplu flux cu intensitatea λ.
Intensitatea debitului de serviciu este μ. Durata serviciului este o variabilă aleatorie supusă legii distribuției exponențiale. Fluxul de servicii este cel mai simplu flux de evenimente Poisson. O solicitare primită când canalul este ocupat este pusă în coadă și așteaptă serviciul. Vom presupune că dimensiunea cozii este limitată și nu poate găzdui mai mult de m aplicații, adică o aplicație care s-a regăsit în momentul sosirii la CMO m +1 cereri (m
așteaptă la coadă și unul fiind deservit) părăsește CMO.
(0‑1)
Sistemul de ecuații care descrie procesul din acest sistem are o soluție:
Numitorul primei expresii este o progresie geometrică cu primul termen 1 și numitorul ρ, de unde obținem La ρ
(0‑8)
= 1 se poate recurge la calcul direct
Numărul mediu de aplicații din sistem.
(0‑9)
Din moment ce numărul mediu de aplicații din sistemunde este numărul mediu de aplicații aflate în service, știind că rămâne de găsit. Deoarece există un singur canal, atunci numărul de cereri deservite poate fi fie 0, fie 1 cu probabilitățile P 0 și P 1 = 1- P 0
(0‑10)
în consecință, de unde
(0‑11)
iar numărul mediu de aplicaţii din sistem este.
Timp mediu de așteptare pentru o aplicație în coadă
adică, timpul mediu de așteptare pentru o aplicație în coadă este egal cu numărul mediu de aplicații din coadă împărțit la intensitatea fluxului de aplicații.
Timpul în care o aplicație rămâne în sistem este suma timpului de așteptare al aplicației în coadă și timpul de service. Dacă sarcina sistemului este 100%, atunci =1/μ, în caz contrar = q/μ. De aici
(0‑13)
Conținutul lucrării.
Pregătirea instrumentelor experimentale .
Se efectuează în mod similar în conformitate cu regulile generale.
Calcul folosind un model analitic.
1. Pregătiți următorul tabel în Microsoft Excel.
2. În coloanele pentru parametrii QS ai tabelului, notați datele inițiale care sunt determinate conform regulii:
m=1,2,3
(lungimea maximă a cozii).
Pentru fiecare valoare O solicitare primită când canalul este ocupat este pusă în coadă și așteaptă serviciul. Vom presupune că dimensiunea cozii este limitată și nu poate găzdui mai mult de este necesar să se găsească valori teoretice și experimentale ale indicatorilor QS pentru următoarele perechi de valori:
= <порядковый номер в списке группы>
3. Introduceți formulele corespunzătoare în coloanele cu indicatorii modelului analitic.
Experimentați pe un model de simulare.
1. Setați modul de lansare cu timp de serviciu distribuit exponențial, setând valoarea parametrului corespunzător la 1.
2. Pentru fiecare combinație O solicitare primită când canalul este ocupat este pusă în coadă și așteaptă serviciul. Vom presupune că dimensiunea cozii este limitată și nu poate găzdui mai mult de și rulați modelul.
3. Introduceți rezultatele curselor în tabel.
4. Introduceți formule pentru a calcula valoarea medie a indicatorului în coloanele corespunzătoare din tabel P deschis, q și A.
Analiza rezultatelor .
1. Analizați rezultatele obținute prin metode teoretice și experimentale, comparând rezultatele între ele.
2. Pentru m=3, reprezentați grafic dependențele pe o diagramă P deschis din datele obţinute teoretic şi experimental.
Optimizarea parametrilor QS .
Rezolvați problema optimizării mărimii numărului de locuri dintr-o coadă O solicitare primită când canalul este ocupat este pusă în coadă și așteaptă serviciul. Vom presupune că dimensiunea cozii este limitată și nu poate găzdui mai mult de pentru un aparat cu un timp mediu de serviciu = din punctul de vedere al obtinerii profitului maxim. Ca condiții ale problemei, luați:
- venit din deservirea unei aplicații egal cu 80 USD/oră,
- costul de întreținere a unui dispozitiv este egal cu 1cu/oră.
1. Pentru calcule, este recomandabil să creați un tabel:
Prima coloană este completată cu valorile numerelor din seria naturală (1,2,3...).
Toate celulele din a doua și a treia coloană sunt umplute cu și valori.
Formulele pentru coloanele tabelului din secțiunea 0 sunt transferate în celulele coloanelor de la a patra la a noua.
În coloanele cu datele inițiale ale secțiunilor Venituri, Cheltuieli, Profit, introduceți valorile (vezi mai sus).
În coloanele cu valori calculate ale secțiunilor Venituri, Cheltuieli, Profit, notați formulele de calcul:
- numărul de aplicații pe unitatea de timp
N r =A
- venitul total pe unitatea de timp
I S = I r *N r
- consumul total pe unitatea de timp
E S =E s + E q *(n-1)
- profit pe unitatea de timp
P = I S - E S
Unde
Ir - venituri dintr-o singură cerere,
E s - costul de operare al unui dispozitiv,
Ec - costul operarii unui loc la coada.
Grafice pentru P deschis,
- tabel cu date pentru a găsi cele mai bune m și valoarea lui m opt,
- graficul profitului pe unitatea de timp versus m.
Întrebări de securitate :
1) Oferiți o scurtă descriere a modelului QS cu un singur canal cu o coadă limitată.
2) Ce indicatori caracterizează funcționarea unui QS cu un singur canal cu defecțiuni?
3) Cum se calculează probabilitatea p 0 ?
4) Cum se calculează probabilitățile p eu?
5) Cum să găsiți probabilitatea eșecului în deservirea unei aplicații?
6) Cum să găsiți lățimea de bandă relativă?
7) Care este debitul absolut?
8) Cum se calculează numărul mediu de aplicații din sistem?
9) Dați exemple de QS cu o coadă limitată.
Sarcini.
1) Portul are o dană de marfă pentru descărcarea navelor. Debitul este de 0,5 vizite pe zi. Timpul mediu de descărcare pentru o navă este de 2 zile. Dacă sunt 3 nave în coada pentru descărcare, atunci nava care sosește este trimisă într-o altă dană pentru descărcare. Găsiți indicatori de performanță a danei.
2) Biroul de informații al stației de cale ferată primește solicitări telefonice la o intensitate de 80 de solicitări pe oră. Operatorul biroului de asistență răspunde la un apel primit în medie de 0,7 minute. Dacă operatorul este ocupat, clientul primește mesajul „Așteptați răspuns” cererea este plasată într-o coadă, a cărei lungime nu depășește 4 solicitări. Oferiți o evaluare a activității biroului de asistență și o opțiune pentru reorganizarea acestuia
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 o colecție 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 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 (secțiunea mașini). 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 avans, 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ă aleatoare 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.
Să fie sistemul î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 stării a-lea este probabilitatea ca în momentul de timp, sistemul să fie în stare. 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 lupta 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 lucrării 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 cereri nu depind de starea QS-ului în sine (cate canale sunt ocupate). Într-un QS închis– depinde. 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 aplicație 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 cereri 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), în timp ce de la dreapta la stânga există un flux 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 scădea 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 ca aplicația să fie luată în considerare, iar timpul mediu de așteptare să fie 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 pe care o aplicație rămâne î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ă, prin urmare 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 eficienței 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 dintr-o coadă poate fi calculat direct ca așteptarea matematică a unei variabile aleatoare discrete:
(20)
Din nou (expresia din paranteză) 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 de rezidență al unei cereri în sistem, precum și al unui 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 pentru o 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:
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. 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”.
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.
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
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)Pn- 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 eșec. 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, O solicitare primită când canalul este ocupat este pusă în coadă și așteaptă serviciul. Vom presupune că dimensiunea cozii este limitată și nu poate găzdui mai mult de =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 =Pn + 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 apar î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 reparație, restul sunt în stare 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.
Operațiunile sau eficiența sistemului de așteptare sunt următoarele.Pentru QS cu eșecuri:
Pentru SMO cu așteptare nelimitată atât debitul absolut cât și cel relativ își pierd sensul, deoarece fiecare solicitare primită va fi deservită mai devreme sau mai târziu. Pentru un astfel de QS, indicatorii importanți sunt:
Pentru Tip mixt QS se folosesc ambele grupe de indicatori: atât relativ cât şi debit absolut, și caracteristicile așteptărilor.
În funcție de scopul operațiunii de coadă, oricare dintre indicatorii dați (sau un set de indicatori) poate fi selectat ca criteriu de eficiență.
Model analitic Un QS este un set de ecuații sau formule care permit determinarea probabilităților stărilor sistemului în timpul funcționării acestuia și calcularea indicatorilor de performanță pe baza caracteristicilor cunoscute ale fluxului de intrare și canalelor de servicii.
Nu există un model analitic general pentru un QS arbitrar. Modelele analitice au fost dezvoltate pentru un număr limitat de cazuri speciale de QS. Modelele analitice care reflectă mai mult sau mai puțin precis sistemele reale sunt de obicei complexe și greu de vizualizat.
Modelarea analitică a unui QS este mult facilitată dacă procesele care au loc în QS sunt markoviane (fluxurile de cereri sunt simple, timpii de service 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, după rezolvarea acestora, se pot determina indicatorii de eficiență selectați.
Să ne uităm la exemple de QS.
2.5.1. QS multicanal cu defecțiuni
Exemplul 2.5. Trei inspectori de trafic verifică borderourile șoferilor de camion. Dacă cel puțin un inspector este liber, camionul care trece este oprit. Dacă toți inspectorii sunt ocupați, camionul trece fără să se oprească. Fluxul camioanelor este simplu, timpul de verificare este aleatoriu cu o distribuție exponențială.
Această situație poate fi modelată printr-un QS cu trei canale cu eșecuri (fără coadă). Sistemul este în buclă deschisă, cu solicitări omogene, monofazat, cu canale absolut fiabile.
Descrierea statelor:
Toți inspectorii sunt liberi;
Un inspector este ocupat;
Doi inspectori sunt ocupați;
Trei inspectori sunt ocupați.
Graficul stării sistemului este prezentat în Fig. 2.11.
Orez. 2.11.
Pe grafic: - intensitatea debitului camionului; - intensitatea verificărilor documentelor de către un singur inspector de trafic.
Se efectuează simularea pentru a determina porțiunea de vehicule care nu va fi testată.
Soluţie
Partea necesară a probabilității este probabilitatea de angajare a tuturor celor trei inspectori. Deoarece graficul de stare reprezintă o schemă tipică de „moarte și reproducere”, vom găsi folosirea dependențelor (2.2).
Capacitatea de transfer a acestui post de inspector de trafic poate fi caracterizată debit relativ:
Exemplul 2.6. Pentru a primi și procesa rapoarte de la grupul de recunoaștere, un grup de trei ofițeri a fost numit în departamentul de informații al asociației. Intensitatea estimată a fluxului de rapoarte este de 15 rapoarte pe oră. Timpul mediu pentru procesarea unui raport de către un ofițer este de . Fiecare ofițer poate primi rapoarte de la orice grup de recunoaștere. Ofițerul eliberat procesează ultimul dintre rapoartele primite. Rapoartele primite trebuie procesate cu o probabilitate de cel puțin 95%.
Stabiliți dacă echipa de trei ofițeri desemnată este suficientă pentru a îndeplini sarcina atribuită.
Soluţie
Un grup de ofițeri funcționează ca un CMO cu eșecuri, format din trei canale.
Flux de rapoarte cu intensitate 
poate fi considerat cel mai simplu, deoarece este totalul mai multor grupuri de recunoaștere. Intensitatea serviciului 
. Legea distribuției este necunoscută, dar acest lucru este neimportant, deoarece s-a demonstrat că pentru sistemele cu defecțiuni poate fi arbitrară.
Descrierea stărilor și graficul stărilor QS vor fi similare cu cele date în exemplul 2.5.
Deoarece graficul de stare este o schemă de „moarte și reproducere”, există expresii gata făcute pentru probabilitățile limită ale stării:
Atitudinea se numește dată fiind intensitatea fluxului de aplicaţii. Semnificația sa fizică este următoarea: valoarea reprezintă numărul mediu de cereri care ajung la QS în timpul mediu de deservire a unei cereri.
În exemplu 
.
În QS-ul luat în considerare, apare o defecțiune atunci când toate cele trei canale sunt ocupate, adică. Apoi:
Deoarece probabilitatea de eșecîn procesarea rapoartelor este mai mare de 34% (), atunci este necesar să se mărească personalul grupului. Să dublăm compoziția grupului, adică CMO va avea acum șase canale și să calculăm:
Astfel, doar un grup de șase ofițeri va putea procesa rapoartele primite cu o probabilitate de 95%.
2.5.2. QS multicanal cu așteptare
Exemplul 2.7. La secțiunea de trecere a râului există 15 instalații de trecere similare. Fluxul de echipamente care sosesc la trecere este în medie de 1 unitate/min, timpul mediu de traversare a unei unități de echipament este de 10 minute (inclusiv întoarcerea vehiculului de trecere).
Evaluați principalele caracteristici ale traversării, inclusiv probabilitatea unei traversări imediate imediat după sosirea unității de echipament.
Soluţie
Debit absolut, adică tot ce se apropie de trecere este practic traversat imediat.
Numărul mediu de instalații de trecere operaționale:
Ratele de utilizare a feribotului și timpii de nefuncționare:
A fost dezvoltat și un program pentru a rezolva exemplul. Se presupune că intervalele de timp pentru care echipamentele ajung la trecere și timpul de trecere sunt distribuite conform unei legi exponențiale.
Ratele de utilizare a traversării după 50 de curse sunt aproape aceleași: 
.
Lungimea maximă a cozii este de 15 unități, timpul mediu petrecut în coadă este de aproximativ 10 minute.
Scopul serviciului QS. Calculatorul online este conceput pentru a calcula următorii indicatori ai QS cu un singur canal:- probabilitatea eșecului canalului, probabilitatea unui canal liber, debitul absolut;
- debit relativ, timpul mediu de serviciu, timpul mediu de oprire a canalului.
Instrucţiuni. Pentru a rezolva astfel de probleme online, selectați modelul QS. Specifica intensitatea fluxului de cerere λŞi intensitatea debitului de serviciu μ. Pentru un QS cu un singur canal cu o lungime limitată la coadă, puteți specifica lungimea cozii m, iar pentru un QS cu un singur canal cu o coadă nelimitată - numărul de aplicații din coadă (pentru a calcula probabilitatea ca aceste aplicații să fie în coadă). vezi soluția exemplu. . Soluția rezultată este salvată într-un fișier Word.
Clasificarea sistemelor de așteptare cu un singur canal
Exemplul nr. 1. Benzinărie auto are unul benzinărie. Se presupune că cel mai simplu flux de vagoane intră în stație cu o intensitate de λ=11 vagoane/oră. Timpul de deservire a cererii este o variabilă aleatorie care respectă o lege exponențială cu parametrul μ=14 vehicule/oră. Determinați numărul mediu de mașini din stație.
Exemplul nr. 2. Există un punct pentru efectuarea inspecției preventive a mașinilor cu un grup de inspecție. Este nevoie de o medie de 0,4 ore pentru a inspecta și identifica defectele fiecărei mașini. În medie, 328 de mașini sunt primite pentru inspecție pe zi. Fluxurile de cereri și servicii sunt cele mai simple. Dacă o mașină care sosește la punctul de inspecție nu găsește niciun canal liber, acesta lasă punctul de inspecție neservit. Determinați probabilitățile limitative ale condițiilor și caracteristicilor de întreținere ale punctului de control preventiv.
Soluţie. Aici α = 328/24 ≈ = 13,67, t = 0,4. Aceste date trebuie introduse în calculator.
În practică, QS-urile cu un singur canal cu o coadă (un medic care servește pacienții, un procesor care execută comenzile mașinii) sunt destul de comune. Prin urmare, este necesar să se ia în considerare QS cu un singur canal cu o coadă mai detaliat.
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 l; fluxul de serviciu are o intensitate m inversă timpului mediu de serviciu la cerere t aproximativ. Este necesar să se găsească probabilitățile finale ale stărilor QS, precum și caracteristicile eficacității sale:
L SIST– numărul mediu de aplicații în sistem;
W SYST– timpul mediu pe care o cerere rămâne în sistem;
L FOARTE– numărul mediu de aplicații în coadă;
W FOARTE– timpul mediu în care o aplicație rămâne în coadă;
P ZAN- 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, prin urmare, din același motiv.
Soluţie. Starea sistemului, ca și înainte, va fi numerotată după numărul de aplicații din QS:
-S 0 – canalul este liber;
-S 1 – canalul este ocupat (servirea unei cereri), nu există coadă;
-S 2 – canalul este ocupat, o cerere este în coadă;
-S k – canalul este ocupat, k-1 aplicațiile sunt la coadă.
Teoretic, numărul de stări este nelimitat (infinit). Formulele pentru probabilitățile finale în schema morții și reproducerii au fost derivate numai pentru cazul unui număr finit de stări, dar vom face presupunerea că le vom folosi pentru un număr infinit de stări. Atunci numărul de termeni din formulă va fi infinit. Obținem o expresie pentru p o:
Seria din formula (17) este o progresie geometrică. Știm că seria converge - este o progresie infinit descrescătoare cu un numitor r. Când seria diverge (care este o dovadă indirectă, deși nu strictă, că probabilitățile finale ale stărilor p o, p 1, …, p k,...există numai când ). Apoi:
Să găsim numărul mediu de aplicații către CMO L SIST. Variabila aleatoare Z - numărul de aplicații din sistem - are valori posibile 0, 1, 2, ..., k, ... cu probabilități p o, p 1, …, p k,... Așteptările sale matematice sunt egale cu:
Folosind formula lui Little (9), găsim timpul mediu pe care o cerere 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 service. Aceasta înseamnă (după regula adunării așteptărilor matematice) numărul mediu de aplicații din coadă L FOARTE egal cu numărul mediu de aplicații din sistem L SIST 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 P ZAN. Este evident că:
Prin urmare, numărul mediu de cereri aflate în deservire este:
Folosind formula lui Little (9), găsim timpul mediu în care o aplicație rămâne în coadă.
Încărcare...
