Cola M / M / c - M/M/c queue

En la teoría de colas , una disciplina dentro de la teoría matemática de la probabilidad , la cola M / M / c (o modelo Erlang – C ) es un modelo de colas de múltiples servidores . 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 de trabajo se distribuyen exponencialmente. 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

${\ Displaystyle Q = {\ begin {pmatrix} - \ lambda & \ lambda \\\ mu & - (\ mu + \ lambda) & \ lambda \\ & 2 \ mu & - (2 \ mu + \ lambda) & \ lambda \\ && 3 \ mu & - (3 \ mu + \ lambda) & \ lambda \\ &&&& \ ddots \\ &&&& c \ mu & - (c \ mu + \ lambda) & \ lambda \\ &&&&& c \ mu & - ( c \ mu + \ lambda) & \ lambda \\ &&&&&& c \ mu & - (c \ mu + \ lambda) & \ lambda \\ &&&&&&& \ ddots \\\ end {pmatrix}}}$

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 del 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 se utiliza el servidor , el sistema tiene una distribución estacionaria con función de masa de probabilidad.${\ Displaystyle \ rho = {\ frac {\ lambda} {c \ mu}} <1}$

${\ Displaystyle \ pi _ {0} = \ left [\ left (\ sum _ {k = 0} ^ {c-1} {\ frac {(c \ rho) ^ {k}} {k!}} \ derecha) + {\ frac {(c \ rho) ^ {c}} {c!}} {\ frac {1} {1- \ rho}} \ right] ^ {- 1}}$ ${\ Displaystyle \ pi _ {k} = {\ begin {cases} \ pi _ {0} {\ dfrac {(c \ rho) ^ {k}} {k!}}, & {\ mbox {if}} 0 <k <c \\ [10pt] \ pi _ {0} {\ dfrac {(c \ rho) ^ {k} c ^ {ck}} {c!}}, & {\ Mbox {if}} c \ leq k \ end {casos}}}$

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

${\ Displaystyle {\ text {C}} (c, \ lambda / \ mu) = {\ frac {\ left ({\ frac {(c \ rho) ^ {c}} {c!}} \ right) \ izquierda ({\ frac {1} {1- \ rho}} \ right)} {\ sum _ {k = 0} ^ {c-1} {\ frac {(c \ rho) ^ {k}} {k !}} + \ left ({\ frac {(c \ rho) ^ {c}} {c!}} \ right) \ left ({\ frac {1} {1- \ rho}} \ right)}} = {\ frac {1} {1+ \ left (1- \ rho \ right) \ left ({\ frac {c!} {(c \ rho) ^ {c}}} \ right) \ sum _ {k = 0} ^ {c-1} {\ frac {(c \ rho) ^ {k}} {k!}}}}}$

que se conoce como fórmula C de Erlang y a menudo se denota C ( c , λ / μ ) o E _{2, c} ( λ / μ ). El número medio de clientes en el sistema (en servicio y en cola) viene dado por

${\ Displaystyle {\ frac {\ rho} {1- \ rho}} {\ text {C}} (c, \ lambda / \ mu) + c \ rho.}$

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.

Escriba T _k  = min (t:  k trabajos en el sistema en el tiempo 0 ⁺ y k  - 1 trabajos en el sistema en el tiempo t ) y η _k ( s ) para la transformada de Laplace-Stieltjes de la distribución de T _k . Luego

1. Para k  >  c , T _k tiene la misma distribución que T _c .
2. Para k  =  c ,
   ${\ Displaystyle \ eta _ {c} (s) = {\ frac {c \ mu} {k \ mu + s + \ lambda - \ lambda \ eta _ {c} (s)}}.}$
3. Para k  <  c ,
   ${\ Displaystyle \ eta _ {k} (s) = {\ frac {k \ mu} {k \ mu + s + \ lambda - \ lambda \ eta _ {k + 1} (s)}}.}$

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

${\ Displaystyle {\ frac {{\ text {C}} (c, \ lambda / \ mu)} {c \ mu - \ lambda}} + {\ frac {1} {\ mu}}.}$

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.

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 y es donde 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. Se ha ofrecido una aproximación para la distribución del tiempo de respuesta. ${\ Displaystyle {\ frac {c \ mu} {n}}}$

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). Cualquier otra llegada a la cola se considera "perdida". Suponemos que K  ≥  c . El modelo tiene una matriz de tasas de transición.

${\ Displaystyle Q = {\ begin {pmatrix} - \ lambda & \ lambda \\\ mu & - (\ mu + \ lambda) & \ lambda \\ & 2 \ mu & - (2 \ mu + \ lambda) & \ lambda \\ && 3 \ mu & - (3 \ mu + \ lambda) & \ lambda \\ &&&& \ ddots \\ &&&& c \ mu & - (c \ mu + \ lambda) & \ lambda \\ &&&&& c \ mu & - ( c \ mu + \ lambda) & \ lambda \\ &&&&&&& \ ddots \\ &&&&&&& c \ mu & - (c \ mu) \\\ end {pmatrix}}}$

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.

Análisis transitorio

Vea Takács para una solución transitoria y Stadje para los resultados de períodos ocupados.

Análisis estacionario

Las probabilidades estacionarias están dadas por

${\ Displaystyle \ pi _ {0} = \ left [\ sum _ {k = 0} ^ {c} {\ frac {\ lambda ^ {k}} {\ mu ^ {k} k!}} + {\ frac {\ lambda ^ {c}} {\ mu ^ {c} c!}} \ sum _ {k = c + 1} ^ {K} {\ frac {\ lambda ^ {kc}} {\ mu ^ { kc} c ^ {kc}}} \ right] ^ {- 1}}$

${\ displaystyle \ pi _ {k} = {\ begin {cases} {\ frac {(\ lambda / \ mu) ^ {k}} {k!}} \ pi _ {0} & {\ text {for} } k = 1,2, \ ldots, c \\ {\ frac {(\ lambda / \ mu) ^ {k}} {c ^ {kc} c!}} \ pi _ {0} & {\ text { para}} k = c + 1, \ ldots, K. \ end {cases}}}$

El número medio de clientes en el sistema es

${\ Displaystyle \ mathbb {E} [N] = {\ frac {\ lambda} {\ mu}} + \ pi _ {0} {\ frac {\ rho (c \ rho) ^ {c}} {(1 - \ rho) ^ {2} c!}}}$

y el tiempo medio de respuesta de un cliente es

${\ Displaystyle \ mathbb {E} [T] = {\ frac {1} {\ mu}} + \ pi _ {0} {\ frac {\ rho (c \ rho) ^ {c}} {\ lambda ( 1- \ rho) ^ {2} c!}}}$

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

${\ Displaystyle {\ hat {X}} _ {n} (t) = {\ frac {X (nt) - \ mathbb {E} (X (nt))} {\ sqrt {n}}}}$

converge a un proceso de difusión.

1. Fije μ y c , aumente λ y escale en n  = 1 / (1 -  ρ ) ² .
2. Fije μ y ρ , aumente λ y c , y escale en n  =  c .
3. Fijar como una constante β donde
   ${\ Displaystyle \ beta = (1- \ rho) {\ sqrt {s}}}$

y aumentar λ y c utilizando la escala de n  =  c o n  = 1 / (1 -  ρ ) ² . Este caso se denomina régimen de Halfin-Whitt .

Ver también

• Solución de expansión espectral
• Cola M / G / k

Referencias