Notació de Kendall

En teoria de cues, una disciplina dins de la teoria matemàtica de la probabilitat, la notació de Kendall (o de vegades notació Kendall) és el sistema estàndard utilitzat per descriure i classificar un node de cua. D. G. Kendall va proposar descriure models de cua utilitzant tres factors escrits A/S/c el 1953,^[1] on A denota el temps entre les arribades a la cua, S la distribució del temps de servei i c el nombre de servidors del node. Des de llavors s'ha estès a A/S/c/K/N/D, on K és la capacitat de la cua, N és la mida de la població de llocs de treball a servir i D és la disciplina de la cua.^[2]^[3]^[4]

Quan no s'especifiquen els tres paràmetres finals (per exemple, cua M/M/1), se suposa que K = ∞, N = ∞ i D = FIFO.^[5]

A: El procés d'arribada

Un codi que descriu el procés d'arribada. Els codis utilitzats són:

Símbol	Nom	Descripció	Exemples
M	markovià o sense memòria^[6]	Procés d'arribada Poisson (o aleatori) (és a dir, temps d'entre arribades exponencials).	Cua M/M/1
M^X	Màrkovià de mida gran	Procés de Poisson amb una variable X aleatòria per al nombre d'arribades alhora.	Cua M^X/M^Y/1
MAP	Procés d'arribada markovià	Generalització del procés de Poisson.
BMAP	Procés d'arribada per lots de Markov	Generalització del MAP amb múltiples arribades
MMPP	Procés de Poisson modulat per Màrkov	Procés de Poisson on les arribades es troben en «grups».
D	Distribució degenerada	Un temps entre arribades determinat o fix.	Cua D/M/1
E_k	Distribució d'Erlang	Una distribució d'Erlang amb k com a paràmetre forma (és a dir, suma de k variables aleatòries i.i.d. exponencials).
G	Distribució general	Tot i que G sol fer referència a arribades independents, alguns autors prefereixen utilitzar GI per ser explícits.
PH	Distribució de tipus fase	Algunes de les distribucions anteriors són casos especials de la distribució tipus fase, sovint utilitzats en lloc d'una distribució general.

S: Distribució del temps de servei

Això dona la distribució del temps del servei d'un client. Algunes notacions comunes són:

Símbol	Nom	Descripció	Exemples
M	markovià o sense memòria^[6]	Temps de servei exponencial.	Cua M/M/1
M^Y	Màrkovià de mida gran	Temps de servei exponencial amb una variable Y aleatòria per a la mida del lot d'entitats ateses alhora.	Cua M^X/M^Y/1
D	Distribució degenerada	Un temps entre arribades determinat o fix.	Cua M/D/1
E_k	Distribució d'Erlang	Una distribució d'Erlang amb k com a paràmetre forma (és a dir, suma de k variables aleatòries i.i.d. exponencials).
G	Distribució general	Tot i que G sol fer referència a arribades independents, alguns autors prefereixen utilitzar GI per ser explícits.	Cua M/G/1
PH	Distribució de tipus fase	Algunes de les distribucions anteriors són casos especials de la distribució tipus fase, sovint utilitzats en lloc d'una distribució general.
MMPP	Procés de Poisson modulat per Màrkov	Distribucions de temps de servei exponencials, on el paràmetre de velocitat està controlat per una cadena de Màrkov.^[7]

c: El nombre de servidors

El nombre de canals de servei (o servidors). La cua M/M/1 té un únic servidor, i la cua M/M/c té c servidors.

K: La capacitat del sistema

La capacitat del sistema, o el nombre màxim de clients permesos en el sistema, inclosos els que estan en servei. Quan el nombre és el màxim, es desvienr les noves arribades. Si aquest número s'omet, s'assumeix que la capacitat és il·limitada o infinita.

Nota: De vegades es denota C + k on k és la mida del buffer (memòria intermèdia), el nombre de llocs de la cua per sobre del nombre de servidors C.

N: La població que truca

La mida de la font de trucada. La mida de la població de la qual provenen els clients. Una petita població afectarà significativament la velocitat d'arribada efectiva, ja que, a mesura que hi ha més treballs a les cues, queden menys disponibles per arribar al sistema. Si s'omet el nombre, es suposa que la població és il·limitada o infinita.

D: La disciplina de la cua

La política del servei o l'ordre de prioritat que son servits els traballs de la cua o de la línia d'espera:

Símbol	Nom	Descripció
FIFO / FCFS	Primer en entrar, primer en sortir. First In First Out / First Come First Served	Els clients són atesos per ordre d'arribada.
LIFO / LCFS	Últim en entrar, primer en sortir. Last in First Out / Last Come First Served	Els clients són atesos per ordre invers a l'arribada.
SIRO	Servei en ordre aleatori (Service In Random Order)	Els clients són atesos aleatòriament, sense tenir en compte l'ordre d'arribada.
PNPN	Servei prioritari (Priority service)	Els clients són atesos per prioritat, inclosos els preventius i els no-preventius (veure cua de prioritats).
PS	Compartir processos Processor Sharing	Els clients són atesos simultàniament, i cadascun rep una fracció igual de la capacitat de servei disponible.

Nota: Una pràctica de notació alternativa és registrar la disciplina de cues davant la població i la capacitat del sistema, amb parèntesi adjunt o sense. Això normalment no causa confusió perquè la notació és diferent.

Referències

↑ Kendall, D. G «Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain» (en anglès). The Annals of Mathematical Statistics, 24(3), 1953, pàg. 338. DOI: 10.1214/aoms/1177728975. JSTOR: 2236285.
↑ Lee, Alec Miller. «cap 15. A Problem of Standards of Service». A: Applied Queueing Theory (en anglès). Nova York: MacMillan, 1966. ISBN 0-333-04079-1.
↑ Taha, Hamdy A. Operations research: an introduction (en anglès), 1968.
↑ Sen, Rathindra P. Operations Research: Algorithms And Applications (en anglès). Prentice-Hall of India, 2010, p. 518. ISBN 81-203-3930-4.
↑ Gautam, N. «Queueing Theory». A: Operations Research and Management Science Handbook (en anglès). 20073432, 2007, p. 1-2 (Operations Research Series). DOI 10.1201/9781420009712.ch9. ISBN 978-0-8493-9721-9.
↑ ^6,0 ^6,1 Zonderland, M. E; Boucherie, R. J. «Queuing Networks in Health Care Systems». A: Handbook of Healthcare System Scheduling (en anglès). 168, 2012, p. 201 (International Series in Operations Research & Management Science). DOI 10.1007/978-1-4614-1734-7_9. ISBN 978-1-4614-1733-0.
↑ Zhou, Yong-Ping; Gans, Noah. «#99-40-B: A Single-Server Queue with Markov Modulated Service Times» (en anglès). Financial Institutions Center, Wharton, UPenn, 1999. Arxivat de l'original el 2010-06-21. [Consulta: 5 desembre 2019].

[1] Kendall, D. G «Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain» (en anglès). The Annals of Mathematical Statistics, 24(3), 1953, pàg. 338. DOI: 10.1214/aoms/1177728975. JSTOR: 2236285.

[2] Lee, Alec Miller. «cap 15. A Problem of Standards of Service». A: Applied Queueing Theory (en anglès). Nova York: MacMillan, 1966. ISBN 0-333-04079-1.

[3] Taha, Hamdy A. Operations research: an introduction (en anglès), 1968.

[4] Sen, Rathindra P. Operations Research: Algorithms And Applications (en anglès). Prentice-Hall of India, 2010, p. 518. ISBN 81-203-3930-4.

[5] Gautam, N. «Queueing Theory». A: Operations Research and Management Science Handbook (en anglès). 20073432, 2007, p. 1-2 (Operations Research Series). DOI 10.1201/9781420009712.ch9. ISBN 978-0-8493-9721-9.

[Zonderland-6] 6,0 ^6,1 Zonderland, M. E; Boucherie, R. J. «Queuing Networks in Health Care Systems». A: Handbook of Healthcare System Scheduling (en anglès). 168, 2012, p. 201 (International Series in Operations Research & Management Science). DOI 10.1007/978-1-4614-1734-7_9. ISBN 978-1-4614-1733-0.

[7] Zhou, Yong-Ping; Gans, Noah. «#99-40-B: A Single-Server Queue with Markov Modulated Service Times» (en anglès). Financial Institutions Center, Wharton, UPenn, 1999. Arxivat de l'original el 2010-06-21. [Consulta: 5 desembre 2019].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Teoria de cues
Nodes de cua únics	Cua D/M/1 Cua M/D/1 Cua M/D/c Cua M/M/1 Teorema de Burke Cua M/M/c Cua M/M/∞ Cua M/G/1 Fórmula de Pollaczek-Khinchine Mètode de la matriu analítica Cua M/G/k Cua G/M/1 Cua G/G/1 Fórmula de Kingman Equació de Lindley Cua d'unió de forquilles Cua de mida gran
Processos d'arribada	Procés d'arribada markovià Procés d'arribada racional Procés de Poisson
Xarxes de cues	Teorema de Gordon-Newell Anàlisi del valor mitjà Algoritme de Buzen Xarxa BCMP Xarxa G Xarxa de Jackson Equacions de trànsit Xarxa de Kelly
Polítiques de servei	Compartiment de processos FIFO LIFO Round-robin Temps restant més curt Treball més curt
Conceptes clau	Cadena de Màrkov en temps continu Llei de Little Mètode de Beneš Mètode de descomposició Notació de Kendall Solució en forma de producte Equació d'equilibri Quasireversibilitat Mètode de servidor equivalent al flux Teorema de l'arribada
Teoremes de límit	Aproximació al trànsit intens Moviment brownià reflectit Límit fluid Teoria del camp mitjà
Extensions	Cua de prova de nou Cua fluida Pèrdua de xarxa Sistema de votació Xarxa de cues adversàries Xarxa de cues en capes
Sistema d'informació	Canonada Congestió de xarxa Control de flux Cua de missatges Distribució d'Erlang Enginyeria de tràfic Erlang Memòria intermèdia Planificador Planificador de xarxes Qualitat de servei