• Author / Uploaded
• Enrique Ruiz

• Categories
• Teoría de la medida
• Modelado científico
• Teoría estadística
• Teoría de probabilidad
• Física y matemáticas

Citation preview

(3.b) MODELOS EXPONENCIALES de COLAS

INTRODUCCIÓN A LOS PROCESOS DE NACIMIENTO Y MUERTE. Ecuaciones de equilibrio. Condición de E.E. APLICACIÓN DE LAS ECUACIONES DE EQUILIBRIO: La cola M/M/1. Ilustración del comportamiento. MODELOS DE COLAS EXPONENCIALES. Trabajo de servidores en paralelo. Casos importantes: M/M/s , M/M/s/K , M/M/s/./N. Propiedades. Longitudes medias y Tiempos de permanencia.

Cap. 15 Hillier F.S., Lieberman G.J. “Introduction to Operations Research” Holden day Inc. 1986. Cap. 4 Gross D., Harris C.M."Fundamentals of queueing theory" John Wiley and Sons. 1998.

I.O.E. Diplomatura de Estadística

TEORIA DE COLAS

UPC

TIEMPO DE VIDA CONDICIONAL

PROPIEDAD 2. Caso exponencial. Ausencia de memoria τi-1

τi

θ

I.O.E. Diplomatura de Estadística

s

UPC

Máquina 1

τ1 Máquina 2

τ2 τ N=2

N=3

N=20

N=5

N=50 Palm (1943)

PROCESOS DE NACIMIENTO Y MUERTE • "Nacimiento" indica llegada al S.E • "Muerte" indica salida del S.E. Puede ocurrir que el tiempo entre llegadas τ sea v.a. con distribución dependiente del estado N del sistema. t

τi1

τ

i2

τ

i3

……

τik

τik

1. Si N (t ) = n el tiempo entre llegadas τ ~ exp. de parámetro λ n . 2. Si N (t ) = n el tiempo de servicio ~exp. De parámetro µ n .

Sólo una llegada o una salida al/del sistema puede darse en cada instante t.

I.O.E. Diplomatura de Estadística

UPC

Diagrama de tasas de transición Muestra las posibles transiciones permitidas en el estado del sistema en un instante.

Tasas del proceso de llegadas al S.E. λ1

λ0 0

1

2

λn

λn-1

λ2 •••

n-1

µn µ2 µ3 µ1 Tasas del proceso de servicio en el S.E.

λn+1 n+1

n

µn+1

•••

µn+2

La distribución de probabilidades del estado del sistema, N(t), en régimen estacionario es relativamente intuitivo de deducir a partir del diagrama de tasas de transición.

λ1

λ0 1

0

2

µ2

µ1

Estado 0 1 2 M

n −1 n M

λn

λn-1

λ2 •... ••

µ3

Tasa incidente µ1 ⋅ P1 λ0 ⋅ P0 + µ 2 ⋅ P2

λ1 ⋅ P1 + µ 3 ⋅ P3

µn

• •... •

n+1

n

n-1

λn+1

µn+1

µn+2

= Tasa emergente = λ0 ⋅ P0 (λ1 + µ1 )⋅ P1 = (λ2 + µ 2 )⋅ P2 = M

λn−2 ⋅ Pn−2 + µ n ⋅ Pn = λn−1 ⋅ Pn−1 + µ n+1 ⋅ Pn+1 = M

(λn−1 + µ n−1 )⋅ Pn−1 (λn + µ n )⋅ Pn

Hay tantas ecuaciones como valores pueda presentar N(t), por tanto, si en el S.E. sólo pueden haber como máximo K clientes, habrán K+1 ecuaciones.

Resolución del sistema de ecuaciones

 P1  P 2  P3     Pn  P  n+1  

