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

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

A sorbanállási elméletben az M/M/1-típusú sorbanállásra jellemző, hogy egy kiszolgáló van, a rendszerbe érkezések a Poisson-folyamat szerint történnek, és a kiszolgálási idő exponenciális eloszlású. A megnevezés (M/M/1) a Kendall-féle jelölés szerint történt. Ez a típus a legegyszerűbb modell.[1]

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

A sorbanállás sztochasztikus folyamat, melynek állapottere {0,1,2,3...}, ahol a rendszerben lévő sorbanállók száma megfelel a számoknak.

  • Az érkezési sebesség λ, a Poisson-folyamatnak megfelelően történik, és az i - i+1 átmenet jelzi, hogy új sorbanálló tag érkezett,
  • A kiszolgálási idő exponenciális eloszlású, μ paraméterrel,
  • A sor elején egy kiszolgáló látja el a beérkezőket, a FCFS szerint (aki elsőnek jött, elsőnek lesz kiszolgálva); Amikor a kiszolgálás megtörtént, az ügyfél (entitás) elhagyja a rendszert, és eggyel csökken a rendszerben az ügyfelek száma,
  • A tároló (a kiszolgálás helye) végtelen nagy, így nincs korlátja a belépő ügyfelekre nézve.

Ezt a modellt a folytonos idejű Markov-lánccal lehet leírni, átmeneti mátrixxal:

Q=\begin{pmatrix}
-\lambda & \lambda \\
\mu & -(\mu+\lambda) & \lambda \\
&\mu & -(\mu+\lambda) & \lambda \\
&&\mu & -(\mu+\lambda) & \lambda &\\
&&&&\ddots
\end{pmatrix}

Ez ugyanaz a mátrix, mint amivel a születés-halálozás folyamatot írják le. Az állapottér {0,1,2,3,...}. MM1 queue state space.svg

Az átmenet képlete[szerkesztés | forrásszöveg szerkesztése]

Az M/M/1-típusú sorbanállási modellnél a t időtől függő valószínűségi tömegfüggvény írja le, hogy a modell egy adott állapotban van. Tegyük fel, hogy a sorbanállási folyamat a kezdetben i állapotban van, és a pk(t) valószínűség t időben , és k állapotban:[2]

p_k(t)=e^{-(\lambda+\mu)t}[ \rho^{(k-i)/2} I_{k-i}(at) + \rho^{(k-i-1)/2} I_{k+i+1}(at) + (1-\rho) \rho^{k} \sum_{j=k+i+2}^{\infty} \rho^{-j/2}I_j(at) ]

ahol \rho=\lambda/\mu, a=2\mu\sqrt{\rho} és Ik a módosított elsőfajú Bessel függvény.

Állandósult eloszlás[szerkesztés | forrásszöveg szerkesztése]

Csak λ<μ esetben stabil a modell. Ha átlagosan, a beérkezések gyorsabban történnek, mint a kiszolgálások, akkor a sor végtelen nagyra nő, és a rendszernek nem lesz állandósult eloszlása. Az állandósult eloszlás a korlátozó tényező a nagy t-kre.

A rendszerben lévő ügyfelek száma[szerkesztés | forrásszöveg szerkesztése]

Annak a valószínűsége, hogy az állandósult folyamat i állapotban van (i ügyfelet tartalmaz, beleértve a kiszolgálás alatt lévőket is):[3]

\pi_i=(1-\rho)\rho^i.\, Látható, hogy az ügyfelek száma a geometriai eloszlást követi 1−ρ paraméterrel. Így az ügyfelek átlagos száma: ρ/(1−ρ). .[4]

A kiszolgáló foglaltsági periódusa[szerkesztés | forrásszöveg szerkesztése]

A kiszolgáló foglaltsági periódusa az az idő, mely az ügyfél – az üres rendszerbe való -beérkezésének pillanatától számít addig, amíg az ügyfél elhagyja a rendszert, mely újra üres lesz. A foglaltsági periódus valószínűségi sűrűségfüggvénye: [5][6][7] f(t)=\begin{cases}
\frac{1}{t\sqrt{\rho}}e^{-(\lambda+\mu)t}I_1(2t\sqrt{\lambda\mu}) & t>0\\
0 & \text{máskülönben}\end{cases} ahol I1 a módosított elsőfajú Bessel függvény,Laplace-transzformációt alkalmazva[8] , és invertálva az eredményt.[9] Az M/M/1-típusú sorbanállási modell foglaltsági periódusának Laplace-transzformáltja:[10]

\mathbb E( e^{-\theta F} )= \frac{1}{2 \lambda}(\lambda + \mu + \theta - \sqrt{(\lambda + \mu + \theta)^2 - 4 \lambda \mu})

Válaszidő[szerkesztés | forrásszöveg szerkesztése]

Az átlagos válaszidő (a teljes idő, amit az ügyfél a rendszerben tölt) a Little-törvény segítségével számolható ki, mivel 1/(μ'−λ). Az átlagos várakozási idő: 1/(μ − λ) − 1/μ = ρ/(μ − λ).

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

  • Khintchine, A. Y: Mathematical theory of a stationary queue. (hely nélkül): Matematicheskii Sbornik 39 (4):. 1932. 73–84. o.  
  • Response time distributions in queueing network models. (hely nélkül): Computer Science. 1993.  

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

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

  1. http://www.win.tue.nl/~iadan/que/h4.pdf
  2. Queueing Systems Volume 1: Theory (1975). ISBN 0471491101 
  3. Harrison, Peter. Performance Modelling of Communication Networks and Computer Architectures. Addison–Wesley, 172–173. o (1992) 
  4. doi:10.1023/A:1013913827667
  5. doi:10.1007/BF01157854
  6. (1958.) „Many server queueing processes with Poisson input and exponential service times”. Pacific J. Math. 8 (1), 87-118. o.  
  7. 2.12 Busy-Period Analysis, Fundamentals of Queueing Theory. Wiley. ISBN 1118211642 
  8. Adan, Ivo: Course QUE: Queueing Theory, Fall 2003: The M/M/1 system. (Hozzáférés: 2012. augusztus 6.)
  9. Stewart, William J.. Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton University Press (2009). ISBN 0-691-14062-6 
  10. Asmussen, Søren. Applied Probability and Queues. Springer (2003). ISBN 0387002111