En la teoría de las colas , una disciplina dentro de la teoría matemática de la probabilidad , una cola M / D / 1 representa la longitud de la cola en un sistema que tiene un solo servidor, donde las llegadas están determinadas por un proceso de Poisson y los tiempos de servicio del trabajo son fijos (deterministas). El nombre del modelo está escrito en la notación de Kendall . [1] Agner Krarup Erlang publicó por primera vez este modelo en 1909, iniciando el tema de la teoría de las colas . [2] [3] Una extensión de este modelo con más de un servidor es la cola M / D / c .
Definición de modelo
Una cola M / D / 1 es un proceso estocástico cuyo espacio de estado es el conjunto {0,1,2,3, ...} donde el valor corresponde al número de entidades en el sistema, incluyendo cualquiera que esté actualmente en servicio.
- Las llegadas ocurren a una tasa λ según un proceso de Poisson y mueven el proceso del estado i al i + 1.
- Los tiempos de servicio son el tiempo determinista D (sirviendo a una tasa μ = 1 / D ).
- Un solo servidor atiende a las entidades de una en una desde el principio de la cola, de acuerdo con una disciplina de orden de llegada . Cuando se completa el servicio, la entidad abandona la cola y el número de entidades en el sistema se reduce en uno.
- El búfer es de tamaño infinito, por lo que no hay límite en la cantidad de entidades que puede contener.
Matriz de transición
La matriz de probabilidad de transición para una cola M / D / 1 con tasa de llegada λ y tiempo de servicio 1, tal que λ <1 (para la estabilidad de la cola) viene dada por P como se muestra a continuación: [4]
, , n = 0,1, ....
Métricas de rendimiento clásicas
Las siguientes expresiones presentan las métricas de rendimiento clásicas de un sistema de cola de un solo servidor, como M / D / 1, con:
- tasa de llegada ,
- tasa de servicio , y
- utilización
El número medio de entidades en el sistema, L viene dado por:
El número medio de entidades en la cola (línea), L Q viene dado por:
El tiempo medio de espera en el sistema, ω viene dado por:
El tiempo medio de espera en la cola (línea), ω Q viene dado por:
Ejemplo
Considerando un sistema que tiene un solo servidor, con una tasa de llegada de 20 entidades por hora y la tasa de servicio es una constante de 30 por hora.
Entonces, la utilización del servidor es: ρ = 20/30 = 2/3. Usando las métricas que se muestran arriba, los resultados son los siguientes: 1) Número promedio en la línea L Q = 0,6667; 2) Número promedio en el sistema L = 1.333; 3) Tiempo promedio en línea ω Q = 0.033 hora; 4) Tiempo promedio en el sistema ω = 0.067 hora.
Relaciones para el tiempo medio de espera en las colas M / M / 1 y M / D / 1
Para una cola de equilibrio M / G / 1, el valor esperado del tiempo W que pasa un cliente en la cola viene dado por la fórmula de Pollaczek-Khintchine como se muestra a continuación: [5]
donde τ es el tiempo medio de servicio; σ 2 es la varianza del tiempo de servicio; y ρ = λτ <1, siendo λ la tasa de llegada de los clientes.
Para la cola M / M / 1, los tiempos de servicio se distribuyen exponencialmente, entonces σ 2 = τ 2 y el tiempo medio de espera en la cola denotado por W M viene dado por la siguiente ecuación: [5]
Con esto, se puede derivar la ecuación correspondiente para la cola M / D / 1, asumiendo tiempos de servicio constantes. Entonces, la varianza del tiempo de servicio se vuelve cero, es decir, σ 2 = 0. El tiempo medio de espera en la cola M / D / 1 denotado como W D viene dado por la siguiente ecuación: [5]
De las dos ecuaciones anteriores, podemos inferir que la longitud media de la cola en la cola M / M / 1 es el doble que en la cola M / D / 1.
Distribución estacionaria
El número de trabajos en la cola se puede escribir como cadena de Markov tipo M / G / 1 y la distribución estacionaria encontrada para el estado i (escrito π i ) en el caso D = 1 es [4]
Demora
Defina ρ = λ / μ como la utilización; entonces el retraso medio en el sistema en la cola M / D / 1 es [6]
y en la cola:
Periodo ocupado
El período ocupado es el período de tiempo medido desde el instante en que un primer cliente llega a una cola vacía hasta el momento en que la cola está nuevamente vacía. Este período de tiempo es igual a D veces el número de clientes atendidos. Si ρ <1, entonces el número de clientes atendidos durante un período ocupado de la cola tiene una distribución de Borel con el parámetro ρ . [7] [8]
Capacidad finita
Distribución estacionaria
Se puede calcular una distribución estacionaria para el número de clientes en la cola y la longitud media de la cola utilizando funciones generadoras de probabilidad . [9]
Solución transitoria
La solución transitoria de una cola M / D / 1 de capacidad finita N, a menudo escrita M / D / 1 / N, fue publicada por García et al. en 2002. [10]
Solicitud
Incluye aplicaciones en diseño de red de área amplia , [11] donde un solo procesador central lee los encabezados de los paquetes que llegan de manera exponencial, luego calcula el siguiente adaptador al que debe ir cada paquete y despacha los paquetes en consecuencia. Aquí, el tiempo de servicio es el procesamiento del encabezado del paquete y la verificación de redundancia cíclica, que son independientes de la longitud de cada paquete que llega. Por lo tanto, se puede modelar como una cola M / D / 1. [12]
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. doi : 10.1214 / aoms / 1177728975 . JSTOR 2236285 .
- ^ Kingman, JFC (2009). "El primer siglo de Erlang y el siguiente". Sistemas de colas . 63 : 3-4. doi : 10.1007 / s11134-009-9147-4 .
- ^ Erlang, AK (1909). "La teoría de probabilidades y conversaciones telefónicas" (PDF) . NYT Tidsskrift para Matematik B . 20 : 33–39. Archivado desde el original (PDF) el 1 de octubre de 2011.
- ^ a b Nakagawa, Kenji (2005). "Sobre la expansión de la serie para las probabilidades estacionarias de una cola M / D / 1" (PDF) . Revista de la Sociedad de Investigación de Operaciones de Japón . 48 (2): 111-122. doi : 10.15807 / jorsj.48.111 .
- ^ a b c Cooper, Robert B. (1981). Introducción a la teoría de las colas . Elsevier Science Publishing Co. p. 189. ISBN 0-444-00379-7.
- ^ Cahn, Robert S. (1998). Diseño de redes de área amplia: conceptos y herramientas para la optimización . Morgan Kaufmann. pag. 319. ISBN 1558604588.
- ^ Tanner, JC (1961). "Una derivación de la distribución de Borel". Biometrika . 48 : 222–224. doi : 10.1093 / biomet / 48.1-2.222 . JSTOR 2333154 .
- ^ Haight, FA; Breuer, MA (1960). "La distribución Borel-Tanner". Biometrika . 47 : 143. doi : 10.1093 / biomet / 47.1-2.143 . JSTOR 2332966 .
- ^ Brun, Olivier; García, Jean-Marie (2000). "Solución Analítica de Colas M / D / 1 de Capacidad Finita". Revista de probabilidad aplicada . Fideicomiso de probabilidad aplicada . 37 (4): 1092–1098. doi : 10.1239 / jap / 1014843086 . JSTOR 3215497 .
- ^ García, Jean-Marie; Brun, Olivier; Gauchard, David (2002). "Solución analítica transitoria de colas M / D / 1 / N". Revista de probabilidad aplicada . Fideicomiso de probabilidad aplicada. 39 (4): 853–864. doi : 10.1239 / jap / 1037816024 . JSTOR 3216008 .
- ^ Kotobi, Khashayar; Bilén, Sven G. (2017). "Compartir espectro a través de reproductores cognitivos híbridos evaluados por un modelo de colas M / D / 1" . Revista EURASIP sobre comunicaciones inalámbricas y redes . 2017 : 85. doi : 10.1186 / s13638-017-0871-x . Consultado el 5 de mayo de 2017 .
- ^ Chan, Robert S. (1998). Diseño de redes de área amplia: conceptos y herramientas para la optimización . Morgan Kaufmann Publishers Inc. pág. 319. ISBN 1-55860-458-8.