Rețele de așteptare și aplicația lor. Rețea de cozi. Rețele de coadă stocastice

Rețea de așteptare (SeMO) - o rețea care oferă servicii cererilor primite. Cerințele de service în QS sunt efectuate de dispozitivele de service. QS clasic conține de la unu la un număr infinit de dispozitive. În funcție de disponibilitatea posibilității de așteptare prin cereri primite pentru începerea reparației, QS-ul se împarte în: sisteme cu pierderi, în care se pierd cerințele care nu au găsit un singur dispozitiv gratuit la momentul sosirii; În acest caz, cererile pendinte formează o coadă; sisteme cu o unitate de capacitate finită (în așteptare și restricții), în care lungimea cozii nu poate depăși capacitatea unității; în acest caz, cererea care ajunge la QS debordant (nu există locuri libere de așteptare) se pierde.

Fiecare QS este conceput pentru a repara (îndeplini) un anumit flux de revendicări (sau cerințe) care sosesc la intrarea sistemului, în mare parte nu în mod regulat, ci la ore aleatorii. Cererile de difuzare, în general, nu durează, de asemenea, o constantă, cunoscută dinainte, ci un timp aleatoriu. După repararea cererii, canalul este eliberat și este gata să primească următoarea solicitare. Natura aleatorie a fluxului și timpul de deservire a acestora duc la o sarcină neuniformă de lucru a QS: la anumite intervale de timp, revendicările neservite se pot acumula la intrarea QS (intră în coadă sau lasă QS neservit), în timp ce în alte perioade, cu canale gratuite la intrarea QS, nu vor exista reclamații , ceea ce duce la descărcarea sistemului, adică la canalele inactive.

Astfel, în orice QS, se pot distinge următoarele elemente principale:

) fluxul de aplicații primite;

) coada;

) canale de servicii;

) fluxul de ieșire a revendicărilor deservite.

Fiecare QS, în funcție de parametrii săi: natura fluxului de aplicații, numărul de canale de service și performanța acestora, precum și regulile de organizare a muncii, au o anumită eficiență operațională (lățime de bandă), ceea ce îi permite să facă față mai mult sau mai puțin cu succes fluxului de aplicații.

Subiectul studierii teoriei cozii este QS.

Scopul teoriei în coadă este de a dezvolta recomandări pentru construcția rațională a QS, organizarea rațională a muncii lor și reglarea fluxului de aplicații pentru a asigura o eficiență ridicată a funcționării QS.

Pentru a atinge acest obiectiv, sunt stabilite sarcinile din teoria cozii, constând în stabilirea dependențelor eficienței funcționării QS de organizarea sa (parametrii): natura fluxului de solicitări, numărul de canale și performanța acestora și regulile de operare QS.

Natura aleatorie a fluxului de solicitări și durata serviciului lor generează un proces aleatoriu în QS.

Definiție: Un proces aleatoriu (sau o funcție aleatorie) este o corespondență în care fiecare valoare a argumentului (în acest caz, un moment din intervalul de timp al experimentului) este atribuită o variabilă aleatorie (în acest caz, starea QS). serviciu de masă

În multe domenii ale economiei, finanțelor, producției și vieții de zi cu zi, un rol important îl joacă sisteme de servicii de masă (OCM), adică sisteme în care, pe de o parte, există cereri masive (cerințe) pentru prestarea oricăror servicii, iar pe de altă parte, aceste solicitări sunt satisfăcute.

Ca exemple de OCP în domeniul financiar și economic, se pot cita sisteme care sunt: \u200b\u200bbănci de diferite tipuri, organizații de asigurări, inspecții fiscale, servicii de audit, diverse sisteme de comunicații (inclusiv stații de telefonie), încărcare și descărcare complexe (stații de marfă), benzinării, diverse întreprinderi și organizații de servicii (magazine, unități de catering, birouri de informații, coafoare, case de bilete, oficii de schimb valutar, magazine de reparații, spitale).

Astfel de sisteme precum rețele de calculatoare, sisteme de colectare, stocare și prelucrare a informațiilor, sisteme de transport, zone de producție automatizate, linii de producție pot fi, de asemenea, considerate ca un fel de OCM.

În comerț, multe operațiuni sunt efectuate în procesul de deplasare a masei de mărfuri de la sfera de producție la sfera de consum. Astfel de operațiuni sunt: \u200b\u200bîncărcarea și descărcarea mărfurilor, transportul, ambalarea, ambalarea, depozitarea, afișarea, vânzarea, etc. Activitățile de tranzacționare se caracterizează prin fluxul masiv de mărfuri, bani, servicii pentru clienți în masă etc., precum și efectuarea operațiunilor corespunzătoare, care sunt aleatorii. Toate acestea creează denivelări în activitatea organizațiilor și întreprinderilor comerciale, generează sarcini de descărcare, dezactivare și suprasarcină. Cozile necesită mult timp, de exemplu, de la clienții din magazine, șoferii de mașini la depozitele de mărfuri, așteptând descărcarea sau încărcarea.

În această privință, sarcinile de analiză a activității, de exemplu, a unui departament de vânzări, a unei întreprinderi comerciale sau a unei secțiuni apar pentru a evalua activitățile acestora, pentru a identifica deficiențele, rezervele și pentru a lua în final măsuri pentru creșterea eficienței sale. În plus, apar probleme asociate creării și implementării unor metode mai economice de efectuare a operațiunilor în cadrul unei secții, departament, întreprindere comercială, bază vegetală, gestionarea comerțului, etc. În consecință, în organizarea comerțului, metodele teoriei în coadă fac posibilă determinarea numărul optim de puncte de desfacere ale unui profil dat, numărul de vânzători, frecvența de livrare a mărfurilor și alți parametri.

