16.22: Cadenas de Colas de Tiempo Continuo

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

Teoría Básica

Introducción

En un modelo de cola, los clientes llegan a una estación para recibir servicio. Como siempre, los términos son genéricos; aquí hay algunos ejemplos típicos:

• Los clientes son personas y la estación de servicio es una tienda.
• Los clientes son solicitudes de archivo y la estación de servicio es un servidor web.

Figura\(\PageIndex{1}\): Diez clientes y un servidor

Los modelos de colas pueden ser bastante complejos, dependiendo de factores como la distribución de probabilidad que gobierna la llegada de los clientes, la distribución de probabilidad que gobierna el servicio de los clientes, el número de servidores y el comportamiento de los clientes cuando todos los servidores están ocupados. En efecto, la teoría de colas tiene su propio léxico para indicar algunos de estos factores. En esta sección, discutiremos algunas de las cadenas básicas de colas de tiempo continuo. En un sentido general, el interés principal en cualquier modelo de colas es el número de clientes en el sistema en función del tiempo, y en particular, si los servidores pueden manejar adecuadamente el flujo de clientes. Esta sección es paralela a la sección sobre cadenas de colas de tiempo discreto.

Nuestros supuestos principales son los siguientes:

1. Hay\( k \in \N_+ \cup \{\infty\} \) servidores.
2. Los clientes llegan de acuerdo a un proceso de Poisson con tarifa\( \mu \in (0, \infty) \).
3. Si todos los servidores están ocupados, un nuevo cliente va al final de una sola línea de clientes esperando servicio.
4. El tiempo requerido para atender a un cliente tiene una distribución exponencial con parámetro\( \nu \in (0, \infty) \).
5. Los tiempos de servicio son independientes de cliente a cliente, y son independientes del proceso de llegada.

Suposición (b) significa que los tiempos entre llegadas de clientes son independientes y distribuidos exponencialmente, con parámetro\( \mu \). La suposición (c) significa que tenemos un modelo primero en entrar, primero en salir, a menudo abreviado FIFO. Tenga en cuenta que hay tres parámetros en el modelo: el número de servidores\( k \), el parámetro exponencial\( \mu \) que gobierna las llegadas y el parámetro exponencial\( \nu \) que gobierna los tiempos de servicio. Los casos especiales\( k = 1 \) (un solo servidor) y\( k = \infty \) (infinitamente muchos servidores) merecen una atención especial. Como se puede adivinar, los supuestos conducen a una cadena de Markov en el tiempo continuo.

Dejar\( X_t \) denotar el número de clientes en el sistema (esperando en la fila o siendo atendidos) en el momento\( t \in [0, \infty) \). Entonces\( \bs{X} = \{X_t: t \in [0, \infty)\} \) es una cadena de Markov en tiempo continuo\( \N \), conocida como la cadena M/M/\( k \) cola.

En cuanto a la estructura básica de la cadena, las cantidades importantes son los parámetros exponenciales para los estados y la matriz de transición para la cadena de salto incrustada.

Para la\( k \) cadena\( \bs{X} \) M/M/

1. La función de parámetro exponencial\( \lambda \) viene dada por\( \lambda(x) = \mu + \nu x \) if\( x \in \N \) y\( x \lt k \) y\( \lambda(x) = \mu + \nu k \) if\( x \in \N \) y\( x \ge k \).
2. La matriz de transición\( Q \) para la cadena de salto viene dada por\ begin {align*} Q (x, x - 1) & =\ frac {\ nu x} {\ mu +\ nu x},\; Q (x, x + 1) =\ frac {\ mu} {\ mu +\ nu x},\ quad x\ in\ N,\, x\ lt k\\ Q (x, x - 1) & =\ frac {\ nu k} {\ mu +\ nu k},\; Q (x, x + 1) =\ frac {\ mu} {\ mu +\ nu k},\ quad x\ in\ N, x\ ge k\ end {align*}

Entonces la cadena M/M/ es una\( k \) cadena de nacimiento-muerte con 0 como punto límite reflectante. Es decir, en estado\( x \in \N_+ \), el siguiente estado es\( x - 1 \) o\( x + 1 \), mientras que en el estado 0, el siguiente estado es 1. Cuando\( k = 1 \), la cola de servidor único, el parámetro exponencial en estado\( x \in \N_+ \) es\( \mu + \nu \) y las probabilidades de transición para la cadena de salto son\[ Q(x, x - 1) = \frac{\nu}{\mu + \nu}, \; Q(x, x + 1) = \frac{\mu}{\mu + \nu} \] Cuando\( k = \infty \), la cola infinita del servidor, los casos anteriores para\( x \ge k \) son vacíos, por lo que el parámetro exponencial en estado\( x \in \N \) es\( \mu + x \nu \) y las probabilidades de transición son\[ Q(x, x - 1) = \frac{\nu x}{\mu + \nu x}, \; Q(x, x + 1) = \frac{\mu}{\mu + \nu x} \]

Generador Infinitesimal

El generador infinitesimal de la cadena da la misma información que la función de parámetro exponencial y la matriz de transición de salto, pero en una forma más compacta.

Para la cadena M/M/\( k \) cola\( \bs{X} \), el generador\( G \) infinitesimal viene dado por\ begin {align*} G (x, x) & = - (\ mu +\ nu x),\; G (x, x - 1) =\ nu x,\; G (x, x + 1) =\ mu;\ quad x\ in\ N,\, x\ lt k\\ G (x, x) & = - (\ mu +\ nu k),\; G (x, x - 1) =\ nu k,\; G (x, x + 1) =\ mu;\ quad x\ en\ N,\, x\ ge k\ end {align*}

Entonces para\( k = 1 \), la cola de servidor único, el generador\( G \) viene dado por\( G(0, 0) = -\mu \),\( G(0, 1) = \mu \), mientras que para\( x \in \N_+ \),,\( G(x, x) = -(\mu + \nu) \),\( G(x, x - 1) = \nu \),\( G(x, x + 1) = \mu \). Para\( k = \infty \), el caso del servidor infinito, el generador\( G \) viene dado por\( G(x, x) = -(\mu + \nu x) \)\( G(x, x - 1) = \nu x \), y\( G(x, x + 1) = \mu \) para todos\( x \in \N \).

Clasificación y comportamiento limitante

Nuevamente, vamos a\( \bs{X} = \{X_t: t \in [0, \infty)\} \) denotar la cadena de\( k \) colas M/M/ con tarifa de llegada\( \mu \), tarifa de servicio\( \nu \) y con\( k \in \N_+ \cup \{\infty\} \) servidores. Como se señaló en la introducción, de fundamental importancia es la cuestión de si los servidores pueden manejar el flujo de clientes, para que la cola finalmente se vacíe, o si la longitud de la cola crece sin ataduras. Para entender el comportamiento limitante, necesitamos clasificar la cadena como transitoria, recurrente nula o recurrente positiva, y encontrar las funciones invariantes. Esto será fácil de hacer usando nuestros resultados para cadenas de nacimiento-muerte más generales en tiempo continuo. Tenga en cuenta primero que\( \bs{X} \) es irreducible. Es mejor considerar el servidor único y los casos de servidor infinito individualmente.

La cadena de colas de servidor único\( \bs{X} \) es

1. Transitorio si\( \nu \lt \mu \).
2. Recurrente nulo si\( \nu = \mu \).
3. Positivo recurrente si\( \nu \gt \mu \). La distribución invariante es la distribución geométrica on\( \N \) con parámetro\( \mu / \nu \). La función de densidad de probabilidad invariante\( f \) viene dada por\[ f(x) = \left(1 - \frac{\mu}{\nu}\right) \left(\frac{\mu}{\nu}\right)^x, \quad x \in \N \]

Prueba

Esto se desprende directamente de los resultados de la cadena de nacimiento-muerte\( \mu \) en tiempo continuo, con tasa de natalidad constante\( \N \) y tasa de mortalidad constante\( \nu \) en\( \N_+ \).

El resultado tiene sentido intuitivo. Si la tasa de servicio es menor que la tasa de llegada, la cadena es transitoria y la longitud de la cola crece hasta el infinito. Si la tasa de servicio es mayor que la tasa de llegada, la cadena es recurrente positiva. En el límite entre estos dos casos, cuando las tarifas de llegada y servicio son las mismas, la cadena es nula recurrente.

La cadena infinita de colas de servidores\( \bs{X} \) es positiva recurrente. La distribución invariante es la distribución de Poisson con parámetro\( \mu / \nu \). La función de densidad de probabilidad invariante\( f \) viene dada por\[ f(x) = e^{-\mu / \nu} \frac{\left(\mu / \nu\right)^x}{x!}, \quad x \in \N \]

Prueba

Esto también se desprende de los resultados de la cadena de nacimiento-muerte en tiempo continuo. En la notación de esa sección, la tasa de natalidad es constante,\( \mu(x) = \mu \) para\( x \in \N \) y la tasa de mortalidad es proporcional al número de clientes en el sistema:\( \nu(x) = \nu x \) for\( x \in \N_+ \). De ahí que la función invariante (única hasta multiplicación por constantes) es\[ x \mapsto \frac{\mu(0) \cdots \mu(x - 1)}{\nu(1) \cdots \nu(x)} = \frac{\mu^x}{\nu^x x!} \] Normalizada, esta es la distribución de Poisson con parámetro\( \mu / \nu \).

Este resultado también tiene sentido intuitivo.