Rețelele de așteptare și aplicațiile acestora. rețea de așteptare. Rețele stocastice de așteptare

Net la coadă(CEM) - o rețea care oferă servicii la solicitările primite. Menținerea cerințelor în QS este realizată de dispozitivele de service. QS clasic conține de la unul la un număr infinit de dispozitive. În funcție de posibilitatea ca cererile primite să aștepte începerea service-ului, QS-urile sunt împărțite în: sisteme cu pierderi, în care cererile care nu au găsit un singur dispozitiv liber la momentul sosirii se pierd; În acest caz, cererile în așteptare formează o coadă;sisteme cu o unitate de capacitate finită (așteptare și restricții), în care lungimea cozii nu poate depăși capacitatea unității; în acest caz, revendicarea care ajunge la QS supraaglomerat (nu există locuri libere de așteptat) este pierdută.

Fiecare QS este conceput pentru a servi (executa) un anumit flux de aplicații (sau cerințe) care intră în sistem, în cea mai mare parte, nu în mod regulat, ci în momente aleatorii. Serviciu de aplicații, caz general, de asemenea, nu durează o constantă, cunoscută dinainte, ci un timp aleatoriu. După deservirea cererii, canalul este eliberat și este gata să primească următoarea solicitare. Natura aleatorie a fluxului și timpul serviciului lor duce la o sarcină de lucru neuniformă a QS: la anumite intervale de timp, cererile neservite se pot acumula la intrarea QS (fie intră în coadă, fie lasă QS neservit), în timp ce la alte perioade, cu canale libere la intrarea QS, nu vor exista cereri, ceea ce duce la subîncărcarea QS-ului, adică. la canalele inactive.

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

) fluxul de aplicații de intrare;

) întoarce;

) canale de servicii;

) fluxul de ieșire al cererilor deservite.

Fiecare QS, în funcție de parametrii săi: natura fluxului de aplicații, numărul de canale de servicii și performanța acestora, precum și regulile de organizare a muncii, are o anumită eficiență de funcționare (capacitate), care îi permite să mai mult sau mai mult. să facă față cu mai puțin succes fluxului de aplicații.

Subiectul de studiu al teoriei stării de așteptare sunt QS.

Scopul teoriei cozilor este de a dezvolta recomandări pentru construirea rațională a unui QS, organizare raţională munca lor și reglarea fluxului de aplicații pentru a asigura eficiența ridicată a funcționării QS.

Pentru atingerea acestui scop se stabilesc sarcinile teoriei cozilor de aşteptare care constau în stabilirea dependenţelor eficienţei funcţionării QS de organizarea (parametrii): natura fluxului de aplicaţii, numărul de canale şi performanța acestora și regulile QS.

Natura aleatorie a fluxului de cereri și durata serviciului acestora generează un proces aleatoriu în QS.

Definiție: Un proces aleatoriu (sau o funcție aleatoare) este o corespondență în care fiecărei valori a argumentului (în acest caz, un moment din intervalul de timp al experimentului) i se atribuie o variabilă aleatoare (în acest caz, starea QS) . la coadă

În multe domenii ale economiei, finanțelor, producției și vieții rol important Joaca sisteme de asteptare(SMO), adică astfel de sisteme în care, pe de o parte, există solicitări (cerințe) masive pentru prestarea oricăror servicii, iar pe de altă parte, aceste solicitări sunt satisfăcute.

Ca exemple de QS în sfera financiară și economică, putem cita sisteme care sunt: ​​bănci de diferite tipuri, organizații de asigurări, inspectorate fiscale, servicii de audit, diverse sisteme de comunicații (inclusiv posturi telefonice), complexe de încărcare și descărcare (stații de mărfuri), benzinării, diverse intreprinderiși organizații de servicii (magazine, unități de catering, birouri de informații, coafor, case de bilete, case de schimb valutar, ateliere de reparații, spitale).

Sisteme precum rețele de calculatoare, sisteme de colectare, stocare și procesare a informațiilor, sisteme de transport, site-urile de producție automatizate, liniile de producție pot fi, de asemenea, considerate ca un fel de QS.

În comerț, multe operațiuni sunt efectuate în procesul de mutare a masei de mărfuri din sfera producției în sfera consumului. Astfel de operațiuni sunt: ​​încărcarea și descărcarea mărfurilor, transportul, ambalarea, ambalarea, depozitarea, afișarea, vânzarea etc. Pentru activitati comerciale caracterizată printr-un flux masiv de mărfuri, bani, servicii în masă pentru clienți etc., precum și efectuarea operațiunilor corespunzătoare, care sunt de natură aleatorie. Toate acestea creează denivelări în muncă. organizatii comercialeși întreprinderi, generează subîncărcări, timpi de nefuncționare și supraîncărcări. Cozile ocupă mult timp, de exemplu, de la cumpărătorii din magazine, șoferii de mașini la depozitele de mărfuri, așteptarea descărcarii sau încărcării.

