miniatura|Diagrama d'una cua M/M/1 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, 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.

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

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

SímbolNomDescripcióExemplesMmarkovià o sense memòriaProcés d'arribada Poisson (o aleatori) (és a dir, temps d'entre arribades exponencials).Cua M/M/1MXMàrkovià de mida granProcés de Poisson amb una variable X aleatòria per al nombre d'arribades alhora.Cua MX/MY/1MAPProcés d'arribada markoviàGeneralització del procés de Poisson.BMAPProcés d'arribada per lots de MarkovGeneralització del MAP amb múltiples arribadesMMPPProcés de Poisson modulat per MàrkovProcés de Poisson on les arribades es troben en «grups».DDistribució degeneradaUn temps entre arribades determinat o fix.Cua D/M/1EkDistribució 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).GDistribució generalTot i que G sol fer referència a arribades independents, alguns autors prefereixen utilitzar GI per ser explícits.PHDistribució de tipus faseAlgunes 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ímbolNomDescripcióExemplesMmarkovià o sense memòriaTemps de servei exponencial.Cua M/M/1MYMàrkovià de mida granTemps de servei exponencial amb una variable Y aleatòria per a la mida del lot d'entitats ateses alhora.Cua MX/MY/1DDistribució degeneradaUn temps entre arribades determinat o fix.Cua M/D/1EkDistribució 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).GDistribució generalTot i que G sol fer referència a arribades independents, alguns autors prefereixen utilitzar GI per ser explícits.Cua M/G/1PHDistribució de tipus faseAlgunes de les distribucions anteriors són casos especials de la distribució tipus fase, sovint utilitzats en lloc d'una distribució general.MMPPProcés de Poisson modulat per MàrkovDistribucions de temps de servei exponencials, on el paràmetre de velocitat està controlat per una cadena de Màrkov.

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

Categoria:Notació matemàtica Categoria:Teoria de cues