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

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) = X_w(t) + X_s(t)
• X_w(t): a várakozó igények száma a _t_ időpontban
• X_s(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[X_s]=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[X_w]=E[λ]E[W], azaz (átlagos sorhossz) = (átlagos érkezési intenzitás) * (átlagos várakozási idő)

Diszkrét Markov-lánc

• _p_i^(t)_: _i_. állapot valószínűsége _t_ időpontban
• _p_ij^(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: p_ij^(k+n)(m) = Σ_l p_il^(k)(m) p_lj⁽ⁿ⁾(m+k)
• láncra: Π^(k+n)(m) = Π^(k)(m) Π⁽ⁿ⁾(m+k)
• homogén láncra: Π^(k+n)=Π^(k)Π⁽ⁿ⁾, és P⁽ⁿ⁾=P⁽⁰⁾Πⁿ

Diszkrét Markov-lánc tulajdonságai

• homogén (homogeneity): az állapotátmeneti mátrix független az időtől: Π⁽¹⁾(t) = Π, p_ij^(k)(t) = p_ij
• irreducibilitás (irreducibility): minden állapot minden állapotból elérhető. ∀i,j állapotpárra ∃k: p_ij^(k)>0
• aperiodikusság (aperiodicity)
  • _i_ állapot aperiodikus, ha ∃n₀, hogy ∀ n>n₀ p_ii⁽ⁿ⁾>0
  • a Markov-lánc aperiodikus, ha ∀i,j ∃n₀, hogy ∀ n>n₀ p_ij⁽ⁿ⁾>0
  • ha a lánc irreducibilis és egy állapota aperiodikus, akkor a lánc is aperiodikus
• visszatérőség (recurrence)
  • f_ij^(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
  • f_ij = Σf_ij⁽ⁿ⁾
  • _i_ állapot visszatérő, ha a jövőben 1 valószínűséggel újból érintjük: f_ii=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: Σnf_ii⁽ⁿ⁾<∞
  • ha a lánc irreducibilis és egy állapota visszatérő, akkor az a lánc is visszatérő
• stabilitás (stability)
  • ∀i ∃lim_t→∞ p_i^(t)=p_i, é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 (p_ii<1)
  • homogén Markov-láncra: E(Τ_i) = 1/(1-p_ii)

Folytonos Markov-lánc

• _p_ij(t)_: P(_t_ idő múlva a _j_ állapotban lesz a rendszer | most az _i_ állapotban van)
• Π = [p_ij(t)]: állapotátmeneti mátrix
• P(t) = [p₀(t), p₁(t), ...]: állapotok eloszlása az idő függvényében
• _q_ij_: i→j állapotátmenet rátája. Σ_j q_ij = 0
• _Q_ = [q_ij]: 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: p_ij(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 ∃ lim_t→∞ p_i(t) = p_i
  • _P_ = [p₀, p₁, ...]
  • 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/-q_ii

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

-- Peti - 2006.11.07.