En la teoría de las colas , una disciplina dentro de la teoría matemática de la probabilidad , la cola M / M / c (o modelo Erlang – C [1] : 495 ) es un modelo de cola multiservidor . [2] En la notación de Kendall, describe un sistema en el que las llegadas forman una sola cola y se rigen por un proceso de Poisson , hay c servidores y los tiempos de servicio del trabajo se distribuyen exponencialmente. [3] Es una generalización de la cola M / M / 1 que considera solo un servidor. El modelo con infinitos servidores es la cola M / M / ∞.
Definición de modelo
Una cola M / M / c es un proceso estocástico cuyo espacio de estado es el conjunto {0, 1, 2, 3, ...} donde el valor corresponde a la cantidad de clientes en el sistema, incluidos los que están actualmente en servicio.
- Las llegadas ocurren a una tasa λ de acuerdo con un proceso de Poisson y mueven el proceso del estado i al i +1.
- Los tiempos de servicio tienen una distribución exponencial con el parámetro μ . Si hay menos de c trabajos, algunos de los servidores estarán inactivos. Si hay más de c trabajos, los trabajos se ponen en cola en un búfer.
- El búfer es de tamaño infinito, por lo que no hay límite en la cantidad de clientes que puede contener.
El modelo se puede describir como una cadena de Markov en tiempo continuo con una matriz de tasa de transición
en el espacio de estado {0, 1, 2, 3, ...}. El modelo es un tipo de proceso de nacimiento-muerte . Escribimos ρ = λ / ( c μ ) para la utilización del servidor y requerimos ρ <1 para que la cola sea estable. ρ representa la proporción promedio de tiempo que cada uno de los servidores está ocupado (asumiendo que los trabajos que encuentran más de un servidor vacante eligen sus servidores al azar).
El diagrama de espacio de estados para esta cadena es el siguiente.
Análisis estacionario
Número de clientes en el sistema
Si la intensidad del tráfico es mayor que uno, la cola crecerá sin límite, pero si la utilización del servidor entonces el sistema tiene una distribución estacionaria con función de masa de probabilidad [4] [5]
donde π k es la probabilidad de que el sistema contenga k clientes.
La probabilidad de que un cliente que llega se vea obligado a unirse a la cola (todos los servidores están ocupados) viene dada por
que se conoce como fórmula C de Erlang y a menudo se denota C ( c , λ / μ ) o E 2, c ( λ / μ ). [4] El número medio de clientes en el sistema (en servicio y en cola) viene dado por [6]
Período ocupado del servidor
El período ocupado de la cola M / M / c puede referirse a:
- período ocupado completo: el período de tiempo entre una llegada que encuentra c −1 clientes en el sistema hasta una salida que deja el sistema con c −1 clientes
- período ocupado parcial: el período de tiempo entre una llegada que encuentra el sistema vacío hasta una salida que deja el sistema nuevamente vacío. [7]
Write [8] [9] T k = min (t: k puestos de trabajo en el sistema en el tiempo 0 + y k - 1 ofertas en el sistema en el tiempo t ) y η k ( s ) para las Laplace-Stieltjes transforman de la distribución de T k . Entonces [8]
- Para k > c , T k tiene la misma distribución que T c .
- Para k = c ,
- Para k < c ,
Tiempo de respuesta
El tiempo de respuesta es la cantidad total de tiempo que un cliente pasa tanto en la cola como en el servicio. El tiempo medio de respuesta es el mismo para todas las disciplinas de servicio que conservan el trabajo y es [6]
Clientes en la disciplina de primero en llegar, primero en ser atendido
El cliente experimenta un servicio exponencial inmediato o debe esperar a que se atienda a k clientes antes que a su propio servicio, experimentando así una distribución de Erlang con el parámetro de forma k + 1. [10]
Clientes en la disciplina de intercambio de procesadores
En una cola de procesador compartido, la capacidad de servicio de la cola se divide equitativamente entre los trabajos de la cola. En la cola M / M / c, esto significa que cuando hay co menos trabajos en el sistema, cada trabajo recibe servicio a una tasa μ . Sin embargo, cuando hay más de c trabajos en el sistema, la tasa de servicio de cada trabajo disminuye ydonde n es el número de trabajos en el sistema. Esto significa que las llegadas después de un trabajo de interés pueden afectar el tiempo de servicio del trabajo de interés. Se ha demostrado que la transformada de Laplace-Stieltjes de la distribución del tiempo de respuesta es una solución a una ecuación integral de Volterra a partir de la cual se pueden calcular los momentos. [11] Se ha ofrecido una aproximación para la distribución del tiempo de respuesta. [12] [13]
Capacidad finita
En una cola M / M / c / K, solo K clientes pueden hacer cola a la vez (incluidos los que están en servicio [4] ). Cualquier otra llegada a la cola se considera "perdida". Suponemos que K ≥ c . El modelo tiene una matriz de tasas de transición.
en el espacio de estado {0, 1, 2, ..., c , ..., K }. En el caso de que c = K , la cola M / M / c / c también se conoce como modelo Erlang – B. [1] : 495
Análisis transitorio
Consulte Takács para una solución transitoria [14] y Stadje para los resultados del período ocupado. [15]
Análisis estacionario
Las probabilidades estacionarias están dadas por [16]
El número medio de clientes en el sistema es [16].
y el tiempo medio de respuesta de un cliente es [16]
Límites de tráfico pesado
Escribiendo X ( t ) para el número de clientes en el sistema en el tiempo t , se puede demostrar que bajo tres condiciones diferentes el proceso
converge a un proceso de difusión. [1] : 490
- Fije μ y c , aumente λ y escale en n = 1 / (1 - ρ ) 2 .
- Fijar μ y ρ , aumentar λ y c , y escalar en n = c .
- Fijar como una constante β donde
y aumentar λ y c utilizando la escala de n = c o n = 1 / (1 - ρ ) 2 . Este caso se denomina régimen de Halfin-Whitt . [17]
Ver también
- Solución de expansión espectral
- Cola M / G / k
Referencias
- ↑ a b c Gautam, Natarajan (2012). Análisis de colas: métodos y aplicaciones . Prensa CRC. ISBN 9781439806586.
- ^ Harrison, Peter ; Patel, Naresh M. (1992). Modelado de rendimiento de redes de comunicación y arquitecturas informáticas . Addison – Wesley. pag. 173.
- ^ 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 .
- ^ a b c Kleinrock, Leonard (1975). Sistemas de colas Volumen 1: Teoría . págs. 101–103, 404. ISBN 0471491101.
- ^ Bolch, G .; Greiner, S .; de Meer, H .; Trivedi, KS (1998). "Sistemas de cola de una sola estación". Redes de colas y cadenas de Markov . págs. 209 –262. doi : 10.1002 / 0471200581.ch6 . ISBN 0471193666.
- ^ a b Barbeau, Michel; Kranakis, Evangelos (2007). Principios de redes ad-hoc . John Wiley e hijos. pag. 42 . ISBN 0470032901.
- ^ Artalejo, JR; López-Herrero, MJ (2001). "Análisis del período ocupado para la cola M / M / c: un enfoque algorítmico". Revista de probabilidad aplicada . 38 (1): 209–222. doi : 10.1239 / jap / 996986654 . JSTOR 3215752 .
- ^ a b Omahen, K .; Marathe, V. (1978). "Análisis y aplicaciones del ciclo de retardo para el sistema de colas M / M / c" . Revista de la ACM . 25 (2): 283. doi : 10.1145 / 322063.322072 .
- ^ Daley, DJ; Servi, LD (1998). "Períodos inactivos y ocupados en colas M / M / k estables". Revista de probabilidad aplicada . 35 (4): 950. doi : 10.1239 / jap / 1032438390 .
- ^ Iversen, Villy B. (20 de junio de 2001). "Manual de ingeniería de teletráfico UIT / ITC" (PDF) . Consultado el 7 de agosto de 2012 .
- ^ Braband, J. (1994). "Distribuciones de tiempo de espera para colas de intercambio de procesador M / M / N". Comunicaciones en estadística. Modelos estocásticos . 10 (3): 533–548. doi : 10.1080 / 15326349408807309 .
- ^ Braband, J. (1995). "Distribuciones de tiempo de espera para colas de intercambio de procesador M / M / N cerradas". Sistemas de colas . 19 (3): 331–344. doi : 10.1007 / BF01150417 .
- ^ Braband, Jens; Schassberger, Rolf (21 a 23 de septiembre de 1993). "Asignación cuántica aleatoria: un nuevo enfoque para distribuciones de tiempo de espera para colas de intercambio de procesadores M / M / N". En Walke, B .; Spaniol, O. (eds.). Messung, Modellierung und Bewertung von Rechen- und Kommunikationssystemen: 7. ITG / GI-Fachtagung . Aquisgrán: Springer. págs. 130-142. ISBN 3540572015.
- ^ Takács, L. (1962). Introducción a la teoría de las colas . Londres: Oxford University Press. págs. 12-21.
- ^ Stadje, W. (1995). "Los períodos de mucha actividad de algunos sistemas de colas". Procesos estocásticos y sus aplicaciones . 55 : 159-167. doi : 10.1016 / 0304-4149 (94) 00032-O .
- ^ a b c Allen, Arnold O. (1990). Probabilidad, estadística y teoría de colas: con aplicaciones informáticas . Publicaciones profesionales del Golfo. págs. 679–680 . ISBN 0120510510.
- ^ Halfin, Shlomo; Whitt, Ward (1981). "Límites de tráfico pesado para colas con muchos servidores exponenciales" (PDF) . Investigación operativa . 29 (3): 567–588. doi : 10.1287 / opre.29.3.567 . JSTOR 170115 .