Tömegkiszolgálás - Fogalmak és jelölések

A VIK Wikiből
A lap korábbi változatát látod, amilyen Szikszayl (vitalap | szerkesztései) 2014. március 13., 13:54-kor történt szerkesztése után volt.
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez
← Vissza az előző oldalra – Tömegkiszolgálás

Alapfogalmak

Ráta jellegű mennyiségek

(mértékegység: 1/s, 1/óra, stb)

  • Érkezési ráta
    • λ(t) = pillanatnyi érkezési ráta, mértékegysége: [kérés/idő]
    • λi = érkezési ráta _i_ sorhossz mellett
    • _E[λ]_: várható érkezési ráta, csak stabil rendszerre értelmezett. E[λ] = ΣP(X=i)λi
  • Kiszolgálási intenzitás
    • _μ(t)_: pillanatnyi kiszolgálási intenzitás, mértékegysége: [kiszolgált kérés/idő]
    • μi = kiszolgálási intenzitás _i_ sorhossz mellett
  • Távozási ráta
    • S(t): pillanatnyi távozási ráta
    • E[S]: várható távozási ráta, csak stabil rendszerre értelmezett. E[S] = ΣP(X=i)μi

Idő jellegű mennyiségek

  • _W_ = várakozással töltött idő
    • E[W] = egy igény átlagos várakozással töltött ideje.
  • _x_ = kiszolgálási idő
    • E[x] = egy igény átlagos kiszolgálási ideje.
    • Exponenciális eloszlású kiszolgálási idő esetén E[x] = 1/μ
  • _T_ = rendszerben töltött idő
    • E[T]: egy igény rendszerben átlagosan eltöltött ideje.
  • E[W] + E[x] = E[T]

Darabszám jellegű mennyiségek

  • X(t): a rendszerben lévő várakozó és kiszolgálás alatti igények száma a _t_ időpontban, valószínűségi változó
    • X: a rendszerbeli igények számának eloszlása, ha az eloszlás független az időtől
    • X(t) = Xw(t) + Xs(t)
  • Xw(t): a várakozó igények száma a _t_ időpontban
  • Xs(t): a kiszolgálás alatti igények száma a _t_ időpontban
  • U(t): a munkahátralék a _t_ időpontban, azaz mennyi idő alatt ürülne ki a rendszer, ha nem érkezne több kérés

Folyamegyensúly

  • Folyamegyensúly: veszteségmentes és stabil rendszerben E[λ]=E[S]
    • M/M/1 rendszerre alkalmazva λ=S és P(X=0)=1-λ/μ

Little-formula

  • Munkamegőrző (work-conserving) rendszer: ha van várakozó kérés és szabad kiszolgáló, a kiszolgálás azonnal megkezdődik
  • Little-formula: veszteségmentes és munkamegőrző rendszerben tetszőleges kiszolgálási elv mellett E[X]=E[λ]E[T], ha léteznek a várható értékek. Azaz (rendszerbeli igények átlagos száma) = (átlagos érkezési intenzitás) * (rendszerben eltöltött átlagos idő)
    • Probléma: _T_ függ λ-tól, ezért a képlet alkalmazhatósága ilyen formában nehézkes
    • Alkalmazás kiszolgálóra: E[Xs]=E[λ]E[x], azaz (kiszolgálás alatti igények átlagos száma) = (átlagos érkezési intenzitás) * (átlagos kiszolgálási idő)
    • Alkalmazás pufferra: E[Xw]=E[λ]E[W], azaz (átlagos sorhossz) = (átlagos érkezési intenzitás) * (átlagos várakozási idő)

Diszkrét Markov-lánc

  • _pi(t)_: _i_. állapot valószínűsége _t_ időpontban
  • _pij(k)(t)_: _k_ lépéses i→j átmeneti valószínűség _t_ időpontban
  • (k)(t)_: _k_ lépéses átmeneti valószínűségmátrix _t_ időpontban

Chapman-Kolmogorov egyenlőség

  • állapotátmenetre: pij(k+n)(m) = Σl pil(k)(m) plj(n)(m+k)
  • láncra: Π(k+n)(m) = Π(k)(m) Π(n)(m+k)
  • homogén láncra: Π(k+n)=Π(k)Π(n), és P(n)=P(0)Πn

Diszkrét Markov-lánc tulajdonságai

  • homogén (homogeneity): az állapotátmeneti mátrix független az időtől: Π(1)(t) = Π, pij(k)(t) = pij
  • irreducibilitás (irreducibility): minden állapot minden állapotból elérhető. i,j állapotpárra k: pij(k)>0
  • aperiodikusság (aperiodicity)
    • _i_ állapot aperiodikus, ha n0, hogy n>n0 pii(n)>0
    • a Markov-lánc aperiodikus, ha i,j n0, hogy n>n0 pij(n)>0
    • ha a lánc irreducibilis és egy állapota aperiodikus, akkor a lánc is aperiodikus
  • visszatérőség (recurrence)
    • fij(k) homogén Markov-láncban annak a valószínűsége, hogy ha _i_ állapotban vagyunk, _j_ állapotot legközelebb _k_ lépés múlva érintjük
    • fij = Σfij(n)
    • _i_ állapot visszatérő, ha a jövőben 1 valószínűséggel újból érintjük: fii=1
    • _i_ állapot pozitív visszatérő, ha visszatérő, és a következő előfordulás idejének várható értéke véges: Σnfii(n)<∞
    • ha a lánc irreducibilis és egy állapota visszatérő, akkor az a lánc is visszatérő
  • stabilitás (stability)
    • i limt→∞ pi(t)=pi, és ez a határérték független a kezdőállapottól
    • az eloszlás határértékét egyensúlyi eloszlásnak (stationary distribution) hívjuk
  • stabilitás feltétele
    • véges Markov-láncra: stabil irreducibilis és aperiodikus
    • végtelen Markov-láncra: stabil irreducibilis, aperiodikus és pozitív visszatérő
    • végtelen Markov-láncra: stabil irreducibilis, aperiodikus és teljesül a Foster-kritérium
  • _i_ állapot tartásideje: átlagosan hány lépésig maradunk az _i_ állapotban (pii<1)
    • homogén Markov-láncra: E(Τi) = 1/(1-pii)

Folytonos Markov-lánc

  • _pij(t)_: P(_t_ idő múlva a _j_ állapotban lesz a rendszer | most az _i_ állapotban van)
  • Π = [pij(t)]: állapotátmeneti mátrix
  • P(t) = [p0(t), p1(t), ...]: állapotok eloszlása az idő függvényében
  • _qij_: i→j állapotátmenet rátája. Σj qij = 0
  • _Q_ = [qij]: rátamátrix

Folytonos Markov-lánc tulajdonságai

  • irreducibilitás: minden állapot minden állapotból véges időn belül elérhető. i,j állapotpárra t: pij(t)>0
  • visszatérőség: ugyanúgy, mint diszkrét esetben
    • ha a lánc irreducibilis és egy állapota visszatérő, akkor a lánc is visszatérő
  • stabilitás feltétele
    • véges Markov-láncra: stabil irreducibilis (periodikusság nem értelmezhető)
    • végtelen Markov-láncra: stabil irreducibilis és pozitív visszatérő
    • végtelen Markov-láncra: stabil teljesül a Foster-kritérium
  • határeloszlás
    • stabil láncra limt→∞ pi(t) = pi
    • _P_ = [p0, p1, ...]
    • meghatározása: a PQ=0 egyenletrendszert vagy az állapotgráf vágásaira felírt folyamegyensúlyi egyenleteket kell megoldani.
  • _i_ állapot tartásideje: átlagosan mennyi ideig maradunk az _i_ állapotban
    • homogén Markov-láncra: E(Τi) = 1/-qii

Lásd még: Tömegkiszolgálás - Összefoglaló

-- Peti - 2006.11.07.