Un alt exemplu tipic de sisteme de coadă pot fi depozite sau baze ale organizațiilor de aprovizionare și vânzări, iar sarcina teoriei de la coadă se reduce la stabilirea raportului optim între numărul de cerințe de serviciu care intră în bază și numărul dispozitivelor de deservire, la care costurile totale de întreținere și pierderile din timpul dezactivării transportului ar fi minime. Teoria cu coada poate găsi, de asemenea, aplicație pentru calcularea zonei instalațiilor de depozitare, în timp ce zona de depozitare este considerată un dispozitiv de service, iar sosirea vehiculelor pentru descărcare este o cerință.

Principalele caracteristici ale OCM

OCM include următoarele elementele: sursa de solicitări, fluxul de cereri primite, coada, dispozitivul de service (canalul de serviciu), fluxul de solicitări ieșite (cererile difuzate).

Fiecare QS este conceput pentru a repara (îndeplini) un anumit flux de revendicări (revendicări) care sosesc la intrarea sistemului, în principal nu în mod regulat, dar la ore aleatorii. Servirea aplicațiilor nu durează, de asemenea, pentru un timp constant, predeterminat, ci pentru un timp aleatoriu, care depinde de multe motive aleatorii. După repararea cererii, canalul este eliberat și este gata să primească următoarea solicitare.

Natura aleatorie a fluxului de revendicări și timpul de deservire a acestora duce la o încărcare de lucru inegală a QS: la anumite intervale de timp la intrarea QS, se pot acumula revendicări neservite, ceea ce duce la o supraîncărcare a QS; în unele alte intervale de timp, cu canale libere la intrarea CMO, nu există revendicări. va fi, ceea ce duce la descărcarea sistemului, adică la înghețarea canalelor sale. Comenzile care se acumulează la intrarea QS, fie „devin” în coadă, fie din anumite motive, imposibilitatea de a rămâne în continuare la coadă, lasă QS-ul neservit.

Schema QS este prezentată în figura 5.1.

Figura 5.1 - Schema sistemului de cozi

Fiecare QS include în structura sa un anumit număr de dispozitive de service, care sunt numite canale de servicii... Rolul canalelor poate fi jucat de diferite dispozitive, persoane care efectuează anumite operațiuni (casiere, operatori, vânzători), linii de comunicare, mașini etc.

OCM este subiect de studiu teoria cozii.

Scopul teoriei în coadă - elaborarea de recomandări privind construcția rațională a QS, organizarea rațională a activității acestora și reglarea fluxului de aplicații pentru a asigura eficiența ridicată a funcționării QS.

Pentru atingerea acestui obiectiv, sarcinile teoriei în coadă sunt stabilite, constând în stabilirea dependențelor eficienței funcționării QS de organizarea sa (parametrii).

La fel de caracteristicile eficienței funcționării sistemului pot fi selectate trei grupuri principale de indicatori (de obicei medii):

1. Indicatori ai eficienței utilizării OCM:

1.1. Randamentul absolut al QS este numărul mediu de aplicații pe care QS le poate servi pe unitatea de timp.

1.2. Randamentul relativ al QS este raportul dintre numărul mediu de cereri deservite de QS pe unitatea de timp și numărul mediu de cereri primite în același timp.

1.3. Durata medie a perioadei de angajare a unei organizații medicale.

1.4. Rata de utilizare a QS este ponderea medie a timpului în care QS este ocupat în servirea aplicațiilor.

2. Indicatori de calitate a serviciului:

2.1. Timpul mediu de așteptare pentru o solicitare în coadă.

2.2. Timpul mediu petrecut de o aplicație în OCM.

2.3. Probabilitatea de a refuza cererea de serviciu fără a aștepta.

2.4. Probabilitatea ca cererea primită să fie imediat acceptată pentru service.

2.5. Legea distribuției timpului de așteptare pentru o aplicație în coadă.

2.6. Legea distribuției timpului petrecut de o cerere în QS

2.7. Numărul mediu de aplicații din coadă.

2.8. Numărul mediu de cereri în OCM etc.

3. Indicatori de performanță a perechii „SMO - consumator” care funcționează, unde „consumator” este înțeles ca întregul set de aplicații sau o parte din sursa lor (de exemplu, venitul mediu adus de OCM pe unitatea de timp etc.).

Natura aleatorie a fluxului de aplicații și durata serviciului lor se generează în QS proces aleatoriu... Din momentele din timp T i și intervale de timp de primire a cererilor T, durata operațiunilor de întreținere T obsstând la coadă T och, lungimea cozii eu sunt Sunt variabile aleatorii, atunci caracteristicile stării sistemelor de coadă sunt de natură probabilistică. Prin urmare, pentru a rezolva problemele teoriei serviciului de masă, este necesar să studiem acest proces aleatoriu, adică. construiți și analizați modelul său matematic.

Studiul matematic al funcționării QS este foarte simplificat dacă procesul aleatoriu care are loc în el este markov... Pentru ca un proces aleatoriu să fie Markov, este necesar și suficient ca toate fluxurile de evenimente sub influența cărora tranzițiile sistemului de la stat la stat să fie (cele mai simple) poisson.

Curentul cel mai simplu are trei proprietăți principale: obișnuință, staționalitate și absența efectului aferent.

Fluxul obișnuit înseamnă imposibilitatea practică de a primi simultan două sau mai multe cerințe. De exemplu, probabilitatea ca mai multe case de marcat dintr-un magazin self-service să eșueze în același timp este destul de mică.

