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

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

<style> span.sum { font-size: larger; position:relative; bottom:-1px; } </style>

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: Összefoglaló a töki zh-hoz

-- Peti - 2006.11.07.