Teoria cozilor

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Diagrama unui sistem de cozi, cu clienți, servere, cozi și fluxuri de trafic de intrare și de ieșire

Teoria cozii este studiul matematic al liniilor de așteptare (sau a cozilor ) și a proceselor conexe, cum ar fi procesul de sosire a cozii, așteptarea (în esență un proces de stocare) și procesul de servicii. Poate fi aplicat la o mare varietate de probleme, în special în domeniile transportului , telecomunicațiilor , prestării de servicii (de exemplu, în domeniul asistenței medicale ) și operațiunilor comerciale . De obicei considerată o ramură a cercetării operaționale , originile sale datează din 1909 când inginerul danez Agner Krarup Erlang a publicat un articol intitulat Teoria probabilității și conversațiile telefonice referitoare la așteptarea în apelurile telefonice.

Descriere

Notare Kendall

În 1953 , David George Kendall a introdus notația A / B / C , extinsă ulterior ca 1/2/3/4/5/6 pentru a oferi o descriere imediată a modelului sistemului de coduri:

  1. Un cod care descrie distribuția probabilității timpilor de sosire a locurilor de muncă în sistem; codurile sunt:
  2. Un cod care reprezintă distribuția probabilității timpilor de serviciu a lucrărilor , utilizând aceleași simboluri.
  3. Numărul de canale de servicii, cunoscut și sub numele de servere sau servere (de exemplu, oficii poștale).
  4. Dimensiunea maximă a sistemului, care corespunde sumei dintre joburile din coadă și joburile din canalele de servicii; când se atinge maximul, sosirile ulterioare sunt refuzate. Dacă nu este indicat, dimensiunea înseamnă infinit.
  5. Mărimea populației de la care pot ajunge clienții; acest lucru limitează rata sosirilor, cu cât sunt mai multe locuri de muncă în coadă, cu atât mai puține locuri de muncă sunt disponibile pentru a intra în sistem. Dacă nu este indicat, dimensiunea înseamnă infinit.
  6. Ordinea în care sunt servite joburile din coadă (implicit este FIFO):
    • First Come First Served ( FCFS ) (sau First In First Out - FIFO ) (primul care ajunge este primul servit);
    • Last Come First Served ( LCFS ) (sau Last In First Out - LIFO ) (ultimul care ajunge este servit primul);
    • Serviciu în ordine aleatorie ( SIRO );
    • PRI (există un sistem de selectare a utilizatorilor în funcție de prioritate (un exemplu este camera de urgență, cu coduri alb, verde și roșu).

Cele mai studiate modele sunt sistemele M / M / s / K, cu sek care pot asuma valori diferite (cel mai simplu model este M / M / 1 , cu un singur server și capacitate nelimitată): acest lucru se datorează faptului că distribuția exponențială Intervalelor de sosire și serviciu permite studierea sistemelor de așteptare ca procese de naștere și deces .

Sistemele de cozi și teoria traficului

Pictogramă lupă mgx2.svg Același subiect în detaliu: Trafic (telecomunicații) .
Comparație între tehnicile FIFO și LIFO.
Lanțuri Markov pentru sisteme de coadă cu stări, tranziție de stări și probabilități relative, utilizate pentru modelarea sistemelor de coadă

Sistemele de coadă pot fi modelate prin lanțuri Markov cu timp continuu sau cu sisteme dinamice caracterizate de state N, probabilitate de stat egală cu P (Ni) și probabilitate de tranziție de la o stare la alta egală cu produsul între frecvența de tranziție f și intervalul de timp dt, depinzând doar de starea actuală a sistemului și nu de cele anterioare (sistem fără memorie). Starea reprezintă situația în care sistemul se află în ceea ce privește variabilele luate ca referință (în general nu univocă), iar evoluția sistemului este mapată cu o succesiune de salturi între stările în sine. Cunoscute frecvențele de tranziție, adică probabilitatea de tranziție a stării, este posibilă derivarea probabilităților de stare P (Si) prin rezolvarea lanțului Markov; din cunoașterea acestor probabilități este posibil să se deriveze parametrii de performanță de interes, cum ar fi traficul eliminat, probabilitatea de respingere, timpul de așteptare etc.

Definind fluxul care vine din starea i-a spre starea k-th ca produs P (Sk) * qk, i între probabilitatea stării în k și frecvența de tranziție către starea k, pentru calcularea probabilității stării vom folosește condiția exprimată de legea conservării fluxurilor care afirmă că suma fluxurilor de intrare este egală cu suma fluxurilor de ieșire dintr-o stare. Prin aplicarea acestui principiu fiecărei stări obținem un sistem de ecuații S în S necunoscut (probabilitățile stării) la fel de multe ca stările S; ecuațiile nu sunt toate independente una de cealaltă, prin urmare soluția sistemului este imposibilă (determinant nul) decât dacă o ecuație este înlocuită cu suma probabilităților stărilor egale cu una.

Un tip de lanțuri Markov sunt lanțurile de naștere și moarte în care tranzițiile sunt permise numai între straturile „adiacente” și pentru care este identificabilă o linie de tăiere a fluxului. Un sistem de coadă se numește Markovian dacă poate fi modelat printr-un lanț de naștere și moarte Markov cu un proces exponențial negativ de sosire și serviciu a parametrilor λ (naștere) și υ (moarte) și valorile așteptate corespunzătoare egale cu 1 / λ și 1 / υ.

Într-un sistem S-Servants, devine fundamental un parametru de performanță numit Blocking Probability, care depinde de numărul S de servitori și de traficul de intrare oferit Ao. Acest parametru este calculat prin referire la formula Erlang B ale cărei valori, pentru S și A fixe, sunt exprimate în formă tabelată. La fel de interesantă este și probabilitatea de așteptare în coadă exprimată în funcție de numărul de servere și de traficul oferit prin formula Erlang C. Într-o rețea de telecomunicații, sistemele de coadă și problemele legate de gestionarea traficului sunt prezente în stiva de protocol a sistemelor de procesare, transmisie și recepție a fluxului de informații, adică terminalele gazdă și subsistemele de comutare interne ( routere ) și mai mult în general în toate dispozitivele de rețea care au trafic de intrare.

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității Tesauro BNCF 22124 · LCCN (EN) sh85109832 · GND (DE) 4255044-0 · BNF (FR) cb12647707b (dată) · NDL (EN, JA) 00.567.524