Teoría de colas Andrés Ramos Universidad Pontificia Comillas http://www.iit.comillas.edu/aramos/
[email protected] TEORÍA DE COLAS
1
Sistemas de colas • Una cola se produce cuando la demanda de un servicio por parte de los clientes excede la capacidad del servicio. • Se necesita conocer (predecir) el ritmo de entrada de los clientes y el tiempo de servicio con cada cliente. Objetivo: Equilibrar los costes de capacidad del servicio y el “coste” de una espera larga.
TEORÍA DE COLAS Estudio matemático de las características de los sistemas de colas.
TEORÍA DE COLAS
2
Proceso en una cola 1. Entrada de clientes
cola o línea de espera 2. Sistema de colas mecanismo de servicio 3. Salida de clientes SISTEMA DE COLAS FUENTE ENTRADA CLIENTES
TEORÍA DE COLAS
COLA
MECANISMO SERVICIO
SALIDA CLIENTES
3
Ejemplos Clientes Clientes tienda Clientes banco Clientes supermercado Automóvil Automóvil Avión Llamadas telefónicas Enfermos Cajas Juicios pendientes
TEORÍA DE COLAS
Servicio Venta artículo Operación financiera Cobro compra Llenar depósito Reparación avería Aterrizaje / despegue Conversación Atención médica Transporte Juicio
Servidores Dependiente Ventanilla Caja Surtidor Operarios taller Pista Centralitas Médico Robot de almacenamiento Jueces
4
Entrada de clientes TAMAÑO Número total de clientes potenciales (población de entrada): • Finito (fuente limitada) (sistema cerrado) • Infinito (fuente ilimitada) (sistema abierto) Suposición habitual: tamaño infinito (es decir, el número de clientes en la cola NO afecta el número potencial de clientes fuera de ella) ENTRADA O FUENTE • Unitaria • Por bloques TIEMPO ENTRE LLEGADAS • Determinista • Probabilista (distribución de probabilidad exponencial) TASA MEDIA DE LLEGADA λ Número medio de entrada de clientes por unidad de tiempo Llegadas de clientes son independientes e idénticamente distribuidas (IID)
TEORÍA DE COLAS
5
Cola Número máximo de clientes admisible • Finito • Infinito Suposición habitual: colas de longitud infinita (pérdida del cliente o reintento) Número de canales (carriles de una calle ante un semáforo) en la cola e interferencia entre ellos
Disciplina de la cola Orden de selección de sus miembros para ser atendidos • FIFO, FIFO con límite • LIFO • SIRO (Aleatorio) • Por prioridad (interruptora o no)
TEORÍA DE COLAS
6
Mecanismo de servicio SERVIDORES Proporcionan el servicio al cliente Número de servidores: • Uno • Varios Independencia o no entre servidores TIEMPO DE SERVICIO • Determinista • Probabilista (distribución de probabilidad exponencial) TASA MEDIA DE SERVICIO µ Número medio de clientes que son atendidos en un servidor por unidad de tiempo. Servicios a clientes son independientes e idénticamente distribuidas (IID)
TEORÍA DE COLAS
7
Especificación de un sistema de colas Distribución del tiempo entre llegadas / Distribución del tiempo de servicio / Número de servidores / Número máximo de clientes en el sistema / Disciplina de la cola M D E G
exponencial degenerada (tiempos constantes) Erlang (Gamma) general
Ejemplos: M/M/s
tiempo entre llegadas exponencial / tiempo de servicio exponencial / s servidores
M/M/s/K/FIFO M/M/s/s M/G/1
TEORÍA DE COLAS
8
Medidas de eficacia de un sistema de colas λ µ
ρ
tasa de llegada 1/λ tiempo medio entre llegadas consecutivas tasa de servicio 1/µ tiempo medio de servicio factor de utilización (intensidad de tráfico): fracción esperada de tiempo que están
ocupados los s servidores N L Nq Lq T W Tq Wq c
ρ=
λ sµ
habitualmente ρ < 1
estado del sistema, número de clientes en el sistema (cola + servicio) número medio de clientes en el sistema L = E[N] longitud de la cola, número de clientes en la cola número medio de clientes en la cola Lq = E[Nq] tiempo de estancia de los clientes en el sistema tiempo medio de estancia de los clientes en el sistema W = E[T] tiempo de espera de los clientes en la cola Wq = E[Tq] tiempo medio de espera de los clientes en la cola número medio de servidores ocupados
TEORÍA DE COLAS
9
¿Qué sistema de colas es más efectivo? Sistema de 8 servidores con 8 colas.
Sistema de 1 cola que abastece a 8 servidores.
TEORÍA DE COLAS
10
Fórmulas de Little para condición estacionaria en sistema M/M/1 La condición estacionaria se produce cuando la distribución del número de clientes en el sistema se conserva a través del tiempo. Número medio de clientes en el sistema/cola = tasa de llegada x tiempo medio de los clientes en el sistema/cola L = λW Lq = λWq Tiempo medio de los clientes en el sistema = tiempo medio de los clientes en la cola + tiempo medio de servicio W = Wq + 1/µ Número medio de clientes en el sistema = número medio de clientes en la cola + factor de utilización (número medio de clientes siendo atendidos) L = Lq + λ/µ NO PUEDEN UTILIZARSE SI HAY TASAS DE SERVICIO DIFERENTES.
TEORÍA DE COLAS
11
Distribución exponencial T
variable aleatoria tiempo entre llegadas o tiempo de servicio
α e −α t t ≥ 0 fT (t ) = t<0 0
fT(t) estrictamente decreciente en t
α
Probabilidad de una llegada después del instante t P {T > t} = e −α t t var(T ) = 1 α 2 1/α FALTA DE MEMORIA: La distribución de la probabilidad del tiempo que falta para que ocurra el evento es siempre la misma independientemente del tiempo que haya pasado P {T > ∆t | T > t + ∆t} P {T > t + ∆t} e −α ( t +∆t ) P {T > t + ∆t | T > ∆t} = = −α∆t = e −α t = P {T > t} P {T > ∆t} e El mínimo de variables aleatorias exponenciales tiene distribución exponencial. TEORÍA DE COLAS
P (B / A) =
P (A / B ) ⋅ P (B ) P (A)
12
Procesos de Poisson Si los tiempos entre llegadas/servicios se distribuyen según una exponencial el número de llegadas/servicios hasta un cierto tiempo es un proceso de Poisson. N (t ) número de ocurrencias (llegadas o servicios) en el tiempo t (t ≥ 0) . Se distribuye según una Poisson con parámetro α t (α número medio de ocurrencias por unidad de tiempo)
(α t ) n e −α t n = 0,1,… P {N (t ) = n} = n! P {N (t ) = 0} = e −α t = P {T > t} E [ N (t ) ] = α t La probabilidad de ocurrencia de un suceso en el siguiente intervalo (pequeño) de tiempo ∆t sabiendo que no se ha producido hasta ese momento t es α∆t P {T ≤ t + ∆t | T > t} ≅ α∆t
TEORÍA DE COLAS
13
Procesos de Poisson PROPIEDAD REPRODUCTIVA: La suma de procesos de entrada de Poisson es también un proceso de Poisson siendo la tasa la suma de las tasas respectivas. DIVISIBILIDAD: Si las llegadas a un sistema son de tipo Poisson con tasa α y cada llegada es encaminada a un subsistema s con una probabilidad pi el proceso de llegada a cada subsistema es también de Poisson con tasa α pi
TEORÍA DE COLAS
14
Modelo general. Proceso estacionario de nacimiento y muerte Nacimiento = llegada de clientes al sistema Muerte = salida de clientes una vez servidos N (t ) estado del sistema en tiempo t = número de cliente en el sistema Hipótesis: • Distribución del tiempo que falta para la llegada es exponencial con parámetro λn n = 0,1,… siendo λn la tasa de llegada de clientes al sistema dado que hay n clientes N (t ) = n • Distribución del tiempo que falta para la salida es exponencial con parámetro µn n = 0,1,… siendo µn la tasa de salida de clientes del sistema dado que hay n clientes N (t ) = n • Independencia entre el tiempo hasta próxima llegada y tiempo hasta próxima salida
TEORÍA DE COLAS
15
Diagrama de transiciones Por ser proceso de Poisson, la probabilidad de ocurrencia de un suceso en un ∆t es proporcional a ∆t siendo ∆t → 0 Tanto la llegada como la salida son procesos de Poisson e independientes, luego de un estado dado sólo se puede pasar a dos posibles estados. λ0
0
1
µ1
TEORÍA DE COLAS
λ2
λ1
2
µ2
λn-1
3
µ3
...
λn
n
n-1
µn
...
n+1
µn+1
16
Tasa media de llegada al estado n Tasa media de salida del estado n
Pn
λn −1Pn −1 + µn +1 Pn +1 λn Pn + µn Pn
probabilidad de que haya n clientes en el sistema de manera estacionaria
Por ser el sistema estacionario (tasa medio de llegada = tasa media de salida) para cualquier λn −1Pn −1 + µn +1Pn +1 = λn Pn + µn Pn estado n
TEORÍA DE COLAS
17
n=0
µ1P1 = λ0 P0
n =1
λ0 P0 + µ2 P2 = (λ1 + µ1 ) P1
n=2
λ1 P1 + µ3 P3 = (λ2 + µ2 ) P2
λ λ ⋯ λ0 Pn = n −1 n −2 P µn µn −1 ⋯ µ1 0 λ λ ⋯ λ0 Cn = n −1 n −2 µn µn −1 ⋯ µ1 C0 = 1 ∞
∞
n =0
n =0
∑ Pn = ∑ Cn P0 = 1
∞
∑P n =0
=1
n
n = 1,2,… n=0
P0 =
1 ∞
∑C n =0
TEORÍA DE COLAS
λ0 P µ1 0 λλ P2 = 1 0 P0 µ2 µ1 λ λλ P3 = 2 1 0 P0 µ3 µ2 µ1 P1 =
n
18
∞
Número medio de clientes en el sistema
L = ∑ nPn n =0 ∞
Número medio de clientes en cola con s servidores
Lq = ∑ ( n − s ) Pn n=s ∞
Tasa media de llegadas
λ = ∑ λn Pn n =0
TEORÍA DE COLAS
19
Cola M/M/1 Tasa media de llegada λ constante e independiente del estado del sistema Tasa media de servicio µ constante e independiente del estado del sistema
ρ=
Factor de utilización λ
0
µ
Para alcanzar estado estable
λ
λ
1
λ µ
2
µ
λ
3
...
µ
µ
n
λ Cn = = ρ n µ
Pn = ρ n P0
P0 =
1
= 1− ρ
∞
∑ρ
ρ <1
λ
n
n-1
λn = λ µn = µ
n+1
...
µ
Pn = (1 − ρ ) ρ n
n = 0,1,2,…
n
n =0
TEORÍA DE COLAS
20
Medidas de funcionamiento de cola M/M/1 ∞
Número medio de clientes en el sistema
L = ∑ nPn =
L
1− ρ
=
λ
µ −λ ρ2 λ2 Lq = ∑ ( n − 1) Pn = = 1 − ρ µ(µ − λ ) n =1 n =0 ∞
Número medio de clientes en cola con 1 servidor
ρ
Factor de utilización del servidor
1 1 = λ µ − λ µ (1 − ρ ) 1 ρ Wq = W − = µ µ (1 − ρ ) ρ = L − Lq = 1 − P0
Probabilidad de tiempo de espera en cola nulo
P0 = 1 − ρ = P {Wq = 0}
Tiempo medio de los clientes en el sistema Tiempo medio de los clientes en cola
Probabilidad de tiempo de espera en cola > t Probabilidad de tiempo de estancia en el sistema > t
TEORÍA DE COLAS
W=
=
P {Wq > t} = ρ e − µ (1− ρ )t
P {W > t} = e − µ (1− ρ ) t
t≥0 t≥0
21
Cola M/M/s Tasa media de llegada λ constante e independiente del estado del sistema Tasa media de servicio µ
ρ=
Factor de utilización
1
µ
TEORÍA DE COLAS
λ
2
2µ
ρ <1
Para alcanzar estado estable
λ
λ
0
λ sµ
λn = λ nµ n ≤ s µn = sµ n > s
...
s-2
λ
s-1
(s-1)µ
s
sµ
22
1 λ n n≤s µ n ! Cn = s n−s 1 λ λ n>s s ! µ sµ P0 =
1 ∞
∑C n =0
P0 =
= n
1 n
1 s −1
∑ n =0
( sρ ) n!
TEORÍA DE COLAS
s
∞ 1 λ 1 λ λ 1+ ∑ + ∑ n =1 n ! µ n =s s ! µ sµ s −1
n
+
( sρ )
s
s !(1 − ρ )
n−s
=
1 n
s
1 λ 1 λ 1 1+ ∑ + s! µ 1 − λ n =1 n ! µ sµ s −1
1 λ n P0 n! µ Pn = n 1 λ 1 s ! µ s n − s P0
n≤s n>s
23
Medidas de funcionamiento de cola M/M/s s (λ µ ) ρ
Número medio de clientes en cola con s servidores
Lq =
Número medio de clientes en el sistema
L = Lq +
s !(1 − ρ )
Tiempo medio de los clientes en cola
Wq =
Lq
Tiempo medio de los clientes en el sistema
W=
L
2
P0
λ µ
λ λ
= Wq +
1
µ
Probabilidad de tiempo de estancia en el sistema > t P0 (λ µ ) s 1 − e − µt ( s −1−λ µ ) − µt t≥0 P {W > t} = e 1 + s !(1 − ρ ) s − 1 − λ µ Probabilidad de tiempo de espera en cola > t
P {Wq > t} = 1 − P {Wq = 0} e − sµ (1− ρ ) t t ≥ 0 s −1
Probabilidad de tiempo de espera en cola nulo
P {Wq = 0} = ∑ Pn n =0
TEORÍA DE COLAS
24
Cola M/M/s/K K número máximo de clientes en el sistema (por ejemplo, lugares disponibles para los clientes –camillas-) No se permite la entrada cuando el sistema está lleno. λ n = 0,1,2,…, K − 1 Tasa media de llegada λn = n≥K 0 Número de servidores inferior al número máximo de clientes 1 λ n n! µ s n−s λ λ 1 Cn = s ! µ sµ 0 TEORÍA DE COLAS
n = 0,1,2,…, s n = s, s + 1,…, K
n>K
s≤K
1 λ n P0 n = 0,1,2,…, s n! µ s n−s λ λ 1 Pn = P0 n = s, s + 1,…, K s ! µ sµ 0 n>K 25
P0 =
1 K
∑P n =0
=
n
1 n
1 λ 1 λ + ∑ s! µ n =0 n ! µ s
s
λ ∑ n = s +1 s µ K
Número medio de clientes en cola Número medio de clientes en el sistema Tasa media de llegada (entrada efectiva)
n−s
Lq =
s (λ µ ) ρ
s !(1 − ρ )
P0 1 − ρ K − s − ( K − s ) ρ K − s (1 − ρ )
s −1
s −1
n =0
n =0
L = ∑ nPn + Lq + s (1 − ∑ Pn )
λEF = λ (1 − PK )
Tiempo medio de los clientes en cola
Wq =
Tiempo medio de los clientes en el sistema
W=
TEORÍA DE COLAS
2
Lq
λEF L
λEF
26
Cola M/G/1 Tiempos entre llegadas independientes y distribución exponencial con tasa de llegada λ 1 Tiempos de servicio independientes y distribución general F (•) con media y varianza
µ
σ2 No se puede aplicar el proceso generalizado de nacimiento y muerte. λ ρ 2 + λ 2σ 2 Fórmula de Pollaczek-Khintchine: L = ρ + siendo ρ = . 2(1 − ρ ) µ
TEORÍA DE COLAS
27
Sistema cerrado con cola M/M/1 Fuente finita de tamaño m . Clientes una vez servidos vuelven a la fuente. Tiempos entre llegadas independientes y distribución exponencial con tasa de llegada ( m − n )λ n < m dependiente del número de clientes en el sistema λn = n≥m 0 Probabilidad de cada estado m! −1 m Pn = ρ n P0 = (m − n + 1) ρ Pn−1 0 < n ≤ m m! ρ n (m − n)! y P0 = 1 + ∑ n =1 ( m − n )! Pn = 0 n>m siendo ρ =
λ µ
TEORÍA DE COLAS
28
Tasa media de llegada al sistema Número medio de clientes en cola
λEF = (m − L)λ 1+ ρ Lq = m − (1 − p0 ) ρ
Número medio de clientes en el sistema
L=m−
Tiempo medio de los clientes en cola
Wq =
1 − p0
ρ
Lq
( m − L )λ L Tiempo medio de los clientes en el sistema W = ( m − L )λ
TEORÍA DE COLAS
=
1 m 1+ ρ − µ 1 − p0 ρ
29
Sistema cerrado con cola M/M/s Fuente finita de tamaño m . Clientes una vez servidos vuelven a la fuente. Tiempos entre llegadas independientes y distribución exponencial con tasa de llegada ( m − n )λ n < m dependiente del número de clientes en el sistema λn = n≥m 0 nµ 0 ≤ n ≤ s Tasa media de servicio µ µn = sµ s ≤ n ≤ m Probabilidad de cada estado m λ n 0≤n≤s P0 n µ λ siendo ρ = Pn = n sµ m n !(λ / µ ) n s ! s n − s P0 s ≤ n ≤ m λEF = (m − L)λ Tasa media de llegada al sistema
TEORÍA DE COLAS
30
Cola M/M/s/s Capacidad del sistema es igual número de servidores (centrales telefónicas). Probabilidad de que el sistema esté saturado (número de clientes igual a número de ( sρ ) s / s ! servidores) Ps = s ∑ ( s ρ )i / i ! i =0
TEORÍA DE COLAS
31
Cola M/M/∞ El sistema tiene un número muy grande de servidores (sistemas de autoservicio, visitas a una ciudad). Tasa de llegadas λn = λ Tasa de servicios µn = n µ n − λ / µ (λ / µ ) Probabilidad de cada estado pn = e n = 0,1,... n! λ 1 Medidas de funcionamiento de la cola L = ; Lq = 0; W = ; Wq = 0
µ
TEORÍA DE COLAS
µ
32
Diseño óptimo de los sistemas de colas Objetivo: Determinar el nivel de servicio que minimiza la suma de costes incurridos por proporcionar el servicio + costes de los clientes por estar en el sistema (Número medio de clientes en el sistema L por coste de estancia de cada cliente Cc) Coste de los clientes: • Pérdidas de ganancia por pérdida de clientes • Coste social del servicio • Pérdida de productividad Decisiones: s • Número de servidores por instalación • Eficiencia de los servidores µ • Número de sistemas en servicio (instalaciones) λ
TEORÍA DE COLAS
33
Optimizar el número de servidores µ, λ Cs
conocidos y fijos coste por servidor por unidad de tiempo
min E [CT ( s )] = sCs + Cc L( s )
s∈N
CT ( s − 1) ≥ CT ( s ) ≤ CT ( s + 1)
⇒
L( s ) − L( s + 1) ≤
TEORÍA DE COLAS
Cs ≤ L( s − 1) − L( s ) Cc
34
Optimizar la tasa de servicio λ
conocida y fija coste por unidad de tasa de servicio por unidad de tiempo
Cµ
min E [CT ( µ )] = µCµ + Cc L( µ )
Para cola M/M/1
L=
λ µ −λ
∂E [CT ( µ )] =0 ∂µ
TEORÍA DE COLAS
⇒
µ =λ+
Cc λ Cµ 35
Optimizar la tasa de servicio y la capacidad del sistema λ CK Cp
conocida y fija coste por unidad de capacidad por unidad de tiempo coste por clientes perdidos por unidad de tiempo
E [CT ( µ , K )] = µCµ + Cc L( µ , K ) + KCK + λ PK C p
TEORÍA DE COLAS
K ∈N
36
