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$](img42.gif)
paraméterű Poisson-folyamat, vagyis a beérkezési
idközök
![$\lambda$](img42.gif)
paraméterű exponenciális eloszlású valószínűségi
változók. A kiszolgálási idők
![$\mu$](img464.gif)
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
![$X(t)$](img282.gif)
a
![$t$](img18.gif)
időpillanatban a rendszerben tartózkodó igények számát,
és azt mondjuk, hogy a rendszer a
![$k$](img232.gif)
állapotban van, ha
![$X(t)=k$](img465.gif)
. Mivel a fellépő valószínűségi változók
exponenciális eloszlásúak, vagyis emlékezet nélküliek,
az
![$X(t)$](img282.gif)
folytonos idejű Markov-lánc lesz. Vizsgáljuk meg a rendszer
állapotváltozásainak valószínűségeit egy adott
![$h$](img284.gif)
időtartam alatt:
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
![$o(h)$](img285.gif)
-val egyenlő, így
Az előbbiekhez hasonlóan írható fel annak valószínűsége,
hogy a rendszer
![$k$](img232.gif)
állapotban volt és a
![$h$](img284.gif)
időtartam után a
![$k-1$](img297.gif)
állapotba került:
Könnyen látható továbbá, hogy
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:
Vagyis az összes születési intenzitás
![$\lambda$](img42.gif)
, az összes halálozási intenzitás pedig
![$\mu$](img464.gif)
. 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:
vagyis
Az eredmény kézenfekvő. Az ergodikusság feltétele
általánosságban (és így annak is, hogy egy
![$P_k>0$](img474.gif)
stacionárius megoldást kapjunk)
![$S_1<\infty$](img475.gif)
és
![$S_2=\infty$](img476.gif)
; esetünkben az első feltétel:
Az
![$S_1$](img478.gif)
sor akkor és csak akkor konvergens, ha
Az ergodicitás második feltétele esetünkben
Ez akkor teljesül, ha
![$\lambda /\mu \leq 1$](img481.gif)
. 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 $](img482.gif)
. A
![$P_0$](img323.gif)
valószínűség kiszámolásához a normalizáló
feltételt használjuk és azt kapjuk, hogy
Mivel
![$\lambda <\mu $](img482.gif)
, ezért a sor konvergens, és így
A kihasználtsági tényező
![$\varrho ={\lambda \over \mu }$](img485.gif)
vagy
![$1$](img44.gif)
. A stabilitás feltétele miatt a
![$0\leq \varrho <1$](img486.gif)
egyenlőséget meg kell követelni. Ez biztosítja,
hogy
![$P_0>0$](img396.gif)
legyen. Így
amely valóban valószínűségi eloszlás,
nevezetesen a geometriai eloszlás. A rendszer
![{\dlt jellemzői}](img488.gif)
:
(I.) A rendszerben tartózkodó igények átlagos száma:
A rendszerben tartózkodó igények számának
szórásnégyzete:
(II.) A várakozó igények átlagos száma
(átlagos sorhossz):
Az átlagos sorhossz szórásnégyzete:
(III.) A szerver kihasználtsága:
(4) alapján látható, hogy
ahol
![$E\delta$](img436.gif)
a
kiszolgáló átlagos foglaltsági periódushossza,
![${1 \over \lambda }$](img496.gif)
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$](img42.gif)
paraméterrel. Így
melyből
(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,
ahol
![$P_k(t)$](img254.gif)
- mint korábban is - annak valószínűsége,
hogy a
![$t$](img18.gif)
pillanatban a rendszer a
![$k$](img232.gif)
állapotban van,
![$R_k(t))$](img500.gif)
pedig annak valószínűsége, hogy egy a
![$t$](img18.gif)
pillanatban érkező igény a rendszert a
![$k$](img232.gif)
állapotban találja. Jelölje
azt az eseményt, hogy egy beérkezés történik
a
![$(t,t+\Delta t)$](img226.gif)
intervallumban. Ekkor
ahol
![$X(t)$](img282.gif)
a rendszerbeli igények száma a
![$t$](img18.gif)
pillanatban. Felhasználva a feltételes valószínűség
definícióját,
Poisson-folyamat esetén tudjuk, hogy (az emlékezetnélküliség
miatt) az
![$A(t,t+\Delta t)$](img505.gif)
esemény nem függ a
![$t$](img18.gif)
pillanatban a rendszerben tartózkodó igények számától
(és magától a
![$t$](img18.gif)
időtől sem), ezért
így
Azaz, annak valószínűsége, hogy egy beérkező
igény a rendszert a
![$k$](img232.gif)
állapotban találja, éppen azzal a valószínűséggel
egyezik meg, hogy a rendszer a
![$k$](img232.gif)
állapotban van. Ha egy tetszőleges pillanatban egy igény
érkezik,
![$P_0$](img323.gif)
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
![$n$](img20.gif)
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ó
![$n-1$](img508.gif)
igény elhagyja a rendszert. Feltettük, hogy a kiszolgálások
egymástól függetlenek és
![$\mu$](img464.gif)
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$](img509.gif)
vagy (Erlang-) eloszlású
![$\mu$](img464.gif)
és
![$n$](img20.gif)
paraméterrel. Emlékeztetőül az
![$n$](img20.gif)
és
![$\mu$](img464.gif)
paraméterű Erlang-eloszlás sűrűségfüggvénye:
Jelölje
![$f_W(x)$](img511.gif)
egy tetszőleges igény várakozási idejének
sűrűségfüggvényét,
![$x>0$](img512.gif)
. A teljes valószínűség tétele értelmében:
Tehát
Így
Az átlagos várakozási idő:
(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:
Az eloszlásfüggvény:
Vagyis azt kaptuk, hogy a tartózkodási idő is exponenciális
eloszlású
![$\mu (1-\varrho )=\mu -\lambda $](img522.gif)
paraméterrel. Ezért az átlagos
rendszerbeli tartózkodási idő:
Továbbá, nyilvánvaló, hogy
Vegyük észre, hogy
Továbbá
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=$](img528.gif)
?