λ0 = ⋅ P0 µ1 λ0λ1 λ1 λ1 1 = ⋅ P1 + ⋅(µ1 ⋅ P1 −λ0 ⋅ P0 ) = ⋅ P1 = ⋅ P0 µ2 µ2 µ2 µ1µ2 λ0λ1λ2 λ2 λ2 λ2 1 1 = ⋅ P2 + ⋅(µ2 ⋅ P2 −λ1 ⋅ P1 ) = ⋅ P2 + ⋅(µ1 ⋅ P1 −λ0 ⋅ P0 ) = ⋅ P2 = ⋅ P0 µ3 µ3 µ3 µ3 µ3 µ1µ2µ3 M λn−1 λn−1 λn−1 λ0λ1 Kλn−1 1 1 = ⋅ Pn−1 + ⋅(µn−1 ⋅ Pn−1 −λn−2 ⋅ Pn−2 ) = ⋅ Pn−1 + ⋅(µ1 ⋅ P1 −λ0 ⋅ P0 ) = ⋅ Pn−1 = ⋅ P0 µn µn µn µn µn µ1µ2 Kµn λn λ0λ1 Kλn = L= ⋅ Pn = ⋅ P0 µn+1 µ1µ2 Kµn+1 M

λ0 λ1 Kλn−1 Cn = µ1 µ 2 K µ n

n = 1, 2,K ;

λ0 λ1 Kλn−1 ⋅ P0 = Cn ⋅ P0 Pn = µ1 µ 2 K µ n ∞

∑

n =0

Pn =

∞

∑

n =0

C0

n = 1, 2,K

Cn ⋅ P0 = 1 → P0 =

1 ∞

∑

n =0

Las probabilidades de estado estacionario quedan definidas si:

=1

Cn

∞

∑

n =0

Cn < +∞

En caso de que el S.E. pueda contener sólo K clientes como máximo, el sumatorio se extiende de n=0 a n=K y siempre será finito.

I.O.E. Diplomatura de Estadística

UPC

APLICACIÓN DE LAS ECUACIONES DE EQUILIBRIO: el modelo M/M/1 Hipótesis del modelo: • Tiempos entre llegadas i.i.d. de ley exponencial con parámetro λn = λ . • Tiempos de servicio i.i.d. según una ley exponencial de parámetro µ n = µ . • Un único servidor, s = 1.

λn = λ n = 0,1, 2,K µ n = µ n =1, 2,K λ

λ 1

0

µ

•... ••

2

µ

µ

λ

λ

λ

n+1

n

n-1

µ

λ

µ

• •... •

µ

➨

➨

λ = ρ Hay régimen estacionario si el factor de carga del S.E. es µ t,K,Tn > t}) =1− P({T1 > t})LP({Tn > t}) = n t − α −αnt −α1t ∑ i =1 i =1− e Le =1− e =1− e−α t

I.O.E. Diplomatura de Estadística UPC

La interpretación que puede darse de la propiedad en el caso del tiempo entre llegadas es que si la población esta constituida para diferentes clases de clientes que llegan cada una al sistema de espera según una ley exponencial vinculada a la clase, entonces el tiempos entre las llegadas de 2 clientes cualesquiera sigue una ley exponencial, o el que es equivalente, la población puede tratarse desde el punto de vista de la distribución entre llegadas al sistema de espera como si fuera homogénea.

Fuente 1 Fuente 2 Fuente n

α1 α2

α1 + α2 + …+αn

αn

I.O.E. Diplomatura de Estadística UPC

Î Si hay n servidores, el tiempo que resta hasta la próxima finalización de servicio no depende del instante ni del servidor que ha completado el último servicio y sigue una distribución exponencial, lo que permite tratar sistemas de espera con n>1 servidores, como si tuvieran un único servidor pero que trabaja tan rápido como los n juntos. Î Supongamos n fuentes exponenciales y sean r1 …rn los intervalos de tiempo transcurridos desde el último suceso para las fuentes 1 … n respectivamente. Consideremos variables aleatorias s1 …sn , tiempos contados desde el instante actual hasta el próximo suceso para cada una de las n fuentes.

Por la propiedad de ausencia de memoria las variables aleatorias s1, … sn también se distribuyen exp. con parámetros α1 , α2 …, αn

el tiempo contado a partir del instante actual hasta que algún otro suceso proviniente de las n fuentes se produzca, se distribuye

r1

s1

r2

rn

s2

sn

n

exponencialmente con parámetro

α = ∑αi . i =1

Instante actual

I.O.E. Diplomatura de Estadística UPC

MODELO M/M/s

• • •