Staționar se numește un flux pentru care așteptarea matematică a numărului de cerințe care intră în sistem pe unitatea de timp (notăm λ ) nu se schimbă în timp. Astfel, probabilitatea unui anumit număr de revendicări să intre în sistem într-o perioadă de timp dată ? T depinde de valoarea sa și nu depinde de originea sa de axa timpului.

Fără afecțiune înseamnă că numărul de reclamații primite de sistem înainte de moment T, nu stabilește câte solicitări vor intra în sistem în timpul (T +? T)... De exemplu, dacă un registru de numerar se rupe în acest moment și este eliminat de casierie, acest lucru nu afectează posibilitatea unei noi pauze la această casă de marcat în momentul următor și cu atât mai mult cu cât există probabilitatea unei pauze la alte case de marcat.

Pentru fluxul cel mai simplu, frecvența de sosire a revendicărilor în sistem respectă legea lui Poisson, adică probabilitatea sosirii la timp Tneted k cerințele sunt date de formulă

unde λ — debitul, adică, numărul mediu de aplicații care ajung la QS pe unitatea de timp,

unde τ - valoarea medie a intervalului de timp între două aplicații vecine.

Pentru un astfel de flux de revendicări, timpul dintre două revendicări vecine este distribuit exponențial cu densitatea de probabilitate

Timpul de așteptare aleatoriu în coada pentru începutul serviciului poate fi, de asemenea, considerat distribuit exponențial:

unde ν — trafic de coadă, adică, numărul mediu de solicitări care sosesc pentru serviciu pe unitatea de timp,

unde T och este valoarea medie a timpului de așteptare din coadă.

Fluxul de ieșire a cererilor este asociat cu fluxul de servicii din canal, unde durata serviciului T obs este o variabilă aleatorie și respectă în multe cazuri o lege de distribuție exponențială cu densitate

unde μ — debitul serviciului, adică, numărul mediu de cereri difuzate pe unitatea de timp,

O caracteristică importantă a OCM, care combină indicatorii λ și μ , este un intensitatea sarcinii, care arată gradul de acord al fluxurilor de aplicații specificate:

Indicatorii enumerați k, τ, λ, l pts, T pts, ν, T obs, μ, ρ, P k sunt cele mai frecvente pentru OCM.

Aplicarea diferitelor metode matematice la formalizare. Accentul se pune pe un sistem complex - imprevizibil. Purtător incertitudinea este o persoană.

Un exemplu tipic de probleme stocastice (aleatorii, probabilistice) sunt modelele sistemelor de coadă.

OCM-urile sunt omniprezente. Este vorba despre rețele de telefonie, benzinării, servicii pentru consumatori, case de bilete, evenimente comerciale etc.

Din punctul de vedere al modelării procesului de așteptare, apar situațiile în care se formează cozi de cereri (solicitări) pentru serviciu după cum urmează. După intrarea în sistemul de servire, cererea se alătură cozii altor cereri (primite anterior). Canalul de serviciu selectează o solicitare din partea celor din coadă pentru a începe să o servească. După finalizarea procedurii de reparație pentru următoarea solicitare, canalul de service începe să presteze următoarea solicitare, dacă există una în blocul de așteptare. Ciclul de funcționare al QS de acest tip se repetă de multe ori pe întreaga perioadă de funcționare a sistemului de service. Se presupune că tranziția sistemului la deservirea clientului următor după finalizarea serviciului de reparație a clientului anterior are loc instantaneu, la ore aleatorii.

Exemple de QS-uri sunt:

posturi de întreținere a vehiculelor;

posturi de reparații auto;

firmele de audit etc.

Fondatorul teoriei cozilor, în special teoria cozilor, este cunoscutul om de știință danez A.K. Erlang (1878-1929), care a studiat procesele de serviciu la centralele telefonice.

Sistemele în care au loc procesele de servicii se numesc sisteme de coadă (QS).

Pentru a descrie sistemul de cozi, trebuie să specificați:

- fluxul de intrare al aplicațiilor;

- disciplina serviciului;

- timp de serviciu

- numărul de canale de servicii.

Flux de intrare cerințele (aplicațiile) sunt descrise prin identificarea drept probabilistică legea distribuției momentele de primire a cererilor în sistem și numărul de revendicări în fiecare internare.

La atribuire discipline de serviciu (DO) este necesar să se descrie regulile pentru a face coadă și deservirea cererilor în sistem. În acest caz, lungimea cozii poate fi limitată sau nelimitată. În cazul restricțiilor privind lungimea cozii, cererea primită la intrarea QS este respinsă. Cele mai frecvent utilizate DO sunt determinate de următoarele reguli:

primul venit, primul servit;

a venit ultimul - a servit primul; (cutie pentru mingi de tenis, teanc în tehnică)

selectarea aleatorie a aplicațiilor;

selectarea aplicațiilor după criteriul priorității.

Timpul de serviciu cererea către QS este o variabilă aleatorie. Cea mai comună lege de distribuție este legea exponențială.  - viteza de serviciu.  \u003d numărul de solicitări / unitate de servicii. timp.

Canale de servicii, pot fi aranjate în paralel și în serie. Cu un aranjament secvențial de canale, fiecare client este deservit pe toate canalele secvențial. Cu un aranjament paralel de canale, serviciul se efectuează pe toate canalele simultan, pe măsură ce devin gratuite.

Structura generalizată a QS este prezentată în Fig.

Subiect teoria cozii este stabilirea relației dintre factorii care determină funcționalitatea QS și eficacitatea funcționării acestuia.

