1
Teoría de colas
Teoría de colas
Alternativa a estudios de simulación
Aplicación a problemas con estructura especial
Sistemas con esperas
Relaciones exactas para valores de interés
Si la variabilidad tiene formas determinadas
En otros casos, aproximaciones
Eficiencia computacional
Aún cuando se tengan relaciones aproximadas
2
Teoría de colas
Conceptos básicos:
Cola, sistema al que
Llegan clientes (aleatoriamente),
que son servidos (con duración aleatoria)
Capacidad limitada
Si está totalmente ocupada, clientes esperan
Distintos órdenes de atención a clientes
Se puede escoger el orden para los que estén esperando
3
Teoría de colas
Ejemplos:
Empresas de servicios:
Colas en un banco
Hipermercados
Hospitales
Administración
Transporte
Aterrizaje de aviones
Trenes
Congestión de carreteras
Telecomunicaciones
4
Teoría de colas
Tratamiento:
Cola simple
Información necesaria:
Tiempo entre llegadas, Ti
Tiempo de servicio, Si , y número de servidores n
Disciplina de servicio
(Gp:) n
5
Teoría de colas
Cantidades de interés
Relacionadas con clientes
Número de clientes en el sistema, N
Número de clientes esperando, N
Relacionadas con tiempos
Tiempo de paso por el sistema, S
Tiempo de espera, W
Medidas de capacidad del sistema
Tiempo desocupado de servidores, I
6
Teoría de colas
Resultados para estado estacionario
Comportamiento estable de la cola
Si se observa pasado un tiempo muy largo
Si se inicia la cola con la distribución adecuada, esta no cambia
Resultados para régimen transitorio
Más complejos
Ecuaciones diferenciales (Khinchine-Pollacek)
Menos útiles
7
Teoría de colas
Relaciones básicas
Relación entre tiempos medios y número medio de clientes
Ley de Little:
E [N ] = ? E [W ]
donde ? es la tasa de llegadas externas
Aplicaciones
8
Teoría de colas
Objeto del estudio
Relaciones para obtener valores de salida
Valores medios y distribuciones de
Números de clientes
Tiempos
En función de valores de entrada
Valores medios y distribuciones de
Tiempos entre llegadas
Tiempos de servicio
9
Teoría de colas
Relaciones
Más generales
Entre varios valores de salida
Ley de Little: números de clientes y tiempos
Independientes de la distribución
Más específicas
Valores de salida en función de valores de entrada
Dependientes de la distribución
10
Teoría de colas
Ley de Little
Justificación:
Se observa una cola durante un tiempo largo, t
En ese tiempo, se tienen nT llegadas al sistema,
nT ? ? t
Tiempo de paso acumulado de todas las llegadas,
v = ?i Pi
Promedio v/nT ? E [S ]
Promedio v/t ? E [N ]
11
Teoría de colas
Resultados más detallados
Bajo hipótesis sobre cola
Caso más simple (cola M/M/1):
Tiempos entre llegadas con distribución exponencial, E [T ] = 1/?
Tiempos de servicio con distribución exponencial, E [S ] = 1/?
1 servidor
Disciplina: FCFS (se atiende primero a quien primero llega)
12
Teoría de colas
Resultados:
Probabilidad de tener n clientes en la cola:
(1 – ?) ? n , ? = ?/?
Número medio de clientes en la cola:
E [N ] = ?/(1 – ?)
Tiempo medio de espera:
E [W ] = (1/?) ?2/(1 – ?)
13
Teoría de colas
Justificación para N:
Balance de probabilidad
Tasas de salida de un estado iguales a tasas de entrada
P(N = k)(? + ?) = P(N = k+1)? + P(N = k-1)?
P(N = 0)? = P(N = 1)?
Despejando recursivamente
P(N = 1) = ?P(N = 0), P(N = 2) = ?2P(N = 0), …
Condición adicional, ?k P(N = k) = 1
Única solución del sistema (infinito)
14
Teoría de colas
Justificación para W:
W = 0 si al llegar el cliente la cola está vacía (N = 0)
Probabilidad 1 – ?
W = ?i Si si N > 0 (vars. independientes)
Empleando funciones características
Condicionada a que se produzca espera:
Exponencial con parámetro ?(1 – ?)
15
Teoría de colas
Cola M/M
Más de un servidor, M/M/n
La misma justificación sigue siendo válida
Probabilidades para el número en cola, N:
si k < n entonces C (n?)k/k!
si k ? n entonces C ?knn /n!
Constante C se determina para que las probabilidades sumen 1
16
Teoría de colas
Aplicación:
Cola de supermercado:
80 clientes/h.
Servicio: 40 s./cliente
Número medio de clientes
80/60 ?
? = ??? = 0,89 E [N ] = ?? = 8
60/40 1 – ?
17
Teoría de colas
Ejemplo: supermercado
Tiempo medio de espera:
1 ?2 1 (8/9)2
E [W ] = ? ?? = ??? ??? = 5,33 min
? 1-? 80/60 1-8/9
Con dos cajeros en operación:
Doble cola y clientes se reparten (40cl./h.)
40/60
? = ??? = 0,44 E [N ] = 0,8 E [W ] = 0,53
60/40
18
Teoría de colas
Ejemplo: supermercado
Estrategia más eficiente: cola simple y los clientes son atendidos por el primer cajero disponible
? = 0,44 E [N ] = 1,11 E [W ] = 0,16
Se ahorran las esperas en un cajero cuando el otro está vacío
19
Teoría de colas
Redes de colas
En muchos casos prácticos, colas no aisladas, sino interconectadas (redes)
Situación típica en producción, cadenas de distribución, etc.
En general, procesos que requieran más de una etapa
20
Teoría de colas
Redes de colas
Llegadas y servicios exponenciales
Resultado básico
Cada cola actúa como si fuese independiente de las demás
Información necesaria:
Llegadas a cada cola, ?
Diferentes de las llegadas externas, ?
21
Teoría de colas
Cálculo de tasa de llegadas a cada cola
Balance en la red
Dada la matriz de rutas R
Probabilidad de ir a otra cola desde una dada
Llegadas a una cola:
Suma de llegadas externas y llegadas desde otras colas
Llegadas a cada cola: solución de
? = ? + R ?
22
Teoría de colas
Redes de colas
Se forman la matriz R y el vector ?
Se calcula la tasa de llegadas a cada cola,
? = ? + R ?
Se calcula el dato deseado de cada cola,
1 ?i ?i
E [W ] = ? ?? ?i = ?
?i 1-?i ?i
23
Teoría de colas
Redes de colas. Ejemplo:
Llegadas: 50 h-1, servicios: 60 h-1, 65 h-1
0 0 50 50
R = ? = ? =
1 0 0 50
1 5/6 1 1 50/65 2
E [W1 ] = ? ??? = ? h-1 , E [W2 ] = ? ???? = ? h-1
60 1-5/6 12 65 1-50/65 39
(Gp:) n1
(Gp:) n2
24
Teoría de colas
¿Qué sucede si las distribuciones no son exponenciales?
Servicios no exponenciales:
Necesitamos la varianza (variabilidad)
?2 1+Cs2 ?s
E [N ] = ? + ?? ?? Cs = ???
1-? 2 E [S ]
1 ? 2 1+Cs2
E [W ] = ? ?? ???
? 1-? 2
25
Teoría de colas
Ejemplo: supermercado
Supongamos que Cs = 0,5
E [N ] = 6,22 E [W ] = 4
Al reducir la variabilidad, se reduce proporcionalmente el tiempo de espera y el número de clientes en la cola
(Distribución exponencial, C = 1)
26
Teoría de colas
Tiempos entre llegadas no exponenciales
? 1 ?
E [N ] = ?? E [W ] = ? ??
1-? ? 1-?
pero ahora ? se tiene que calcular resolviendo la ecuación
? = T * ( ? – ? ? )
No depende sólo de la varianza
27
Teoría de colas
Ejemplo: supermercado
80 llegadas/h. Uniformemente
2a ? ? (1 – ? ) = 1 – exp(-2a ? (1 – ? ))
donde a = 0,75 min (tiempo medio entre llegadas), y ? = 1,5 min-1
Solución:
? = 0,84 E [W ] = 3,5
28
Teoría de colas
Distribuciones generales.
Si tiempos de servicios y entre llegadas siguen distribuciones generales
No existen fórmulas exactas
Alternativas:
Simulación
Fórmulas aproximadas para casos especiales
29
Teoría de colas
Caso general. Fórmulas aproximadas
1 ? 1
E [W ] ? ? ??? (Cs2 + ? Ct2 )
? 2(1-?) ? 2
válida si ? ? 1
Simulación: ineficiente si ? ? 1
Proceso muy lento para alcanzar un error determinado
30
Teoría de colas
Ejemplo. Supermercado
Servicios uniformes entre 0 y 80 s.
80 llegadas/h. uniformemente
Resultados aproximados:
C2 = 4/3 E [W ] ? 8,06
Simulación (6900 replicaciones):
E [W ] = 2,06 ? 0,2
31
Teoría de colas
Redes de colas.
Servicios o llegadas no exponenciales: se aproximan a partir de la variabilidad de los datos (aproximaciones con segundos momentos)
Alternativa: simulación
Códigos de ordenador especializados
32
Ejercicio 1
Una cola (una pista de aterrizaje)
Distribuciones:
S ? Unif[2,5] T ? exp(?)
Objetivo: E [W ] ? 5
Relación:
1 ? 1+Cs2 Var(S ) 1
E [W ] = ? ?? ??? , Cs2 = ??? , ? = ??
? 1-? 2 E [S ]2 E [S ]
33
Ejercicio 1
Coeficiente de variación:
a +b 1 ?b
E [S ] = ?? , E [S 2] = ?? ? x 2 dx = (b 2+ab +a 2)/3
2 b -a ?a
Var(S ) 3/4
Var(S ) = E [S 2] – E [S ]2 = 3/4 , Cs2 = ??? = ?? = 3/49
E [S ]2 (7/2)2
Tasa de llegadas:
? = 10/87 = 0,115 min-1 = 6,9 h-1
34
Ejercicio 1
Dos pistas de aterrizaje:
Colas separadas: tomar S igual a la mitad (sólo cambia ?),
? = 5/12 = 0,417 min-1 = 25 h-1
Cola común, ? = ?/(m ?)
(m ? )k
P (N = k ) = p0 ??? si k < m
k !
m m ? k
= p0 ??? si k ? m
m !
35
Ejercicio 1
Cola común
?
p0 (1 + 2? + 2 ? ? k ) = 1, p0 = (1-? )/(1+? )
k=2
?
E [N ] = 2p0 ? (k – 2) ? k = 2p0 ? 3/(1-? )2
k=2
Ley de Little:
E [N ] = ?E [W ]
? = (5?/(1+5?))½, ? = 2?? = 0,438 min-1 = 26,3 h-1
36
Ejercicio 2
Supongamos ritmo no aleatorio
Condiciones:
n1 + n2 + n3 + n4 = N
r1 n1 = r2 n2 = r3 n3 = r4 n4
Asignación:
1/ri
ni = N ???
?j 1/rj
n1 = 2 , n2 = 5 , n3 = 10 , n4 = 7
37
Ejercicio 2
Ritmo máximo de procesamiento:
mini ri ni = 75 dec./h
Caso aleatorio:
Ritmos medios no varían
Tiempo medio de paso por el sistema
S = ?i Si = ?i E [Ni ] / ?
38
Ejercicio 2
Tiempo medio de procesamiento
Tasa de llegadas: 70 dec./h
Tasa común a todas las etapas
Supongamos en cada etapa colas independientes para cada servidor
? 1 ?i
?i = ?? , E [Wi ] = ? ??
ni ?i ?i 1-?i
39
Ejercicio 2
Resultados:
?1 = 0,875 ?2 = 0,933 ?3 = 0,875 ?4 = 0,833
E [S1] = 0,2 E [S2] = 1 E [S3] = 1 E [S4] = 0,5
E [S ] = 2,7 h
Modificaciones:
min ?i ?i
s.a ?i = ? / ?i (ni + ?i )
?i ?i / ?i (1-?i ) ? W
?i ? 0 , entera
40
Ejercicio 2
Solución: (?2 = 1)
?1 = 0,875 ?2 = 0,778 ?3 = 0,875 ?4 = 0,833
E [S1] = 0,2 E [S2] = 0,3 E [S3] = 1 E [S4] = 0,5
Para un tiempo de proceso de 1 h.
?1 = 1 ?2 = 2 ?3 = 3 ?4 = 1
?1 = 0,875 ?2 = 0,933 ?3 = 0,875 ?4 = 0,833
E [S1] = 0,2 E [S2] = 1 E [S3] = 1 E [S4] = 0,5
41
Ejercicio 2
Colas comunes a todos los servidores:
?1 = 0,875 ?2 = 0,778 ?3 = 0,875 ?4 = 0,833
E [S1] = 0,107 E [S2] = 0,234 E [S3] = 0,185 E [S4] = 0,123
El tiempo de paso se cumple sin añadir nuevos funcionarios
42
Ejercicio 2
Probabilidad de volver atrás
Cambios en las tasas de llegada:
70 0 0 0 0.08 76.6
0 1 0 0 0.04 79.9
? = ? + R ? , ? = , R = , ? =
0 0 1 0 0.03 82.4
0 0 0 1 0 82.4
Las tasas son mayores
Se aplica el mismo procedimiento con los nuevos valores
43
Ejercicio 2
Resultados:
Colas individuales (3,7,13,8):
?1 = 0,64 ?2 = 0,76 ?3 = 0,79 ?4 = 0,86
E [S1] = 0,07 E [S2] = 0,28 E [S3] = 0,60 E [S4] = 0,59
Cola única por etapa (2,6,11,7):
?1 = 0,96 ?2 = 0,84 ?3 = 0,94 ?4 = 0,98
E [S1] = 0,30 E [S2] = 0,14 E [S3] = 0,26 E [S4] = 0,67