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