Sistemas de colas

Los sistemas de colas constituyen un ejemplo de una clase más amplia de sistemas dinámicos conocidos como sistemas de flujo. Un sistema de flujo se caracteriza por la presencia de objetos que fluyen, se mueven o son transferidos a través de uno o más canales de capacidad finita. Las actuales redes de telecomunicación son sistemas de flujo: los objetos que fluyen son en este caso paquetes de datos, voz o video (en redes digitales), o llamadas telefónicas (en redes analógicas); los canales en estas redes son los cables o sistemas de radio que permiten el transporte de los objetos. Por capacidad finita de los canales entendemos el hecho de que un canal solo permite el transporte de objetos a una velocidad o tasa finita.

Elementos de un sistema de colas

En general en los sistemas de colas, tanto los tiempos entre llegadas de clientes como las duraciones de los servicios son aleatorios; como consecuencia son también aleatorios los tiempos de espera y la longitud de la cola. Para el análisis de los sistemas de colas utilizaremos la siguiente notación:

Si suponemos que las variables T_n tienen la misma distribución de probabilidad (tiempos entre llegadas idénticamente distribuidos), representaremos la función de distribución común por:

Si los tiempos de servicio Xn tienen también la misma distribución de probabilidad (tiempos de servicio idénticamente distribuidos), representamos la función de distribución común por:

Notación de Kendall

La notación de Kendall permite establecer una clasificación de los distintos modelos de colas en los que cada cliente debe recibir un solo servicio. Esta notación consiste en un un código de la forma L/S/m/C/M, donde:

Los códigos más habituales para estas distribuciones de los tiempos entre llegadas y de servicio son: M (exponencial), G (general), y D (determinista). Ejemplos de sistemas descritos por la notación de Kendall son:

M/M/1: Llegadas según un proceso de Poisson homogéneo (y por tanto tiempos entre llegadas con distribución exponencial), tiempos de servicio exponen ciales y un solo servidor.

M/M/1/K: idéntico al anterior, pero con un buffer de capacidad finita K.

M/G/1: Llegadas según un proceso de Poisson homogéneo, tiempos de servicio con distribución general, un único servidor.

Intensidad de tráfico y ergodicidad

El cociente ρk = λk/µk se conoce con el nombre de intensidad de tráfico, y mide la relación entre el número de llegadas y el número de salidas por unidad de tiempo. Puede probarse que la condición necesaria y suficiente para que un proceso de nacimiento-muerte sea ergódico (alcance el equilibrio) es que exista un valor k0 tal que para todo k ≥ k0:

Esta condición tiene un significado muy intuitivo: indica que el sistema sólo alcanza el equilibrio si a partir de cierto número de clientes en el sistema (k0), la velocidad a que llegan los clientes es inferior a la velocidad con que son atendidos. Es fácil darse cuenta de que si ocurriese lo contrario, la cola crecería indefinidamente (todos los estados del sistema serían transitorios) y no se alcanzaría el equilibrio.

Formula de Little

Consideremos un sistema de colas en equilibrio, y sean E [T] el tiempo esperado entre llegadas, E [S] el tiempo esperado que permanece en el sistema un cliente arbitrario y E [N] el número esperado de clientes en el sistema en un instante arbitrario. La fórmula de Little establece que:

Si λ es el número esperado de llegadas por unidad de tiempo se tiene que λ = 1/E [T] y la fórmula de Little puede expresarse también como:

Una demostración intuitiva de este resultado parte de las observaciones siguientes:

Puede probarse que la fórmula de Little es válida bajo procesos de llegada y servicio muy generales, e incluso cuando la disciplina de la cola no es FIFO.

El sistema M/M/1

El sistema M/M/1 es el modelo de cola más simple. Consiste en un único canal de servicio o servidor en el que las llegadas y salidas se producen de acuerdo con un proceso de nacimiento y muerte con tasas de llegada y salida respectivas:

Para un sistema de este tipo, los tiempos entre dos llegadas consecutivas, {Tn; n ∈ N},

son variables aleatorias independientes y con distribución de probabilidad exponencial de parámetro λ. Asimismo, los sucesivos tiempos de servicio {Xn; n ∈ N} son también variables aleatorias independientes y con distribución de probabilidad exponencial de parámetro µ. Se deduce que la distribución del tamaño de la cola en el equilibrio (sistema ergódico) viene dada por la expresión:

que corresponde a la distribución geométrica de parámetro λ µ. Para que exista solución de equilibrio debe ocurrir que λ < µ. Ello garantiza además que la ecuación representa una distribución de probabilidad correctamente definida. Si llamamos N a la variable aleatoria que representa el número de clientes en el sistema en el equilibrio, dado que su distribución de probabilidad es la distribución geométrica de parámetro ρ = λ/µ, su esperanza vendrá dada por:

y su varianza:

Si E [S] es el tiempo esperado que cada cliente permanece en el sistema y tenemos en cuenta que el número medio de clientes que acceden al sistema por unidad de tiempo es λ (ya que los tiempos entre dos llegadas consecutivas tienen distribución de probabilidad exponencial de parámetro λ), aplicando la fórmula de Little se tiene que, en los sistemas M/M/1:

El tiempo medio de espera en cola puede calcularse como E[W] = E[S]−E[X] = E[S] − 1 µ. Sustituyendo el valor obtenido se tiene:

Obsérvese que tanto E [N] como E [S] y E [W] son inversamente proporcionales a 1 − ρ. Por tanto el número medio de clientes en el sistema y los tiempos medios el cola y en el sistema, crecen ilimitadamente a medida de la intensidad de tráfico ρ se aproxima a 1.

Sistemas con capacidad finita: la cola M/M/1/C

El modelo M/M/1 admite múltiples generalizaciones, siendo una de las más inmediatas que la capacidad de la cola sea un valor finito C. Ello significa que el sistema puede albergar como máximo C clientes (incluido el que está recibiendo servicio) por lo que los que lleguen mientras el sistema está lleno son rechazados. Esta situación puede ser modelada fácilmente mediante un proceso de nacimiento y muerte si definimos:

Este sistema siempre alcanza el equilibrio, pues para k ⩾ C se tiene λk/µk = 0. Aplicando las fórmulas con estos coeficientes se obtiene sin dificultad:

En este sistema la probabilidad de que un cliente sea rechazado coincide con la probabilidad de encontrar el sistema lleno a su llegada, esto es, P (Rechazo) = P_c.

Colas con más de un servidor: cola M/M/m

La cola M/M/m es la generalización del modelo M/M/1 al caso de m servidores. Supondremos que el cliente que ocupa la primera posición de la cola es atendido por el primer servidor que queda libre. Para modelar esta cola mediante un proceso de nacimiento-muerte basta con hacer las siguientes consideraciones:

Se sigue sin dificultad que la probabilidad en el equilibrio de que haya k clientes en el sistema es:

Una cantidad que suele resultar de interés es la probabilidad de que un nuevo cliente tenga que hacer cola; en este caso, dicha probabilidad es:

Esta expresión se conoce como fórmula C de Erlang, que la empleó a principios del siglo pasado para el estudio de sistemas telefónicos.

Sistemas de colas no markovianos.

Los modelos de colas elementales vistos hasta ahora son puramente markovianos: suponen que el proceso de llegadas de clientes al sistema es de Poisson, lo que significa que el tiempo entre llegadas sucesivas de clientes sigue una distribución exponencial, y que la duración del servicio es también exponencial. Estos modelos resultan extremadamente simples pues la falta de memoria de la  distribución exponencial da lugar a que, una vez conocido el número de clientes presente en el sistema en un instante determinado, cualquier otra información sobre la historia del sistema es irrelevante para el conocimiento (probabilista) de su futuro. Ahora bien, ello también da lugar a que las características de estos sistemas sean muchas veces inverosímiles en la práctica. La situación más habitual es que el conocimiento de cuánto tiempo lleva un cliente ocupando el servicio proporcione información sobre el tiempo que aún le resta para terminar. Asimismo, el tiempo transcurrido desde la última llegada de un cliente al sistema puede informar sobre el tiempo que falta hasta la próxima llegada. El tratamiento analítico de estos modelos es bastante más complicado y requiere el uso de métodos matemáticos que exceden el nivel de este curso. No obstante, su simulación puede llevarse a cabo mediante procesos muy similares a los vistos en este capítulo. En el apéndice se ilustra la programación en R mediante la simulación de un modelo de colas con llegadas y salidas no markovianos que permite estimar en dicho modelo parámetros de interés relativos a la ocupación del sistema y los tiempos de espera

La 

Referencia Bibliográfica:

P. Saavedra, C.N. Hernández, J. Artiles, A. Santana. (2011). Estadística y Procesos Estocásticos.