II.1. Az M/M/1 típusú klasszikus sorbanállási rendszer

II.1. Az M/M/1 típusú klasszikus sorbanállási rendszer

Az M/M/1 rendszer a legegyszerűbb nemtriviális rendszer. Emlékeztetünk rá, hogy ebben az esetben a beérkezési folyamat $\lambda$ paraméterű Poisson-folyamat, vagyis a beérkezési idközök $\lambda$ paraméterű exponenciális eloszlású valószínűségi változók. A kiszolgálási idők $\mu$ paraméterű exponenciális eloszlású valószínűségi változók. Feltesszük továbbá, hogy a beérkezési időközök, és a kiszolgálási idők egymástól független valószínűségi változók. Jelölje most

időpillanatban a rendszerben tartózkodó igények számát, és azt mondjuk, hogy a rendszer a

állapotban van, ha

. Mivel a fellépő valószínűségi változók exponenciális eloszlásúak, vagyis emlékezet nélküliek, az

folytonos idejű Markov-lánc lesz. Vizsgáljuk meg a rendszer állapotváltozásainak valószínűségeit egy adott

időtartam alatt:

$\begin{displaymath} \eqalign{ p_{k,k+1}(h)=&\left(\lambda h+o(h)\right)\left(1... ...ght)^k\left(\mu h+o(h)\right)^{k-1},\cr &k=0,1,2,...\ .\cr} \end{displaymath}$

Az összeg első tagja annak a valószínűsége, hogy a rendszerben egy igény érkezett, és nem szolgáltak ki egyet sem. Az összeg második tagja pedig annak a valószínűségét adja, hogy a rendszerbe 2 vagy több igény érkezett, és a beérkezettnél eggyel kevesebb került kiszolgálásra. De ez a valószínűség éppen

-val egyenlő, így

$\begin{displaymath} p_{k,k+1}(h) = \lambda h+o(h). \end{displaymath}$

Az előbbiekhez hasonlóan írható fel annak valószínűsége, hogy a rendszer

állapotban volt és a

időtartam után a

állapotba került:

$\begin{displaymath} \eqalign{ p_{k,k-1}(h)&=\left(\mu h+o(h)\right)\left(1-(\l... ...ight)^{k-1}\left( \mu h+o(h)\right)^k \cr &=\mu h+o(h).\cr} \end{displaymath}$

Könnyen látható továbbá, hogy

$\begin{displaymath} p_{k,j}=o(h),\qquad\mid k-j\mid\geq 2. \end{displaymath}$

Tehát egy olyan születési-halálozási folyamattal van dolgunk, amit a születési és halálozási intenzitások alábbi megválasztásával lehet jellemezni:

$\begin{displaymath}\lambda_k=\lambda,\qquad k=0,1,2,...,\end{displaymath}$

$\begin{displaymath}\mu_k=\mu , \qquad k=1,2,3... .\end{displaymath}$

Vagyis az összes születési intenzitás $\lambda$ , az összes halálozási intenzitás pedig $\mu$ . Feltesszük, hogy végtelen hosszúságú sorok is létrejöhetnek, és az igények kiszolgálása FIFO elv alapján történik. Helyettesítsük be az intenzitásokat a (3)-ba, így a következő adódik:

$\begin{displaymath} P_k=P_0\prod_{i=0}^{k-1}{\lambda \over \mu }, \end{displaymath}$

vagyis

$\begin{displaymath} P_k=P_0{\lambda \overwithdelims() \mu }^k, \qquad k\geq 0. \end{displaymath}$

Az eredmény kézenfekvő. Az ergodikusság feltétele általánosságban (és így annak is, hogy egy

stacionárius megoldást kapjunk) $S_1<\infty$ és $S_2=\infty$ ; esetünkben az első feltétel:

$\begin{displaymath} S_1=\sum_{k=0}^\infty{P_k \over P_0}=\sum_{k=0}^\infty {\lambda \overwithdelims() \mu }^k<\infty. \end{displaymath}$

sor akkor és csak akkor konvergens, ha

$\begin{displaymath}\lambda /\mu <1.\end{displaymath}$

Az ergodicitás második feltétele esetünkben

$\begin{displaymath} S_2=\sum_{k=0}^\infty{1 \over \lambda {P_k \overwithdelims(... ...y{1 \over \lambda }{\mu \overwithdelims() \lambda }^k=\infty. \end{displaymath}$

Ez akkor teljesül, ha $\lambda /\mu \leq 1$ . Tehát az ergodikusság szükséges és elégséges feltétele az M/M/1 sor esetén egyszerűen $\lambda <\mu$ . A

valószínűség kiszámolásához a normalizáló feltételt használjuk és azt kapjuk, hogy

$\begin{displaymath} P_0={1 \over 1+\sum\limits_{k=1}^\infty{\lambda \overwithdelims() \mu }^k}. \end{displaymath}$

Mivel $\lambda <\mu$ , ezért a sor konvergens, és így

$\begin{displaymath} P_0={1 \over 1+{\lambda /\mu \over 1-\lambda /\mu }}=1-{\lambda \over \mu }. \end{displaymath}$

A kihasználtsági tényező $\varrho ={\lambda \over \mu }$ vagy

. A stabilitás feltétele miatt a $0\leq \varrho <1$ egyenlőséget meg kell követelni. Ez biztosítja, hogy

legyen. Így

$\begin{displaymath} P_k=(1-\varrho )\varrho ^k, \qquad k=0,1,2,... , \end{displaymath}$

amely valóban valószínűségi eloszlás, nevezetesen a geometriai eloszlás. A rendszer ${\dlt jellemzői}$ :

(I.) A rendszerben tartózkodó igények átlagos száma:

$\begin{displaymath} \overline{N}=\sum_{k=0}^\infty kP_k= (1-\varrho)\varrho \sum_{k=1}^\infty k\varrho ^{k-1}=\end{displaymath}$

$\begin{displaymath} =(1-\varrho )\varrho\sum_{k=1}^\infty {d\varrho^k \over d\v... ...1 \overwithdelims() 1-\varrho }= {\varrho \over 1-\varrho }. \end{displaymath}$

A rendszerben tartózkodó igények számának szórásnégyzete:

$\begin{displaymath} \eqalign{ \sigma_N^2=&\sum_{k=0}^\infty(k-\overline{N})^2P... ...lims() 1-\varrho }^2={\varrho \over (1-\varrho )^2}. \cr } \end{displaymath}$

(II.) A várakozó igények átlagos száma (átlagos sorhossz):

$\begin{displaymath} \overline{Q}=\sum_{k=1}^\infty (k-1)P_k=\sum_{k=1}^\infty k... ...-(1-P_0)=\overline{N}-\varrho ={\varrho ^2 \over 1-\varrho }. \end{displaymath}$

Az átlagos sorhossz szórásnégyzete:

$\begin{displaymath} \sigma_Q^2=\sum_{k=1}^\infty (k-1)^2P_k-\overline{Q}^2= {\varrho ^2(1+\varrho -\varrho ^2) \over (1-\varrho )^2}. \end{displaymath}$

(III.) A szerver kihasználtsága:

$\begin{displaymath} U_s=1-P_0={\lambda \over \mu }=\varrho . \end{displaymath}$

(4) alapján látható, hogy

$\begin{displaymath} P_0={{1 \over \lambda } \over {1 \over \lambda }+E\delta}, \end{displaymath}$

ahol $E\delta$ a kiszolgáló átlagos foglaltsági periódushossza, ${1 \over \lambda }$ a tétlenségi idő várható értéke. Mivel a szerver addig tétlen, amíg igény nem érkezik, az pedig exponenciális eloszlású $\lambda$ paraméterrel. Így

$\begin{displaymath} 1-\varrho ={{1 \over \lambda } \over {1 \over \lambda }+E\delta}, \end{displaymath}$

melyből

$\begin{displaymath} E\delta={1 \over \lambda }{\varrho \over 1-\varrho }={1 \over \lambda }\overline{N}= {1 \over \mu -\lambda }. \end{displaymath}$

(IV.) Egy igény várakozási idejének eloszlása:

Megmutatjuk, hogy olyan sorbanállási rendszernél, amelybe az igények Poisson-folyamat szerint érkeznek,

$\begin{displaymath} P_k(t)=R_k(t), \end{displaymath}$

ahol

- mint korábban is - annak valószínűsége, hogy a

pillanatban a rendszer a

állapotban van,

pedig annak valószínűsége, hogy egy a

pillanatban érkező igény a rendszert a

állapotban találja. Jelölje

$\begin{displaymath}A(t,t+\Delta t)\end{displaymath}$

azt az eseményt, hogy egy beérkezés történik a $(t,t+\Delta t)$ intervallumban. Ekkor

$\begin{displaymath} R_k(t):=\lim_{\Delta t \to 0} P \left( X(t)=k \vert A(t,t+\Delta t) \right), \end{displaymath}$

ahol

a rendszerbeli igények száma a

pillanatban. Felhasználva a feltételes valószínűség definícióját,

$\begin{displaymath} R_k(t)=\lim_{\Delta t \to 0} { P \left( X(t)=k \hbox{ , }... ...lta t) \right) \over P \left( A(t,t+\Delta t) \right) } = \end{displaymath}$

$\begin{displaymath} =\lim_{\Delta t \to 0} { P \left( A(t,t+\Delta t) \vert ... ...X(t)=k \right) \over P \left( A(t,t+\Delta t) \right) } . \end{displaymath}$

Poisson-folyamat esetén tudjuk, hogy (az emlékezetnélküliség miatt) az $A(t,t+\Delta t)$ esemény nem függ a

pillanatban a rendszerben tartózkodó igények számától (és magától a

időtől sem), ezért

$\begin{displaymath} P \left( A(t,t+\Delta t) \vert X(t)=k \right) =P \left( A(t,t+\Delta t) \right) , \end{displaymath}$

így

$\begin{displaymath} R_k(t)=P \left( X(t)=k \righte). \end{displaymath}$

Azaz, annak valószínűsége, hogy egy beérkező igény a rendszert a

állapotban találja, éppen azzal a valószínűséggel egyezik meg, hogy a rendszer a

állapotban van. Ha egy tetszőleges pillanatban egy igény érkezik,

lesz annak a valószínűsége, hogy nem kell várakoznia, hisz ekkor a rendszer üres. Minden más esetben várakoznia kell. Tegyük fel, hogy az érkezés pillanatában

igény tartózkodik a rendszerben. Ekkor az érkező igénynek meg kell várnia, míg a kiszolgálás alatt álló igény kiszolgálása befejeződik és az előtte álló

igény elhagyja a rendszert. Feltettük, hogy a kiszolgálások egymástól függetlenek és $\mu$ paraméterű exponenciális eloszlásúak. Köztudott, hogy az exponenciális eloszlás emlékezetnélküli, így a kiszolgálás alatt levő igény eloszlása független attól mióta folyik a kiszolgálás, ezért a várakozási idő $\Gamma$ vagy (Erlang-) eloszlású $\mu$ és

paraméterrel. Emlékeztetőül az

és $\mu$ paraméterű Erlang-eloszlás sűrűségfüggvénye:

$\begin{displaymath} f_n(x)={\mu(\mu x)^{n-1} \over (n-1)!} e^{-\mu x}, \qquad x\geq 0. \end{displaymath}$

Jelölje

egy tetszőleges igény várakozási idejének sűrűségfüggvényét,

. A teljes valószínűség tétele értelmében:

$\begin{displaymath} f_W(x)=\sum_{n=1}^\infty {(\mu x)^{n-1} \over(n-1)!}\mu e^{... ...\mu \sum_{k=0}^\infty {(\mu x\varrho )^k \over k!}e^{-\mu x}= \end{displaymath}$

$\begin{displaymath} =(1-\varrho )\varrho \mu e^{-\mu (1-\varrho )x}. \end{displaymath}$

Tehát

$\begin{displaymath} \vbox{ \halign{$ ...$

Így

$\begin{displaymath} F_W(x)=1-\varrho +\varrho \left(1-e^{-\mu (1-\varrho )x}\right)= 1-\varrho e^{-\mu (1-\varrho )x}. \end{displaymath}$

Az átlagos várakozási idő:

$\begin{displaymath} \overline{W}=\int\limits_0^\infty xf_W(x)dx={\varrho \over \mu (1-\varrho )}= \varrho E\delta=\overline{N}{1 \over \mu }. \end{displaymath}$

(V.) Egy igény tartózkodási idejének eloszlása:

A gondolatmenet az előzőhöz hasonló, de az igény akkor hagyja el a rendszert, ha őt is kiszolgálták, így az Erlang eloszlás tagból tevődik össze. Tehát a sűrűségfügvény:

$\begin{displaymath} f_T(x)=\sum_{n=0}^\infty (1-\varrho )\varrho ^n{(\mu x)^n \... ...ho )e^{-\mu x}\sum_{n=0}^\infty {(\varrho \mu x)^n \over n!}= \end{displaymath}$

$\begin{displaymath} =\mu (1-\varrho )e^{-\mu (1-\varrho )x}. \end{displaymath}$

Az eloszlásfüggvény:

$\begin{displaymath} F_T(x)=1-e^{-\mu (1-\varrho )x}. \end{displaymath}$

Vagyis azt kaptuk, hogy a tartózkodási idő is exponenciális eloszlású
$\mu (1-\varrho )=\mu -\lambda$ paraméterrel. Ezért az átlagos rendszerbeli tartózkodási idő:

$\begin{displaymath} \overline{T}={1 \over \mu (1-\varrho )}={1 \over \mu -\lambda }. \end{displaymath}$

Továbbá, nyilvánvaló, hogy

$\begin{displaymath} \overline{T}=\overline{W}+{1 \over \mu }={\varrho \over \mu... ...= {1 \over \mu (1-\varrho )}={1 \over \mu -\lambda }=E\delta. \end{displaymath}$

Vegyük észre, hogy

$\begin{displaymath} \lambda \overline{T}=\lambda {1 \over \mu (1-\varrho )}={\varrho \over 1-\varrho }=\overline{N}. \leqno(*) \end{displaymath}$

Továbbá

$\begin{displaymath} \lambda \overline{W}=\lambda {\varrho \over \mu (1-\varrho )}={\varrho ^2 \over 1-\varrho }=\overline{Q}. \leqno(**) \end{displaymath}$

A (*) és a (**) összefüggéseket Little-formuláknak nevezzük, melyek általánosabb esetben is igazak maradnak.

Példa:

1. Egy postahivatalban naponta 70 személy fordul meg (a posta minden nap 10 óra hosszat van nyitva) ; óránként 10 személyt képesek kiszolgálni. Tételezzük fel, hogy a beérkezések megfelelnek a Poisson-folyamat jellegzetességeinek és a kiszolgálás exponenciális eloszlású. Mekkora lesz a várakozó sor átlagos hossza, mi annak a valószínűsége, hogy sorban 2-nél több személy várakozzék? Mennyi a várható sorban állási idő? Mennyi annak a valószínűsége, hogy a várakozás 20 percnél több időt vesz igénybe? $E\delta=$ ?

${\bold Megold\'as:}$ Legyen

óra, akkor $\lambda=7$ , $\mu=10$ , $\varrho={7\over 10}$

$\begin{displaymath}\overline{N}={\varrho\over 1-\varrho}={7 \over 3},\ \ \overli... ...-\varrho= {7\over 3}-{7\over 10}={70-21 \over 30}={49\over 30}\end{displaymath}$

$\begin{displaymath}P(n>3)=1-P(n\leq 3)=1-P_0-P_1-P_2-P_3=\end{displaymath}$

$\begin{displaymath}=1-1+\varrho -(1-\varrho)(\varrho +\varrho^2 +\varrho^3)=\varrho^4=0.343\cdot 0.7=0.2401\end{displaymath}$

$\begin{displaymath}\overline{W}={\overline{N}\over \mu}={7\over 3\cdot 10}={7\over 30} \hbox{ \'ora } \approx 14 \hbox{ perc}\end{displaymath}$

$\begin{displaymath}P\left(W>{1\over 3}\right)=1-F_W\left({1\over 3}\right)=0.7\cdot e^{-10\cdot {1\over 3}\cdot 0.3}= 0.7\cdot e^-1=0.257\end{displaymath}$

Nyitólap Tartalomjegyzék Fejezetek ( B I II III IV F ) Letöltések

FRAME-mel

FRAME nélkül

<< Előző

Következő >>