View
14
Download
0
Category
Preview:
DESCRIPTION
Teoria de Colas
Citation preview
TEORA DE COLAS 1
Teora de colas
Andrs Ramos Universidad Pontificia Comillas
http://www.iit.upcomillas.es/aramos/ Andres.Ramos@upcomillas.es
TEORA DE COLAS 2
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.
TEORA DE COLAS
Estudio matemtico de las caractersticas de los sistemas de colas.
TEORA DE COLAS 3
Proceso en una cola 1. Entrada de clientes
2. Sistema de colas cola o lnea de espera
mecanismo de servicio
3. Salida de clientes
COLA MECANISMO SERVICIO
FUENTE ENTRADA CLIENTES
SALIDA CLIENTES
SISTEMA DE COLAS
TEORA DE COLAS 4
Ejemplos
Clientes Servicio Servidores
Clientes tienda Venta artculo Dependiente Clientes banco Operacin financiera Ventanilla Clientes supermercado Cobro compra Caja Automvil Llenar depsito Surtidor Automvil Reparacin avera Operarios taller Avin Aterrizaje / despegue Pista
Llamadas telefnicas Conversacin Centralitas Enfermos Atencin mdica Mdico Cajas Transporte Robot de almacenamiento Juicios pendientes Juicio Jueces
TEORA DE COLAS 5
Entrada de clientes TAMAO Nmero total de clientes potenciales (poblacin de entrada): Finito (fuente limitada) (sistema cerrado) Infinito (fuente ilimitada) (sistema abierto) Suposicin habitual: tamao infinito (es decir, el nmero de clientes en la cola NO afecta el nmero potencial de clientes fuera de ella)
ENTRADA O FUENTE Unitaria Por bloques
TIEMPO ENTRE LLEGADAS Determinista Probabilista (distribucin de probabilidad exponencial)
TASA MEDIA DE LLEGADA Nmero medio de entrada de clientes por unidad de tiempo Llegadas de clientes son independientes e idnticamente distribuidas (IID)
TEORA DE COLAS 6
Cola Nmero mximo de clientes admisible
Finito Infinito Suposicin habitual: colas de longitud infinita (prdida del cliente o reintento) Nmero de canales (carriles de una calle ante un semforo) en la cola e interferencia entre ellos
Disciplina de la cola Orden de seleccin de sus miembros para ser atendidos
FIFO, FIFO con lmite LIFO SIRO (Aleatorio) Por prioridad (interruptora o no)
TEORA DE COLAS 7
Mecanismo de servicio SERVIDORES
Proporcionan el servicio al cliente Nmero de servidores: Uno Varios Independencia o no entre servidores
TIEMPO DE SERVICIO
Determinista Probabilista (distribucin de probabilidad exponencial)
TASA MEDIA DE SERVICIO
Nmero medio de clientes que son atendidos en un servidor por unidad de tiempo. Servicios a clientes son independientes e idnticamente distribuidas (IID)
TEORA DE COLAS 8
Especificacin de un sistema de colas Distribucin del tiempo entre llegadas / Distribucin del tiempo de servicio / Nmero de servidores / Nmero mximo de clientes en el sistema / Disciplina de la cola M exponencial D degenerada (tiempos constantes) E Erlang (Gamma) G 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
TEORA DE COLAS 9
Medidas de eficacia de un sistema de colas tasa de llegada 1/ tiempo medio entre llegadas tasa de servicio 1/ tiempo medio de servicio factor de utilizacin (intensidad de trfico): fraccin esperada de tiempo que estn ocupados los s servidores
s
= habitualmente < 1
N estado del sistema, nmero de clientes en el sistema (cola + servicio) L nmero medio de clientes en el sistema L = E[N] Nq longitud de la cola, nmero de clientes en la cola Lq nmero medio de clientes en la cola Lq = E[Nq] T tiempo de estancia de los clientes en el sistema W tiempo medio de estancia de los clientes en el sistema W = E[T] Tq tiempo de espera de los clientes en la cola Wq tiempo medio de espera de los clientes en la cola Wq = E[Tq] c nmero medio de servidores ocupados
TEORA DE COLAS 10
Qu sistema de colas es ms efectivo? Sistema de 8 servidores con 8 colas.
Sistema de 1 cola que abastece a 8 servidores.
TEORA DE COLAS 11
Frmulas de Little para condicin estacionaria en sistema M/M/1 La condicin estacionaria se produce cuando la distribucin del nmero de clientes en el sistema se conserva a travs del tiempo. Nmero 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/ Nmero medio de clientes en el sistema = nmero medio de clientes en la cola + factor de utilizacin
L = Lq + /
TEORA DE COLAS 12
Distribucin exponencial T variable aleatoria tiempo entre llegadas o tiempo de servicio
0( )
0 0
t
T
e tf t
t
=
=
2var( ) 1T =
FALTA DE MEMORIA: La distribucin de la probabilidad del tiempo que falta para que ocurra el evento es siempre la misma independientemente del tiempo que haya pasado
{ } { } { }{ } { }( )|
|t t
t
t
P T t T t t P T t t eP T t t T t e P T t
P T t e
+
> > + > + > + > = = = = >
>
El mnimo de variables aleatorias exponenciales tiene distribucin exponencial.
1/
fT(t)
t
( / ) ( )( / )
( )
P A B P BP B A
P A
=
TEORA DE COLAS 13
Procesos de Poisson Si los tiempos entre llegadas/servicios se distribuyen segn una exponencial el nmero de llegadas/servicios hasta un cierto tiempo es un proceso de Poisson. ( )N t nmero de ocurrencias (llegadas o servicios) en el tiempo t ( 0)t . Se distribuye
segn una Poisson con parmetro t ( nmero medio de ocurrencias por unidad de tiempo)
{ } ( )( )!
n tt eP N t n
n
= = 0,1,n =
{ } { }( ) 0 tP N t e P T t= = = > [ ]( )E N t t=
La probabilidad de ocurrencia de un suceso en el siguiente intervalo (pequeo) de tiempo t sabiendo que no se ha producido hasta ese momento t es t { }|P T t t T t t + >
TEORA DE COLAS 14
Procesos de Poisson PROPIEDAD REPRODUCTIVA:
La suma de procesos de entrada de Poisson es tambin 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 ip el proceso de llegada a cada subsistema es tambin de Poisson con tasa ip
TEORA DE COLAS 15
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 = nmero de cliente en el sistema
Hiptesis:
Distribucin del tiempo que falta para la llegada es exponencial con parmetro n 0,1,n = siendo n la tasa de llegada de clientes al sistema dado que hay n clientes
( )N t n= Distribucin del tiempo que falta para la salida es exponencial con parmetro n
0,1,n = siendo n la tasa de salida de clientes del sistema dado que hay n clientes ( )N t n=
Independencia entre el tiempo hasta prxima llegada y tiempo hasta prxima salida
TEORA DE COLAS 16
Diagrama de transiciones Por ser proceso de Poisson, la probabilidad de ocurrencia de un suceso en un t es proporcional a t siendo 0t Tanto la llegada como la salida son procesos de Poisson e independientes, luego de un estado dado slo se puede pasar a dos posibles estados.
31 2 n+1n-1 n
1 2 n-1 n
2 3 n n+1
...0 ...
0
1
31 2 n+1n-1 n
1 2 n-1 n
2 3 n n+1
...0 ...
0
1
TEORA DE COLAS 17
Tasa media de llegada al estado n 1 1 1 1n n n nP P + ++ Tasa media de salida del estado n n n n nP P +
nP 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 estado n 1 1 1 1n n n n n n n nP P P P + ++ = +
TEORA DE COLAS 18
0n = 1 1 0 0P P = 01 01
P P
=
1n = 0 0 2 2 1 1 1( )P P P + = + 1 02 02 1
P P
=
2n = 1 1 3 3 2 2 2( )P P P + = + 2 1 03 03 2 1
P P
=
1 2 00
1 1
n nn
n n
P P
=
0
1nn
P
=
=
1 2 0
1 1
n nn
n n
C
=
1,2,n =
0 1C = 0n =
00 0
1n nn n
P C P
= =
= = 0
0
1
n
n
P
C
=
=
TEORA DE COLAS 19
Nmero medio de clientes en el sistema 0
n
n
L nP
=
=
Nmero medio de clientes en cola con s servidores ( )q nn s
L n s P
=
=
Tasa media de llegadas 0
n n
n
P
=
=
TEORA DE COLAS 20
Cola M/M/1 Tasa media de llegada constante e independiente del estado del sistema n = Tasa media de servicio constante e independiente del estado del sistema n = Factor de utilizacin
= Para alcanzar estado estable 1 <
n
n
nC
= =
0n
nP P= 0
0
11
n
n
P
=
= =
(1 ) nnP = 0,1,2,n =
31 2 n+1n-1 n
...0 ...
31 2 n+1n-1 n
...0 ...
TEORA DE COLAS 21
Medidas de funcionamiento de cola M/M/1
Nmero medio de clientes en el sistema 0 1
n
n
L nP
=
= = =
Nmero medio de clientes en cola con 1 servidor 2 2
1
( 1)1 ( )q nn
L n P
=
= = =
Tiempo medio de los clientes en el sistema 1 1
(1 )
LW = = =
Tiempo medio de los clientes en cola 1
(1 )qW W
= =
Factor de utilizacin del servidor 01qL L P = = Probabilidad de tiempo de espera en cola nulo { }0 1 0qP P W= = = Probabilidad de tiempo de espera en cola > t { } (1 )tqP W t e > = 0t Probabilidad de tiempo de estancia en el sistema > t { } (1 )tP W t e > = 0t
TEORA DE COLAS 22
Cola M/M/s Tasa media de llegada constante e independiente del estado del sistema n =
Tasa media de servicio n
n n s
s n s
= >
Factor de utilizacin s
= Para alcanzar estado estable 1 <
3 1 2 s s-2 s-1
2 (s-1) s
...
TEORA DE COLAS 23
1
!
1
!
n
n s n s
n sn
C
n ss s
=
>
01 1
0 1 1
1 1 1
1 1 1 1 11 1
! ! ! ! 1
n s n s n ss s
n
nn n s n
P
Cn s s n s
s
== = =
= = =
+ + + +
( ) ( )0 10
1
! !(1 )
n ss
n
Ps s
n s
=
=
+
0
0
1
!
1 1
!
n
n n
n s
P n sn
P
P n ss s
=
>
TEORA DE COLAS 24
Medidas de funcionamiento de cola M/M/s
Nmero medio de clientes en cola con s servidores ( )
02!(1 )
s
qL Ps
=
Nmero medio de clientes en el sistema qL L
= +
Tiempo medio de los clientes en cola qqL
W =
Tiempo medio de los clientes en el sistema 1
q
LW W = = +
Probabilidad de tiempo de estancia en el sistema > t
{ }( 1 )
0 ( ) 11!(1 ) 1
s t st P eP W t e
s s
> = +
0t
Probabilidad de tiempo de espera en cola > t { } { } (1 )1 0 s tq qP W t P W e > = = 0t Probabilidad de tiempo de espera en cola nulo { } 1
0
0s
q n
n
P W P
=
= =
TEORA DE COLAS 25
Cola M/M/s/K K nmero mximo de clientes en el sistema (por ejemplo, lugares disponibles para los clientes camillas-) No se permite la entrada cuando el sistema est lleno.
Tasa media de llegada 0,1,2, , 1
0 nn K
n K
= =
Nmero de servidores inferior al nmero mximo de clientes s K
1 0,1,2, ,
!
1 , 1, ,
!
0
n
s n s
n
n sn
C n s s Ks s
n K
=
= = +
>
0
0
1 0,1,2, ,
!
1 , 1, ,
!
0
n
s n s
n
P n sn
P P n s s Ks s
n K
=
= = +
>
TEORA DE COLAS 26
0
0 0 1
1 1
1 1
! !
K n s n ss K
n
nn n s
P
Pn s s
== = +
= =
+
Nmero medio de clientes en cola ( )
021 ( ) (1 )
!(1 )
s
K s K s
qL P K ss
=
Nmero medio de clientes en el sistema 1 1
0 0
(1 )s s
n q n
n n
L nP L s P
= =
= + +
Tasa media de llegada (entrada efectiva) (1 )EF KP =
Tiempo medio de los clientes en cola qqEF
LW =
Tiempo medio de los clientes en el sistema EF
LW =
TEORA DE COLAS 27
Cola M/G/1 Tiempos entre llegadas independientes y distribucin exponencial con tasa de llegada Tiempos de servicio independientes y distribucin general ( )F con media
1
y varianza
2 No se puede aplicar el proceso generalizado de nacimiento y muerte.
Frmula de Pollaczek-Khintchine: 2 2 2
2(1 )L
+= +
siendo
= .
TEORA DE COLAS 28
Sistema cerrado con cola M/M/1 Fuente finita de tamao m . Clientes una vez servidos vuelven a la fuente. Tiempos entre llegadas independientes y distribucin exponencial con tasa de llegada
dependiente del nmero de clientes en el sistema ( )
0nm n n m
n m
y 1
01
!1
( )!
nm
n
mp
m n
=
= +
siendo
=
TEORA DE COLAS 29
Tasa media de llegada al sistema ( )EF m L = Nmero medio de clientes en cola 0
1(1 )qL m p
+
=
Nmero medio de clientes en el sistema 01 p
L m
=
Tiempo medio de los clientes en cola 0
1 1
( ) 1q
q
L mW
m L p
+= =
Tiempo medio de los clientes en el sistema ( )
LW
m L =
TEORA DE COLAS 30
Sistema cerrado con cola M/M/s Fuente finita de tamao m . Clientes una vez servidos vuelven a la fuente. Tiempos entre llegadas independientes y distribucin exponencial con tasa de llegada
dependiente del nmero de clientes en el sistema ( )
0nm n n m
n m
TEORA DE COLAS 31
Cola M/M/s/s Capacidad del sistema es igual nmero de servidores (centrales telefnicas). Probabilidad de que el sistema est saturado (nmero de clientes igual a nmero de
servidores)
0
( ) / !
( ) / !
s
s si
i
s sP
s i
=
=
TEORA DE COLAS 32
Cola M/M/ El sistema tiene un nmero muy grande de servidores (sistemas de autoservicio, visitas a una ciudad). Tasa de llegadas n = Tasa de servicios n n =
Probabilidad de cada estado /( / )
0,1,...!
n
np e nn
= =
Medidas de funcionamiento de la cola 1
; 0; ; 0q qL L W W
= = = =
TEORA DE COLAS 33
Diseo 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 (Nmero medio de clientes en el sistema L por coste de estancia de cada cliente Cc)
Coste de los clientes:
Prdidas de ganancia por prdida de clientes Coste social del servicio Prdida de productividad
Decisiones:
Nmero de servidores por instalacin s Eficiencia de los servidores Nmero de sistemas en servicio (instalaciones)
TEORA DE COLAS 34
Optimizar el nmero de servidores , conocidos y fijos sC coste por servidor por unidad de tiempo
[ ]min ( ) ( )s cE CT s sC C L s= + s N
( 1) ( ) ( 1)CT s CT s CT s +
( ) ( 1) ( 1) ( )s
c
CL s L s L s L s
C +
TEORA DE COLAS 35
Optimizar la tasa de servicio conocida y fija C coste por unidad de tasa de servicio por unidad de tiempo
[ ]min ( ) ( )cE CT C C L = + Para cola M/M/1
L
=
[ ]( )
0E CT
=
c
C
C
= +
TEORA DE COLAS 36
Optimizar la tasa de servicio y la capacidad del sistema conocida y fija KC coste por unidad de capacidad por unidad de tiempo
pC coste por clientes perdidos por unidad de tiempo
[ ]( , ) ( , )c K K pE CT K C C L K KC P C = + + + K N
Recommended