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]

Diagrama d'una cua M/M/1

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'arribadaModifica

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
MX Màrkovià de mida gran Procés de Poisson amb una variable X aleatòria per al nombre d'arribades alhora. Cua MX/MY/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
Ek 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 serveiModifica

Això dóna 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
MY 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 MX/MY/1
D Distribució degenerada Un temps entre arribades determinat o fix. Cua M/D/1
Ek 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 servidorsModifica

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

K: La capacitat del sistemaModifica

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 trucaModifica

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 cuaModifica

Vegeu també: Planificador de xarxa

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ènciesModifica

  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. 
  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.