III.1.6. A foglaltsági periódusok vizsgálata


Ebben a pontban a sorbanállási rendszereket egy újabb nézőpontból elemezzük. Vezessük be azt az $U\left(t\right)$ sztochasztikus folyamatot, amely megadja a $t$ pillanatban a munkahátralékot (restanciát), azaz azt az időtartamot, amely ahhoz szükséges, hogy a rendszer üressé váljon, ha a $t$ pillanat után új igényt nem engedünk be. Ezt néha "virtuális" várakozási időnek is nevezzük, mert érkezési sorrendben történő (FIFO) kiszolgálás esetén megmutatja, mennyi időt kellene várnia a sorban egy (virtuális) igénynek, ha a $t$ pillanatban lépne be. Mi azonban az általánosabb, munkahátralék terminológiát fogjuk használni, mivel az bármilyen kiszolgálási elv esetén érvényes, míg a "virtuális várakozás" kifejezés csak FIFO elv esetén megfelelő. Ha $U\left(t\right)>0$, akkor foglaltnak nevezzük a rendszert, ha $U\left(t\right)=0$, akkor üresnek. A 2. ábrát tanulmányozva észrevehetjük, hogy a rendszerben váltakozva jönnek létre foglalt és szabad időszakok, azaz foglaltsági és üresjárati intervallumok. A foglaltsági intervallumok hosszát $Y_1,Y_2,\ldots$, az üresjárati intervallumokét $I_1,I_2,\ldots$ jelöli. Az ábrán a $C_1$ igény a $\tau_1$ pillanatban lép be a rendszerbe, és $x_1$ a kiszolgálási ideje. Mivel beérkezése előtt a rendszer üres volt, $0$ volt a munkahátralék, de a beérkezéssel egy foglaltsági intervallum kezdődik, és a munkahátralék ezzel $x_1$-re ugrik, mivel ennyi ideig tartana, amíg a rendszer újra üressé válna, ha új beérkezéseket nem engednénk meg. A $\tau_1$ időpont után a munkahátralék egyenletesen -- $1$ intenzitással -- fogy. A $\tau_2=\tau_1+t_2$ időpontban érkezik a $C_2$ igény a rendszerbe, ezzel a munkahátralék $x_2$-vel, $C_2$ kiszolgálási idejével, függőlegesen felugrik. Ezután folytatódik a csökkenés, mivel a kiszolgálás zavartalanul tart. A $C_3$ igény $\tau_3$ pillanatban érkezik, ez $x_3$-mal való ugrást eredményez, majd $U\left(t\right)$ csökkenése folytatódik egészen a $\tau_1+Y_1$ időpillanatig, mikor is az összes rendszerben lévő igény kiszolgálása befejeződik. Ezzel véget ér a foglaltsági intervallum és elkezdődik egy új üresjárati intervallum.

2. ábra

0.6cm Az üresjárat a $\tau_4$ pillanatban ér véget, a $C_4$ igény beérkezésével. Az általa kezdett foglaltsági intervallum csak egy igényt tartalmaz. Összefoglalva az eddigieket, tehát az $U\left(t\right)$ függvénynek függőleges (pozitív) ugrása van minden igénybeérkezéskor, aminek nagysága éppen az adott igény kiszolgálási ideje. Ezután lineárisan ($-1$ iránytangenssel) csökken, egészen addig, míg $U(t)$ pozitív. Ha elérte a nulla értéket, akkor nulla marad a következő igény beérkezéséig. Ez a sztochasztikus folyamat folytonos állapotterű, diszkrét ugrásokat tartalmazó Markov folyamat, hiszen a hátralévő munkát jelenti, ami a múlttal a jelenen keresztül van csak kapcsolatban. Vegyük még észre, hogy ha a kiszolgálási elv FIFO, akkor az ábrán a távozási pillanatokat az $U\left(t\right)$ függvénygörbe csökkenő szakaszainak a vízszintes tengelyig történő meghosszabbításával kaphatjuk meg. Az $U\left(t\right)$ függény értéke független a kiszolgálási elvtől, csak azt használjuk fel, hogy a kiszolgálóegység foglalt, amíg igény van a rendszerben, és minden igény csak a teljes kiszolgálása után távozzon a rendszerből. Az ilyen rendszert munkamegőrzëëő rendszernek nevezzük. Nézzük most meg közelebbről az üresjárati és foglaltsági intervallumok eloszlását. Feltevésünk szerint ($M/G/1$ rendszerben)

