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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Search