Teoría de colas
Teoría de colas


Alternativa a estudios de simulación
Aplicación a problemas con estructura especial


Relaciones exactas para valores de interés



Sistemas con esperas
Si la variabilidad tiene formas determinadas
En otros casos, aproximaciones
Eficiencia computacional

Aún cuando se tengan relaciones aproximadas
1
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
2
Teoría de colas
Ejemplos:

Empresas de servicios:





Transporte




Colas en un banco
Hipermercados
Hospitales
Administración
Aterrizaje de aviones
Trenes
Congestión de carreteras
Telecomunicaciones
3
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

n
4
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
5
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
6
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

7
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
8
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

9
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 ]

10
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)

11
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 - )

12
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)

13
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 - )
14
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
15
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
60/40

E [N ] =  = 8
1-
16
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

17
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
18
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

19
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, 
20
Teoría de colas
Cálculo de tasa de llegadas a cada cola

Balance en la red

Dada la matriz de rutas R


Llegadas a una cola:


Probabilidad de ir a otra cola desde una dada
Suma de llegadas externas y llegadas desde otras
colas
Llegadas a cada cola: solución de
=+R
21
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
E [W ] =  
i 1-i
i
i = 
i
22
Teoría de colas
Redes de colas. Ejemplo:
n1

n2
Llegadas: 50 h-1, servicios: 60 h-1, 65 h-1
R=
0 0
1 0
=
50
0
=
50
50
1 5/6
1
1 50/65
2
-1
E [W1 ] =   =  h , E [W2 ] =   =  h-1
60 1-5/6 12
65 1-50/65 39
23
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
24
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)

25
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

26
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

27
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

28
Teoría de colas
Caso general. Fórmulas aproximadas
1 
1
E [W ]    (Cs2 + 2Ct2 )
 2(1-)

válida si   1
Simulación: ineficiente si   1

Proceso muy lento para alcanzar un error
determinado
29
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
30
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

31
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 = 2 ,  = 
 1-
2
E [S ]
E [S ]
32
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 ) = E [S

2]
- E [S
]2
Var(S )
3/4
= 3/4 , Cs =  =  = 3/49
E [S ]2
(7/2)2
2
Tasa de llegadas:
 = 10/87 = 0,115 min-1 = 6,9 h-1
33
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!
mm k
= p0 
si k  m
m!
34
Ejercicio 1

Cola común

p0 (1 + 2 + 2   k ) = 1,
k=2
p0 = (1- )/(1+ )

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
35
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
36
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 ] / 
37
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
38
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
39
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
40
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
41
Ejercicio 2
Probabilidad de volver atrás

Cambios en las tasas de llegada:
=+R, =
70
0
0
0
,R=
0
1
0
0
0
0
1
0
0 0.08
76.6
0 0.04
79.9
, =
0 0.03
82.4
1 0
82.4
Las tasas son mayores
 Se aplica el mismo procedimiento con los
nuevos valores

42
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
43
Descargar

Document