Probleme de proiectare a QS.

Problemele de determinare a caracteristicilor structurii QS includ problema alegerii numărului de canale de servicii (elemente de bază (Ф) eu )), problema determinării unei metode de conectare a canalelor (un set de elemente de legătură (Hj)), și, de asemenea, sarcina de a determina lățimea de bandă a canalelor.

1). Selectarea structurii... Dacă canalele funcționează în paralel, atunci problema alegerii Str este redusă la determinarea numărului de canale din partea de servire, în funcție de condiția de a asigura operabilitatea QS. (Cu excepția cazului în care coada este în continuă creștere).

Rețineți că, pentru a determina numărul de canale de sistem, în cazul aranjării lor paralele, este necesar să se respecte starea de operabilitate a sistemului... Notăm:  - numărul mediu de cereri sosite pe unitatea de timp, adică intensitatea fluxului de intrare;  este numărul mediu de aplicații satisfăcute pe unitatea de timp, adică intensitatea serviciului; S - numărul de canale de servicii. Apoi va fi scrisă condiția de operare a QS

sau
... Îndeplinirea acestei condiții permite calcularea limitei inferioare a numărului de canale.

Dacă
, sistemul nu poate gestiona coada. În același timp, coada crește la infinit.

2). Este necesar să se determine criteriul eficienței funcționăriiQS luând în considerare costul pierderii de timp atât din partea aplicațiilor, cât și din partea părții de servire.

Următoarele trei grupuri principale de indicatori sunt considerați ca indicatori ai eficienței funcționării QS:

1. Indicatori ai eficienței utilizării OCM.

Randamentul absolut al QS este numărul mediu de aplicații pe care QS le poate servi pe unitatea de timp.

Randamentul relativ al QS este raportul dintre numărul mediu de cereri deservite de QS pe unitatea de timp și numărul mediu de cereri primite în acest timp.

Durata medie a perioadei de angajare a unei organizații medicale.

Rata de utilizare a QS este ponderea medie de timp în care QS este ocupat în servirea aplicațiilor.

2. Indicatori ai calității aplicațiilor de servicii.

Timpul mediu de așteptare pentru o solicitare în coadă.

Timpul mediu petrecut de o aplicație în OCM.

Probabilitatea ca o solicitare să fie respinsă fără a aștepta.

Probabilitatea ca cererea primită să fie imediat acceptată pentru service.

Legea distribuției timpului de așteptare pentru o aplicație în coadă.

Legea distribuției timpului petrecut de o cerere în QS.

Numărul mediu de aplicații din coadă.

Numărul mediu de cereri în OCM.

3. Indicatori ai eficienței funcționării perechii „SMO - consumator”.

Atunci când alegeți un criteriu pentru eficiența funcționării QS, este necesar să se țină seama de o abordare dublă în considerarea sistemelor de coadă. De exemplu, funcționarea unui supermarket, ca un SMO, poate fi vizualizată din părți opuse. Pe de o parte, acceptat în mod tradițional, clientul care așteaptă la rândul său la plata reprezintă o cerere de servicii, iar casierul este un canal de servicii. Pe de altă parte, un casier care așteaptă clienții poate fi considerat o solicitare de servicii, iar un client poate fi considerat un dispozitiv de servicii capabil să satisfacă cererea, adică. du-te la casa de marcat și oprește casierul inactiv forțat. (în mod tradițional - cumpărători\u003e decât casierii, dacă casierii\u003e decât cumpărătorii, ei așteaptă cumpărători).

DIN
Ținând cont de acest lucru, este recomandabil să minimalizăm simultan ambele părți ale QS.

Utilizarea unei astfel de abordări duale implică necesitatea de a lua în considerare, la formarea criteriului de eficiență, nu numai indicatorii de mai sus separat, ci și mai mulți indicatori care reflectă atât interesele subsistemelor de service, cât și ale serviciilor de service ale QS. De exemplu, s-a arătat că cel mai important criteriu de eficiență în sarcinile de așteptare este timpul total petrecut de un client la o coadă, pe de o parte, și timpul de oprire al canalelor de servicii, pe de altă parte.

Clasificarea sistemului de așteptare

1. După natura serviciului, se disting următoarele tipuri de HMS:

1.1. Sisteme de așteptare sau sisteme de coadă... Cererile care au intrat în sistem și nu au fost acceptate imediat pentru service se acumulează la coadă. Dacă canalele sunt gratuite, atunci solicitarea este comunicată. Dacă toate canalele sunt ocupate în momentul sosirii unei solicitări, următoarea solicitare va fi difuzată după finalizarea serviciului precedent. Un astfel de sistem se numește acces complet (cu coadă nelimitată).

Există sisteme cu service de reparații de sine stătătoare, unde repararea începe la anumite puncte în timp;

Sisteme de coadă limitate... (reparare garaj)

Sisteme cu defecțiuni... Toate cererile care au ajuns la momentul notificării cererii sunt refuzate. (GTS)

Sisteme cu flux de intrare de grup și servicii de grup... În astfel de sisteme, revendicările ajung uneori în grupuri; serviciul are loc și în grupuri.

2. În funcție de numărul de canale de servicii, OCM sunt împărțite în următoarele grupuri.

SMO cu un singur canal

CMO multicanal... Deservirea următoarei solicitări poate începe înainte de sfârșitul deservirii cererii anterioare. Fiecare canal acționează ca un dispozitiv de service independent.

3. În funcție de gama de obiecte deservite, se disting două tipuri.

OCM închis. Un sistem închis în coadă este un sistem în coadă în care revendicările deservite pot fi returnate la sistem și returnate în service. Exemple de AIO închise sunt magazinele de reparații, băncile de economii.

CMO-uri deschise.

4. În funcție de numărul de etape de întreținere, se disting CMO monofazate și multifazice.

Fază singularăQS sunt sisteme omogene care efectuează aceeași operație de întreținere.

multifază SMO sunt sisteme în care canalele de servicii sunt localizate secvențial și efectuează diferite operațiuni de întreținere. Stațiile de service auto sunt un exemplu de sistem multifazic.

Clasificarea de mai sus este condiționată. În practică, OCM-urile acționează cel mai adesea ca sisteme mixte. De exemplu, revendicările așteaptă ca serviciul să înceapă până la un anumit punct, după care sistemul începe să funcționeze ca un sistem cu defecțiuni.

Procesul la întâmplare de la Markov cu stări discrete și timp continuu considerat în prelegerea anterioară are loc în sistemele de coadă (QS).

Sisteme de coadă - acestea sunt sisteme în care cererile de servicii ajung la ore aleatorii, iar solicitările primite sunt deservite folosind canalele de servicii disponibile pentru sistem.

Exemple de sisteme de coadă sunt:

decontare și puncte de numerar în bănci, la întreprinderi;
calculatoare personale care servesc aplicații sau cerințe pentru rezolvarea anumitor probleme;
stații de service auto; Benzinărie;
firme de audit;
departamentele inspectoratelor fiscale angajate în acceptarea și verificarea raportării curente a întreprinderilor;
centrale telefonice etc.

	Nodurile	cerinţe

Spital	infirmieri	Pacientii
producere
Aeroport	Ieșirea pistei Puncte de înregistrare	pasagerii

Să luăm în considerare schema de lucru a QS (Fig. 1). Sistemul constă dintr-un generator de solicitare, un dispecerat și o unitate de servicii, o unitate de contabilitate cu defecte (terminator, distrugător de comenzi). În general, un nod de serviciu poate avea mai multe canale de servicii.

Fig. 1

Generator de aplicații - un obiect care generează aplicații: o stradă, un atelier cu unități instalate. Intrarea primește fluxul de aplicații (fluxul de clienți către magazin, fluxul de unități sparte (mașini, mașini-unelte) pentru reparații, fluxul de vizitatori în garderobă, fluxul de mașini către benzinărie etc.).
dispecer - o persoană sau dispozitiv care știe ce să facă cu aplicația. Un nod care reglementează și direcționează cererile către canalele de servicii. dispecer:

acceptă cereri;
formează o coadă dacă toate canalele sunt ocupate;
le direcționează către canalele de servicii, dacă sunt disponibile;
refuză cererile (din diverse motive);
primește informații de la nodul de serviciu despre canalele libere;
monitorizează timpul de funcționare al sistemului.

Coadă - acumulator de aplicații. Este posibil să nu existe coadă.
Nodul serviciului constă dintr-un număr finit de canale de servicii. Fiecare canal are 3 stări: gratuit, ocupat, nu funcționează. Dacă toate canalele sunt ocupate, puteți veni cu o strategie cui să transferați solicitarea.
renegare din service apare dacă toate canalele sunt ocupate (unele dintre ele pot să nu funcționeze).

Pe lângă aceste elemente de bază în OCM, unele surse disting și următoarele componente:

terminator - distrugătorul tranzacțiilor;

depozit - acumulator de resurse și produse finite;

cont contabil - pentru efectuarea tranzacțiilor de tipul „detașării”;

manager - manager resurse;

Clasificarea OCM

Prima diviziune (prin prezența cozilor):

OCM cu eșecuri;
OCM cu coadă.

ÎN OCM cu respingeri o solicitare care ajunge la un moment în care toate canalele sunt ocupate primește un refuz, părăsește QS-ul și nu va fi deservit în viitor.

ÎN OCM cu coadă o solicitare care ajunge în momentul în care toate canalele sunt ocupate nu pleacă, ci intră la coadă și așteaptă să fie servită.

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

Deci, de exemplu, sunt considerate următoarele QS-uri:

QS cu solicitări nerăbdătoare (durata cozii și timpul de serviciu sunt limitate);
QS cu un serviciu prioritar, adică, unele solicitări sunt răspândite etc.

Tipurile de restricție de coadă pot fi combinate.

O altă clasificare împarte OCM în funcție de sursa de aplicații. Cererile (cerințele) pot fi generate de sistemul însuși sau de un mediu extern care există independent de sistem.

Desigur, fluxul de aplicații generat de sistemul propriu va depinde de sistem și de starea sa.

În plus, OCM sunt împărțite în deschisOCM și închis OCP.

Într-un QS deschis, caracteristicile fluxului de aplicații nu depind de starea QS în sine (câte canale sunt ocupate). Într-un QS închis, acestea depind. De exemplu, dacă un lucrător servește un grup de mașini care necesită ocazional ajustare, atunci intensitatea fluxului de „cerințe” de la mașini depinde de câte dintre ele funcționează deja în mod corespunzător și așteaptă ajustarea.

Un exemplu de sistem închis: plata de către casier a salariilor la întreprindere.

După numărul de canale, OCM-urile sunt împărțite în:

un singur canal;
mai multe canale.

Caracteristici de sistem în coadă

Principalele caracteristici ale unui sistem de cozi de orice fel sunt:

fluxul de intrare a cererilor sau serviciilor primite;
disciplina coadă;
mecanism de serviciu.

Cerințe de flux de intrare

Pentru a descrie fluxul de intrare, trebuie să setați o lege probabilistică care determină secvența de ori la sosirea cererilor de servicii, și indicați numărul acestor cereri în fiecare chitanță obișnuită. În acest caz, de regulă, acestea operează cu conceptul de „distribuție probabilistică a momentelor de primire a creanțelor”. Aici pot face la fel cerințe unice și de grup (numărul acestor cereri în fiecare admitere obișnuită). În ultimul caz, vorbim de obicei despre un sistem de servicii cu serviciu de grup paralel.

A i- ora de sosire între cerințe - variabile aleatoare independente distribuite în mod egal;

E (A) - timpul mediu de admitere (MO);

λ \u003d 1 / E (A) - intensitatea primirii cererilor;

Caracteristicile fluxului de intrare:

O lege probabilistică care determină succesiunea orelor de primire a solicitărilor de servicii.
Numărul de solicitări la fiecare sosire succesivă pentru fluxurile de grup.

Disciplina cozii

Coadă - un set de cerințe care așteaptă serviciul.

Coada are un nume.

Disciplina cozii definește principiul conform căruia cererile care sosesc la intrarea sistemului de servire sunt conectate de la coadă la procedura de service. Cele mai frecvent utilizate discipline de coadă sunt definite de următoarele reguli:

primul venit, primul servit;

primul în primul out (FIFO)

cel mai frecvent tip de coadă.

Ce structură de date ar fi potrivită pentru a descrie o astfel de coadă? Matricea este proastă (limitată). Puteți utiliza o structură de tip LIST.

Lista are un început și un sfârșit. Lista constă din intrări. O înregistrare este o celulă dintr-o listă. Cererea ajunge la sfârșitul listei și este selectată pentru service de la începutul listei. Înregistrarea constă dintr-o descriere a aplicației și o legătură (un indicator a cui se află în urmă). În plus, dacă coada are o limită de timp, atunci trebuie specificată și limita de timp.

În calitate de programatori, ar trebui să poți face liste cu două fețe, pe o singură parte.

Listă acțiuni:

introduceți în coadă;
ia de la început;
scoateți din listă după expirare.
a venit ultimul - a servit primulLIFO (clemă de cartuș, capăt mortal la o gară, a intrat într-o trăsură ambalată)

O structură cunoscută sub numele de STACK. Poate fi descris de o matrice sau o structură de listă;

selectarea aleatorie a aplicațiilor;
selectarea aplicațiilor după criteriul priorității.

Fiecare aplicație este caracterizată, printre altele, de un nivel de prioritate și la sosire nu este plasată nu în coada cozii, ci la sfârșitul grupului său prioritar. Dispeceratul sortează după prioritate.

Caracteristicile cozii

prescripţietimp de asteptare momentul începerii serviciului (există o coadă cu un timp limitat de așteptare pentru serviciu, care este asociat cu conceptul de „lungime de coadă admisibilă”);
lungimea cozii.

Mecanismul de service

Mecanismul de service este determinată de caracteristicile procedurii de serviciu în sine și de structura sistemului de servicii. Caracteristicile procedurii de întreținere includ:

numărul de canale de servicii ( N);
durata procedurii de deservire (distribuția probabilistică a timpului de deservire a revendicărilor);
numărul de cereri satisfăcute ca urmare a fiecărei astfel de proceduri (pentru cererile de grup);
probabilitatea eșecului canalului de servire;
structura sistemului de servicii.

Pentru o descriere analitică a caracteristicilor procedurii de service, se operează cu conceptul de „distribuție probabilistică a timpului de deservire a clienților”.

S i - timp de serviciu eucerințele;

E (S) - timpul mediu de servire;

μ \u003d 1 / E (S)- rapiditatea solicitărilor de deservire.

Trebuie menționat că timpul de serviciu al unei solicitări depinde de natura cererii în sine sau de cerințele clientului și de starea și capacitățile sistemului de servire. În unele cazuri, este de asemenea necesar să se țină seama probabilitatea eșecului canalului de service după un anumit interval de timp limitat. Această caracteristică poate fi modelată ca un flux de eșecuri care intră în QS și au prioritate față de toate celelalte aplicații.

Rata de utilizare a OCM

N· Μ este rata de service din sistem atunci când toate dispozitivele de service sunt ocupate.

ρ=λ/( Nμ) se numește coeficientul de utilizare a sistemului , arată cât sunt implicate resursele sistemului.

Structura sistemului de servicii

Structura sistemului de servicii este determinată de numărul și aranjarea reciprocă a canalelor de servicii (mecanisme, dispozitive etc.). În primul rând, trebuie subliniat faptul că un sistem de servicii nu poate avea un singur canal de servicii, ci mai multe; un sistem de acest fel este capabil să îndeplinească mai multe cerințe simultan. În acest caz, toate canalele de servicii oferă aceleași servicii și, prin urmare, se poate susține că există serviciu paralel .

Exemplu. Contoare de vânzare în magazin.

Sistemul de servicii poate consta din mai multe tipuri diferite de canale de servicii, prin care fiecare cerință de serviciu trebuie să treacă, adică, în sistemul de servicii procedurile de servicii pentru clienți sunt implementate secvențial ... Mecanismul de serviciu definește caracteristicile fluxului de cereri de ieșire (servit).

Exemplu. Comisia medicală.

Serviciu combinat - deservirea depozitelor în casa de economii: mai întâi controlorul, apoi casierul. De regulă, există 2 controlere pentru un casier.

Asa de, funcționalitatea oricărui sistem de coadă este determinată de următorii factori principali :

distribuția probabilistică a timpilor de primire a cererilor de servicii (unice sau de grup);
puterea sursei cerințelor;
distribuția probabilistică a duratei serviciului;
configurația sistemului de servicii (serviciu paralel, serial sau paralel-serial);
numărul și performanța canalelor de servire;
disciplina cozii.

Principalele criterii pentru eficacitatea funcționării QS

La fel de principalele criterii pentru eficacitatea funcționării sistemelor de coadă în funcție de natura problemei rezolvate, pot exista:

probabilitatea serviciului imediat al cererii primite (P obsl \u003d K obs / K post);
probabilitatea de a refuza comunicarea cererii primite (P deschis \u003d K deschis / K post);

Evident, P obsl + P deschis \u003d 1.

Fluxuri, întârzieri, întreținere. Formula Pollachek-Khinchin

Întârziere - unul dintre criteriile pentru deservirea QS, timpul petrecut de aplicație în așteptarea serviciului.

D i - întârziere la coada cererii eu;

W i \u003d D i + S i- timpul petrecut în sistemul cerinței eu.

(cu probabilitatea 1) este întârzierea medie în stare constantă a unei solicitări în coadă;

(cu probabilitatea 1) - timpul mediu statistic constant petrecut de cerere în OCM (în așteptare).

Q (t) -numărul de solicitări din coadă la un moment dat t;

L (t)– numărul de solicitări din sistem la un moment dat t(Q (t) plus numărul de solicitări care sunt în service la un moment dat t.

Apoi indicatorii (dacă există)

(cu probabilitatea 1) - numărul mediu de solicitări în coadă la stat constant;

(cu probabilitatea 1) este numărul mediu de solicitări în sistem constant la timp.

Rețineți că ρ<1 – обязательное условие существования d, w, Qși L în sistemul de cozi.

Reamintind că ρ \u003d λ / ( Nμ), atunci se vede că dacă intensitatea sosirii cererilor este mai mare decât Nμ, apoi ρ\u003e 1 și este firesc ca sistemul să nu poată face față unui astfel de flux de cereri și, prin urmare, nu putem vorbi despre valori d, w, Qși L.

Cele mai generale și necesare rezultate pentru sistemele de coadă includ ecuațiile de conservare

Trebuie menționat că criteriile menționate mai sus pentru evaluarea performanței sistemului pot fi calculate analitic pentru sistemele de coadă M / M / N(N\u003e 1), adică sisteme cu fluxuri de cereri și servicii ale Markov. Pentru M / G /sunt pentru orice distribuție G și pentru alte sisteme. În general, distribuția timpului între sosiri, distribuția timpului de serviciu sau ambele cantități trebuie să fie exponențiale (sau un fel de distribuție exponențială a ordinii k-a Erlang) pentru a fi posibilă o soluție analitică.

În plus, puteți vorbi și despre astfel de caracteristici precum:

randament absolut al sistemului - A \u003d P obsl * λ;
randament relativ al sistemului -

Un alt exemplu interesant (și ilustrativ) de soluție analitică – calculul întârzierii medii a cozii la starea de echilibru pentru un sistem de coadă M / G /1 după formula:

În Rusia, această formulă este cunoscută sub numele de formula Pollachek – Khinchin, în străinătate, această formulă este asociată cu numele Ross (Ross).

Astfel, dacă E (S) este mai importantă, atunci supraîncărcarea (în acest caz măsurată ca d) va fi mai mare; ceea ce este de așteptat. Formula dezvăluie și un fapt mai puțin evident: congestionarea crește și atunci când variabilitatea distribuției timpului de serviciu crește, chiar dacă timpul mediu de serviciu rămâne același. Intuitiv, acest lucru poate fi explicat după cum urmează: variația variabilei aleatorii a timpului de serviciu poate prelua o valoare mare (deoarece aceasta trebuie să fie pozitivă), adică singurul dispozitiv de service va fi ocupat mult timp, ceea ce va duce la o creștere a cozii.

Subiectul teoriei în coadă este stabilirea unei relații între factorii care determină funcționalitatea sistemului de așteptare și eficiența funcționării acestuia. În majoritatea cazurilor, toți parametrii care descriu sistemele de coadă sunt variabile sau funcții aleatorii, astfel încât aceste sisteme sunt denumite sisteme stocastice.

Natura aleatorie a fluxului de revendicări (revendicări), precum și, în cazul general, durata serviciului duce la faptul că un sistem aleatoriu are loc în sistemul de așteptare. După natura procesului aleatoriu care apar în sistemul de coadă (QS), distingeți sistemele Markov și non-Markov ... În sistemele Markov, fluxul de solicitări primite și fluxul de solicitări (pretenții) deservite sunt Poisson. Fluxurile Poisson facilitează descrierea și construirea unui model matematic al unui sistem de coadă. Aceste modele au soluții destul de simple, de aceea, majoritatea aplicațiilor cunoscute ale teoriei în coadă folosesc schema Markov. În cazul proceselor non-Markov, problemele studierii sistemelor de coadă devin mult mai complicate și necesită utilizarea modelării statistice, a metodelor numerice folosind calculatoare.

Pentru toate modelele de rețele de așteptare descrise în capitolul 2, s-a presupus că timpul de serviciu al cererilor în diferite etape ale traseului este independent. Aceasta reflectă în mod inadecvat situația reală din rețelele de transmitere a informațiilor, în care lungimea (volumul) unui mesaj în timpul transmiterii acestuia de la un nod la altul nu se schimbă, ceea ce duce la necesitatea studierii rețelelor cu durate dependente (în special, identice) de transmitere a mesajelor pe canale.

În lucrarea de față, după care se presupune că, împreună cu durata serviciului, fiecare mesaj este caracterizat, de asemenea, de volumul propriu și, în ceea ce privește duratele serviciului, se asumă doar independența lor condiționată (pentru un volum fix), ceea ce face posibilă luarea în considerare a dependenței duratelor de serviciu ale aceluiași mesaj în diferite etape ale acestuia traseu. În același timp, ne restrângem la principiile de rutare Kelly (rețelele tip Jackson cu rutare Markov sunt un caz special al modelului analizat).

Se oferă o dovadă alternativă a reprezentării multiplicative pentru probabilitățile staționare ale statelor unor astfel de rețele cu noduri de diferite tipuri, punerea în aplicare a așa-numitelor discipline de servicii simetrice și admiterea dependenței de revendicare a serviciilor la diferite noduri ale rutei. Acest lucru nu afectează problemele subtile ale existenței distribuțiilor staționare pentru rețelele generale, care fac obiectul cercetării independente.

5.2.1 Descrierea rețelei. Notaţie

Luați în considerare o rețea MO, pentru a descrie care vom folosi următoarea notație:

M este un set finit de noduri de rețea,

M este numărul de noduri din rețeaua MO,

Numărul nodului,.

Se presupune că nodurile sunt de următoarele tipuri:

0) cele multiliniare exponențiale, cu capacitate de stocare infinită și disciplină FIFO (rețineți că teorema de mai jos poate fi transferată cu ușurință la nodurile exponențiale cu o alegere aleatorie a unui dispozitiv sau a unui loc din coadă);