Tiempos entre llegadas τ i.i.d. de ley exp. con parámetro λ. s > 1 servidores iguales. Tiempo de servicio x i.i.d. según una ley exp. de parámetro µ.

λ

λ 1

0

µ

λn = λ n ⋅ µ µn =  s ⋅ µ λ 2

2µ

•••

3µ

n = 0,1, 2,K n =1, 2,K, s − 1 n = s , s + 1,K λ λ s+1

s

s-1

sµ

λ

sµ

•••

sµ

λ 1. 4. El número de clientes al sistema de espera es ≤ K. El número máximo de clientes N(t) presentes en el S.E. debe ser ≤ K Si el S.E. está lleno al llegar un cliente éste se pierde:

λ

λ 1

0

µ ➨

2

2µ

•••

3µ

λ

λ

λ

sµ

••• K

s+1

s

s-1

λ

sµ

sµ

Siempre alcanzará régimen estacionario.

I.O.E. Diplomatura de Estadística UPC

 1  λ n     n!  µ  s n−s λ0 λ1 K λ n −1  1  λ   λ  =     Cn = µ1 µ 2 K µ n  s !  µ   sµ   0 

n = 1, 2,K, s − 1 n = s, s + 1,K, K n = K + 1, K + 2,K

➨ Lo que facilita el estado del sistema en régimen estacionario: ∞

∞

∑ P = ∑C P0 =

n =0

1

=

∞

∑C n =0

n

n

n =0

n

P n = C n ⋅ P0

⋅ P0 = 1 → 1 n

K 1 λ 1 λ   + ∑   ∑ n =0 n !  µ  n=s s !  µ  s −1

i C0 = 1

s

 λ     sµ 

n−s

λ = ≠1 . ρ ; s⋅µ

Si K no es demasiado alto es aconsejable utilizar las fórmulas generales para procesos de nacimiento y muerte en equilibrio.

I.O.E. Diplomatura de Estadística UPC

∞

K −1

K −1

n =0

n =0

n =0

λ = ∑ λn ⋅ Pn = ∑ λ ⋅ Pn = λ ⋅ ∑ Pn = λ ⋅ (1 − PK )

Si N (t) < K

Si N (t) = K Población

Sistema de Espera

I.O.E. Diplomatura de Estadística UPC

• La esperanza matemática de la variable aleatoria longitud de cola s

s

K −s 1 λ 1 λ s+n−s Lq = ∑ (n − s ) ⋅ Pn = ∑ n   (ρ ) P0 =   P0 ∑ nρ n =... n=s n =0 n =0 s!  µ  s!  µ  ∞

K −s

s

1 λ ρ K −s K −s ( ( ) − ρ − − ⋅ ρ ⋅ (1 − ρ )). .... =   P0 1 K s 2 s!  µ  (1 − ρ )

λ = ≠1 . ρ En las fórmulas presentadas se ha supuesto s⋅µ • La esperanza matemática de la variable aleatoria estado del sistema.

 1 λ L = ∑ n ⋅ Pn = λ ⋅ W = λ ⋅ Wq +  = Lq + µ µ n =0  ∞

Aplicación de las fórmulas de Little para el calculo de W y Wq .

L [ ] W = EW = λ

[ ]

Wq = E Wq =

Lq

λ

I.O.E. Diplomatura de Estadística UPC

MODELO M/M/s/./N S.E. con población finita (N) que presupone: • Tiempo de permanencia en la población de los clientes i.i.d según ley exp. de parámetro λ • Tiempos de servicio por servidor i.i.d. según ley exp. de parámetro µ. • Un conjunto de servidores en paralelo s > 1. • Una población finita de clientes limitado al valor N. Para simplificar

se supone N > s.

Es un S.E. cerrado: Hay siempre N clientes (población+S.E.) Tras salir del S.E. el cliente se reintegra en la Población

Población

Sistema de Espera

EJEMPLO: TALLER DE REPARACIONES En un taller de reparación de motores hay 3 mecánicos. Atienden un conjunto de 12 motores de una planta. • Cada mecánico repara un motor en un tiempo x ~ exp. E[x]=1día. • Tras repararse un motor es puesto en servicio inmediatamente. • El tiempo entre averías de un motor τ ~ exp. E[τ]=20 días.

Motores Población funcionando

TALLER

Sistema de Espera

M/M/s/./N: DIAGRAMA DE TASAS (N-1)λ

Nλ 1

0

2

2µ

µ

•••

n  λ N!     (N − n )! n !  µ  s n−s λ  λ  λ0 λ1 K λn −1  N!     = Cn = µ1µ 2 K µ n  (N − n )! s !  µ   sµ   0 

∞

∑

P0 =

1 ∞

∑

n =0

Cn

n =0

=

Pn =

∞

∑

n =0

i C0 = 1

n = s, s + 1, K , N n = N + 1, N + 2, K

Cn ⋅ P0 = 1 → 1 n

sµ

n = 1, 2, K , s − 1

N λ  λ  N! N! ∑   +∑   n =0 (N − n )! n ! µ   n=s (N − n )! s !  µ  s −1

sµ

sµ

3µ

N

N-1

N-2

N-3

λ

2λ

3λ

(N-2)λ

s

λ     sµ 

n−s

No se puede conseguir una expresión analítica compacta y los cálculos con población finita se desarrollan a partir de tablas específicas.

∞

N

n=s

n=s

Lq = ∑ (n − s ) ⋅ Pn = ∑ (n − s ) ⋅ Pn ➨ La esperanza matemática de la variable aleatoria estado del sistema se puede

deducir a partir de

Lq ,

 s −1  L = ∑n ⋅ Pn = ∑n ⋅ Pn + ∑n ⋅ Pn = ∑n ⋅ Pn + Lq + s ⋅ 1 − ∑Pn  n =0 n =0 n=s n =0  n =0  ∞

s −1

s −1

N

➨ Cálculo de la tasa media efectiva de llegadas por unidad de tiempo, ∞

N

n =0

n =0

N

N

n =0

n =0

λ = ∑ λn ⋅ Pn = ∑ (N − n )⋅ λ ⋅ Pn = ∑ N ⋅ λ ⋅ Pn − ∑ n ⋅ λ ⋅ Pn = N

= N ⋅ λ − λ ⋅ ∑ n ⋅ Pn = N ⋅ λ − L ⋅ λ ⋅ = (N − L )⋅ λ n =0

➨ La aplicación de las fórmulas de Little permite deducir el tiempo medio de espera en el

sistema W y en la cola de los sistema W q

L W = E[W ] = λ

y

[ ]

Wq = E Wq =

Lq

λ .

I.O.E. Diplomatura de Estadística UPC

SESION DE PROBLEMAS: USO de QTS_EXCEL probability

M/M/c system-size probabilities 0,25 0,20 0,15 0,10 0,05 0,00 0

2

4

6

8

10

size CDF for M/M/c line waiting times 1,00

cdf

0,80 0,60 0,40 0,20 0,00 0

0,5

1 time

1,5

Terminal de facturación de equipaje Un terminal de facturación dispone de 2 operarios que atienden los clientes que llegan según una distribución de Poisson de media 80 clientes por hora y esperen en una cola única hasta que alguno de los operarios esté libre. El tiempo requerido para atender un cliente esta distribuido exponencialmente con media 1.2 minutos. 1. Cual es el número esperado de clientes en la terminal de hacecturación? 2. Cual es el tiempos medios que un clientes pasa a la terminal de hacecturación? 3. Qué porcentaje del tiempo está libre un determinado operario? Modelo M/M/2 Tasa de llegadas

λ = 80 clientes/hora

ρ=

λ 80 = = 0.8 s ⋅ µ 2 ⋅ 50

60 µ = = 50 clientes/hora. Tasa de servicio por operario 1.2 s

1 λ  P0 → Lq = s!  µ

 

 Lq =  Wq λ ρ  P0 →  2 (1−ρ) L = + λ →W = L  Lq µ λ 

I.O.E. Diplomatura de Estadística UPC

P0 =

1 n

s

1 λ 1 λ 1     + ∑   s! µ  1 − ρ n =0 n !  µ  s −1

=

s

1 2

n

1  80  1  80  1 +     ∑ 2!  50  1 − 0.8 n = 0 n !  50  1

= 0.111

2

1 λ 1 8 0 .8 ρ Lq =   P0 =   (0.111) = 2.84 2 2 s! µ  (1 − 0.8) (1 − ρ ) 2!  5  1. El

número medios de clientes 80 λ L = Lq + = 2.84 + = 4.44 clientes. 50 µ

en

el

terminal

de

clientes

facturación

es

L 4.44 = = = 0.0555 horas W 2. Un clientes pasa en promedio en el terminal de facturación λ 80 = 3.33 minutos. 3. 1 ⋅ P0 + 1 2 ⋅ P1 = (1 + 1 2 ⋅ C1 ) ⋅ P0 = (1 + 1 2 ⋅ 8 5) ⋅ P0 = 0.2 ■

I.O.E. Diplomatura de Estadística UPC

El servicio de urgencias de un hospital El servicio de urgencias de un hospital dispone permanentemente de un médico de guardia, pero se han detectado tiempos de espera desaconsejables en muchas ocasiones, de manera que Dirección del Hospital quiere avaluar los beneficios de disponer de un segundo médico de urgencias. La tasa de llegada de enfermos al servicio de urgencias es de 1 paciente cada 30 minutos y el tiempo medio de servicio es de 20 minutos para

paciente. Determinar los parámetros ρ , P0 , Lq , L, Wq i W con s=1 y s=2 médicos de guardia. Determinar la función de distribución de probabilidad del tiempo de espera hasta ser examinado un paciente en ambas situaciones. En el caso M/M/1, ρ=

2 1 23 ρ λ 2 = = 2 pacientes L= = ; P0 = 1 − ρ = 1 − = 1− ρ 1− 2 3 µ 3 3 3

(2 3) = 4 pacientes ρ2 Lq = = 1− ρ 1− 2 3 3 2

W=

L 2 = = 1 hora λ 1

Wq = ρ ⋅ W = (2 3)⋅ 1 =

2 hora 3

I.O.E. Diplomatura de Estadística UPC

s

λ 2 1 = = = ρ En el caso M/M/2, s ⋅ µ 2⋅3 3 .

P0 =

P0 → Lq =

1 n

s

1 λ 1 λ 1   +   ∑ s! µ  1 − ρ n =0 n !  µ  s −1

s

=

1 λ    s! µ

 

 Lq =  W q λ ρ  P0 2 →  (1−ρ) L = + λ →W = L  Lq µ λ 

1 n

2

1 2 1 2 1 +     ∑ ! 3 2 ! n  3  1−1 3   n =0 1

=

1 2

2

1λ 1 2 1 1 3 1 ρ =   = Lq =   P0 pacientes 2 2 s! µ  (1 − ρ ) 2!  3  2 (1 − 1 3) 12 L = Lq +

W=

λ 1 2 3 = + = pacientes µ 12 3 4

L 3 1 3 = ⋅ = horas λ 4 2 8

Wq =

Lq

λ

=

1 1 1 horas ⋅ = 12 2 24

■ I.O.E. Diplomatura de Estadística UPC

Ejemplo: El Asesor Fiscal El asesor fiscal Un asesor fiscal dispone de un local para atender a sus clientes, los cuales se concentran mayoritariamente durante los meses de mayo y junio. El local tiene una capacidad máxima de 8 asientos en espera, el cliente se va si no encuentra un asiento libre, y el tiempo entre llegadas de clientes se puede considerar distribuido exponencialmente según un parámetro λ = 20 clientes por hora en período punta. El tiempo de una consulta esta distribuido exponencial con una media de 12 minutos, 1. ¿Cuantas consultas por hora realizará en promedio? 2. ¿Cual es el tiempo medio de permanencia en el local? El modelo es M/M/1/9  n 1− ρ ρ ⋅ Pn = Cn ⋅ P0 =  1 − ρ K +1  0

ρ=

λ 20 = =4 µ 5

n = 0,1, 2,K, K n = K + 1, K + 2,K

K =9,

P9 = C 9 ⋅ P0 = ρ 9 ⋅

1− ρ 1− 4 9 4 = ⋅ = 0.75 1 − ρ 10 1 − 410

∞

λ = ∑ λ ⋅ Pn = λ ⋅ (1 − P9 ) = 20 ⋅ (1 − 0.75 ) = 5 clientes/hora n =0

L=

(K + 1)ρ ρ − 1− ρ 1 − ρ K +1

K +1

) ) L 8.6 ) 4 10 ⋅ 4 = = 1.73 horas. = − = 8.6 clientes W = E[W ] = 10 1− 4 1− 4 5 λ 10

I.O.E. Diplomatura de Estadística UPC

Modelo de Reparación de Avionetas Una pequeña compañía aérea de una isla de las Antillas dispone de 5 avionetas, que hay que reparar con una tasa de 1 cada 30 días. Se disponen de 2 técnicos para reparaciones, cada uno de los cuales necesita un promedio de 3 días para una reparación. Los tiempos entre averías y de reparación son exponenciales. 1. Determinar el número medios de avionetas en funcionamiento. 2. Calcular el tiempo medio que una avioneta esta fuera de servicio cuando requiere una reparación. 3. Calcular el porcentaje del tiempo que un determinado técnico esta libre.

1 = λ El modelo es exponencial y de población finita: M/M/2//5. La tasa de averías es 30 avionetas por día y la tasa de reparaciones es µ =

1 avionetas por día. 3

El número medios de avionetas en funcionamiento es el número total de avionetas, N, menos el número esperado de avionetas en reparación, L: N

N − L = 5 − L = 5 − ∑ n ⋅ Pn . n =0

Hay que determinar las Pn = C n ⋅ P0 y para esto hacen falta las Cn y P0 . I.O.E. Diplomatura de Estadística UPC

n  5! 1    λ0 λ1 K λn −1  (5 − n )!n !  10  = Cn = µ1 µ 2 K µ n  5!  1  2  1  n − 2  (5 − n )!2!  10   2 ⋅10 

n =1 y C0 = 1 n = 2,K,5

n  5!  1   ⋅ P0   (5 − n )! n !  10  Pn = C n ⋅ P0 =  2 n−2 5 ! 1 1      ⋅ P0  (5 − n )!2 !  10   2 ⋅10 

i

1 0.5

n = 2, K ,5

3 4 5 C 0.015 0.0015 0.000075 ∞ ∞ 1 1 = ⋅ = → = = = 0.619 P C P P 1 ∑ ∑ n n 0 0 5 + + + + + 1 0 . 5 0 . 1 0 . 015 0 . 0015 0 . 000075 n =0 n =0 ∑ Cn i

0 1

n=1

2 0.1

n =0

i Pi

0 0.619

1 0.310

2 0.062

3 0.009

4 0.001

5 0.00004

N

➨

N − L = 5 − L = 5 − ∑ n ⋅ Pn = 5 − 0.465 = 4.535 avionetas en promedio en funcionamiento. n =0

I.O.E. Diplomatura de Estadística UPC

➨ El tiempo medio que una avioneta pasa en reparación es W.

W =

L 0.465 = = 3.08 días λ 0.151

1 1 ( ) ( ) N L 5 0 . 465 = ⋅ − = ⋅ − = ⋅ (4.535) = 0.151 λ λ donde 30 30 ➨ La fracción de tiempo que un determinado técnico pasa inactivo es

P0 + 0.5 ⋅ P1 = 0.619 + 0.5 ⋅ 0.310 = 0.774 .

I.O.E. Diplomatura de Estadística UPC

( 3.c) INTRODUCCIÓN A LOS MODELOS NO EXPONENCIALES Y REDES DE COLAS

• INTRODUCCIÓN A LAS REDES DE COLAS. Concepto de red abierta y cerrada. Redes abiertas y Teorema de Jackson. • MODELOS NO EXPONENCIALES Cola M/G/1: Fórmula de Pollaczeck-Khintchine. Cola G/M/1: casos Ek/M/1, Hip/M/1, Hyp/M/1. Uso de QTS_EXCEL. • APROXIMACIONES PARA COLAS GI/G/s. Aproximación de Allen-Cuneen. Aproximaciones para colas congestionadas (Heavy Traffic) Cap. 5 Allen A. O. “Probability, Statistics and Queueing Theory” Academic Press. 1998.

I.O.E. Diplomatura de Estadística

UPC