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

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

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

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

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

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

Kapcsolódó szócikkek

Jegyzetek

↑ 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

[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.)

[sun-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”, The Patriot-News , 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)

[tijms-7] Tijms, H.C, Algorithmic Analysis of Queues, Chapter 9 in A First Course in Stochastic Models, Wiley, Chichester, 2003

[8] :10.1214/aoms/1177728975

[9] ttp://pass.maths.org.uk/issue2/erlang/index.html

[10] :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.)

[Flood,_J.E._Telecommunications_Switching_1998-12] Flood, J.E. Telecommunications Switching, Traffic and Networks, Chapter 4: Telecommunications Traffic, New York: Prentice-Hall, 1998.

[penttinen-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] :10.1016/0169-7552(93)90073-D

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]