Notação de Kendall - Kendall's notation
Na teoria das filas , uma disciplina dentro da teoria matemática da probabilidade , a notação de Kendall (ou às vezes a notação de Kendall ) é o sistema padrão usado para descrever e classificar um nó de filas. DG Kendall propôs descrever modelos de enfileiramento usando três fatores escritos A / S / c em 1953, onde A denota o tempo entre as chegadas à fila, S a distribuição do tempo de serviço ec o número de canais de serviço abertos no nó. Desde então, foi estendido para A / S / c / K / N / D, onde K é a capacidade da fila, N é o tamanho da população de empregos a serem servidos e D é a disciplina de enfileiramento .
Quando os três parâmetros finais não são especificados (por exemplo, fila M / M / 1 ), é assumido K = ∞, N = ∞ e D = FIFO .
R: O processo de chegada
Um código que descreve o processo de chegada. Os códigos usados são:
Símbolo | Nome | Descrição | Exemplos |
---|---|---|---|
M | Markoviano ou sem memória | Processo de Poisson (ou processo aleatório) de chegada (isto é, tempos exponenciais entre chegadas). | Fila M / M / 1 |
M X | lote Markov | Processo de Poisson com uma variável aleatória X para o número de chegadas de uma vez. | Fila M X / M Y / 1 |
MAPA | Processo de chegada de Markovian | Generalização do processo de Poisson. | |
BMAP | Processo de chegada em lote Markoviano | Generalização do MAP com múltiplas chegadas | |
MMPP | Processo de Poisson modulado por Markov | Processo de Poisson onde as chegadas estão em "clusters". | |
D | Distribuição degenerada | Um tempo determinístico ou fixo entre chegadas. | Fila D / M / 1 |
E k | Distribuição Erlang | Uma distribuição Erlang com k como parâmetro de forma (isto é, soma de k i.id variáveis aleatórias exponenciais ). | |
G | Distribuição geral | Embora G geralmente se refira a chegadas independentes, alguns autores preferem usar GI para ser explícito. | |
PH | Distribuição de tipo de fase | Algumas das distribuições acima são casos especiais do tipo de fase, freqüentemente usados no lugar de uma distribuição geral. |
S: A distribuição do tempo de serviço
Isso dá a distribuição do tempo de serviço de um cliente. Algumas notações comuns são:
Símbolo | Nome | Descrição | Exemplos |
---|---|---|---|
M | Markoviano ou sem memória | Tempo de serviço exponencial . | Fila M / M / 1 |
M Y | bulk Markov | Tempo de serviço exponencial com uma variável aleatória Y para o tamanho do lote de entidades atendidas de uma vez. | Fila M X / M Y / 1 |
D | Distribuição degenerada | Um tempo de serviço determinado ou fixo. | Fila M / D / 1 |
E k | Distribuição Erlang | Uma distribuição Erlang com k como parâmetro de forma (isto é, soma de k i.id variáveis aleatórias exponenciais ). | |
G | Distribuição geral | Embora G geralmente se refira ao tempo de serviço independente, alguns autores preferem usar GI para ser explícito. | Fila M / G / 1 |
PH | Distribuição de tipo de fase | Algumas das distribuições acima são casos especiais do tipo de fase, freqüentemente usados no lugar de uma distribuição geral. | |
MMPP | Processo de Poisson modulado por Markov | Distribuições de tempo de serviço exponencial , onde o parâmetro de taxa é controlado por uma cadeia de Markov. |
c : O número de servidores
O número de canais de serviço (ou servidores). A fila H / M / 1 tem um único servidor e o H / H / c fila c servidores.
K: O número de lugares na fila
A capacidade da fila ou o número máximo de clientes permitidos na fila. Quando o número está neste máximo, as chegadas futuras são recusadas. Se esse número for omitido, a capacidade será considerada ilimitada ou infinita.
- Nota: Isso às vezes é denotado como c + K, onde K é o tamanho do buffer, o número de lugares na fila acima do número de servidores c .
N: a população chamadora
O tamanho da origem da chamada. O tamanho da população de onde vêm os clientes. Uma população pequena afetará significativamente a taxa efetiva de chegada , porque, quanto mais clientes estiverem no sistema, haverá menos clientes livres disponíveis para chegar ao sistema. Se este número for omitido, a população é considerada ilimitada ou infinita.
D: A disciplina da fila
A Disciplina de Serviço ou Ordem de Prioridade que os trabalhos na fila, ou fila de espera, são servidos:
Símbolo | Nome | Descrição |
---|---|---|
FIFO / FCFS | Primeiro a entrar, primeiro a sair / primeiro a chegar, primeiro a ser servido | Os clientes são atendidos na ordem em que chegaram (usada por padrão). |
UEPS / LCFS | Último a chegar, primeiro a sair / Último a chegar, primeiro a ser servido | Os clientes são atendidos na ordem inversa à ordem em que chegaram. |
SIRO | Serviço em ordem aleatória | Os clientes são atendidos em uma ordem aleatória, sem levar em conta a ordem de chegada. |
PQ | Enfileiramento prioritário | Existem várias opções: Enfileiramento prioritário preemptivo, Enfileiramento não preemptivo, Enfileiramento justo ponderado baseado em classe, Enfileiramento justo ponderado. |
PS | Compartilhamento de processador | Os clientes são atendidos na ordem determinada, sem levar em consideração a ordem de chegada. |
- Nota : Uma prática de notação alternativa é registrar a disciplina da fila antes da população e da capacidade do sistema, com ou sem parênteses. Normalmente, isso não causa confusão porque a notação é diferente.