M/G/1-típusú sorbanállás

A Wikipédiából, a szabad enciklopédiából

A sorbanállás-elméletben az M/G/1-típusú sorbanállás olyan sorbanállási modell, ahol a beérkező entitások véletlenszerűek (M), a Poisson-folyamat szerint, a szolgáltatási idő (G) általános eloszlású, és egy kiszolgáló van.[1]. A jelölés a Kendall-féle jelölést követi, és ennek a kiterjesztése a M/M/1-típusú sorbanállás, ahol a szolgáltatási idő exponenciális eloszlású. Az M/G/1-típusú sorbanállás modellezi a rögzített fejű merevlemez működését.[2]

A modell működése[szerkesztés | forrásszöveg szerkesztése]

A sorbanállás sztochasztikus folyamat, melynek állapottere {0,1,2,3...}, ahol a sorbanállók száma megfelel a számoknak. Az i - i+1 átmenet jelzi, hogy új sorbanálló tag érkezett. Az ilyen érkezések közötti időnek exponenciális eloszlása van, λ paraméterrel. Az i - i-1 átmenet jelzi, hogy egy tagot kiszolgáltak a sorból, és távozott. A kiszolgáláshoz szükséges idő általános eloszlási függvény szerint történik. Az érkezés és kiszolgálás közötti idő hossza valószínűségi változó, és feltételezhetően független más paraméterektől.

Sorbanállás hossza[szerkesztés | forrásszöveg szerkesztése]

Az állandosult sor hossz-eloszlásának generátor függvényét a Pollaczek–Khinchine tarnszformáció adja meg:[2]

\Pi(z) = \frac{(1-\rho)(1-z)G(z)}{G(z)-z}

ahol G(z)=B^* [[\lambda(1-z)] and B^* a kiszolgálási idő eloszlásának Laplace–Stieltjes transzformációja. A Pollaczek–Khinchine formula megadja a rendszer átlagos sorbanállási hosszát és az átlagos várakozási időt.[3][4] Mivel az érkezéseket a Poisson-folyamat határozza meg, az érkezési elmélet érvényes.

M/G/1 típusú Markov-lánc[szerkesztés | forrásszöveg szerkesztése]

Tekintsük az M/G/1 sorbanállás beágyazott Markov-láncát, ahol az érkezés után azonnali időpontokat nézzük. Az ügyfélt zéró másodperc alatt kiszolgálják. A távozások között, 0, 1, 2, 3,…érkezés lehetséges. Így a lánc i –ből i-1, i, i+1, i+2…be mozoghat, ….[5] A beágyazott Markov-lánc átmeneti mátrixa:

P = \begin{pmatrix}
a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \\
a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \\
0   & a_0 & a_1 & a_2 & a_3 & \cdots \\
0   & 0   & a_0 & a_1 & a_2 & \cdots \\
0   & 0   & 0   & a_0 & a_1 & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{pmatrix}

ahol:

a_v = \int_0^\infty e^{-\lambda u} \frac{(\lambda u)^v}{v!} \text{d}F(u) ~\text{ for } v \geq 0

és F(u) a kiszolgálási idő eloszlása, λ a Poisson-féle érkezési ráta a sorba. A Markov-láncot a generátor mátrixxal, vagy mátrix blokkal, az M/G/1-típusú Markov-láncnak hívják, mely kifejezést M. F. Neuts-től származik.[6][7][8] Egy stacionárius M/G/1-típusú Markov-lánc a Ramaswami-formulaval számítható.[8]

Több kiszolgáló esete[szerkesztés | forrásszöveg szerkesztése]

Egy M/G/k-típusú sorbanállás, ahol k>1 számú kiszolgáló van, még nyitott probléma.[9] Ebben a modellben, az érkezések Poisson-folyamat szerint történnek, és bármely kiszolgáló elláthatja a bejövőt. Különböző szerzők számos közelítést alkottak a sorbanállás átlagos nagyságára, az átlagos késleltetési időre és az állandó eloszlásra.[10]

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

  • Ross, Sheldon M.; Seshadri, Sridhar: Hitting time in an M/G/1 queue. (hely nélkül): Journal of Applied Probability:. 1999. 
  • Stewart, William J: Probability, Markov chains, queues, and simulation. (hely nélkül): Princeton University Press. 2009. ISBN 0691140626  

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

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

  1. Gittins, John C. (1989). Multi-armed Bandit Allocation Indices. John Wiley & Sons. p. 77. ISBN 0471920592
  2. ^ a b Harrison, Peter; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley.
  3. doi:10.1007/BF01194620
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  4. Khintchine, A. Y (1932.). „Mathematical theory of a stationary queue”. Matematicheskii Sbornik 39, 73–84. o. Hozzáférés ideje: 2011. július 14.  
  5. Stewart, William J.. Probability, Markov chains, queues, and simulation. Princeton University Press (2009). ISBN 0-691-14062-6 
  6. Neuts, M. F . (1989.). „Structured Stochastic Matrices of M/G/1 Type and Their Applications”, New York, Kiadó: Marcel Dekk..  
  7. doi:10.1080/15326349808807483
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  8. ^ a b doi:10.1093/acprof:oso/9780198527688.001.0001
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  9. doi:10.1007/s11134-009-9147-4
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  10. doi:10.1007/s11134-008-9073-x
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand