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://ww.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
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  5. doi:10.1007/BF01157854
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  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