Sorbanállás-elmélet

A Wikipédiából, a szabad enciklopédiából
(Sorbanállási elmélet szócikkből átirányítva)

A sorbanállás-elmélet különböző folyamatok eseményeivel kapcsolatos várakozási sorokat, sorbanállási időket a kiszolgálásra, és ezek összefüggéseit tárgyalja az alkalmazott matematikai eszközeivel. A sorbanállási elméletben becslési modellt alkotnak a sorbanállás hosszáról és időtartartamáról, és a kiszolgálás sikerességéről.[1] A sorbanállási elméletet általában az operációkutatás ágának tekintik, mert az eredményeket gyakran felhasználják üzleti döntéseknél, ahol az erőforrások becslése nem elhanyagolhatók.[2] A sorbanállási elmélet kialakulásának kezdete Agner Krarup Erlang (1878 -1929), dán matematikus nevéhez fűződik, aki a koppenhágai telefonközpont működésére készített modellt. Ez a modell inspirálta a sorbanállási problémák kezelését a távközlésben, a forgalomtervezésnél, számítástechnikában, kereskedelemben, és kórházaknál.[3][4] [5][6]

Egyszerű csomóponti sorbanállás[szerkesztés | forrásszöveg szerkesztése]

Az egyszerű csomóponti sorbanállásokat a Kendall-féle jelöléssel jellemeznek A/B/C formában, ahol A írja le a beérkezési időközt, B a munka nagyságát (kiszolgálási idő), és C a kiszolgálók számát.[7][8] Agner Krarup Erlang, dán mérnök, aki a koppenhágai telefonközpontban dolgozott, 1909-ben publikálta először a dolgozatát a sorbanállási elméletről. Poisson-folyamattal modellezte a központba érkező telefonhívások számát, és megalkotta a az M/D/1-típusú sorbanállás (1917), és az M/D/k-típusú sorbanállás (1920) modelljeit.[9][10][11] A Kendall-féle jelölés:

  • M, a Markov rövidítése, és azt jelenti, hogy a beérkezések a Poisson-folyamat szerint történnek,
  • D jelentése : determinisztikus, és azt jelenti, hogy kiszolgálás idő egy határozott érték,
  • k jelentése: a kiszolgálók száma a sorbanállási csomópontokon (k = 1, 2,...). Ha egy csomóponton több munka van, mint kiszolgáló, akkor a munkák fognak sorbanállni és várni a kiszolgálásra.

Az M/M/1-típusú sorbanállás egy egyszerű modell, ahol egy kiszolgáló látja el a munkákat, melyek a Poisson-folyamat szerint érkeznek, és exponenciális eloszlásúak. Az M/G/1-típusú sorbanállásnál, a G (general), az általánost jelenti és azt jelenti, hogy a valószínűségi eloszlás tetszőleges. Ezt a típust Pollaczek–Khinchine-formulanak is hívják. A II.Világháború után a sorbanállási elmélet a matematikusok kutatási területe lett. A modern csomagkapcsolt hálózatokban használatos sorbanállási elméletet Leonard Kleinrock dolgozta ki 1960-ban.

Sorbanállás a távközlésben[szerkesztés | forrásszöveg szerkesztése]

A nyilvános kapcsolt távbeszélő-hálózatot (PSTN) úgy tervezték, hogy a hívások kis veszteséggel jöjjenek létre. A veszteséget a szolgáltatás hatékonysága mérőszámmal minősítették, mely megmutatta, hogy ha nem volt elegendő kapacitás, akkor a hívást visszautasították vagy elveszett. Egy alternatív megoldás, hogy a rendszer egy alternatív útvonalra irányítja a hívást, annak ellenére, hogy a rendszernek véges kapacitása van. A sorbanállás alkalmazása lehetővé teszi, hogy a PSTN-ben a bejövő hívás ne vesszen el, hanem sorbanáll, amíg lesz szabad útvonal, vagy korábban szabad kezelő.[12]