\begin{displaymath} A\left(t\right)=P\left(t_n\le t\right)=1-e^{-\lambda t},\ \ \ \ \ t\ge 0 , \end{displaymath}


\begin{displaymath} B\left(x\right)=P\left(x_n\le x\right) , \end{displaymath}

ahol $A\left(t\right)$ és $B\left(x\right)$ is független $n$-től. A minket érdeklő eloszlások

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


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

az üresjárati és a foglaltsági intervallum eloszülásai. Kezdjük az üresjárati intervallumok eloszlásával, amit az $M/G/1$ rendszer esetén elég egyszerű meghatározni. Amikor egy foglaltsági intervallum véget ér, akkor ezzel együtt elkezdődik egy üresjárati intervallum, és ez befejeződik, amint egy új igény érkezik. A Markovitás miatt az új igény beérkezéséig tartó idő $A\left(t\right)$ eloszlású, így

\begin{displaymath} F\left(y\right)=1-e^{-\lambda y},\ \ \ \ \ y\ge 0. \end{displaymath}

A foglaltsági intervallumok eloszlását már kissé bonyolultabb meghatározni. A 3. ábra az $U\left(t\right)$ munkahátralékot ábrázolja. A $\tau_1$pillanatban érkezik az addig üres rendszerbe a $C_1$ igény, melynek kiszolgálási ideje $x_1$, így $\tau_1+x_1$ a távozási időpontja. $C_1$ kiszolgálása alatt új igények léphetnek be a rendszerbe, melyekkel folytatódik a foglaltsági intervallum. A könnyebb kezelhetőség érdekében részekre bontjuk a $C_1$ által generált foglaltsági intervallumot. A Takács Lajos által használt módszert alkalmazzuk, nevezetesen a FIFO kiszolgálási elv helyett LIFO-t használunk, azaz az utolsónak érkezett igényt szolgáljuk ki először. Ezt megtehetjük, hiszen tudjuk, hogy a foglaltsági intervallum hosszának eloszlása független az igények kiszolgálási sorrendjétől. Így tehát $C_1$ távozásakor a $C_4$ kerül a kiszolgálócsatornába, $C_2$-t és $C_3$-at időlegesen úgy tekintjük, mintha nem lennének a rendszerben. Emiatt a $C_4$ kiszolgálásának kezdőpillanatát úgy tekinthetjük, mintha új foglaltsági intervallum -- tulajdonképpen foglaltsági részintervallum -- kezdődne. Ennek a részintervallumnak a hossza $X_4$, az az idő, amíg a $C_4$-nek és a $C_4$ kiszolgálása alatt beérkezett igényeknek a kiszolgálása tart. Példánkban az $X_4$ intervallum alatt a $C_4,C_6,C_5$ igényeket szolgálják ki. $X_4$ végén, a $\tau+x_1+X_4$ pillanatban a LIFO elv szerint -- folytatva a rekurziót -- a $C_3$ igény kiszolgálása kezdődik el. Az általa generált foglaltsági részintervallum hosszúsága $X_3$, ami alatt a $C_3,C_7,C_8,C_9$ igények kerülnek kiszolgálásra. Ennek végeztével a $C_2$ igény kerül sorra az előzőekhez hasonlóan, és utána véget is ér a $C_1$ által generált foglaltsági intervallum.

3. ábra

A foglaltsági intervallum

