Sorbanállás-elmélet
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ésAz 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ésA 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ésA 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ésEgy 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- https://web.archive.org/web/20130123204351/http://eventhelix.com/RealtimeMantra/CongestionControl/queueing_theory.htm
- https://web.archive.org/web/20111207044006/http://queueing-systems.ens-lyon.fr/
- http://www.ee.cityu.edu.hk/~zukerman/classnotes.pdf
- Pollaczek–Khinchine-formula
- Erlang
- Jackson-hálózat
- Sűrűségfüggvény
- Skálaparaméter
- Alakparaméter
- Eloszlásfüggvény
- Valószínűségszámítás
- Statisztika
Jegyzetek
szerkesztés- ↑ Archivált másolat. [2013. január 23-i dátummal az eredetiből archiválva]. (Hozzáférés: 2013. január 26.)
- ↑ Sundarapandian, V.. 7. Queueing Theory, Probability, Statistics and Queueing Theory. PHI Learning (2009). ISBN 8120338448
- ↑ 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.)
- ↑ Lawrence W. Dowdy, Virgilio A.F. Almeida, Daniel A. Menasce: Performance by Design: Computer Capacity Planning By Example pp. 480
- ↑ Schlechter, Kira. „Hershey Medical Center to open redesigned emergency room”, The Patriot-News , 2009. március 2.
- ↑ 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)
- ↑ Tijms, H.C, Algorithmic Analysis of Queues, Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003
- ↑ doi:10.1214/aoms/1177728975
- ↑ http://pass.maths.org.uk/issue2/erlang/index.html
- ↑ doi:10.1007/s11134-009-9151-8
- ↑ (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.)
- ↑ a b Flood, J.E. Telecommunications Switching, Traffic and Networks, Chapter 4: Telecommunications Traffic, New York: Prentice-Hall, 1998.
- ↑ Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory.
- ↑ Penttinen A., Chapter 8 – Queueing Systems, Lecture Notes: S-38.145 - Introduction to Teletraffic Theory
- ↑ doi:10.1016/0169-7552(93)90073-D