II.4. Az M/M/n/n típusú Erlang-féle veszteséges rendszer


Ezen modellre $n$ csatornás veszteséges rendszerként is szokás hivatkozni az alábbiak miatt. Az $n$ csatornás rendszerbe Poisson-folyamat szerint érkeznek az igények. Ha van üres csatorna vagy szerver az igény kiszolgálása exponenciális időtartamú $\mu$ paraméterrel. Ha minden kiszolgáló egység foglalt, akkor az igény elvész, azaz sorbanállás nem megengedett. Ezen probléma a tömegkiszolgálás egyik legrégibb problémája, mellyel a század elején a telefonközpontok kihasználtságával kapcsolatban foglalkozott A. K. Erlang és C. Palm. Hasonló jelenséggel találkozunk a parkolóhelyek esetében is. A feltételek alapján ez is egy születési-kihalási folyamattal modellezhető, melynek intenzitásai a következők:

\begin{displaymath} \lambda_k=\cases{\lambda &\hbox{, ha $k<n$},\cr 0&\hbox{, ha $k\geq n$},} \end{displaymath}


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

Azt mondjuk, hogy a folyamat $k$ állapotban van, ha $k$ szerver foglalt, azaz ha $k$ igény tartózkodik a rendszerben. Nyilvánvalóan az e rgodikus eloszlás létezik, mivel a folyamat véges állapotterű. A folyamat stacionárius eloszlása:

\begin{displaymath} P_k=\cases{ P_0 \displaystyle{\lambda \overwithdelims() \mu... ... k!} &\hbox{, ha $k\leq n$},\cr 0 &\hbox{, ha $k>0$}.\cr} \end{displaymath}

A normalizáló feltétel miatt:

\begin{displaymath} P_0=\left(\sum_{k=0}^n{\lambda \overwithdelims() \mu }^k{1 \over k!}\right)^{-1}, \end{displaymath}

így

\begin{displaymath} P_k={\displaystyle{\lambda \overwithdelims() \mu }^k{1 \ove... ...yle \sum\limits_{i=0}^n{\varrho ^i \over i!}}, \qquad k\le n. \end{displaymath}

A rendszer egyik jellemzője a

\begin{displaymath} P_n={\displaystyle{\varrho ^n \over n!} \over \displaystyle \sum\limits_{k=0}^n{\varrho ^k \over k!}} \end{displaymath}

valószínűség, melyet először Erlang vezetett be (1917-ben) és Erlang-féle veszteségformula vagy Erlang-féle B formula néven ismert, általában $B(n,\lambda /\mu )$ szimbólummal jelölik. A $P_n$ valószínűség annak a valószínűsége stacionárius esetben, hogy egy újonnan érkező igényt nem fogad a rendszer, azaz az igény elveszik.


Kis $n$-re a $P_0$ valószínűség könnyen kiszámolható. Nagy $n$-re és kis $\varrho$-ra $P_0\approx e^{-\varrho }$, így

\begin{displaymath} P_k\approx{\varrho ^k \over k!}e^{-\varrho }, \end{displaymath}

azaz a Poisson-eloszlás. Nagy $n$-re és nagy $\varrho$-ra általában

\begin{displaymath}\sum\limits_{j=0}^n{\varrho ^j \over j!}\ne e^\varrho .\end{displaymath}

Ebben az esetben a nevező a $\varrho$ közepű Poisson-eloszlás első $(n+1)$ tagjának összege. Elegendő nagy $\varrho$-ra ($\varrho >15$) a Poissson-eloszlást közelítjük $\varrho$ közepű és $\sqrt{\varrho }$ szórású normális eloszlással, így

\begin{displaymath} P_n\approx{\displaystyle{\varrho ^n \over n!}e^{-\varrho } \over \displaystyle\Phi(s)}, \end{displaymath}

ahol

\begin{displaymath} \Phi(s)=\int\limits_{-\infty }^s{1 \over \sqrt{2\pi}}e^{-{x^2 \over 2}}dx, \end{displaymath}

és

\begin{displaymath} s={n+{1 \over 2}-\varrho \over \sqrt{\varrho }}. \end{displaymath}

Az M/M/n/n rendszer jellemzői:


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

\begin{displaymath} \overline{N}=\overline{n}=\sum_{j=0}^njP_j=\sum_{j=0}^nj{\v... ...rho \sum_{j=0}^{n-1}{\varrho ^i \over i!}P_0=\varrho (1-P_n), \end{displaymath}

így $1$ szerverre jutó átlagos igényszám:

\begin{displaymath} {\varrho \over n}(1-P_n). \end{displaymath}

(II.) A szerverek kihasználtsága:

Mint már láttuk

\begin{displaymath} U_s=\sum\limits_{i=1}^n{i\over n}P_i={\bar{n}\over n}. \end{displaymath}

Jelen esetben

\begin{displaymath} U_s={\varrho \over n}(1-P_n). \end{displaymath}

(III.) Az átlagos tétlenségi idő (egy konkrét kiszolgáló esetén): A jól ismert (4) vagy (5) összefüggést alkalmazva:

\begin{displaymath} P(\hbox{az adott kiszolg\'al\'oegys\'eg foglalt})= {1/\mu \over \overline{e}+1/\mu }, \end{displaymath}

ahol $\overline{e}$ az átlagos tétlenségi idő. Így

\begin{displaymath} {\varrho \over n}(1-P_n)={1/\mu \over \overline{e}+1/\mu }, \end{displaymath}

tehát

\begin{displaymath} \overline{e}={n \over \lambda (1-P_n)}-{1 \over \mu }. \end{displaymath}

Ha az üres szerverek olyan sorrendben kezdik kiszolgálni az érkező igényeket, mint amilyen sorrendben megüresedtek, akkor egy szerver működését a következőképpen írhatjuk le. Ha egy üressé vált szerver $(j-1)$ másik üres szervert talál megüresedése pillanatában, akkor csak a $j$-edik igény kiszolgálásával kezdődik ismét a foglaltsági periódusa. Jelölje $\overline{e}$ a szerver átlagos üresjárati periódusa hosszát, $\overline{e}_j$ pedig a fenti állapotban az átlagos tétlenségi időt. Nyilvánvalóan $\overline{e}_j={j \over \lambda }$, $\overline{e}$ pedig a teljes várható érték tétele alapján:

\begin{displaymath} \eqalign{ \overline{e}=&\sum_{j=1}^n{P_{n-j} \over 1-P_n}{... ...over \lambda }={n \over \lambda (1-P_n)}-{1 \over \mu },\cr} \end{displaymath}

azaz más úton is ugyanarra az eredményre jutunk.

(IV.) A rendszer átlagos foglaltsági periódushosszap:


Nyilvánvalóan (4) alapján

\begin{displaymath} U_r=1-P_0={E\delta^{(n)} \over {1 \over \lambda }+E\delta^{(n)}}, \end{displaymath}

melyből

\begin{displaymath} E\delta^{(n)}={1-P_0 \over \lambda P_0}={\displaystyle\sum\... ...bda \left(1+\sum\limits_{i=1}^n{\varrho ^i \over i!}\right)}. \end{displaymath}

{\bold P\'eld\'ak:}

1. Egy parkolóhoz az autók $20$ másodpercenként érkeznek, és átlagosan $10$ percig maradnak. A beérkezés Poisson, a kiszolgálás exponenciális. Milyen nagynak kell lennie a parkolónak, hogy egy autó legfeljebb 1% eséllyel forduljon vissza, mert a parkoló telített?

{\bold Megold\'as:}

\begin{displaymath}\varrho={\lambda \over \mu} = {10 \over {1\over 3}} = 30\end{displaymath}


\begin{displaymath}P_n={{\varrho^n \over n!}e^{-\varrho} \over \sum^n_{j=0}{\varrho^j \over j!}e^{-\varrho}} = 0.01\end{displaymath}

a normális eloszlású közelítést követve

\begin{displaymath}P_n=0.01 = {{\varrho^n \over n!}e^{-\varrho} \over \Phi\left({n+{1\over 2} - \varrho \over \sqrt{\varrho}}\right) } =\end{displaymath}


\begin{displaymath}{ \Phi\left({n+{1\over 2} - \varrho \over \sqrt{\varrho}}\rig... ...i\left({n+{1\over 2} - \varrho \over \sqrt{\varrho}}\right) }. \end{displaymath}

Ebből

\begin{displaymath}0.99 \Phi\left({n+{1\over 2} - \varrho \over \sqrt{\varrho}}\... ...Phi\left({n-{1\over 2} - \varrho \over \sqrt{\varrho}}\right) .\end{displaymath}

A normális eloszlás táblázatából nem nehéz ellenőrizni, hogy $n=41$.

2. Egy $50$ csatornás telefonközpontba átlagosan $10$ percenként érkeznek hívások Poisson-eloszlás szerint. A kiszolgálási idő exponenciális, $5$ perc átlaggal. Határozzuk meg a rendszer jellemzőit!

{\bold Megold\'as:} Esetünkben Poisson eloszlással való közelítés használható, $\varrho = {\lambda\over \mu}= 0.5$ értékkel. $ P_{50}=0.00000$ a Poisson-eloszlás szerint, sőt, még $n=6$-nál is $P_6=0.00001$. Ez azt jelenti, hogy igény szinte sohasem lesz elutasítva. A foglalt csatornák átlagos száma:

\begin{displaymath}\overline{n}=\varrho(1-P_n)=\varrho=0.5\ ,\end{displaymath}

így az egy csatornára jutó átlagos igényszám:

\begin{displaymath}{0.5\over 50}={5\times 10^{-1}\over 5\times 10} = 10^{-2}\ ,\end{displaymath}

mely egyben a csatornák kihasználtsága. $U_r=1-0.606 = 0.394$, mely a rendszer kihasználatsága. A rendszer átlagos foglaltsági periódushossza:

\begin{displaymath}E\delta = {(1-P_0)\over (\lambda P_0)} = {0.394 \over 2\times 0.606} = {0.394 \over 1.212}=0.32 \hbox{ perc}\end{displaymath}

A csatornák átlagos tétlenségi ideje:

\begin{displaymath}\overline{e}={n \over \lambda (1-P_n)}-{\varrho \over \lambda... ...er 2(1-0)}-{0,5 \over 2} = 25-{1\over 4} = 24.75 \hbox{ perc}.\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ő  >>