A 3. ábrán látszik, hogy egy foglaltsági részintervallum grafikonja megegyezik a foglaltsági intervallum grafikonjával, egy konstanssal eltolva, ami éppen azon igények kiszolgálási idejének összegével egyezik meg, amelyek $C_1$ kiszolgálása alatt érkeztek, és még nem volt lehetőségük a saját foglaltsági részintervallumuk generálására. Vegyük észre, hogy a foglaltsági részintervallumok statisztikusan éppen úgy viselkednek, mint a teljes foglaltsági intervallum, hiszen az összes részintervallumot is egy-egy igény nyitja meg, ezek kiszolgálási ideje azonos eloszlású és egymástól függetlenek, valamint minden részintervallum addig tart, amíg a rendszer be nem pótol<ja az elmaradt munkát, azaz az $U\left(t\right)$ nullává nem válik. Tehát az ${X_k}$ valószínűségi változók független, azonos eloszlásúak és eloszlásuk megegyezik $Y$ eloszlásával. Ezek miatt felírhatjuk, hogy az $Y$ hosszúságú foglaltsági intervallum $1+\tilde{v}$ számú valószínűségi változó összegével egyenlő, ahol a $\tilde{v}$ valószínűségi változó a $C_1$ kiszolgálása alatt beérkezett igények számával egyenlő. Az első a $C_1$ kiszolgálási ideje, a többi a foglaltsági részintervallumok hossza, melyek eloszlása azonos $Y$ eloszlásával. Így

\begin{displaymath} Y=x_1+X_{\tilde{v}+1}+X_{\tilde{v}}+\cdots+X_3+X_2. \end{displaymath}

Tudjuk, hogy $x_1$ $B\left(x\right)$ eloszlású és $X_k$ $G\left(y\right)$ eloszlású. Intuitíven érezhető, hogy a foglaltsági intervallumok eloszlása és a kiszolgálási idő eloszlása kapcsolatban állnak egymással. Hogy többet megtudjunk erről, számoljuk ki a következő feltételes transzformáltakat:

\begin{displaymath} E\left(e^{-sY}\ \vert\ x_1=x, \tilde{v}=k\right)=E\left(e^{-s\left(x+X_{k+1}+\cdots+X_2\right)}\right)= \end{displaymath}


\begin{displaymath} =E\left(e^{8-sx}e^{-sX_{k+1}}\cdots e^{-sX_2}\right). \end{displaymath}

A foglaltsági részintervallumok időtartamai egymástól függetlenek, ezért

\begin{displaymath} E\left(e^{-sY}\ \vert\ x_1=x, \tilde{v}=k\right)=E\left(e^{... ...t)E\left(e^{-sX_{k+1}}\right)\cdots E\left(e^{-sX_2}\right). \end{displaymath}

Mivel $x$ állandó, így $E\left(e^{-sx}\right)=e^{-sx}$, és mert a foglaltsági részintervallumok azonos eloszlásúak, melynek Laplace-Stieltjes transzformáltja $G^*\left(s\right)$, ezért

\begin{displaymath} E\left(e^{-sY}\ \vert\ x_1=x, \tilde{v}=k\right)=e^{-sx}{\left(G^*\left(s\right)\right)}^k. \end{displaymath}

Mivel $\tilde{v}$ az $x$ hosszúságú intervallum alatti beérkezések számát jelenti, ezért $\tilde{v}$ Poisson-eloszlású, várható értéke $\lambda x$. Tüntessük el a $\tilde{v}$ szerinti feltételt:

\begin{displaymath} E\left(e^{-sY}\ \vert\ x_1=x\right)=\sum_{k=0}^\infty E\lef... ...\ \vert\ x_1=x, \tilde{v}=k\right)P\left(\tilde{v}=k\right)= \end{displaymath}


\begin{displaymath} =\sum_{k=0}^\infty e^{-sx}{\left(G^*\left(s\right)\right)}^... ... x}= e^{-x\left(s+\lambda-\lambda G^*\left(s\right)\right)}. \end{displaymath}

Az $x_1$ szerinti feltételt $B\left(x\right)$ szerinti integrálással küszöböljük ki, így azt kapjuk, hogy

\begin{displaymath} G^*\left(s\right)=\int\limits_0^\infty e^{-x\left(s+\lambda-\lambda G^*\left(s\right)\right)}dB\left(x\right). \end{displaymath}

Ez éppen a kiszolgálási idő sűrűségfüggvényének Laplace-transzformáltja az $s+\lambda-\lambda G^*\left(s\right)$ helyen, azaz

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

Ezt a függvényegyenletet általában nem lehet invertálni, viszont numerikusan megoldható tetszőleges $s$ értékre a következő iterációval:

\begin{displaymath} G^*_{n+1}\left(s\right)=B^*\left(s+\lambda-\lambda G^*_n\left(s\right)\right) ,\leqno(23) \end{displaymath}

