Download - Teoria de Colas Sipan
-
7/31/2019 Teoria de Colas Sipan
1/69
Lneas de Espera:
Teora de ColasCurso Mtodos Cuantitativos
Prof. Ing. Santiago Chung Ramrez
-
7/31/2019 Teoria de Colas Sipan
2/69
Las colas
Las colas son frecuentes en nuestra
vida cotidiana:
En un bancoEn un restaurante de comidas
rpidas
Al matricular en la universidad
Los autos en un lavacar
-
7/31/2019 Teoria de Colas Sipan
3/69
Las colas
En general, a nadie le gusta esperar
Cuando la paciencia llega a su lmite,
la gente se va a otro lugar Sin embargo, un servicio muy rpido
tendra un costo muy elevado
Es necesario encontrar un balance
adecuado
-
7/31/2019 Teoria de Colas Sipan
4/69
Teora de colas
Una cola es una lnea de espera
La teora de colas es un conjunto de
modelos matemticos que describensistemas de lneas de espera
particulares
El objetivo es encontrar el estadoestable del sistema y determinar una
capacidad de servicio apropiada
-
7/31/2019 Teoria de Colas Sipan
5/69
Teora de colas
Existen muchos sistemas de colasdistintos
Algunos modelos son muy especiales
Otros se ajustan a modelos ms
generales
Se estudiarn ahora algunos modeloscomunes
Otros se pueden tratar a travs de la
simulacin
-
7/31/2019 Teoria de Colas Sipan
6/69
Sistemas de colas: modelo bsico
Un sistema de colas puede dividirse
en dos componentes principales:
La colaLa instalacin del servicio
Los clientes o llegadas vienen en
forma individual para recibir el
servicio
-
7/31/2019 Teoria de Colas Sipan
7/69
Sistemas de colas: modelo bsico
Los clientes o llegadas pueden ser:
Personas
AutomvilesMquinas que requieren reparacin
Documentos
Entre muchos otros tipos de
artculos
-
7/31/2019 Teoria de Colas Sipan
8/69
Sistemas de colas: modelo bsico
Si cuando el cliente llega no hay
nadie en la cola, pasa de una vez a
recibir el servicio Si no, se une a la cola
Es importante sealar que la cola no
incluye a quien est recibiendo elservicio
-
7/31/2019 Teoria de Colas Sipan
9/69
Sistemas de colas: modelo bsico
Las llegadas van a la instalacin del
servicio de acuerdo con la disciplina
de la cola Generalmente sta es primero en
llegar, primero en ser servido
Pero pueden haber otras reglas ocolas con prioridades
-
7/31/2019 Teoria de Colas Sipan
10/69
Sistemas de colas: modelo bsico
Llegadas
Sistema de colas
Cola
Instalacin
del
servicio
Disciplina
de la cola
Salidas
-
7/31/2019 Teoria de Colas Sipan
11/69
Estructuras tpicas de sistemas
de colas: una lnea, un servidor
Llegadas
Sistema de colas
Cola ServidorSalidas
-
7/31/2019 Teoria de Colas Sipan
12/69
Estructuras tpicas de sistemas de
colas: una lnea, mltiples servidores
Llegadas
Sistema de colas
Cola
ServidorSalidas
Servidor
Servidor
Salidas
Salidas
-
7/31/2019 Teoria de Colas Sipan
13/69
Estructuras tpicas de colas: varias
lneas, mltiples servidores
Llegadas
Sistema de colas
ColaServidor
Salidas
Servidor
Servidor
Salidas
Salidas
Cola
Cola
-
7/31/2019 Teoria de Colas Sipan
14/69
Estructuras tpicas de colas: una
lnea, servidores secuenciales
Llegadas
Sistema de colas
Cola
Servidor
Salidas
Cola
Servidor
-
7/31/2019 Teoria de Colas Sipan
15/69
Costos de un sistema de colas
1. Costo de espera: Es el costo para el
cliente al esperar
Representa el costo de oportunidaddel tiempo perdido
Un sistema con un bajo costo de
espera es una fuente importante decompetitividad
-
7/31/2019 Teoria de Colas Sipan
16/69
Costos de un sistema de colas
2. Costo de servicio: Es el costo de
operacin del servicio brindado
Es ms fcil de estimar El objetivo de un sistema de colas
es encontrar el sistema del costo
total mnimo
-
7/31/2019 Teoria de Colas Sipan
17/69
Sistemas de colas: Las llegadas
El tiempo que transcurre entre dos
llegadas sucesivas en el sistema de
colas se llama tiempo entre llegadas El tiempo entre llegadas tiende a ser
muy variable
El nmero esperado de llegadas porunidad de tiempo se llama tasa media
de llegadas ()
-
7/31/2019 Teoria de Colas Sipan
18/69
Sistemas de colas: Las llegadas
El tiempo esperado entre llegadas es
1/
Por ejemplo, si la tasa media dellegadas es = 20 clientes por hora
Entonces el tiempo esperado entre
llegadas es 1/ = 1/20 = 0.05 horas o3 minutos
-
7/31/2019 Teoria de Colas Sipan
19/69
Sistemas de colas: Las llegadas
Adems es necesario estimar la
distribucin de probabilidad de los
tiempos entre llegadas Generalmente se supone una
distribucin exponencial
Esto depende del comportamiento delas llegadas
-
7/31/2019 Teoria de Colas Sipan
20/69
Sistemas de colas: Las llegadas
Distribucin exponencial
La forma algebraica de la distribucinexponencial es: ????
Dondet representa una cantidad
expresada en de tiempo unidades detiempo (horas, minutos, etc.)
tetserviciodetiempoP 1)(
-
7/31/2019 Teoria de Colas Sipan
21/69
Sistemas de colas: Las llegadas
Distribucin exponencial
Media Tiempo0
P(t)
-
7/31/2019 Teoria de Colas Sipan
22/69
Sistemas de colas: Las llegadas
Distribucin exponencial
La distribucin exponencial supone
una mayor probabilidad para tiempos
entre llegadas pequeos En general, se considera que las
llegadas son aleatorias
La ltima llegada no influye en laprobabilidad de llegada de la
siguiente
-
7/31/2019 Teoria de Colas Sipan
23/69
Sistemas de colas: Las llegadas -
Distribucin de Poisson
Es una distribucin discretaempleada con mucha frecuencia para
describir el patrn de las llegadas a
un sistema de colas Para tasas medias de llegadas
pequeas es asimtrica y se hace
ms simtrica y se aproxima a labinomial para tasas de llegadas altas
-
7/31/2019 Teoria de Colas Sipan
24/69
Sistemas de colas: Las llegadas -
Distribucin de Poisson
Su forma algebraica es:
Donde:
P(k) : probabilidad de k llegadas por
unidad de tiempo : tasa media de llegadas
e = 2,7182818
!)(
k
ekP
k
-
7/31/2019 Teoria de Colas Sipan
25/69
Sistemas de colas: Las llegadas -
Distribucin de Poisson
Llegadas por unidad de tiempo0
P
-
7/31/2019 Teoria de Colas Sipan
26/69
Sistemas de colas: La cola
El nmero de clientes en la cola es el
nmero de clientes que esperan el
servicio El nmero de clientes en el sistema
es el nmero de clientes que esperan
en la cola ms el nmero de clientesque actualmente reciben el servicio
-
7/31/2019 Teoria de Colas Sipan
27/69
Sistemas de colas: La cola
La capacidad de la cola es el nmero
mximo de clientes que pueden estar
en la cola Generalmente se supone que la cola
es infinita
Aunque tambin la cola puede serfinita
-
7/31/2019 Teoria de Colas Sipan
28/69
Sistemas de colas: La cola
La disciplina de la cola se refiere alorden en que se seleccionan los
miembros de la cola para comenzar
el servicio La ms comn es PEPS: primero en
llegar, primero en servicio
Puede darse: seleccin aleatoria,
prioridades, UEPS, entre otras.
-
7/31/2019 Teoria de Colas Sipan
29/69
Sistemas de colas: El servicio
El servicio puede ser brindado por un
servidor o por servidores mltiples
El tiempo de servicio vara de clientea cliente
El tiempo esperado de servicio
depende de la tasa media de servicio()
-
7/31/2019 Teoria de Colas Sipan
30/69
Sistemas de colas: El servicio
El tiempo esperado de servicio
equivale a 1/
Por ejemplo, si la tasa media deservicio es de 25 clientes por hora
Entonces el tiempo esperado de
servicio es 1/ = 1/25 = 0.04 horas, o2.4 minutos
-
7/31/2019 Teoria de Colas Sipan
31/69
Sistemas de colas: El servicio Es necesario seleccionar una
distribucin de probabilidad para lostiempos de servicio
Hay dos distribuciones querepresentaran puntos extremos:
La distribucin exponencial(=media)
Tiempos de servicio constantes(=0)
-
7/31/2019 Teoria de Colas Sipan
32/69
Sistemas de colas: El servicio
Una distribucin intermedia es la
distribucin Erlang
Esta distribucin posee un parmetrode formak que determina su
desviacin estndar:
mediak
1
-
7/31/2019 Teoria de Colas Sipan
33/69
Sistemas de colas: El servicio
Si k= 1, entonces la distribucinErlang es igual a la exponencial
Si k= , entonces la distribucinErlang es igual a la distribucin
degenerada con tiempos constantes
La forma de la distribucin Erlang
vara de acuerdo con k
-
7/31/2019 Teoria de Colas Sipan
34/69
Sistemas de colas: El servicio
Media Tiempo0
P(t)k =
k = 1k = 2
k = 8
-
7/31/2019 Teoria de Colas Sipan
35/69
Sistemas de colas:
Distribucin Erlang
Distribucin Desviacin estndar
Constante 0
Erlang,k = 1 media
Erlang,k = 2
Erlang,k = 4 1/2 media
Erlang,k = 8
Erlang,k = 16 1/4 media
Erlang, cualquierk
media2/1
media8/1
mediak/1
-
7/31/2019 Teoria de Colas Sipan
36/69
Sistemas de colas: Etiquetas para
distintos modelos
Notacin de Kendall:A/B/c A: Distribucin de tiempos entre llegadas
B: Distribucin de tiempos de servicio
M: distribucin exponencial
D: distribucin degenerada
Ek: distribucin Erlang c: Nmero de servidores
-
7/31/2019 Teoria de Colas Sipan
37/69
Estado del sistema de colas
En principio el sistema est en unestado inicial
Se supone que el sistema de colas
llega a una condicin de estadoestable (nivel normal de operacin)
Existen otras condiciones anormales
(horas pico, etc.)
Lo que interesa es el estado estable
-
7/31/2019 Teoria de Colas Sipan
38/69
Desempeo del sistema de colas
Para evaluar el desempeo se
busca conocer dos factores
principales:1. El nmero de clientes que
esperan en la cola
2. El tiempo que los clientes esperanen la cola y en el sistema
-
7/31/2019 Teoria de Colas Sipan
39/69
Medidas del desempeo del
sistema de colas
1. Nmero esperado de clientes en lacolaLq
2. Nmero esperado de clientes en el
sistemaLs
3. Tiempo esperado de espera en la
cola Wq4. Tiempo esperado de espera en el
sistema Ws
-
7/31/2019 Teoria de Colas Sipan
40/69
Medidas del desempeo del sistema de
colas: frmulas generales
qs
qq
ss
qs
LL
WL
WL
WW 1
-
7/31/2019 Teoria de Colas Sipan
41/69
Medidas del desempeo del
sistema de colas: ejemplo
Suponga una estacin de gasolina a
la cual llegan en promedio 45 clientes
por hora
Se tiene capacidad para atender en
promedio a 60 clientes por hora
Se sabe que los clientes esperan enpromedio 3 minutos en la cola
-
7/31/2019 Teoria de Colas Sipan
42/69
Medidas del desempeo del
sistema de colas: ejemplo
La tasa media de llegadas es 45clientes por hora o 45/60 = 0.75
clientes por minuto
La tasa media de servicio es 60
clientes por hora o 60/60 = 1 cliente
por minuto
-
7/31/2019 Teoria de Colas Sipan
43/69
Medidas del desempeo del
sistema de colas: ejemplo
clientesWL
clientesWL
WW
W
qq
ss
qs
q
25.2375.0
3475.0
min41131
min3
-
7/31/2019 Teoria de Colas Sipan
44/69
Medidas del desempeo del
sistema de colas: ejercicio
Suponga un restaurant de comidasrpidas al cual llegan en promedio100 clientes por hora
Se tiene capacidad para atender enpromedio a 150 clientes por hora
Se sabe que los clientes esperan en
promedio 2 minutos en la cola Calcule las medidas de desempeo
del sistema
-
7/31/2019 Teoria de Colas Sipan
45/69
Probabilidades como medidas del
desempeo Beneficios:
Permiten evaluar escenariosPermite establecer metas
Notacin:
Pn : probabilidad de tenern clientesen el sistema
P(Ws
t) : probabilidad de que uncliente no espere en el sistema msdet horas
-
7/31/2019 Teoria de Colas Sipan
46/69
Factor de utilizacin del sistema
Dada la tasa media de llegadas y latasa media de servicio , se define el
factor de utilizacin del sistema .
Generalmente se requiere que < 1
Su frmula, con un servidor y cons
servidores, respectivamente, es:
s
F t d tili i d l i t
-
7/31/2019 Teoria de Colas Sipan
47/69
Factor de utilizacin del sistema -
ejemplo
Con base en los datos del ejemplo
anterior, = 0.75, = 1
El factor de utilizacin del sistema sise mantuviera un servidor es
= / = 0.75/1 = 0.75 = 75%
Con dos servidores (s= 2):
= /s = 0.75/(2*1) = 0.75/2 = 37,5%
-
7/31/2019 Teoria de Colas Sipan
48/69
Modelos de una cola y un servidor
M/M/1: Un servidor con llegadas de Poisson y
tiempos de servicio exponenciales
M/G/1: Un servidor con tiempos entre
llegadas exponenciales y una distribucin
general de tiempos de servicio
M/D/1: Un servidor con tiempos entre
llegadas exponenciales y una distribucin
degenerada de tiempos de servicio
M/Ek/1: Un servidor con tiempos entre
llegadas exponenciales y una distribucin
Erlang de tiempos de servicio
-
7/31/2019 Teoria de Colas Sipan
49/69
Modelo M/M/1
1,0
)()(
)()1(
)(
1
)(
)1()1(
1
2
t
etWPetWP
nLPP
WW
LL
tqts
n
s
n
n
qs
qs
-
7/31/2019 Teoria de Colas Sipan
50/69
Modelo M/M/1: ejemplo
Un lavacar puede atender un auto cada5 minutos y la tasa media de llegadas esde 9 autos por hora
Obtenga las medidas de desempeo deacuerdo con el modelo M/M/1
Adems la probabilidad de tener 0
clientes en el sistema, la probabilidad detener una cola de ms de 3 clientes y laprobabilidad de esperar ms de 30 min.
en la cola y en el sistema
Modelo M/M/1: ejemplo
-
7/31/2019 Teoria de Colas Sipan
51/69
Modelo M/M/1: ejemplo
17.0)60/30(
22.0)60/30(
32.0)3(25.0)1(
min1525.0)(
min2033.0
1
25.2)(
3
75.012
9,12,9
)1(
)1(
1300
2
t
q
t
s
s
q
s
qs
eWP
eWP
LPP
hrsW
hrsW
clientesLclientesL
-
7/31/2019 Teoria de Colas Sipan
52/69
Modelo M/M/1: ejercicio
A un supermercado llegan en promedio 80clientes por hora que son atendidos entresus 5 cajas.
Cada caja puede atender en promedio a
un cliente cada 3 minutos Obtenga las medidas de desempeo de
acuerdo con el modelo M/M/1
Adems la probabilidad de tener 2 clientes
en el sistema, la probabilidad de tener unacola de ms de 4 clientes y la probabilidadde esperar ms de 10 min. en la cola
-
7/31/2019 Teoria de Colas Sipan
53/69
Modelo M/G/1
1
1
1
)1(2
0
222
w
q
qqs
qqs
PP
LWWW
LLL
-
7/31/2019 Teoria de Colas Sipan
54/69
Modelo M/G/1: ejemplo
Un lavacar puede atender un autocada 5 min. y la tasa media de
llegadas es de 9 autos/hora, = 2 min.
Obtenga las medidas de desempeode acuerdo con el modelo M/G/1
Adems la probabilidad de tener 0
clientes en el sistema y la probabilidadde que un cliente tenga que esperar
por el servicio
-
7/31/2019 Teoria de Colas Sipan
55/69
Modelo M/G/1: ejemplo
75.025.01
min7.8145.0
min7.13228.01
31.1)1(2
06.275.31.1
0
222
w
q
q
qs
q
qs
PP
hrsLW
hrsWW
clientesL
clientesLL
-
7/31/2019 Teoria de Colas Sipan
56/69
Modelo M/G/1: ejercicio
A un supermercado llegan en promedio 80clientes por hora que son atendidos entre sus
5 cajas.
Cada caja puede atender en promedio a uncliente cada 3 minutos. Suponga = 5 min
Obtenga las medidas de desempeo de
acuerdo con el modelo M/G/1 Adems la probabilidad de tener 0 clientes en
el sistema y la probabilidad de que un cliente
tenga que esperar por el servicio
-
7/31/2019 Teoria de Colas Sipan
57/69
Modelo M/D/1
1
1
)1(2
2
q
qqs
qss
LWWW
LWL
-
7/31/2019 Teoria de Colas Sipan
58/69
Modelo M/D/1: ejemplo
Un lavacar puede atender un autocada 5 min.
La tasa media de llegadas es de 9
autos/hora.
Obtenga las medidas de desempeo
de acuerdo con el modelo M/D/1
-
7/31/2019 Teoria de Colas Sipan
59/69
Modelo M/D/1: ejemplo
min5.7125.0
min5.1221.01
125.1)1(2
875.1
2
hrsLW
hrsWW
clientesL
clientesWL
q
q
qs
q
ss
-
7/31/2019 Teoria de Colas Sipan
60/69
Modelo M/D/1: ejercicio
A un supermercado llegan en promedio80 clientes por hora que son atendidos
entre sus 5 cajas.
Cada caja puede atender en promedio
a un cliente cada 3 minutos.
Obtenga las medidas de desempeo deacuerdo con el modelo M/D/1
-
7/31/2019 Teoria de Colas Sipan
61/69
Modelo M/Ek/1
1
1
)1(2
)1(2
q
qqs
qss
LWWW
k
kLWL
-
7/31/2019 Teoria de Colas Sipan
62/69
Modelo M/Ek/1: ejemplo
Un lavacar puede atender un auto
cada 5 min.
La tasa media de llegadas es de 9autos/hora. Suponga = 3.5 min
(aprox.)
Obtenga las medidas de desempeode acuerdo con el modelo M/Ek/1
-
7/31/2019 Teoria de Colas Sipan
63/69
Modelo M/Ek/1: ejemplo
min25.111875.0
min25.162708.01
6875.1)1(2
)1(
437.2
2
hrsL
W
hrsWW
clientesk
kL
clientesWL
q
q
qs
q
ss
-
7/31/2019 Teoria de Colas Sipan
64/69
Modelo M/Ek/1: ejercicio
A un supermercado llegan en promedio80 clientes por hora que son atendidos
entre sus 5 cajas.
Cada caja puede atender en promedioa un cliente cada 3 minutos. Suponga
k= 4
Obtenga las medidas de desempeo de
acuerdo con el modelo M/Ek/1
Modelos de un servidor: Ejercicio:
-
7/31/2019 Teoria de Colas Sipan
65/69
Modelos de un servidor: Ejercicio:
complete el cuadro ejemplo lavacar
Modelo Ls Ws Lq Wq
M/M/1
M/G/1
M/D/1
M/Ek/1
-
7/31/2019 Teoria de Colas Sipan
66/69
Modelos de varios servidores M/M/s: sservidores con llegadas de
Poisson y tiempos de servicio
exponenciales
M/D/s: sservidores con tiempos entre
llegadas exponenciales y una distribucin
degenerada de tiempos de servicio
M/Ek/s: sservidores con tiempos entre
llegadas exponenciales y una distribucin
Erlang de tiempos de servicio
M/M/s una lnea de espera
-
7/31/2019 Teoria de Colas Sipan
67/69
M/M/s, una lnea de espera
00
0
02
1
0
0
!
1,
!
,!
1
)()!1(
!!
1
P
s
s
s
PknsiP
ss
P
knsiPnPWW
LWLLP
ssL
ns
s
s
P
s
wsn
n
n
n
nqs
q
qqs
s
q
s
n
ns
-
7/31/2019 Teoria de Colas Sipan
68/69
M/M/s, una lnea de espera
)46)(3(
3
4
2
2
4
2
3
q
q
L
sSi
L
sSi
-
7/31/2019 Teoria de Colas Sipan
69/69