Sorbanállás-elmélet

A Wikipédiából, a szabad enciklopédiából
Kürtőskalács sor a Miskolci Kocsonyafesztiválon - 2015

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 matematika eszközeivel. A sorbanállási elméletben becslési modellt alkotnak a sorbanállás hosszáról és időtartamá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]

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 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-formulának 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]

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 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]

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 , 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 tartózkodási idők átlagolását.[15]

A Poisson-folyamat szerepe[szerkesztés]

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]

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

Kapcsolódó szócikkek[szerkesztés]

Jegyzetek[szerkesztés]

  1. ↑ Archivált másolat. [2013. január 23-i dátummal az eredetiből archiválva]. (Hozzáférés: 2013. január 26.)
  2. ↑ Sundarapandian, V.. 7. Queueing Theory, Probability, Statistics and Queueing Theory. PHI Learning (2009). ISBN 8120338448 
  3. ↑ TU Berlin: Technische Universität Berlin. [2011. július 19-i dátummal az eredetiből archiválva]. (Hozzáférés: 2013. január 26.)
  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. Bayes Business School (formerly Cass) (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
  9. ↑ http://pass.maths.org.uk/issue2/erlang/index.html
  10. ↑ doi:10.1007/s11134-009-9151-8
  11. ↑ (1909) „The theory of probabilities and telephone conversations”. Nyt Tidsskrift for Matematik B 20, 33–39. o. [2011. október 1-i dátummal az eredetiből archiválva]. (Hozzáférés: 2013. január 26.)  
  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
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Sorbanállás-elmélet&oldid=25084002”