ha $0\le G^*_0\left(s\right)\le 1$. Ha $\varrho=\lambda\bar{x}<1$, akkor az eljárással a $G^*\left(s\right)$-et kapjuk meg, így megkísérelhetjük a kapott értékek numerikus inverzióját. (Lásd Kleinrock (1979)) (23) alapján a foglaltsági intervallumok eloszlásának momentumait is meg tudjuk határozni. Legyen

\begin{displaymath} g_k:=E\left(Y^k\right) , \end{displaymath}

akkor $g_k={\left(-1\right)}^kG^{*^{\left(k\right)}}\left(0\right)$ és $\overline{x^k}={\left(-1\right)}^kB^{*^{\left(k\right)}}\left(0\right)$,

\begin{displaymath} g_1=-G^{*^{\left(1\right)}}\left(0\right)={\left.-B^{*^{\le... ...+\lambda-\lambda G^*\left(s\right)\right)\right\vert}_{s=0}= \end{displaymath}


\begin{displaymath} =-B^{*^{\left(1\right)}}\left(0\right)\left(1-\lambda G^{*^{\left(1\right)}}\left(0\right)\right) , \end{displaymath}

ahol felhasználtuk, hogy ha $s=0$, akkor $s+\lambda-\lambda G^*\left(s\right)=0$. Így

\begin{displaymath} g_1=\bar{x}\left(1+\lambda g_1\right). \end{displaymath}

Mivel $\varrho=\lambda\bar{x}$, a következőt kapjuk:

\begin{displaymath} g_1={\bar{x}\over 1-\varrho}. \end{displaymath}

Két dolgot vegyünk észre. Egyrészt, hogy ez csak $\lambda$ és $\bar{x}$ függvénye, másrészt, összehasonlítva ezt az ismert $M/M/1$ rendszer paramétereivel, azt tapasztaljuk, hogy az $M/G/1$-beli foglaltsági intervallumok hosszának várható értéke azonosan számolható az $M/M/1$-ben az igények rendszerben eltöltött átlagos tartózkodási idejével.
A második momentumhoz használjuk fel az ismert összefüggéseket.


\begin{displaymath} \eqalign{ g_2=& G^{*^{\left(2\right)}}\left(s\right)={\lef... ...line{x^2}\left(1-\lambda g_1\right)^2+\bar{x}\lambda g_2.\cr} \end{displaymath}

Innen
\begin{displaymath} g_2={\overline{x^2}\left(1-\lambda g_1\right)^2\over 1-\lam... ...{\lambda \bar{x}\over 1-\varrho}\right)}^2\over 1-\varrho} , \end{displaymath}

azaz

\begin{displaymath} g_2={\overline{x^2}\over {\left(1-\varrho\right)}^3}. \end{displaymath}

Ha tovább számolunk, megfigyelhetjük, hogy a magasabb momentumok nevezőjében az $\left(1-\varrho\right)$ kitevője nő, és ez a meghatározó a momentumok viselkedésében, ha $\varrho\to 1$. Számoljuk ki még a foglaltsági intervallum hosszának szórásnégyzetét:

\begin{displaymath} \sigma_g^2=g_2-g_1^2={\overline{x^2}\over {\left(1-\varrho\... ...ho{\left(\bar{x}\right)}^2\over {\left(1-\varrho\right)}^3} , \end{displaymath}

adódik, ahol $\sigma_b^2$ a kiszolgálási idő eloszlásának szórásnégyzete. Legyen $N_{fi}$ a foglaltsági intervallum alatt kiszolgált igények száma. Vizsgáljuk meg most ennek az eloszlását,

\begin{displaymath} f_n:=P\left(N_{fi}=n\right). \end{displaymath}

Ezen diszkrét eloszlás generátorfüggvénye legyen

\begin{displaymath} H\left(z\right):=E\left(z^{N_{fi}}\right):=\sum_{n=1}^\infty f_nz^n. \end{displaymath}

Az $n=0$ tag azért hiányzik, mert egy foglaltsági intervallum alatt legalább egy igényt ki kell szolgálni. Láttuk, hogy a $\tilde{v}$ valószínűségi változó jelenti az egy igény kiszolgálási ideje alatt a rendszerbe érkező igények számát, és ennek $V\left(z\right)$ generátorfüggvényére levezettük a (8) relációt, azaz

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

egyenletet. A foglaltsági intervallum hossza meghatározásához hasonlóan most képezzük a $\tilde{v}=k$ feltételek melletti feltételes valószínűségeket. Ezek mindegyike egy foglaltsági részintervallumot generál, és az ezekben kiszolgált igények számának eloszlása szintén $\{f_n\}$. Jelölje $N_i$ az $i$-edik foglaltsági részintervallum alatt kiszolgált igények számát. Ebből

\begin{displaymath} E\left(z^{N_{f_i}}\ \vert\ \tilde{v}=k\right)=E\left(z^{1+N_1+\cdots+N_k}\right) =z\prod_{i=1}^k E\left(z^{N_i}\right). \end{displaymath}

mivel az $N_i$-k független, azonos eloszlásúak. Mivel minden $N_i$ eloszlása ugyanaz, mint $N_{f_i}$ eloszlása, ezért

\begin{displaymath} E\left(z^{N_{f_i}}\ \vert\ \tilde{v}=k\right)=z{\left(H\left(z\right)\right)}^k. \end{displaymath}

Ennek a felhasználásával a feltételes várható érték tétele alapján

\begin{displaymath} \eqalign{ H\left(z\right)=&\sum_{k=0}^\infty E\left(z^{N_{... ...z\right)\right)}^k=\cr =&zV\left(H\left(z\right)\right).\cr} \end{displaymath}

Végül (8)< szerint felírhatjuk, hogy

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

Ez meglehetősen hasonlít a foglaltsági intervallum hosszának eloszlásánál kapott eredményre. Könnyen kiszámolhatjuk belőle a foglaltsági intervallumok alatt kiszolgált igények számának $h_k$ momentumait. A Laplace-transzformált és a generátorfüggvény tulajdonságai miatt

\begin{displaymath} h_1=H^{\left(1\right)}\left(1\right)=\left. zB^{*^{\left(1\... ...left(\lambda-\lambda H\left(z\right)\right)\right\vert_{z=1}= \end{displaymath}


\begin{displaymath} =B^{*^{\left(1\right)}}\left(0\right)\left(-\lambda H^{\left(1\right)}\right)+B^*\left(0\right) , \end{displaymath}

mivel $H\left(1\right)=1$. Tehát

\begin{displaymath} h_1=\lambda\bar{x}h_1+1 , \end{displaymath}

azaz

\begin{displaymath} h_1={1\over 1-\varrho}. \end{displaymath}

Továbbá

\begin{displaymath} H^{\left(2\right)}\left(1\right)=h_2-h_1 , \end{displaymath}


\begin{displaymath} \eqalign{ H^{\left(2\right)}\left(1\right)=&\left(B^{*^{\l... ...ght)}^2}+\lambda\bar{x}H^{\left(2\right)}\left(1\right) ,\cr} \end{displaymath}

azaz

\begin{displaymath} h_2-h_1={2\varrho\left(1-\varrho\right)+\lambda^2\overline{... ...r {\left(1-\varrho\right)}^2}+ \varrho\left(h_2-h_1\right) , \end{displaymath}


\begin{displaymath} h_2\left(1-\varrho\right)={2\varrho\left(1-\varrho\right)+\lambda^2\overline{x^2}\over {\left(1-\varrho\right)}^2}+1 , \end{displaymath}


\begin{displaymath} h_2={2\varrho\left(1-\varrho\right)+\lambda^2\overline{x^2}\over {\left(1-\varrho\right)}^3}+{1\over 1-\varrho}. \end{displaymath}

A kiszolgált igények szórásnégyzete:

\begin{displaymath} \sigma_h^2=h_2-h_1^2={2\varrho\left(1-\varrho\right)+\lambd... ...)}^3}+{1\over 1-\varrho}-{1\over {\left(1-\varrho\right)}^2}= \end{displaymath}


\begin{displaymath} ={\lambda^2\overline{x^2}\over {\left(1-\varrho\right)}^3}... ...^2-\left(1-\varrho\right)\over {\left(1-\varrho\right)}^3} , \end{displaymath}

azaz

\begin{displaymath} \sigma_h^2={\varrho\left(1-\varrho\right)+\lambda^2\overline{x^2}\over {\left(1-\varrho\right)}^3}. \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ő  >>