În acest sens, sarcinile de analiză a activității, de exemplu, a departamentului de tranzacționare, întreprindere comercială sau secțiuni, să își evalueze activitățile, să identifice neajunsurile, rezervele și, în cele din urmă, să ia măsuri menite să crească eficacitatea acesteia. În plus, există probleme asociate cu crearea și implementarea unor modalități mai economice de a efectua operațiuni în cadrul unei secțiuni, departament, întreprindere comercială, bază de legume, departament comercial etc. Prin urmare, în organizarea comerțului, metodele teoriei cozilor de așteptare fac este posibil să se determine cantitatea optimă prize acest profil, numărul de vânzători, frecvența importului de mărfuri și alți parametri.

Depozitele sau bazele organizațiilor de aprovizionare și marketing pot servi ca un alt exemplu tipic de sisteme de așteptare, iar sarcina teoriei cozilor este de a stabili raportul optim între numărul de cerințe de servicii care sosesc la bază și numărul de dispozitive de servire, la care costurile totale de întreținere și pierderile din timpul nefuncționării transportului ar fi minime. Teoria cozilor poate găsi aplicație și în calcularea zonei spații de depozitare, în timp ce zona de depozitare este considerată ca un dispozitiv de serviciu, iar sosirea Vehicul pentru descărcare – ca cerință.


Principalele caracteristici ale QS

QS include următoarele elemente: sursa cerințelor, fluxul de cerințe de intrare, coadă, dispozitiv de serviciu (canal de serviciu), flux de cerințe de ieșire (cereri deservite).

Fiecare QS este conceput pentru a servi (executa) un anumit flux de aplicații (cerințe) care intră în sistem, în principal nu în mod regulat, ci în momente aleatorii. Serviciul aplicațiilor durează, de asemenea, nu pentru un timp constant, prestabilit, ci pentru un timp aleatoriu, care depinde de multe motive aleatorii. După deservirea cererii, canalul este eliberat și gata să primească următoarea solicitare.

Natura aleatorie a fluxului de cereri și timpul serviciului acestora duce la o încărcare neuniformă a QS: la anumite intervale de timp, cererile neservite se pot acumula la intrarea QS, ceea ce duce la o supraîncărcare a QS, în timp ce la alte intervale de timp, cu canale libere la intrarea QS-ului, nu există cereri, ceea ce duce la subîncărcarea QS-ului, adică. la lenevia canalelor sale. Aplicațiile care se acumulează la intrarea în 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 aşteptare

Fiecare QS include în structura sa un anumit număr de dispozitive de serviciu, care sunt numite canale de servicii. Rolul canalelor poate fi jucat de diverse dispozitive, persoane care efectuează anumite operațiuni (casieri, operatori, vânzători), linii de comunicație, vehicule etc.

Fiecare QS, în funcție de parametrii săi: natura fluxului de aplicații, numărul de canale de servicii și performanța acestora, precum și regulile de organizare a muncii, are o anumită eficiență de operare (debit), care îi permite mai mult sau mai puțin. face față cu succes fluxului de aplicații.

QS este subiectul de studiu teoria cozilor.

Scopul teoriei cozilor— elaborarea de recomandări privind construcția rațională a QS, organizarea rațională a muncii acestora și reglementarea fluxului de aplicații pentru a asigura o eficiență ridicată a QS.

Pentru atingerea acestui scop se stabilesc sarcinile teoriei cozilor de aşteptare care constau în stabilirea dependenţelor eficienţei funcţionării QS de organizarea (parametrii) acestuia.

La fel de caracteristicile eficacității funcționării QS Există trei grupuri principale de indicatori (de obicei medii) din care puteți alege:

1. Indicatori ai eficacității utilizării QS:

1.1. Absolut debitului QS - numărul mediu de aplicații pe care QS le poate servi pe unitatea de timp.

1.2. Debitul 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 SMO.

1.4. Rata de utilizare a QS este ponderea medie a timpului în care QS este ocupat cu cererile de service.

2. Indicatori de calitate a serviciului aplicației:

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

2.2. Timpul mediu de rezidență al unei cereri în CMO.

2.3. Probabilitatea de respingere a cererii în serviciu fără așteptare.

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

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

2.6. Legea repartizării timpului petrecut de o aplicație în QS.

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

2.8. Numărul mediu de aplicații în QS etc.

3. Indicatori de performanță ai perechii „SMO – consumator”, unde „consumator” înseamnă întregul set de aplicații sau o parte din sursa acestora (de exemplu, venitul mediu adus de QS pe unitatea de timp etc.).

Natura aleatorie a fluxului de aplicații și durata serviciului acestora se generează în QS proces aleatoriu. Pentru că momente în timp T iși intervalele de timp pentru primirea cererilor T, durata operațiunilor de service T obs, stând la coadă Toch, lungimea cozii eu oh sunt variabile aleatorii, atunci caracteristicile stării sistemelor de așteptare sunt probabiliste. Prin urmare, pentru a rezolva problemele teoriei cozilor de așteptare, este necesar să se studieze acest proces aleatoriu, adică. construiți și analizați-l model matematic.

Studiul matematic al funcționării QS este mult simplificat dacă procesul aleatoriu care are loc în acesta este Markovian. Pentru ca un proces aleatoriu să fie markovian, este necesar și suficient ca toate fluxurile de evenimente, sub influența cărora sistemul trece de la stare la stare, să fie (cel mai simplu) Poisson.

Cel mai simplu flux are trei proprietăți principale: obișnuit, staționar și fără efecte secundare.

Curgerea obișnuităînseamnă imposibilitatea practică a primirii simultane a 2 sau mai multe cerințe. De exemplu, probabilitatea ca mai multe case de marcat dintr-un magazin cu autoservire să eșueze în același timp este destul de mică.

Staționar este 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 modifică în timp. Astfel, probabilitatea ca un anumit număr de cerințe să intre în sistem într-o anumită perioadă de timp ?T depinde de valoarea sa și nu depinde de originea referinței sale pe axa timpului.

Fără efect secundarînseamnă că numărul de revendicări primite de sistem înainte de momentul respectiv T, nu determină câte solicitări vor intra în sistem în acest timp (T + ?T). De exemplu, dacă în casă de marcat in momentul de fata a existat o ruptura in caseta de numerar si a fost eliminata de catre casier, acest lucru nu afecteaza posibilitatea unei noi pauze la aceasta casa in momentul urmator si cu atat mai mult probabilitatea unei ruperi in alte case de marcat .

Pentru cel mai simplu flux, frecvența de primire a cerințelor în sistem respectă legea lui Poisson, adică probabilitatea de sosire în timp. T neted k cerințele este dată de formula

Unde λ — intensitatea debitului de aplicare, adică numărul mediu de aplicații care ajung la QS pe unitatea de timp,

Unde τ - valoarea medie a intervalului de timp dintre două aplicații învecinate.

Pentru un astfel de flux de cereri, timpul dintre două cereri învecinate este distribuit exponențial cu o densitate de probabilitate

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

Unde ν — intensitatea traficului la coadă, adică numărul mediu de aplicații care sosesc pentru serviciu pe unitatea de timp,

Unde Toch este timpul mediu de așteptare în coadă.

Fluxul de ieșire al cererilor este asociat cu fluxul de servicii din canal, unde durata serviciului T obs este o variabilă aleatorie și în multe cazuri se supune legii distribuției exponențiale cu densitate

Unde μ — debitul de serviciu, adică numărul mediu de solicitări servite pe unitatea de timp,

O caracteristică importantă a QS, care combină indicatorii λ Și μ , este un intensitatea sarcinii, care arată gradul de coordonare a fluxurilor specificate de aplicații:

Indicatori enumerați k, τ, λ, l och, Toch, ν, T obs, μ, ρ, Р k sunt cele mai comune pentru QS.

Aplicarea diferitelor metode matematice la formalizare. Accent pe un sistem complex - imprevizibil. Purtător incertitudinea este omul.

Un exemplu tipic de probleme stocastice (aleatoare, probabiliste) sunt modelele sistemelor de așteptare.

SMO-urile sunt omniprezente. Acestea sunt rețele de telefonie, benzinării, servicii pentru consumatori, case de bilete, evenimente comerciale etc.

Din poziţia de modelare a procesului de aşteptare, se formează situaţii în care se formează cozi de solicitări (cerinţe) de deservire, în felul următor. După ce a intrat în sistemul de servire, cerința se alătură la coada altor cerințe (primite anterior). Canalul de service selectează o cerință dintre cei din coadă pentru a începe deservirea acestuia. După finalizarea procedurii de deservire a următoarei cereri, canalul de servicii începe să deservească următoarea cerere, dacă există una în blocul de așteptare. Ciclul de funcționare a unui QS de acest fel se repetă de mai multe ori pe toată perioada de funcționare a sistemului de servire. Se presupune că trecerea sistemului la deservirea următoarei cerinţe după finalizarea întreţinerii cerinţei anterioare are loc instantaneu, la momente aleatorii.

Exemple de SMO sunt:

    posturi de intretinere auto;

    Posturi de reparatii auto;

    firme de audit etc.

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

Sistemele în care au loc procesele de servicii sunt numite sisteme de așteptare (QS).

Pentru a descrie un sistem de așteptare, trebuie să specificați:

- fluxul de intrare al aplicațiilor;

- disciplina de serviciu;

- timpul de service

- numărul de canale de servicii.

flux de intrare cerințele (aplicațiile) este descrisă prin identificarea ambelor probabilistice legea distributiei momentele de primire a cerințelor în sistem și numărul de cerințeîn fiecare intrare.

Cand esti intrebat discipline de serviciu(DO) este necesar să se descrie regulile pentru cerințele de așteptare și de service în sistem. Lungimea cozii poate fi atât limitată, cât și nelimitată. În cazul restricțiilor privind lungimea cozii, cererea primită la intrarea QS este refuzată. Cele mai frecvent utilizate DO sunt definite de următoarele reguli:

primul venit, primul servit;

    came last - servit primul; (cutie pentru mingi de tenis, stivuire în tehnică)

    selecția aleatorie a aplicațiilor;

    selectarea cererilor pe criteriu de prioritate.

Timp de service aplicațiile în QS este o variabilă aleatorie. Cea mai comună lege de distribuție este legea exponențială.  - viteza serviciului. =numar de solicitari/unitati de servicii. timp.

Canale de servicii, poate fi amplasat în paralel sau în serie. Cu un aranjament secvenţial de canale, fiecare aplicaţie este deservită pe toate canalele secvenţial. Cu o aranjare paralelă a canalelor, serviciul este efectuat pe toate canalele simultan, pe măsură ce acestea devin gratuite.

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

Subiect teoria cozilor este de a stabili relația dintre factorii care determină funcționalitatea QS și eficacitatea funcționării acestuia.

Probleme de proiectare QS.

Sarcinile de determinare a caracteristicilor structurii QS includ problema alegerii numărului de canale de servicii (elemente de bază (F i)), problema determinării metodei de conectare a canalelor (un set de elemente de conectare (Hj)), precum şi problema determinării debitului canalelor.

unu). Selectarea structurii. Dacă canalele funcționează în paralel, atunci problema alegerii Str se reduce la determinarea numărului de canale din partea de servire pe baza condiției de asigurare a operabilității QS. (Cu excepția cazului în care coada crește la infinit).

Rețineți că la determinarea numărului de canale de sistem, în cazul aranjamentului lor paralel, este necesar să se respecte starea de sănătate a sistemului. Notă:  - numărul mediu de cereri primite pe unitatea de timp, i.e. intensitatea fluxului de intrare;  - numărul mediu de cereri satisfăcute pe unitatea de timp, adică. intensitatea serviciului; S - numărul de canale de servicii. Apoi se va scrie condiția pentru funcționarea QS-ului

sau
. Îndeplinirea acestei condiții ne permite să calculăm limita inferioară a numărului de canale.

Dacă
, sistemul nu poate gestiona coada. Coada crește la nesfârșit.

2). Este necesar să se determine criteriul de eficacitate a funcționării QS, luând în considerare costul pierderilor de timp atât din partea aplicațiilor, cât și din partea piesei de service.

Următoarele trei grupuri principale de indicatori sunt considerate indicatori ai eficacității funcționării QS:

1. Indicatori ai eficacității utilizării QS.

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

    Debitul 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 SMO.

    Rata de utilizare QS este ponderea medie a timpului în care QS este ocupat cu întreținerea aplicațiilor.

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

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

    Timpul mediu de rezidență al unei cereri în CMO.

    Probabilitatea ca cererea să fie refuzată serviciul fără așteptare.

    Probabilitatea ca o solicitare primită să fie imediat acceptată pentru serviciu.

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

    Legea repartizării timpului petrecut de o aplicație în QS.

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

    Numărul mediu de aplicații în CMO.

3. Indicatori ai eficacității funcționării perechii „QS – consumator”.

Atunci când se alege un criteriu pentru eficiența funcționării QS, este necesar să se țină cont de abordarea duală a luării în considerare a sistemelor de așteptare. De exemplu, activitatea unui supermarket, cum ar fi un CMO, poate fi privită din părți opuse. Pe de o parte, acceptată în mod tradițional, cumpărătorul, care așteaptă la coadă la casă, este o cerere de service, iar casieria este un canal de servicii. Pe de altă parte, o casieră care așteaptă clienți poate fi considerată o cerere de serviciu, iar un client este un dispozitiv de service capabil să satisfacă cererea, adică. mergeți la casierie și opriți timpul de nefuncționare forțat al casieriei. (în mod tradițional - cumpărători > decât casierii, dacă casierii > decât cumpărătorii, ei așteaptă cumpărători).

DIN
Având în vedere acest lucru, este oportun să minimizați ambele părți ale QS simultan.

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 simultan, reflectând interesele atât ale subsistemelor QS deservite, cât și ale subsistemelor deservite. De exemplu, se arată că cel mai important criteriu de eficiență în sarcinile de așteptare este timpul total petrecut de client în coadă, pe de o parte, și canalele de servicii inactive, pe de altă parte.

Clasificarea sistemelor de aşteptare

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

1.1. Sisteme de așteptare sau sisteme de așteptare. Cerințele care au intrat în sistem și nu sunt imediat acceptate pentru service sunt acumulate într-o coadă. Dacă canalele sunt gratuite, atunci cererea este servită. Dacă toate canalele sunt ocupate în momentul primirii cererii, următoarea cerere va fi deservită după finalizarea deservirii celei anterioare. Un astfel de sistem se numește complet accesibil (cu coadă nelimitată).

Există sisteme cu serviciu autonom, când serviciul începe la anumite momente de timp;

      Sisteme cu coadă limitată. (reparatie garaj)

      Sisteme cu defecțiuni. Toate cererile sosite la momentul deservirii cererii sunt respinse. (GTS)

      Sisteme cu flux de intrare de grup și serviciu de grup. În astfel de sisteme, aplicațiile ajung în grupuri la momente, iar service-ul are loc și în grupuri.

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

QS cu un singur canal.

QS multicanal. Notificarea următoarei cereri poate începe înainte de încheierea deservirii cererii anterioare. Fiecare canal acționează ca un server independent.

3. După gama de obiecte deservite, se disting două tipuri.

QS închis. Un sistem de așteptare în buclă închisă este un sistem de așteptare în care clienții deserviți pot reveni la sistem și pot fi serviți din nou. Exemple de SMO închise sunt atelierele de reparații, casele de economii.

Deschideți CMO-uri.

4. După numărul de trepte de serviciu, se disting QS monofazat și multifazat.

fază singulară QS sunt sisteme omogene care efectuează aceeași operațiune de service.

Polifazic QS sunt sisteme în care canalele de service sunt dispuse în serie și efectuează diverse operațiuni de service. Stațiile sunt un exemplu de QS cu mai multe faze întreținere mașini.

Clasificarea de mai sus a QS este condiționată. În practică, cel mai adesea QS-urile acționează ca sisteme mixte. De exemplu, aplicațiile așteaptă până la un anumit moment pentru începerea service-ului, după care sistemul începe să funcționeze ca un sistem cu defecțiuni.

Procesul stocastic Markov cu stări discrete și timp continuu luat în considerare în prelegerea anterioară are loc în sistemele de așteptare (QS).

Sisteme de așteptare - sunt sisteme în care cererile de servicii sunt primite la momente aleatorii, în timp ce cererile primite sunt deservite folosind canalele de servicii disponibile sistemului.

Exemple de sisteme de așteptare sunt:

  • noduri de decontare și numerar în bănci, întreprinderi;
  • calculatoare personale, care deservesc aplicațiile primite sau cerințele pentru rezolvarea anumitor probleme;
  • stații de service auto; benzinărie;
  • firme de audit;
  • departamente inspectii fiscale implicat în acceptarea și verificarea raportării curente a întreprinderilor;
  • centrale telefonice etc.

Noduri

Cerințe

Spital

ordinele

Pacienții

Productie

Aeroport

Ieșiri pe pistă

Puncte de înregistrare

Pasagerii

Luați în considerare schema de funcționare QS (Fig. 1). Sistemul constă dintr-un generator de cereri, un dispecer și un nod de serviciu, un nod de contabilizare a eșecului (terminator, distrugător de cereri). Un nod de serviciu poate avea în general mai multe canale de servicii.

Orez. unu
  1. Generator de aplicații – un obiect care generează aplicații: o stradă, un atelier cu unități instalate. Intrarea este fluxul de aplicare(fluxul de clienți către magazin, fluxul de unități sparte (mașini, mașini-unelte) pentru reparații, fluxul de vizitatori către garderobă, fluxul de mașini către benzinării etc.).
  2. Dispecer – o persoană sau un dispozitiv care știe ce să facă cu biletul. Un nod care reglementează și direcționează cererile către canalele de servicii. Dispecer:
  • acceptă cereri;
  • formează o coadă dacă toate canalele sunt ocupate;
  • îi direcționează către canalele de servicii, dacă există;
  • refuză cererile (din diverse motive);
  • primește informații de la nodul de serviciu despre canalele gratuite;
  • ține evidența timpului sistemului.
  1. Întoarce-te - cere acumulator. Este posibil ca coada să nu existe.
  2. Nod de serviciu constă dintr-un număr finit de canale de servicii. Fiecare canal are 3 stări: liber, ocupat, inactiv. Dacă toate canalele sunt ocupate, atunci puteți veni cu o strategie cui să transferați aplicația.
  3. Refuz de la serviciu apare dacă toate canalele sunt ocupate (unele dintre ele pot să nu funcționeze).

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

terminator - distrugător de tranzacții;

depozit - depozitarea resurselor și a produselor finite;

Verifica contabilitate- să efectueze operațiuni de tip „detașare”;

manager - manager de resurse;

Clasificarea CMO

Prima diviziune (prin prezența cozilor):

  • CMO cu eșecuri;
  • CMO cu o coadă.

ÎN CMO cu eșecuri o solicitare care sosește în momentul în care toate canalele sunt ocupate este respinsă, părăsește QS-ul și nu este servită în continuare.

ÎN CMO cu o coadă o aplicație care ajunge într-un moment în care toate canalele sunt ocupate nu pleacă, ci sta la coadă și așteaptă o oportunitate pentru a fi servită.

QS cu cozi subdivizat în tipuri diferite in functie de modul in care este organizata coada - limitat sau nelimitat. Restricțiile se pot referi atât la lungimea cozii, cât și la timpul de așteptare, „disciplina de serviciu”.

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

  • QS cu cereri nerăbdătoare (lungimea cozii și timpul de service sunt limitate);
  • QS cu serviciu prioritar, adică unele aplicații sunt servite în afara rândului etc.

Tipurile de restricții la coadă pot fi combinate.

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

Desigur, fluxul de cereri generate de sistemul însuși va depinde de sistem și de starea acestuia.

În plus, SMO-urile sunt împărțite în deschis CMO și închis SMO.

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

Un exemplu de sistem închis: eliberarea unui salariu de către un casier la o întreprindere.

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

  • monocanal;
  • multicanal.

Caracteristicile sistemului de aşteptare

Principalele caracteristici ale unui sistem de așteptare de orice fel sunt:

  • fluxul de intrare al cerințelor primite sau al solicitărilor de servicii;
  • disciplina la coada;
  • mecanism de service.

Flux de intrare de cerințe

Pentru a descrie fluxul de intrare, trebuie să setați o lege probabilistică care determină succesiunea momentelor de primire a cerințelor de serviciu,și indicați numărul de astfel de cereri în fiecare chitanță obișnuită. În acest caz, de regulă, ele operează cu conceptul de „repartizare probabilistică a momentelor de primire a cerințelor”. Aici poți acționa ca cerințe individuale și de grup (numărul de astfel de creanțe în fiecare chitanță succesivă). În acest din urmă caz, vorbim de obicei despre un sistem de așteptare cu serviciu de grup paralel.

A i– timpul de sosire între cerințe – variabile aleatoare independente distribuite identic;

E(A) este timpul mediu de sosire (MO);

λ=1/E(A)- intensitatea primirii cerinţelor;

Caracteristicile fluxului de intrare:

  1. O lege probabilistică care determină succesiunea momentelor de primire a cerințelor de serviciu.
  2. Numărul de cereri din fiecare sosire următoare pentru fluxuri multicast.

Disciplina la coada

Întoarce-te - un set de cerințe care așteaptă să fie deservite.

Coada are un nume.

Disciplina la coada determină principiul conform căruia cererile care ajung la intrarea sistemului de service sunt conectate din coadă la procedura de service. Cele mai frecvent utilizate discipline de coadă sunt definite de următoarele reguli:

  • primul venit, primul servit;

primul intrat primul ieşit (FIFO)

cel mai comun tip de coadă.

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

Lista are un început și un sfârșit. Lista constă din intrări. O intrare este o celulă de listă. Aplicația ajunge la sfârșitul listei și este selectată pentru service de la începutul listei. Intrarea constă dintr-o descriere a aplicației și un link (un index al cine se află în spatele acesteia). În plus, dacă coada are o limită de timp, atunci trebuie specificată și limita de timp.

Voi, ca programatori, ar trebui să puteți face liste cu două fețe, unilaterale.

Listează acțiuni:

  • introduceți în coadă;
  • ia de la început;
  • eliminați din listă după expirarea timpului.
  • ultimul venit, primul servit LIFO (clemă pentru cartuş, fundătură la gară, a intrat într-o maşină plină).

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

  • selecția aleatorie a aplicațiilor;
  • selectarea cererilor pe criteriu de prioritate.

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

Caracteristicile cozii

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

Mecanism de service

Mecanism de service este determinată de caracteristicile procedurii de service în sine și de structura sistemului de servicii. Procedurile de service includ:

  • numărul de canale de servicii ( N);
  • durata procedurii de service (distribuirea probabilistică a duratei de serviciu a cerinţelor);
  • numărul de cerințe îndeplinite ca urmare a implementării fiecărei astfel de proceduri (pentru aplicațiile de grup);
  • probabilitatea de defecțiune a canalului de servire;
  • structura sistemului de servicii.

Pentru o descriere analitică a caracteristicilor procedurii de service se utilizează conceptul de „distribuție probabilistică a timpului de serviciu al cerințelor”.

Si– timpul de service i a-a cerință;

E(S)– timpul mediu de service;

μ=1/E(S)- viteza de solicitare a serviciului.

Trebuie remarcat faptul că timpul pentru deservirea unei aplicații depinde de natura aplicației în sine sau de cerințele clientului și de starea și capacitățile sistemului de service. În unele cazuri este de asemenea necesar să se țină cont probabilitatea de defectare a canalului de serviciu 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.

Factor de utilizare QS

Nμ – rata de service în sistem când toate dispozitivele de service sunt ocupate.

ρ=λ/( Nμ) se numește Factor de utilizare QS , arată câte resurse de sistem sunt utilizate.

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 că sistemul de servicii poate avea nu un canal de servicii, ci mai multe; un sistem de acest fel este capabil să satisfacă 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. Case de marcat in magazin.

Sistemul de servicii poate consta din mai multe tipuri diferite de canale de servicii prin care trebuie să treacă fiecare cerință de service, adică în sistemul de servicii procedurile de service al cerințelor sunt implementate secvenţial . Mecanismul serviciului definește caracteristicile fluxului de cereri de ieșire (servite).

Exemplu. Comisia medicală.