A sorbanállási technika meghatározza, hogyan kezelje a rendszer a bejövő hívásokat. Meghatározza a módot, hogyan szolgálja ki az ügyfelet a központ, a meglévő erőforrások figyelembevételével.[13] A következőkben négy sorbanállási technikát mutatunk be:

  • FIFO (First in first out=Első be, első ki): A legrégebb várakozót kapcsolják először.
  • LIFO (Last in first out= utolsó be, első ki): A legrövidebb várakozási idővel rendelkező hívást kapcsolják először. Így működnek a számítógépek verem (számítástechnika) memóriái is.
  • Processzor megosztás: az ügyfeleket egyenlő módon szolgálják ki. Mindenkinél hasonló a várakozási idő.
  • Prioritás: magas prioritással rendelkező ügyfelet kapcsolják először.

A központokban a sorbanállást Markov-lánccal modellezik, állapotegyenletekkel. A bejövő hívásokat Poisson-eloszlással modellezik.[12] A klasszikus sorbanállási elmélet komplex számításokkal határozza meg a várakozási időket, a kiszolgálók kihasználtságát, és más paramétereket, melyek a sorbanállás minőségét befolyásolják.[14]

Sorbaállító hálózatok[szerkesztés | forrásszöveg szerkesztése]

A sorbaállító hálózatok olyan rendszerek, melyek tetszőleges, de véges számú m sorbaállási lehetőséget tartalmaznak. A hálózat állapota leírható vektorokkal \scriptstyle{(k_1,k_2,\ldots,k_m)}, ahol ki az ügyfelek száma az i-ik sorban. Nyílt hálózatokban, az ügyfelek beléphetnek és távozhatnak, míg zárt hálózatban az ügyfelek száma rögzített. Az első jelentős eredmény a Jackson-hálózat volt, mely a szorzat-típusú egyensúlyi eloszlással és a várható érték analízissel működik, mely lehetővé teszi az áteresztőképesség és a tartozkodási idők átlagolását.[15]

A Poisson-folyamat szerepe[szerkesztés | forrásszöveg szerkesztése]

Egy használható sorbanállási modell a valós helyzetet modellezi elegendő pontossággal és analitikusan kezelhető. A Poisson-folyamat és más exponenciális valószínűségi eloszlások kielégítik ezeket a követelményeket. A Poisson-folyamat a véletlenszerű eseményeket memóriamentes folyamatként kezeli, ami azt jelenti, hogy a különböző időintervallumoknál nem számít, hogy korábban mi történt. Hasonló a helyzet az exponenciális eloszlásnál is.

Irodalom[szerkesztés | forrásszöveg szerkesztése]

  • Sundarapandian, V: Queueing Theory. Probability, Statistics and Queueing Theory. (hely nélkül): . PHI Learning. 2009 ISBN 8120338448  

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  1. http://www.eventhelix.com/RealtimeMantra/CongestionControl/queueing_theory.htm
  2. Sundarapandian, V.. 7. Queueing Theory, Probability, Statistics and Queueing Theory. PHI Learning (2009). ISBN 8120338448 
  3. TU Berlin: Technische Universität Berlin
  4. Lawrence W. Dowdy, Virgilio A.F. Almeida, Daniel A. Menasce: Performance by Design: Computer Capacity Planning By Example pp. 480
  5. Schlechter, Kira. „Hershey Medical Center to open redesigned emergency room”, 2009. március 2. 
  6. Mayhew, Les, Smith, David. Using queuing theory to analyse completion times in accident and emergency departments in the light of the Government 4-hour target. Cass Business School (2006. December) 
  7. Tijms, H.C, Algorithmic Analysis of Queues", Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003
  8. doi:10.1214/aoms/1177728975
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  9. http://pass.maths.org.uk/issue2/erlang/index.html
  10. doi:10.1007/s11134-009-9151-8
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  11. (1909.) „The theory of probabilities and telephone conversations”. Nyt Tidsskrift for Matematik B 20, 33–39. o.  
  12. ^ a b Flood, J.E. Telecommunications Switching, Traffic and Networks, Chapter 4: Telecommunications Traffic, New York: Prentice-Hall, 1998.
  13. Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory.
  14. Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory
  15. doi:10.1016/0169-7552(93)90073-D
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand