CONFERENCIA 2: Estudio de modelos en Teoría de Colas
SUMARIO:
• Introducción
• Terminología , notaciones y relaciones.
• Ejemplos reales de sistemas de cola.
• Distribución exponencial y sus propiedades.
• Proceso de nacimiento y muerte.
• Modelo de cola M/M/s .
Introducción
La tarea de un analista de colas puede ser de dos tipos:
a) establecer mecanismos para medir la efectividad del sistema o
b) diseñar un sistema “óptimo” (de acuerdo a algún criterio).
(Diseñar eficientemente consiste, básicamente, en definir un sistema cuyo coste (de diseño y de
operación) se justifique por el servicio que da. Dicho servicio se puede evaluar mediante el coste
de “no darlo”. De este modo al diseñar se pretende minimizar unos supuestos costes totales.)
A partir de los datos que nos suministra la teoría de colas se puede obtener la información
necesaria para definir el número de asientos necesarios en una sala de espera, o la estructura de
etapas de un proceso de atención al cliente. En cualquier caso, para poder tomar decisiones hacen
falta datos que la teoría de colas puede dar en alguno de los siguientes tres aspectos:
a) tiempo de espera (en el total del sistema o en la cola)
b) cantidad de clientes esperando (en el sistema o en las colas)
c) tiempo ocioso de los servidores (total o particular de cada servicio)
En esta conferencia se impartirán algunos elementos teóricos que expresen lo anteriormente
mencionado.
Terminología, notaciones y relaciones.
Antes de presentar los resultados es necesario establecer una notación básica:
λ = Número de llegadas por unidad de tiempo
µ = Número de servicios por unidad de tiempo si el servidor está ocupado
c = Número de servidores en paralelo
: Congestión de un sistema con parámetros: (λ,µ, c)
N(t): Número de clientes en el sistema en el instante t
Nq(t): Número de clientes en la cola en en el instante t
Ns(t): Número de clientes en servicio en el instante t
Pn(t): Probabilidad que haya n clientes en el sistema en el instante t = Pr{N(t) = n}
N: Número de clientes en el sistema en el estado estable
Pn: Probabilidad de que haya n clientes en estado estable Pn = Pr{N = n}
L: Número medio de clientes en el sistema
Lq: Número medio de clientes en la cola
Tq: Representa el tiempo que un cliente invierte en la cola
S: Representa el tiempo de servicio
T = Tq+S: Representa el tiempo total que un cliente invierte en el sistema
Wq = E[Tq]: Tiempo medio de espera de los clientes en la cola
W = E[T]: Tiempo medio de estancia de los clientes en el sistema
r: número medio de clientes que se atienden por término medio
Pb: probabilidad de que cualquier servidor esté ocupado
Resultados y relaciones
Si ρ ≥1 el sistema tenderá a crecer inexorablemente.
El número de clientes en el instante t, n(t), es el número de llegadas que han ocurrido hasta t
menos el número de servicios completados hasta t.
El número medio de clientes en el sistema y en la cola se puede calcular de diferentes maneras:
Little, en su famosa fórmula, establece una relación entre la longitud de la cola y el tiempo de
espera:
L = λW Lq = λWq
El tiempo de estancia de un cliente en el sistema se relaciona con el tiempo de espera de un cliente
en la cola,
W = Wq + 1/µ
El número de clientes que por término medio se están atendiendo en cualquier momento es:
r = L – Lq = λ(W – Wq) = λ/µ
En un sistema de un único servidor:
La probabilidad de que un sistema de un único servidor esté vacío es P0 = 1- ρ
La probabilidad de que un servidor (de un sistema de c servidores en paralelo) esté ocupado en el
estado estable es:
El tiempo de estancia del cliente (i +1) en la cola es:
donde S(i) es el tiempo de servicio del cliente i, y T(i) es el tiempo que transcurre desde la llegada del
cliente y hasta la llegada del cliente (i + 1)
Ejemplos de sistemas de cola
• Sistemas de servicios comerciales. (peluquerías, cafeterías, cajeros de bancos, venta de
pizza, etc)
• Sistemas de servicios de transporte. (semáforos, casetas de cobros, estacionamientos).
• Sistemas de servicios internos en las industrias. (fabricación de juguetes, recape de gomas
de vehículos, etc)
A priori se puede pensar que el método más adecuado para recoger datos al analizar un sistema
es establecer una plantilla y recoger los datos sobre el sistema cada cierto tiempo. Esta técnica es
“orientada al tiempo”
Es mejor, sin embargo, utilizar una técnica de recogida de información asociada a eventos.
“La información se recoge cuando algo ocurre”
En una cola convencional los únicos datos a recoger son:
a) cada cuánto llega un cliente
b) cuánto se tarda en servir a cada cliente
No es necesario recoger más información para, a partir de las relaciones expuestas en el apartado
anterior, definir cualquier medida de efectividad.
Ejemplo
Sea un sistema G/G/1. Sean los siguientes datos de entrada:
I 1 2 3 4 5 6 7 8 9 10 11 12
Tiempo entre llegadas entre i+1 e i 2 1 3 1 1 4 2 5 1 2 2 -
Tiempo de servicio al cliente 1 3 6 2 1 1 4 2 5 1 1 3
De la tabla anterior se puede extraer la siguiente información:
Tiempo en Tiempo en Tamaño
que el que el de colas Clientes en
cliente i cliente i Tiempo Tiempo después el sistema
Reloj (t) Entrada/salida entra en sale del en la en el de después de
del cliente i servicio servicio cola sistema t t
0 1-E 0 1 0 1 0 1
1 1-S 0 0
2 2-E 2 5 0 3 0 1
3 3-E 5 11 2 8 1 2
5 2-S 0 1
6 4-E 11 13 5 7 1 2
7 5-E 13 14 6 7 2 3
8 6-A 14 15 6 7 3 4
11 3-D 2 3
12 7-A 15 19 3 7 3 4
13 4-D 2 3
14 8-A;5-D 19 21 5 7 2 3
15 6-D 1 2
19 P-A;7-D 21 26 2 7 1 2
20 10-A 26 27 6 7 2 3
21 8-D 1 2
24 11-A 27 28 3 4 2 3
26 12-A;9-D 28 31 2 5 2 3
27 10-D 1 2
28 11-D 0 1
31 12-D 0 0
A partir de la anterior información obtenida se puede decir que:
clientes por unidad de tiempo clientes por unidad de tiempo
El tiempo medio de estancia en la cola es de 40/12
El tiempo medio de estancia en el sistema es de 70/12
De aquí y a partir de la fórmula de Little
Los procesos de Poisson y la distribución exponencial
La mayor parte de los modelos de colas estocásticas asumen que el tiempo entre diferentes
llegadas de clientes siguen una distribución exponencial. O lo que es lo mismo, que el ritmo de
llegada sigue una distribución de Poisson*.
En esta sección se verán las características de una distribución de Poisson y como se relacionan
con la distribución exponencial. Posteriormente se analizan las más importantes propiedades y
algunas generalizaciones al adoptar tal patrón de llegadas. Se cierra el apartado con argumentos
que apoyan el uso de la distribución de Poisson. Adoptar la distribución de Poisson implica que la
probabilidad de que lleguen n clientes en un intervalo de tiempo t es:
El tiempo entre llegadas se define, de este modo, como la probabilidad de que no llegue ningún
cliente:
siendo por tanto una distribución exponencial.
2.6.1 Propiedades del Patrón de llegadas (o servicio) Poisson-Exponencial
El uso de este patrón de llegada (o de servicio) tiene, entre otras las siguientes propiedades:
P1 El número de llegadas en intervalos de tiempo no superpuestos es estadísticamente
independiente
P2 La probabilidad de que una llegada ocurra entre el tiempo t y t + Δt es λΔt + o(Δt), donde λ
es la tasa de llegada y o(Δt) cumple
P3 La distribución estadística del número de llegadas en intervalos de tiempo iguales es
estadísticamente equivalente
P4 Si el número de llegadas sigue una distribución de Poisson el tiempo entre llegadas sigue
una distribución exponencial de media (1/λ) y al contrario
P5 Si el proceso de llegada es Poisson, los tiempos de llegada son completamente aleatorios
con una función de probabilidad uniforme sobre el periodo analizado.
P6 Para conocer los datos que definen un proceso de Poisson solo es necesario conocer el
número medio de llegadas
P7 Amnesia de la Distribución exponencial: La probabilidad de que falten t unidades para que
llegue el siguiente cliente es independiente de cuanto tiempo llevamos sin que llegue
ningún cliente.
Pr{T ≤ 1/ T ≥ t0} = Pr{0 ≤ T ≤ t1 – t0}
Generalizaciones al Proceso Poisson-Exponencial
a) Variabilidad de λ
Se puede admitir que λ varie con el tiempo. En este caso
b) Llegadas múltiples
Se puede admitir que en cada evento de llegada aparezcan i clientes, donde:
En este caso la probabilidad de que en el instante t hayan aparecido m clientes es:
es la probabilidad de que k ocurrencias den un resultado total de m clientes.
Procesos de nacimiento y muerte en el estado estable
Un proceso estocástico es la abstracción matemática de un proceso empírico, cuyo desarrollo está
gobernado por alguna ley de probabilidad. Desde el punto de vista de la teoría de probabilidades,
un proceso estocástico se define como una familia de variables aleatorias {X(t),t T} definidas
sobre un horizonte T. X(t) es el estado del sistema.
Se dice que un proceso estocástico {X(t) ,t = 0, 1,...} es un proceso de Markov si, para cualquier
conjunto de n instantes t1 < t2 <... < tn, la distribución de X(t) depende únicamente del valor de X(t n-
1). Es decir:
“Dada la situación presente, el futuro es independiente del pasado y el proceso carece de memoria”
Una cola, con proceso de llegada Poisson-Exponencial de media μ, y con proceso de servicio
Poisson-Exponencial de media µ, se puede modelizar como una cadena de Markov continua,
donde en cada intervalo infinitesimal de tiempo puede ocurrir un nacimiento (llegada) o una muerte
(salida)
Al representar las anteriores probabilidades se ha considerado que las tasas de llegada y de
servicio (λ y µ respectivamente) dependen del número de elementos en el sistema.
Una representación gráfica de un fragmento de la cadena de Markov generada es la representada
en la siguiente figura:
λ λ
n-1 n n+1
μ μ
Figura 4: Fragmento de cadena de Markov
Es interesante conocer las probabilidades en el estado estacionario de que haya n elementos en el
sistema. n elementos en el sistema se refleja porque la cadena de Markov está en el estado n.
En situación estacionaria, se puede decir que el “balance de flujo” alrededor del estado n debe ser
0 (sino no sería estable). Así las probabilidades de entrada en el estado n, deben ser iguales a la
probabilidad de las salidas:
λn Pn + μn Pn = λn-1 Pn-1 + μn+1 Pn+1 n>0
En el origen
λ0 P0 = μ1 P1
De las anteriores ecuaciones se puede extraer que:
y dado que
se puede calcular
Aunque la resolución de las anteriores ecuaciones parece complicada, no es estrictamente
necesario conocer cómo se puede resolver para poderlas aplicar. Sólo en el caso de que nuestra
realidad no sea aplicable a un problema ya resuelto deberíamos profundizar en los diferentes
métodos que permiten resolver nuestro problema.
El sistema M/M/1
El propósito de este apartado es exponer diferentes modelos de colas. No es excesivamente
complicado conocer el origen de las fórmulas, y puede ser un ejercicio interesante cuando las
condiciones de partida no son exactamente las aquí consideradas. Sin embargo se ha optado por
la exposición de los resultados directos ya que se pretende la aplicación de éstos y no su
consecución.
Todos los resultados se obtienen para el estado estable.
Una cola M/M/1 tiene un único servidor y las tasas de llegada y de servicio siguen una distribución
de Poisson, siendo por tanto:
La tasa de llegada es a(t)= λe-λt
La tasa de salida es a(t)=µeµt
La probabilidad de que haya n clientes es:
Pn = (1 – ρ)ρn con ρ = λ/μ
El número medio de clientes en la cola es:
Como
De donde
Y aplicando las relaciones fundamentales del apartado 1.5
La cola media cuando el sistema no está vacío es:
Otro resultado interesante es conocer cual es la probabilidad de que haya X o más elementos en el
sistema.
Colas con servidores en paralelo M/M/C
Un sistema con servidores en paralelo se caracteriza porque hay más de un servidor que ejecuta la
misma función con la misma eficiencia.
Se define mientras que la tasa de ocupación del sistema es
Cuando se consideran c servidores en paralelo, las tasas de llegada y de servicio pasan a ser:
donde
La probabilidad de que haga n clientes en un sistema de este tipo es:
Siendo la probabilidad de que el sistema esté vacío:
La longitud de la cola medida es:
El tiempo medio de espera en la cola:
y por tanto,
Para facilitar el cálculo de Lq se ha considerado interesante incluir el siguiente ábaco que relaciona
el valor de ρ con Lq para distintos valores de c.
FIGURA PP 19 (Fichero Teoría de [Link])
Colas con servidores en paralelo y límite de capacidad M/M/c/K
En algunos sistemas la cola no puede albergar a un número indefinido de clientes. En este caso se
dice que el sistema es de capacidad limitada. El límite lo fija el parámetro K que incluye a los
servidores. Las probabilidades de cada estado del sistema
La longitud media de la cola es:
La fórmula de Erlang (M/M/C/C)
Existe un caso especial de la cola con límite de capacidad y es cuando este límite coincide con el
número de servidores. Es decir, no se puede generar cola.
Esta situación da lugar a la distribución de probabilidad conocida como Erlang.
La probabilidad de que haya n elementos en el sistema.
La probabilidad de que el sistema esté lleno es:
Lo sorprendente de esta fórmula es que es válida, independientemente del tipo de distribución del
servicio y por tanto es válida para M/G/C/C
Los valores más relevantes son:
Colas sin límites de servidores (M/M/∞)
En ocasiones se puede estar diseñando un sistema donde el número de servidores simultáneos no
sea un límite (por ejemplo acceso a un servidor de red).
Si el tiempo de servicio tiene igual distribución con el número de servidores (µn=nµ).
La probabilidad de que haya n clientes simultáneamente es:
n≥0 r= λ/μ L= λ/μ W= 1/μ
