1 Teoría de colas Alternativa a estudios de simulación Aplicación a problemas con estructura...
-
Upload
emelina-perla -
Category
Documents
-
view
218 -
download
0
Transcript of 1 Teoría de colas Alternativa a estudios de simulación Aplicación a problemas con estructura...
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 servicion
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
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 ]
9
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)
10
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 - )
11
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 recursivamenteP(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)
12
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 - )
13
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
14
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 -
15
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
16
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
17
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
18
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,
19
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
20
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
21
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 2E [W1 ] = = h-1 , E [W2 ] = = h-1 60 1-5/6 12 65 1-50/65 39
n1 n2
22
Teoría de colas
¿Qué sucede si las distribuciones no son exponenciales? Servicios no exponenciales:
Necesitamos la varianza (variabilidad) 2 1+Cs
2 sE [N ] = + Cs = 1- 2 E [S ] 1 2 1+Cs
2
E [W ] = 1- 2
23
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)
24
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
25
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
26
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
27
Teoría de colas
Caso general. Fórmulas aproximadas 1 1 E [W ] (Cs
2 + Ct2 )
2(1-) 2
válida si 1
Simulación: ineficiente si 1 Proceso muy lento para alcanzar un
error determinado
28
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
29
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
30
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 ]
31
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 , Cs
2 = = = 3/49
E [S ]2 (7/2)2
Tasa de llegadas:
= 10/87 = 0,115 min-1 = 6,9 h-1
32
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 !
33
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
34
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
35
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 ] /
36
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
37
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
38
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
39
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
40
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
41
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