En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , la notación de Kendall (o, a veces, la notación de Kendall ) es el sistema estándar utilizado para describir y clasificar un nodo de cola. DG Kendall propuso describir modelos de colas usando tres factores escritos A / S / c en 1953 [1] donde A denota el tiempo entre llegadas a la cola, S la distribución del tiempo de servicio yc el número de canales de servicio abiertos en el nodo. Desde entonces se ha extendido a A / S / c / K / N / D donde K es la capacidad de la cola, Nes el tamaño de la población de trabajos a servir y D es la disciplina de hacer cola . [2] [3] [4]
Cuando no se especifican los tres parámetros finales (por ejemplo, cola M / M / 1 ), se asume que K = ∞, N = ∞ y D = FIFO . [5]
A: El proceso de llegada
Un código que describe el proceso de llegada. Los códigos utilizados son:
Símbolo | Nombre | Descripción | Ejemplos de |
---|---|---|---|
METRO | Markoviano o sin memoria [6] | Proceso de Poisson (o aleatorio) proceso de llegada (es decir, tiempos entre llegadas exponenciales ). | Cola M / M / 1 |
M X | lote Markov | Proceso de Poisson con una variable aleatoria X para el número de llegadas al mismo tiempo. | Cola M X / M Y / 1 |
MAPA | Proceso de llegada de Markov | Generalización del proceso de Poisson. | |
BMAP | Proceso de llegada por lotes de Markov | Generalización del MAP con múltiples llegadas | |
MMPP | Proceso de poisson modulado por Markov | Proceso de Poisson donde las llegadas se encuentran en "clusters". | |
D | Distribución degenerada | Un tiempo entre llegadas determinista o fijo. | Cola D / M / 1 |
E k | Distribución de Erlang | Una distribución de Erlang con k como parámetro de forma (es decir, suma de k i.id variables aleatorias exponenciales ). | |
GRAMO | Distribución general | Aunque G generalmente se refiere a llegadas independientes, algunos autores prefieren usar GI para ser explícitos. | |
PH | Distribución de tipo de fase | Algunas de las distribuciones anteriores son casos especiales del tipo de fase, que a menudo se utilizan en lugar de una distribución general. |
S: la distribución del tiempo de servicio
Esto da la distribución del tiempo del servicio de un cliente. Algunas notaciones comunes son:
Símbolo | Nombre | Descripción | Ejemplos de |
---|---|---|---|
METRO | Markoviano o sin memoria [6] | Tiempo de servicio exponencial . | Cola M / M / 1 |
M Y | a granel Markov | Tiempo de servicio exponencial con una variable aleatoria Y para el tamaño del lote de entidades atendidas al mismo tiempo. | Cola M X / M Y / 1 |
D | Distribución degenerada | Un tiempo de servicio determinista o fijo. | Cola M / D / 1 |
E k | Distribución de Erlang | Una distribución de Erlang con k como parámetro de forma (es decir, suma de k i.id variables aleatorias exponenciales ). | |
GRAMO | Distribución general | Aunque G generalmente se refiere al tiempo de servicio independiente, algunos autores prefieren usar GI para ser explícitos. | Cola M / G / 1 |
PH | Distribución de tipo de fase | Algunas de las distribuciones anteriores son casos especiales del tipo de fase, que a menudo se utilizan en lugar de una distribución general. | |
MMPP | Proceso de poisson modulado por Markov | Distribuciones exponenciales del tiempo de servicio, donde el parámetro de tarifa está controlado por una cadena de Markov. [7] |
c : el número de servidores
El número de canales de servicio (o servidores). La cola M / M / 1 tiene un solo servidor y la cola M / M / c servidores.
K: el número de lugares en la cola
La capacidad de la cola o el número máximo de clientes permitidos en la cola. Cuando el número está en este máximo, se rechaza la llegada de más personas. Si se omite este número, se supone que la capacidad es ilimitada o infinita.
- Nota: Esto a veces se denota c + K donde K es el tamaño del búfer, el número de lugares en la cola por encima del número de servidores c .
N: La población que llama
El tamaño de la fuente de la llamada. El tamaño de la población de la que proceden los clientes. Una población pequeña afectará significativamente la tasa de llegada efectiva , porque, a medida que hay más clientes en el sistema, hay menos clientes gratuitos disponibles para ingresar al sistema. Si se omite este número, se supone que la población es ilimitada o infinita.
D: La disciplina de la cola
La disciplina de servicio o orden de prioridad de que se atiendan los trabajos en la cola o en la fila de espera:
Símbolo | Nombre | Descripción |
---|---|---|
FIFO / FCFS | Primero en entrar, primero en salir / Primero en llegar, primero en ser servido | Los clientes son atendidos en el orden en que llegaron (utilizado por defecto). |
LIFO / LCFS | Último en entrar, primero en salir / Último en llegar, primero en ser servido | Los clientes son atendidos en orden inverso al orden en el que llegaron. |
SIRO | Servicio en orden aleatorio | Los clientes son atendidos en un orden aleatorio sin tener en cuenta el orden de llegada. |
PQ | Cola de prioridad | Hay varias opciones: Cola prioritaria preventiva, Cola no preventiva, Cola justa ponderada basada en clase, Cola justa ponderada. |
PD | Compartir procesador | Los clientes son atendidos en el orden determinado sin tener en cuenta el orden de llegada. |
- Nota : Una práctica de notación alternativa es registrar la disciplina de la cola antes de la población y la capacidad del sistema, con o sin entre paréntesis. Normalmente, esto no causa confusión porque la notación es diferente.
Referencias
- ^ Kendall, DG (1953). "Procesos estocásticos que ocurren en la teoría de las colas y su análisis por el método de la cadena de Markov incrustada" . Los Anales de Estadística Matemática . 24 (3): 338–354. doi : 10.1214 / aoms / 1177728975 . JSTOR 2236285 .
- ^ Lee, Alec Miller (1966). "Un problema de estándares de servicio (Capítulo 15)". Teoría aplicada de las colas . Nueva York: MacMillan. ISBN 0-333-04079-1.
- ^ Taha, Hamdy A. (1968). Investigación de operaciones: una introducción (edición preliminar).
- ^ Sen, Rathindra P. (2010). Investigación operativa: algoritmos y aplicaciones . Prentice-Hall de la India. pag. 518. ISBN 978-81-203-3930-9.
- ^ Gautam, N. (2007). "Teoría de las colas". Manual de investigación de operaciones y ciencias de la gestión . Serie de investigación de operaciones. 20073432 . págs. 1-2. doi : 10.1201 / 9781420009712.ch9 . ISBN 978-0-8493-9721-9.
- ^ a b Zonderland, ME; Boucherie, RJ (2012). "Redes de colas en sistemas sanitarios". Manual de programación del sistema sanitario . Serie Internacional en Investigación de Operaciones y Ciencias de la Gestión. 168 . pag. 201. doi : 10.1007 / 978-1-4614-1734-7_9 . ISBN 978-1-4614-1733-0.
- ^ Zhou, Yong-Ping; Gans, Noah (octubre de 1999). "# 99-40-B: una cola de un solo servidor con tiempos de servicio modulados de Markov" . Centro de Instituciones Financieras, Wharton, UPenn . Consultado el 11 de enero de 2011 .