1) infinit-liniar;

2) linie unică cu capacitate de stocare infinită, disciplină de inversare a serviciului cu întrerupere a serviciului și serviciu suplimentar;

3) linie unică cu capacitate de stocare infinită și disciplină de divizare uniformă a dispozitivului.

Setul de noduri tip este desemnat și numărul de dispozitive dintr-un nod este.

Pretutindeni, ca și înainte, vom nota variabile aleatorii cu litere mari și laturi, iar realizările lor - cu litere mici, și variabile vectoriale aleatoare și vectori vor fi evidențiate cu caractere aldine.

Rețeaua primește un flux Poisson de solicitări de intensitate și fiecare cerere de intrare este caracterizată de un set de variabile aleatorii care nu depind de variabile aleatorii similare pentru alte solicitări și istoricul funcționării rețelei, unde:

Lungimea aleatorie a traseului de revendicare, adică. numărul de etape la care va fi difuzat;

O rută aleatorie, care este un set de numere de noduri (eventual repetate), traversate secvențial de revendicare la toate etapele L;

Volumele aleatorii din etapele traversate succesiv ale traseului sunt, în general, diferite în diferite etape;

Duratele aleatoare ale serviciului în etapele traversate succesiv ale traseului sunt, de asemenea, în general, diferite în diferite etape. Rețineți că, dacă, la o anumită etapă, o revendicare este difuzată într-un nod de tip 2 sau 3, atunci durata serviciului în această etapă este momentul în care o revendicare ar fi difuzată la acest nod dacă nu ar exista alte revendicări.

Volumul Y poate avea atât un sens fizic real sub formă de, de exemplu, cantitatea de memorie necesară pentru a înregistra un mesaj sau poate fi de natură auxiliară, de exemplu, pentru a specifica tipurile de revendicări din rețea; în ultimul caz, modelul analizat poate fi interpretat ca o rețea ML cu un set continuu de tipuri de mesaje.

Evident, cu o astfel de descriere a rețelei, volumul și lungimea corespund serviciului revendicării din nodul cu numărul Reamintim că rutele R sunt permise în care se pot repeta numerele, adică. un client poate fi servit la același nod de mai multe ori, cu ore de service diferite.

Caracteristicile statistice ale unei variabile aleatorii sunt specificate de funcția de distribuție comună (DF)

dF comună a traseului și volumul cererii în etape, prin

durată comună condiționată a duratei serviciului a cererii în etape cu trasee și volume fixe și până la

dF condițională a duratei de comunicare a cererii în faza (în nod cu un număr) cu un traseu și volume fixe.

Următoarele ipoteze sunt făcute cu privire la funcțiile introduse.

(A 1.) Durata serviciilor se presupune a fi independentă condiționat de-a lungul traseului, adică. DF condițional are forma

(A 2.) Nodurile exponențiale sunt QS-uri liniare (cu capacitate de stocare infinită), ratele de serviciu în care orice cerere a fiecărui server este egală cu

Astfel, dacă, adică în etapa rutei, revendicarea este notificată la un nod de tip 0, apoi

Cu alte cuvinte, durata serviciului într-un nod de tip 0 nu depinde nici de ruta R, nici de volumele Y (inclusiv volumul) și are o distribuție exponențială cu un parametru.

(P 3). Funcțiile de distribuție nu conțin o componentă singulară.

Apoi, densitățile lor, înțelese în sensul obișnuit pentru distribuții absolut continue sau în sens generalizat pentru distribuții discrete și mixte, vor fi notate prin.

În plus, pentru nodurile de tipurile 1-3 am pus

și pentru a reduce notația rezultatelor, notăm în plus prin

densitățile condiționate de distribuție a timpului final (intensitate) de deservire a unei revendicări cu caracteristici în stadiul de rută (la un nod), cu condiția ca timpul să fie difuzat Rețineți că, dacă în faza de traseu, o revendicare este servită la un nod exponențial cu un număr (adică dacă), apoi

Ar putea fi util să citiți: