III.1.5. A várakozási idő eloszlása


Ebben a fejezetben a rendszerben és a sorban eltöltött idő eloszlását számoljuk ki a P-H transzformált-egyenletek segítségével, figyelembe véve azt is, hogy a kiszolgálási elv FIFO. Idézzük fel a $(8)$ egyenletet:

\begin{displaymath} V\left(z\right)=B^*\left(\lambda-\lambda z\right) , \end{displaymath}

ahol $V\left(z\right)$ egy bizonyos kiszolgálási intervallum -- $C_n$ kiszolgálási ideje -- alatt a rendszerbe érkező igények számának generátorfüggvénye, ahol a beérkezési folyamat $\lambda$ paraméterű Poisson-folyamat. Ez az intervallum $B\left(x\right)$ eloszlású, Laplace-transzformáltja $B^*\left(s\right)$. Az ezek közti összefüggést éppen az előbb mutattuk meg. Tekintsük most a $C_n$ igénynek a rendszerben eltöltött idejét. Ekkor $w_n$ a sorba beállástól a sor elhagyásáig terjedő időtartam, a $C_n$ várakozási ideje, $x_n$ pedig a kiszolgálási idő. Jelentse $s_n$ a $C_n$ igény rendszerben eltöltött teljes idejét. $s_n=w_n+x_n.$ $q_n$ azon igények számát jelenti, amelyek a rendszerben maradnak a $C_n$ távozásakor. Ha a kiszolgálási elv FIFO, akkor a $C_n$ érkezésekor a rendszerben lévő igények $C_n$ előtt távoznak, és $C_n$ pontosan a rendszerben való tartózkodása alatt érkezett $q_n$ számú igényt hagyja hátra távozásakor. Így az $s_n$ időtartam alatt érkezett igények száma $q_n$ valószínűségi változó. Az első esetben tehát egy $x_n$ hosszúságú kiszolgálási intervallum alatt érkező $v_n$ igényszám, a második esetben egy $s_n$ hosszúságú tartózkodási intervallum alatt beérkező igények $q_n$ száma érdekel minket. A $C_n$ teljes rendszerbeli tartózkodási idejének eloszlásfüggvénye

\begin{displaymath} S_n\left(y\right):=P\left(s_n\le y\right). \end{displaymath}

Mivel feltettük az ergodicitást, létezik ennek $n$-től független határeloszlása, ha $n\to\infty$. Jelöljük ezt $S\left(y\right)$-nal és legyen $\tilde{s}$ egy olyan valószínűségi változó, melyre

\begin{displaymath} S\left(y\right):=P\left(\tilde{s}\le y\right). \end{displaymath}

A teljes rendszerbeli tartózkodási idő eloszlásfüggvényének Laplace-Stieltjes transzformáltja

\begin{displaymath} S^*\left(s\right):=\int\limits_0^\infty e^{-sy}dS\left(y\right)=E\left(e^{-s\tilde{s}}\right). \end{displaymath}

Mindkét esetben $\lambda$ intenzitású Poisson-féle beérkezési folyamatunk van. A két eset között analógiát fedezhetünk fel. Mivel $v_n$ a $q_n$ megfelelője, ezért $V\left(z\right)$ lesz a $Q\left(z\right)$ megfelelője. Ugyanígy, mivel $x_n$ az $s_n$-nel analóg, a $B^*\left(s\right)$ megfelelője $S^*\left(s\right)$ kell legyen. Ez alapján $(8)$-ból közvetlenül adódik, hogy

\begin{displaymath} Q\left(z\right)=S^*\left(\lambda-\lambda z\right). \end{displaymath}

Felhasználva a P-H transzformált-egyenletet

\begin{displaymath} S^*\left(\lambda-\lambda z\right)=B^*\left(\lambda-\lambda ... ...t)\left(1-z\right)\over B^*\left(\lambda-\lambda z\right)-z} \end{displaymath}

adódik. Hajtsuk végre az $s=\lambda-\lambda z$ változó transzformációt, amiből $z=1-{s\over\lambda}$. Így

\begin{displaymath} S^*\left(s\right)=B^*\left(s\right){s\left(1-\varrho\right)\over s-\lambda+\lambda B^*\left(s\right)}.\leqno(19) \end{displaymath}

Ez, az $M/G/1$-beli teljes tartózkodási idő Laplace-transzformáltjára adott explicit kifejezés a második P-H transzformáltegyenlet. Ebből könnyen levezethetjük a várakozási idő eloszlásának Laplace-Stieltjes transzformáltját, $W^*\left(s\right)$-et. Legyen $C_n$ várakozási idejének eloszlásfüggvénye

\begin{displaymath} W_n\left(y\right):=P\left(w_n\le y\right) , \end{displaymath}

és legyen

\begin{displaymath} \lim_{n\to\infty}W_n\left(y\right)=W\left(y\right) , \end{displaymath}

továbbá a $\tilde{w}$ valószínűségi válttozóra álljon fenn

\begin{displaymath} W\left(y\right):=P\left(\tilde{w}\le y\right). \end{displaymath}

A Laplace-Stieltjes transzformált

\begin{displaymath} W^*\left(s\right):=\int\limits_0^\infty e^{-sy}dW\left(y\right)=E\left(e^{-s\tilde{w}}\right). \end{displaymath}

A várakozási és a kiszolgálási idők egymástól függetlenek, így $\tilde{s}$ felírható két független valószínűségi változó összegeként:

\begin{displaymath} \tilde{s}=\tilde{w}+\tilde{x}. \end{displaymath}

Kihasználva a Laplace-Stieltjes transzformált konvolúciós tulajdonságát

\begin{displaymath} S^*\left(s\right)=W^*\left(s\right)B^*\left(s\right). \end{displaymath}

$(19)$-ből rögtön adódik, hogy

\begin{displaymath} W^*\left(s\right)={s\left(1-\varrho\right)\over s-\lambda+\lambda B^*\left(s\right)}.\leqno(20) \end{displaymath}

Ez a várakozási idő Laplace-transzformáltjára vonatkozó kifejezés a harmadik P-H transzformált-egyenlet. Irjuk fel ezt a következőképpen

\begin{displaymath} W^*\left(s\right)={1-\varrho\over 1-\varrho\left({1-B^*\lef... ...\right)}={1-\varrho\over 1-\varrho\hat{B}^*\left(s\right)} , \end{displaymath}

ahol a korábbi jelöléseinkkel összhangban

\begin{displaymath} \hat{B}^*\left(s\right):={1-B^*\left(s\right)\over s\bar{x}} , \end{displaymath}

a hátralévő kiszolgálási idő sűrűségfüggvényéhez tartozó Laplace-transzformált. Fejtsük hatványsorba $W^*\left(s\right)$-et:*Ehhez az szükséges, hogy $\varrho\hat{B}^*\left(s\right)<1$ legyen, ami igaz, ha $\varrho<1$, hiszen $1-B^*\left(s\right)=1-\int\limits_0^\infty e^{-st}dB\left(t\right)\le 1-\int\li... ...-st\right)dB\left(t\right)= {s\over\mu}={s\varrho\over\lambda}<{s\over\lambda}$, így ${\lambda\over s} \left(1-B^*\left(s\right)\right)<1$, azaz $\varrho\hat{B}^*\left(s\right)<1$.

\begin{displaymath} W^*\left(s\right)=\left(1-\varrho\right)\sum_{k=0}^\infty\varrho^k{\left(\hat{B}^*\left(s\right)\right)}^k.\leqno(21) \end{displaymath}

 


A Laplace-transzformált $k$-adik hatványa az inverz transzformált önmagával vett $k$-szoros konvolúciójának felel meg. Jelöljük ezt a $k$-szoros konvolúciót $ f_{\left(k\right)}\left(x\right):=\underbrace{f\left(x\right)*\cdots *f\left(x\right)}_{k-\hbox{szor}}-\hbox{ szel}. $ Ennek segítségével invertálhatjuk $(21)$-et, így megkapjuk a várakozási idő sűrűségfüggvényét:

\begin{displaymath} w\left(y\right)=\sum_{k=0}^\infty\left(1-\varrho\right)\varrho^k\hat{b}_{\left(k\right)}\left(y\right). \end{displaymath}

Tehát a várakozási idő sűrűségfüggvénye a hátralévő kiszolgálási idő sűrűségfüggvénye konvolúcióinak súlyozott összege, ahol az $\left(1-\varrho\right)\varrho^k$ súlyok az $M/M/1$ rendszerbeli igények számának eloszlásával egyenlők.

A $(20)$ P-H transzformátoregyenlet segítségével levezetünk egy összefüggést a várakozási idő $k$-adik momentumára, $\overline{w^k}$-ra.

\begin{displaymath} W^*\left(s\right)={s\left(1-\varrho\right)\over s-\lambda+\lambda B^*\left(s\right)} , \end{displaymath}


\begin{displaymath} W^*\left(s\right)\left(s-\lambda+\lambda B^*\left(s\right)\right)=s\left(1-\varrho\right). \end{displaymath}

$l$-edik deriváltat véve

\begin{displaymath} {d^lW^*\left(s\right)\left(s-\lambda+\lambda B^*\left(s\right)\right)\over ds^l}={d^ls\left(1-\varrho\right)\over ds^l}. \end{displaymath}

Végezzük el a műveletet a Leibniz-formula segítségével:

\begin{displaymath} \sum_{j=0}^l{l\choose j}{d^{l-j}W^*\left(s\right)\over ds^{... ...ht)\right)\over ds^j}={d^ls\left(1-\varrho\right)\over ds^l}. \end{displaymath}

Tegyük fel, hogy $l>1$, mert a magasabb momentumok érdekelnek, így a jobb oldal nullával egyenlő.

\begin{displaymath} {d^lW^*\left(s\right)\over ds^l}\left(s-\lambda+\lambda B^*... ...er ds^{l-1}} \left(1-\lambda B^{*^{'}}\left(s\right)\right)+ \end{displaymath}


\begin{displaymath} +\sum_{j=2}^l{l\choose j}{d^{l-1}W^*\left(s\right)\over ds^{l-1}} \lambda{d^jB^*\left(s\right)\over ds^j}=0. \end{displaymath}

Tudjuk, hogy $W^{*^{\left(l\right)}}\left(0\right):={\left(-1\right)}^l\overline{w^l}$, így

\begin{displaymath} l{\left(-1\right)}^{l-1}\overline{w^{l-1}}\left(1-\varrho\r... ...-1\right)}^{l-j}\overline{w^{l-j}}{\left(-1\right)}^j b_j=0 , \end{displaymath}

azaz

\begin{displaymath} \overline{w^{l-1}}={\lambda\over l\left(1-\varrho\right)}\sum_{j=2}^l{l\choose j}\overline{w^{l-j}} b_j. \end{displaymath}

Írjunk most $k=l-1$ és $i=j-1$-et:

\begin{displaymath} \overline{w^k}={\lambda\over 1-\varrho}\sum_{i=1}^k{k\choose i}\overline{w^{k-i}} {b_{i+1}\over i+1} ,\leqno(22) \end{displaymath}

ahol $\overline{w^0}:=1$. Ezt a formulát Takács-féle rekurziós képletnek nevezzük. Ennek segítségével felírhatjuk a várakozási idő első néhány momentumát:

\begin{displaymath} \bar{w}={\lambda b_2\over 2\left(1-\varrho\right)} ; \end{displaymath}


\begin{displaymath} \overline{w^2}=2{\lelft(\bar{w}\right)}^2+{\lambda b_3\over 3\left(1-\varrho\right)}. \end{displaymath}

Hogy a rendszerbeli teljes tartózkodási idő hasonló momentumait megkaphassuk, csak az $\tilde{s}=\tilde{w}+\tilde{x}$ összefüggést kell kihasználnunk, hiszen ebből

\begin{displaymath} \overline{s^k}=\overline{{\left(\tilde{w}+\tilde{x}\right)}^k} , \end{displaymath}

amire a binomiális sorfejtést alkalmazva, és felhasználva a várakozási és kiszolgálási idők függetlenségét

\begin{displaymath} \overline{s^k}=\sum_{i=1}^k{k\choose i}\overline{w^{k-i}}b_i. \end{displaymath}

Tehát a várakozási idő momentumaiból megkaphatjuk a teljes tartózkodási idő momentumait.

Most az $M/G/1$ rendszerbeli teljes tartózkodási idő sűrűségfüggvényének Laplace-transzformáltját azon feltételezés alapján adjuk meg, hogy egy új igény beérkezésekor hány igényt talál a rendszerben. A feltételes eloszlás

\begin{displaymath} S\left(y\ \vert\ k\right)=P\left(\hbox{az ig\'eny teljes rendszerbeli tart\'ozkod\'asi ideje}\le y\ \vert\ \right. \end{displaymath}


\begin{displaymath} \left.\vert\ k \hbox{ ig\'enyt tal\'al a rendszerben be\'erkez\'eskor}\right). \end{displaymath}

Ennek Laplace-Stieltjes transzformáltja

\begin{displaymath} S^*\left(s\ \vert\ k\right):=\int\limits_0^\infty e^{-sy}dS\left(y\ \vert\ k\right). \end{displaymath}

Ha $k=0$, azaz egyetlen igényt sem talál a rendszerben, akkor csak saját kiszolgálási idejét tölti el, így

\begin{displaymath} S^*\left(s\ \vert\ 0\right)=B^*\left(s\right). \end{displaymath}

Ha egy igényt talál maga előtt, akkor ezen előző igény hátralévő kiszolgálási idejét és a saját kiszolgálási idejét tölti a rendszerben. Mivel ezek függetlenek, így összegük sűrűségfüggvényének Laplace-transzformáltja az egyes sűrűségfüggvények Laplace-transzformáltjainak szorzatával egyenlő, azaz

\begin{displaymath} S^*\left(s\ \vert\ 1\right)=\hat{B}^*\left(s\right)B^*\left(s\right). \end{displaymath}

Ha $k$ igényt talál maga előtt a beérkező igény, akkor $k-1$ igény kiszolgálási idejét, a saját kiszolgálási idejét és a beérkezésekor éppen kiszolgálás alatt lévő igény hátralévő kiszolgálási idejét tölti a rendszerben. Ez $k+1$ független valószínűségi változó összege, így

\begin{displaymath} S^*\left(s\ \vert\ k\right)={\left(B^*\left(s\right)\right)}^k\hat{B}^*\left(s\right). \end{displaymath}

Az $S^*\left(s\right)$ megadásához csak az $S^*\left(s\ \vert\ k\right)$-knak azon $P_k$ valószínűségekkel vett súlyozott összegét kell vennünk, hogy beérkezéskor éppen $k$ igény van a rendszerben:

\begin{displaymath} S^*\left(s\right)=\sum_{k=0}^\infty S^*\left(s\ \vert\ k\right)P_k. \end{displaymath}

Ez az összefüggés azért érdekes, mert néhány rendszerre így könnyebben kaphatjuk meg az $S^*\left(s\right)$-et.

 

Nyitólap    Tartalomjegyzék    Fejezetek ( B I II III IV F )    Letöltések
FRAME-mel FRAME nélkül
<<   Előző Következő  >>