From Wikipedia, the free encyclopedia
Teoria statului la coadă sau teoria așteptării este studiul matematic al liniilor de așteptare, sau cozi. Modelul unei așteptări (unui stat la coadă) este construit astfel încât lungimea cozii și timpul de așteptare pot fi prezise. Teoria așteptării este, în general, inclusă în cercetarea operațională, deoarece rezultatele sunt adesea folosite în luarea deciziilor de business în funcție de resursele necesare.
Teoria așteptării își are originea în cercetările lui Agner Krarup Erlang, atunci când a creat modele pentru a descrie schimbarea telefoanelor în Copenhaga. Ideile au avut multe aplicații, inclusiv în telecomunicații, ingineria traficului, de calcul[1] și, în special în ingineria industrială, în proiectarea de fabrici, magazine, birouri și spitale, precum și în managementul proiectelor.[2][3]
Nodurile unei cozi cu un singur rând sunt de obicei descrise cu ajutorul notației lui Kendall în formă de O/S/C, în care O descrie timpul dintre sosirile la coadă, S dimensiunea deservirilor și C numărul de servere pe nod.[4][5] În teoria așteptării, multe teoreme pot fi demonstrate prin reducerea cozilor la sisteme matematice cunoscute sub numele de lanțuri Markov, descrise pentru prima dată de către Andrei Markov în 1906.[6]
Inginerul danez Agner Krarup Erlang și-a publicat prima sa lucrare despre ceea se numește acum teoria așteptării, în 1909.[7][8][9] El a modelat numărul de apeluri care sosesc la un schimb într-un proces Poisson și a rezolvat coada M/D/1 în 1917 și modelul M/D/k de așteptare la coadă în 1920.[10] În notația Kendall:
Coada M/M/1 este un model simplu, în care un singur server servește locuri de muncă care sosesc potrivit unui proces Poisson și au cereri de servicii distribuite exponențial. Într-o coadă M/G/1, G înseamnă general și indică o distribuție de probabilitate arbitrară. Modelul M/G/1 a fost rezolvată de Felix Pollaczek în 1930,[11] o soluție mai târziu reformulată în termeni probabilistici de Aleksandr Khinchin și acum cunoscută sub numele de formula Pollaczek–Khinchine.
După 1940, teoria cozilor de așteptare a devenit un domeniu de cercetare de interes pentru matematicieni. În 1953, David George Kendall a rezolvat coada GI/M/k și a introdus o notație modernă pentru cozi, acum cunoscută sub numele de notația Kendall. În 1957 Pollaczek a studiat GI/G/1, folosind o ecuație integrală. John Kingman a dat o formula pentru timpul mediu de așteptare într-o coadă G/G/1: formula Kingman.
Metoda matricei geometrice și metoda matricei analitice au permis luarea în considerare a unor cozi cu intrasosire distribuită de tip fază și cu distribuții ale timpului de deservire. Probleme precum ar fi măsurarea performanței pentru o coadă M/G/k rămâne o problemă deschisă.
Diferite politici de planificare pot fi folosite în nodurile de așteptare:
Rețele de cozi de așteptare sunt sisteme în care un număr de cozi sunt conectate la ceea ce este cunoscut sub numele de rutarea clientului. Atunci când un client este deservit la un nod, el se poate alătura unui alt nod și unei alte cozi pentru a fi servit, sau poate părăsi rețeaua.
Pentru rețelele cu m noduri, starea sistemului poate fi descrisă printr-un vector m–dimensional (x1,x2,...,xm) unde xi reprezintă numărul de clienți la fiecare nod.
Primele rezultate semnificative în acest domeniu au fost rețelele Jackson,[17][18] pentru care există o distribuție staționară eficientă și o analiză a valorii medii[19], care permit măsurători medii, cum ar fi calculul timpilor de tranzitare și de ședere.[20] Dacă numărul total de clienți în rețea rămâne constant, rețeaua se numește rețea închisă și s-a prezentat o formă de distribuție staționară în teorema Gordon–Newell.[21] Acest rezultat a fost extins la rețeaua BCMP[22] în care o rețea cu un timp foarte general de deservire, regimurile și rutarea clienților sunt prezentate ca un produs cu formă de distribuție staționară. Constanta de normalizare poate fi calculată cu algoritmul lui Buzen, propus în 1973.[23]
Rețele de clienți au fost de asemenea investigate, rețelele Kelly, în care clienții din diferite clase experimentează diferite nivele de prioritate la diferite noduri de servicii.[24] Un alt tip de rețele sunt G-rețele, propus pentru prima dată de Erol Gelenbe în 1993:[25] Aceste rețele nu presupun exponențială timp distribuții, cum ar fi clasic Jackson Rețea.
În rețelele discrete de timp în care există o constrângere la care nodurile de deservire pot fi active la un moment dat, algoritmul programării max-greutate alege o politica de deserviri pentru a oferi transfer optim în cazul în care fiecare loc de muncă vizitează doar un singur nod de deservire. În cel mai general caz în care locurile de muncă pot vizita mai mult de un nod, rutarea de contrapresiune oferă transfer optim. Un programator de rețea trebuie să aleagă un algoritm de așteptare, care afectează caracteristicile unei rețele mai mari. A se vedea, de asemenea, programarea stohastică, pentru mai multe detalii despre programarea sistemelor de așteptare.
Limite medii de câmp iau în considerare limitarea comportamentul limitativ al măsurătorii empirice (proporția cozilor în stări diferite), când numărul cozilor (m de mai sus) tinde spre infinit. Impactul altor cozi asupra oricărei cozi în rețea este aproximată printr-o ecuație diferențială. Modelul determinist converge spre aceeași distribuție staționară ca și modelul original.[26]
Limitele fluide sunt analogi determiniști continui ai rețelelor de așteptare obținute luarea limitei când procesul este scalat în timp și spațiu, permițând obiecte eterogene. Această traiectorie scalată converge spre ecuație deterministă care permite demonstrarea stabilității sistemului. Este cunoscut faptul că o rețea de cozi poate fi stabilă, dar are o limită fluidă instabilă.[27]
Într-un sistem cu rate mari de ocupare (utilizare aproape de 1) aproximarea unui trafic intens poate fi folosită pentru a aproxima lungimea procesului de așteptare prin reflectarea mișcării browniene (RMB),[28] procesul Ornstein–Uhlenbeck sau, mai general, procesul de difuzie.[29] Numărul de dimensiuni ale RMB este egal cu numărul nodurilor de așteptare și difuzia este limitată orthantul nenegativ.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.