TEORIA DE COLAS
Presenta:
Alvaro Sanchez Martinez
Pedro Pérez Villanueva
26 Sep -2003
COMIMSA
PICYT
1
SIMULACION AVANZADA
TEORIA DE COLAS
¿Donde esta la espera?
Instalaciones de Servicio
 Restaurantes de comida rapida
 Oficina de correos
 Supermercados
 Bancos
Manufactura
Equipo esperando a ser reparado
Telefono o red de computo
Ordenes de Producto
¿Por que hay espera?
COMIMSA
PICYT
2
SIMULACION AVANZADA
Caracteristicas del Sistema
 Numero de Servidores
• Forma de arribo y servicio
• Comportamiento de la linea
Medicion del Sistema
 Promedio del numero de clientes en espera
• tiempo promedio de espera del cliente
• Utilizacion del sistema
COMIMSA
PICYT
3
SIMULACION AVANZADA
Numero de Servidores
Un servidor
Multiples
servidores
Multiples Servidores
sencillos
COMIMSA
PICYT
4
SIMULACION AVANZADA
Forma de llegada
Usualmente se asume una distribucion Poisson:
Relative Frequency
.18
.16
.14
.12
.10
.08
.06
.04
.02
0
1
2
3
4
5
6
7
8
9
10 11 12 13
Cu stom er s p er time u nit
COMIMSA
PICYT
5
SIMULACION AVANZADA
Tiempo de Servicio
Una distribucion exponencial es asumida:
Relative Frequency (%)
S er vi ce T im e
COMIMSA
PICYT
6
SIMULACION AVANZADA
Comportamiento de la linea de espera
Primeras entradas – Primeras Salidas (FCFS, FIFO):
Prioridades Multiples:
COMIMSA
PICYT
7
SIMULACION AVANZADA
Algunos Modelos
1. Un servidor, tiempo de servicio exponencial (M/M/1)
2. Un servidor, tiempo de servicio general (M/G/1)
3. Servidores multiples, tiempo de servicio exponencial (M/M/s)
Nomenclatura
A/B/s
Distribucion
De llegada
Distribucion
de servicio
Numero de
Servidores
donde
M = distribucion exponencial (“Markovian”)
D = deterministica (constante)
G = distribucion general
COMIMSA
PICYT
8
SIMULACION AVANZADA
Datos conocidos
l
m
=
Tasa de llegada del cliente
=
tasa de servicio (1/m = tiempo de servicio promedio)
s
=
numero de servidores
Lq
=
numero promedio de clientes en la linea
L
=
numero promedio de clientes en el sistema
Wq
=
tiempo promedio de espera en la linea
W
=
Tiempo pormedio de espera (incluyendo tiempo de servicio)
Pn
=
Probabilidad de tener n clientes en el sistema
r
=
Utilizacion del sistema
Se calcula
COMIMSA
PICYT
9
SIMULACION AVANZADA
Conceptos basicos
Los siguientes ecuacione saplican para todos los tipos de
modelos
r
l
•
Utilizacion del sistema
•
Numero promedio de clientes en el sistema
sm
Wq 
•
Tiempo promedio de espera en la linea
•
Tiempo total de espera (incluyendo servicio)
L  Lq 
l
m
Lq
l
W  Wq 
COMIMSA
PICYT
10
1
m
SIMULACION AVANZADA
Modelo 1 (M/M/1)
Formulas
Probabilidad que el sistema este vacio:
P0  1 
l
m
n
 l 
Probabilidad de n clientes en el sistema: Pn  P0  
 m 
Numero promedio en la linea:
COMIMSA
PICYT
11
Lq 
l
2
m m  l 
SIMULACION AVANZADA
Modelo 2 (M/G/1)
Formulas
Numero promedio en linea:
Probabilidad de que le sistema este vacio:
(Caso especial: M/D/1
2
Lq 
COMIMSA
PICYT
12
2
2 1  r 
P0  1 
Lq 
2
l  r
l
)
m
l
2
2 m m  l 
SIMULACION AVANZADA
Model 3 (M/M/s)
Formulas
P0 
Probabilidad que sistema este vacio :
1
s 1
n
l / m 
n 0
n!

Probabilidad de n clientes en el sistema:

s
l / m 
s!(1  r )
( l / m ) n
P0

 n!
Pn  
n
l
/
m



n  s P0

 s! s
for n  1
,s
for n  s
s
Probabilidad de que un nuevo cliente vaya a esperar:
P0
l 
Pw   
m  s!(1  r )
Numero promedio en linea:

(l / m )

L q  P0 
2 
(s  1)! ( s  l / m ) 
s 1
COMIMSA
PICYT
13
SIMULACION AVANZADA
Aplicación de teoria de Colas
Se pueden usar los resultados de
teoria de colas para tomasr las
siguientes decisiones:
Cos t
 Cuantos servidores usar
 Usar un revidor rapido o
varios servidores lentos
T ot al C os t
C os t of
S er v ic e C apa cit y
 Tener un servidor
general o un servidor para
una tarea especifica
C o s t of cu sto m e rs
w ai ti ng
O p ti m u m
S er v ic e C apa cit y
Objetivo:
Minimizar costo total = costo del servidor + costo de espera
COMIMSA
PICYT
14
SIMULACION AVANZADA
Aplicación de teoria de Colas
Problema:
Simulacion del tiempo de espera de un cliente en la fila de
un banco antes de que sea atendido
COMIMSA
Tiempo
Tiempo
Cliente
llegada
salida
1
2
3
4
5
6
0.4
1.6
2.1
3.8
4.0
5.6
PICYT
2.4
3.1
3.3
4.9
5.2
8.6
Tiempo del
servidor
2
0.7
0.2
1.1
0.3
3
15
Tiempo de
espera
0
0.8
1
0
0.9
0
SIMULACION AVANZADA
Inicio
t. llegadas
NA=0 (No. De clientes atendidos)
NNA=0 (No. De clientes no atendidos)
NS=1 (No. De servidores)
T=600 minutos (tiempo servicio)
L=20 (cantidad personas
t. salidas
máximo en la fila)
Dist. Poisson para llegadas
  4 Dist. Exponencial para salida
S =0 (Estado del servidor)
Wq=0 (T. promedio espera en fila)
Lq=0 (T. promedio clientes en fila)
Tts=0 (Tiempo total del servicio)
Ttl=0 (Tiempo total de llegadas)
Tto=0 (Tiempo total)
Cf=0 (No. De clientes en la fila)
Dist. Exponencial
l 4
Dist. Poisson
para llegadas λ=4
Return
Para llegadas λ=4
Return
t. llegadas
Tto=Tto+Ttl
cf=cf+1
No
S=0
NNA=NNA+1
t. servicio
No
t>600
Fin de la
simulación
PICYT
Si
No
Si
COMIMSA
L<20
16
NA=0 (No. De clientes atendidos)
NNA=0 (No. De clientes no atendidos)
t=600 lminutos
(tiempo servicio)
4
L=20 (cantidad personas
 4
máximo en la fila)
Dist. Poisson para llegadas
Dist. Exponencial para salida
Wq=0 (T. promedio espera en fila)
Lq=0 (T. promedio clientes en fila)
tts=0 (Tiempo total del servicio)
tl=0 (Tiempo total de llegadas)
tt=0 (Tiempo total)
cf=0 (No. De clientes en la fila)
SIMULACION AVANZADA
COMIMSA
PICYT
17
SIMULACION AVANZADA
Descargar

Teoria de colas - Rensselaer Hartford Campus