Serviciu combinat - deservirea depozitelor la banca de economii: mai întâi controlorul, apoi casierul. De regulă, 2 controlori per casier.

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

  • repartizarea probabilistica a momentelor de primire a cererilor de servicii (singure sau grup);
  • cerinţe de capacitate sursă;
  • distribuția probabilistică a duratei serviciului;
  • configurarea sistemului de servicii (serviciu paralel, serial sau paralel-serial);
  • numărul și performanța canalelor de difuzare;
  • disciplina la coada.

Principalele criterii de eficacitate a funcționării QS

La fel de principalele criterii de eficacitate a funcţionării sistemelor de aşteptare În funcție de natura problemei care se rezolvă, pot exista:

  • probabilitatea de deservire imediată a aplicației primite (serviciu P =K obs /K post);
  • probabilitatea de refuzare a serviciului cererii primite (P otk =K otk /K post);

Este evident că R obl + P otk =1.

Fluxuri, întârzieri, service. Formula Pollacek-Khinchin

Întârziere – unul dintre criteriile serviciului QS, timpul petrecut de cerere în anticiparea serviciului.

D i– întârziere în coada de cereri i;

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

(cu probabilitatea 1) este întârzierea medie stabilită a unei cereri în coadă;

(cu probabilitatea 1) este timpul mediu în stare de echilibru pe care cerința îl petrece în QS (în așteptare).

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

L(t)– numărul de clienți în sistem simultan t(Q(t) plus numărul de cerințe care sunt în serviciu la momentul respectiv t.

Apoi exponenți (dacă există)

(cu probabilitatea 1) este numărul mediu de cereri în stare de echilibru în coadă;

(cu probabilitatea 1) este numărul mediu de cereri în stare de echilibru din sistem.

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

Dacă ne amintim că ρ= λ/( Nμ), atunci este clar că dacă intensitatea primirii cererilor este mai mare decât Nμ, apoi ρ>1, și este firesc ca sistemul să nu poată face față unui astfel de flux de aplicații și, prin urmare, nu se poate vorbi de d, w, QȘi L.

Cele mai generale și necesare rezultate pentru sistemele de așteptare includ ecuațiile de conservare

Trebuie remarcat faptul că criteriile de mai sus pentru evaluarea performanței sistemului pot fi calculate analitic pentru sistemele de așteptare. M/M/N(N>1), adică sisteme cu fluxuri Markov de clienți și servicii. Pentru M/G/ l pentru orice distribuție Gși pentru alte sisteme. În general, distribuția timpului între sosiri, distribuția timpului de serviciu sau ambele trebuie să fie exponențială (sau un fel de distribuție Erlang exponențială de ordinul k) pentru ca o soluție analitică să fie posibilă.

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

  • debitul absolut al sistemului – А=Р serviciu *λ;
  • debitul relativ al sistemului -

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

.

În Rusia, această formulă este cunoscută ca formula Pollacek. – Khinchin, în străinătate această formulă este asociată cu numele de Ross.

Astfel, dacă E(S) are o valoare mai mare, apoi suprasarcina (măsurată în acest caz ca d) va fi mai mare; ceea ce este de așteptat. Formula relevă și un fapt mai puțin evident: aglomerația 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 astfel: varianța variabilei aleatoare timp de service poate lua o valoare mare (deoarece trebuie să fie pozitivă), adică singurul dispozitiv de service va fi ocupat mult timp, ceea ce va duce la o creștere în coada de așteptare.

Subiectul teoriei cozilor este de a stabili relația dintre factorii care determină funcționalitatea sistemului de așteptare și eficiența funcționării acestuia. În cele mai multe cazuri, toți parametrii care descriu sistemele de așteptare sunt variabile sau funcții aleatorii, astfel încât aceste sisteme sunt denumite sisteme stocastice.

Natura aleatorie a fluxului de aplicații (cerințe), precum și, în cazul general, durata serviciului duce la faptul că în sistemul de așteptare are loc un proces aleatoriu. Prin natura procesului aleator care apar într-un sistem de așteptare (QS) se disting Sisteme Markov și non-Markov . În sistemele Markov, fluxul de cereri de intrare și fluxul de ieșire de cereri deservite (revendicări) sunt Poisson. Fluxurile Poisson facilitează descrierea și construirea unui model matematic al unui sistem de așteptare. Aceste modele au soluții destul de simple, astfel încât cele mai multe dintre aplicațiile binecunoscute ale teoriei cozilor de așteptare folosesc schema Markov. În cazul proceselor non-markoviene, problemele studierii sistemelor de așteptare devin mult mai complicate și necesită utilizarea modelării statistice, a metodelor numerice cu ajutorul unui calculator.

Pentru toate modelele de rețele de așteptare descrise în Capitolul 2, s-a presupus că timpii de deservire a cererilor în diferite etape ale rutei sunt independenți. Aceasta nu reflectă în mod adecvat situația reală din rețelele de transmitere a informațiilor, în care lungimea (volumul) unui mesaj nu se modifică în timpul transmiterii acestuia de la un nod la altul, ceea ce duce la necesitatea studierii rețelelor cu dependente (în special, identice) duratele transmisiei mesajelor pe canale.

În această lucrare, în continuare, se presupune că, alături de durata serviciului, fiecare mesaj este caracterizat și de volumul său propriu, iar independența lor condiționată (cu un volum fix) este asumată față de duratele serviciului, ceea ce ne permite pentru a lua în considerare de fapt dependența duratelor de serviciu ale aceluiași mesaj în diferite etape ale traseului său. În acest caz, ne limităm la principiile de rutare Kelly (rețelele de tip Jackson cu rutare Markov sunt un caz special al modelului luat în considerare).

Se oferă o dovadă alternativă a reprezentării multiplicative pentru probabilitățile de stare staționară a unor astfel de rețele cu noduri de diferite tipuri care implementează așa-numitele discipline de serviciu simetrice și permit dependența cerințelor de serviciu în diferite noduri ale rutei. În același timp, întrebările subtile ale existenței distribuțiilor staționare pentru rețele generale, care fac obiectul cercetărilor independente, nu sunt atinse.

5.2.1 Descrierea rețelei. Notaţie

Luați în considerare o rețea MO, pentru descrierea căreia 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) noduri exponențiale cu mai multe linii cu capacitate de stocare infinită și disciplină FIFO (rețineți că teorema de mai jos poate fi transferată cu ușurință la noduri exponențiale cu o alegere aleatorie a serverului sau a locului în coadă);

1) infinit-liniar;

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

3) monolinie cu capacitate de stocare infinită și disciplina împărțirii uniforme a dispozitivului.

Se notează setul de noduri de tip și numărul de dispozitive din nod - .

Peste tot, ca și înainte, vom desemna variabile aleatoare cu litere mari latine, iar realizările lor - cu literele mici corespunzătoare, iar variabilele și vectorii aleatorii vectoriali vor fi evidențiate cu caractere aldine.

Rețeaua primește Fluxul Poisson intensitatea cererilor, iar fiecare cerere primită este caracterizată de un set de variabile aleatoare independente de variabile aleatoare similare pentru alte solicitări și istoricul rețelei, unde:

Lungimea traseului de ordine aleatorie, de ex. numărul de etape în care va fi deservit;

Rută aleatorie, care este un set de numere de noduri (eventual repetate), trecute secvenţial de aplicaţie la toate L etapele;

Volumele aleatorii la etapele parcurse succesiv ale traseului, în general, sunt diferite în diferite etape;

Duratele aleatorii ale serviciului la etapele parcurse succesiv ale traseului sunt, de asemenea, în general, diferite în diferite etape. Rețineți că, dacă, la un moment dat, o revendicare este deservită la un nod de tip 2 sau 3, atunci durata serviciului pentru această etapă reprezintă timpul în care un client ar fi servit la acest nod dacă nu ar exista alți clienți în el.

Volumul Y poate avea atât o semnificație fizică reală sub forma, de exemplu, a cantității de memorie necesară pentru a scrie un mesaj, cât și poate fi de natură auxiliară, de exemplu, pentru a seta tipurile de solicitări în rețea; în ultimul caz, modelul luat în considerare poate fi interpretat ca o rețea MO cu un set continuu de tipuri de mesaje.

Evident, cu o astfel de descriere a rețelei, volumul și lungimea corespund serviciului cererii în nodul cu numărul . Amintiți-vă că rutele R sunt permise în care numerele pot fi repetate, adică. O reclamație poate fi deservită la același nod de mai multe ori cu timpi de service diferiți.

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

RF comun al traseului și volumelor aplicației la etapele, prin

DF comun condiționat a duratei de serviciu a cererii la etapele cu traseu și volume fixe și după

RF condiționată a duratei deservirii cererii la etapa (la nodul cu numărul ) pentru un traseu și volume fixe.

Despre funcțiile introduse se fac următoarele ipoteze.

(P 1.) Se presupune că timpii de serviciu sunt independenți condiționat de-a lungul rutei, de ex. DF condiționat are forma

(P 2.) Nodurile exponențiale s sunt QS-uri lineare (cu capacitate de stocare infinită) în care ratele de servicii ale oricărui client de către fiecare server sunt egale cu

Astfel, dacă , i.e. la etapa traseului, revendicarea este deservită la nodurile s de tip 0, apoi

Cu alte cuvinte, durata serviciului la 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 parametrul.

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

Atunci densitățile lor, înțelese în sensul obișnuit pentru distribuțiile absolut continue sau în sensul generalizat pentru distribuțiile discrete și mixte, vor fi notate cu , respectiv.

În plus, pentru nodurile de tipuri 1-3, setăm

iar, pentru a scurta notarea rezultatelor, notăm suplimentar prin

densitățile de distribuție condiționată a timpului de încheiere (intensitatea) deservirii unei revendicări cu caracteristici în stadiul de rută (la nodul ) cu condiția ca aceasta să fi fost deservită pentru timp atunci

 

Ar putea fi util să citiți: