Kendallsova notace - Kendalls notation - Wikipedia

Frontační diagram M / M / 1
Uzel zařazování do fronty M / M / 1

v teorie front, disciplína v rámci matematické teorie pravděpodobnosti, Kendallova notace (nebo někdy Kendallova notace) je standardní systém používaný k popisu a klasifikaci uzlového frontu. D. G. Kendall navržený popis modelů čekání na frontu pomocí tří písemných faktorů A / S /C v roce 1953[1] kde A označuje čas mezi příchody do fronty, S rozložení času služby a C počet kanálů služeb otevřených v uzlu. Od té doby byla rozšířena na A / S /C/K./N/ D kde K. je kapacita fronty, N je velikost populace pracovních míst, která mají být obsloužena, a D je disciplína ve frontě.[2][3][4]

Pokud nejsou zadány poslední tři parametry (např. Fronta M / M / 1 ), je předpokládáno K. = ∞, N = ∞ a D =FIFO.[5]

Odpověď: Proces příjezdu

Kód popisující proces příjezdu. Použité kódy jsou:

SymbolnázevPopisPříklady
MMarkovian nebo bez paměti[6]Poissonův proces (nebo náhodný) proces příjezdu (tj. exponenciální časy mezi příjezdy).Fronta M / M / 1
MXvárka MarkovPoissonův proces s náhodnou proměnnou X pro počet příchozích najednou.MX/ MY/ 1 fronta
MAPAMarkovianský proces příjezduZobecnění Poissonova procesu.
BMAPDávkový proces příjezdu MarkovianZobecnění MAPA s více příjezdy
MMPPMarkov modulovaný Poissonův procesPoissonův proces, kdy jsou příjezdy ve „klastrech“.
DDegenerovaná distribuceDeterministický nebo pevný čas mezi přílety.Fronta D / M / 1
EkErlang distribuceErlangská distribuce s k jako parametr tvaru (tj. součet k i.i.d. exponenciální náhodné proměnné).
GObecné rozděleníAčkoli G obvykle se odkazuje na nezávislé příjezdy, někteří autoři raději používají GI být explicitní.
PHFázová distribuceNěkteré z výše uvedených distribucí jsou speciální případy fázového typu, často používané místo obecné distribuce.

S: Distribuce času služby

To poskytuje rozložení času služby zákazníkovi. Některé běžné notace jsou:

SymbolnázevPopisPříklady
MMarkovian nebo bez paměti[6]Exponenciální doba služby.Fronta M / M / 1
MYhromadně MarkovExponenciální doba služby s náhodnou proměnnou Y pro velikost dávky entit obsluhovaných najednou.MX/ MY/ 1 fronta
DDegenerovaná distribuceDoba deterministická nebo pevná.Fronta M / D / 1
EkErlang distribuceErlangská distribuce s k jako parametr tvaru (tj. součet k i.i.d. exponenciální náhodné proměnné).
GObecné rozděleníAčkoli G obvykle se odkazuje na dobu nezávislé služby, někteří autoři raději používají GI být explicitní.Fronta M / G / 1
PHFázová distribuceNěkteré z výše uvedených distribucí jsou speciální případy fázového typu, často používané místo obecné distribuce.
MMPPMarkov modulovaný Poissonův procesExponenciální distribuce času služby, kde je parametr rychlosti řízen Markovovým řetězcem.[7]

C: Počet serverů

Počet servisních kanálů (nebo serverů). The Fronta M / M / 1 má jeden server a Fronta M / M / c C servery.

K: Počet míst ve frontě

Kapacita fronty nebo maximální počet zákazníků povolených ve frontě. Když je počet na tomto maximu, další příchozí jsou odvráceni. Pokud je tento počet vynechán, předpokládá se, že kapacita je neomezená nebo nekonečná.

Poznámka: Toto je někdy označováno C + K. kde K. je velikost vyrovnávací paměti, počet míst ve frontě nad počtem serverůC.

N: Volající populace

Velikost zdroje volání. Velikost populace, ze které zákazníci pocházejí. Malá populace výrazně ovlivní efektivní míra příjezdu, protože s rostoucím počtem úloh je v systému k dispozici méně. Pokud je tento počet vynechán, předpokládá se, že populace je neomezená nebo nekonečná.

D: Disciplína fronty

Servisní disciplína nebo prioritní objednávka, že jsou obsluhovány úlohy ve frontě nebo na čekací lince:

SymbolnázevPopis
FIFO / FCFSFirst In First Out / First Come First ServedZákazníci jsou obsluhováni v pořadí, v jakém dorazili (standardně používáno).
LIFO / LCFSLast in First Out / Last Come First ServedZákazníci jsou obsluhováni v opačném pořadí, než v jakém dorazili.
SIROSlužba v náhodném pořadíZákazníci jsou obsluhováni v náhodném pořadí bez ohledu na pořadí příjezdu.
PQPrioritní řazeníExistuje několik možností: Preventivní prioritní řazení, Nepreventivní řazení, Tříděné vážené spravedlivé řazení, Vážené spravedlivé řazení.
PSSdílení procesoruZákazníci jsou obsluhováni v určeném pořadí bez ohledu na pořadí příjezdu.
Poznámka: Alternativním notačním postupem je zaznamenat frontovou disciplínu před populaci a kapacitu systému, s uzavřenou závorkou nebo bez ní. To obvykle nezpůsobuje zmatek, protože notace je odlišná.

Reference

  1. ^ Kendall, D. G. (1953). „Stochastické procesy vyskytující se v teorii front a jejich analýza metodou zapuštěného Markovova řetězce“. Annals of Mathematical Statistics. 24 (3): 338–354. doi:10.1214 / aoms / 1177728975. JSTOR  2236285.
  2. ^ Lee, Alec Miller (1966). „Problém standardů služby (kapitola 15)“. Aplikovaná teorie front. New York: MacMillan. ISBN  0-333-04079-1.
  3. ^ Taha, Hamdy A. (1968). Operační výzkum: úvod (Předběžné vydání.).
  4. ^ Sen, Rathindra P. (2010). Operační výzkum: Algoritmy a aplikace. Prentice-Hall of India. str. 518. ISBN  978-81-203-3930-9.
  5. ^ Gautam, N. (2007). "Teorie řazení". Příručka pro operační výzkum a řízení. Série operačního výzkumu. 20073432. s. 1–2. doi:10.1201 / 9781420009712.ch9. ISBN  978-0-8493-9721-9.
  6. ^ A b Zonderland, M.E .; Boucherie, R. J. (2012). "Sítě ve frontě v systémech zdravotní péče". Příručka plánování systému zdravotní péče. International Series in Operations Research & Management Science. 168. str. 201. doi:10.1007/978-1-4614-1734-7_9. ISBN  978-1-4614-1733-0.
  7. ^ Zhou, Yong-Ping; Gans, Noah (říjen 1999). „# 99-40-B: Fronta pro jeden server s časem modulovaných služeb Markov“. Centrum finančních institucí, Wharton, UPenn. Citováno 2011-01-11.