anal is is line as espera
TRANSCRIPT
Teoria de colas
Mgp Ing Grover Sánchez Eid 1
Análisis deLíneas de espera
Contenido
1 Definiciones y aplicaciones del Análisis de Líneas de Espera.
2 Elementos y Sistemas de Líneas de Espera3 Procesos estocásticos en L.E.4 Modelos Analíticos5 Modelos de Simulación6 Costos en líneas de espera
Teoria de colas
Mgp Ing Grover Sánchez Eid 2
DefinicionesLínea de espera:Definición básica que identifica un proceso de flujo donde eventualmente puede existir retardo.
Teoría de colas:La disciplina fundamental que estudia el fenómeno de líneas de espera a través de modelos matemáticos.
Sistemas con retardo:Ámbito global de aplicación de la teoría de colas para el análisis de líneas de espera.
• Son frecuentes en nuestra vida cotidiana:– Los clientes en un Banco, en un Restaurante, al
matricular en la Universidad.– Los automóviles en una Gasolinera, los buses
en una Terminal, aviones para aterrizar en un Aeropuerto.
– Maquinas esperando reparación en un Taller, documentos para impresión en una Red, llamadas telefónicas esperando línea de Comunicación.
– Pacientes esperando cama para Hospitalización, automóviles esperando Parqueo.
Las colas…, líneas de espera
Teoria de colas
Mgp Ing Grover Sánchez Eid 3
• En general, a nadie le gusta esperar, cuando la paciencia llega a su límite, la gente se va a otro lugar.
• El tiempo tiene un costo para el cliente y esperar en demasía es perjudicial.
• Sin embargo, un servicio muy rápido tendría un costo muy elevado para el administrador.
• Es necesario encontrar un balance adecuado entre los objetivos del Cliente y del Sistema.
Las colas…, líneas de espera
Teoría de colas• Una cola es una línea de espera, un flujo de una red
donde existe retardo en algún punto.
• La teoría de colas es un conjunto de modelos matemáticos que describen sistemas de líneas de espera particulares.
• Se basa en el análisis de un proceso que considera parámetros con variables estocásticas.
• El objetivo es encontrar el estado estable del sistema y determinar una capacidad de servicio apropiada.
Teoria de colas
Mgp Ing Grover Sánchez Eid 4
Teoría de colas• Existen muchos sistemas de colas distintos, y no todos
pueden modelarse apropiadamente.
• Algunos modelos son muy especiales o resultan muy complejos de analizar.
• Otros sistemas se ajustan a modelos estándar más generales y permiten encontrar soluciones analíticas.
• La mayor parte se pueden tratar mejor a través de la simulación.
• Los procesos determinísticos se manejan también con la Teoría de redes.
Sistema de LE: modelo básico
• Un sistema de colas puede dividirse en tres componentes principales:
– Las unidades que llegan al sistema– La cola o línea de espera donde se
forman las unidades.– La instalación del servicio constituida
por servidores.
Teoria de colas
Mgp Ing Grover Sánchez Eid 5
FRONTERA DEL SISTEMA
UNIDAD DE SERVICIO
UNIDADES QUELLEGAN
ESQUEMA DEL SISTEMA BASICO DE LINEAS DE ESPERA
UNIDADES QUESALEN
COLA
Sistema de LE: modelo básico• Los clientes o llegadas pueden ser:
– Personas– Automóviles– Máquinas que requieren reparación– Documentos– Otros tipos de artículos
• Los clientes o llegadas vienen en forma individual para recibir el servicio.
Unidades = u = k (número)
Teoria de colas
Mgp Ing Grover Sánchez Eid 6
Sistemas de LE: modelo básico
• Cuando el cliente llega y no hay nadie en la cola, pasa de una vez a recibir el servicio.
• Si no, se une a la cola.• La cola no incluye a quien está recibiendo
el servicio.
Sistema de LE: modelo básico• Los servidores o instalación del
servicio puede ser:– Personas– Equipos, Maquinas o Instalaciones– Una combinación
• Los servidores se consideran en forma individual y se especifica el número.
SERVIDORES = s = Número
Teoria de colas
Mgp Ing Grover Sánchez Eid 7
Estructuras típicas de sistemas de LE: una línea, un servidor
Llegadas
Sistema de colas
Cola ServidorSalidas
Estructuras típicas de sistemas de LE: una línea, múltiples servidores
Llegadas
Sistema de colas
Cola
Servidor Salidas
Servidor
Servidor
Salidas
Salidas
Teoria de colas
Mgp Ing Grover Sánchez Eid 8
Estructuras típicas de colas: varias líneas, múltiples servidores
Llegadas
Sistema de colas
Cola Servidor Salidas
Servidor
Servidor
Salidas
Salidas
Cola
Cola
Estructuras típicas de colas: una línea, servidores secuenciales
LlegadasSistema de colas
Cola
Servidor
Salidas
Cola
Servidor
Teoria de colas
Mgp Ing Grover Sánchez Eid 9
Proceso de LE: Las llegadas• Se considera que las llegadas son un proceso
aleatorio, vinculada a una función de probabilidad.• En general se considera un proceso independiente, es
decir que la ultima llegada no influye a la probabilidad de la siguiente llegada. Proceso Markoviano.
• El tiempo que transcurre entre dos llegadas sucesivas en el sistema de colas se llama tiempo entre llegadas.
P(t) = Probabilidad que el tiempo sea t• El tiempo entre llegadas tiende a ser muy variable.• El número esperado de llegadas por unidad de tiempo
se llama tasa media de llegadas (λ): LambdaP(k) = Probabilidad que existan k llegadas
Proceso de LE: Las llegadas
• El tiempo esperado entre llegadas es 1/λ• Por ejemplo, si la tasa media de llegadas
es λ = 20 clientes por hora• Entonces el tiempo esperado entre
llegadas es 1/λ = 1/20 = 0.05 horas ócada 3 minutos.
Teoria de colas
Mgp Ing Grover Sánchez Eid 10
Proceso de LE: Las llegadas• Es necesario estimar la distribución de
probabilidad de los tiempos entre llegadas.• Generalmente se supone una distribución
exponencial.• Esto depende del comportamiento de las
llegadas.• Se realiza una medición de llegadas por tiempo
o de tiempo entre llegadas.• Se aproxima a una función de distribución
teórica y se realizan las pruebas estadísticas.
Proceso de LE: Las llegadas –Distribución exponencial
• La forma algebraica de la distribución exponencial es:
• Donde t representa una cantidad expresada en unidades de tiempo (horas, minutos, etc.), λ es la media de llegadas en unidades/tiempo.
t
etllegadasdetiempoPλ−
−=≤ 1)(
Teoria de colas
Mgp Ing Grover Sánchez Eid 11
Proceso de LE: Las llegadas –Distribución exponencial
Media Tiempo0
P(t)La distribución exponencial supone una mayor probabilidad para tiempos entre llegadas pequeños
Proceso de LE: Las llegadas -Distribución de Poisson
• Es una distribución discreta empleada con mucha frecuencia para describir el patrón de las llegadas a un sistema de colas
• Para tasas medias de llegadas pequeñas es asimétrica y se hace más simétrica y se aproxima a la binomial para tasas de llegadas altas
Teoria de colas
Mgp Ing Grover Sánchez Eid 12
Proceso de LE: Las llegadas -Distribución de Poisson
• Su forma algebraica es:
• Donde:P(k) : probabilidad de k llegadas por unidad de tiempoλ : tasa media de llegadas
( )!
keP kk
λλ −
=
Proceso de LE: Las llegadas -Distribución de Poisson
Llegadas por unidad de tiempo0
P
Teoria de colas
Mgp Ing Grover Sánchez Eid 13
Proceso de LE: El servicio
• El servicio puede ser brindado por un servidor o por servidores múltiples.
• El tiempo de servicio varía de cliente a cliente.
• Se considera el tiempo promedio para un servicio estándar o para un periodo estable.
• El tiempo esperado de servicio depende de la tasa media de servicio (μ): mu
Proceso de LE: El servicio
• El tiempo esperado de servicio equivale a 1/μ
• Por ejemplo, si la tasa media de servicio es de 25 clientes por hora
• Entonces el tiempo esperado de servicio es 1/μ = 1/25 = 0.04 horas, ó 2.4 minutos por servicio
Teoria de colas
Mgp Ing Grover Sánchez Eid 14
Proceso de LE: El servicio
• Es necesario seleccionar una distribución de probabilidad para los tiempos de servicio
• Hay dos distribuciones que representarían puntos extremos:–La distribución exponencial
(σ=media)–Tiempos de servicio constantes
(σ=0)
Proceso de LE: El servicio
• Una distribución intermedia es la distribución Erlang
• Esta distribución posee un parámetro de forma k que determina su desviación estándar:
mediak
1=σ
Teoria de colas
Mgp Ing Grover Sánchez Eid 15
Proceso de LE: El servicio
• Si k = 1, entonces la distribución Erlang es igual a la exponencial
• Si k = ∞, entonces la distribución Erlang es igual a la distribución degenerada con tiempos constantes
• La forma de la distribución Erlangvaría de acuerdo con k
Proceso de LE: El servicio
Media Tiempo0
P(t)k = ∞
k = 1 k = 2
k = 8
Teoria de colas
Mgp Ing Grover Sánchez Eid 16
Distribución Erlang
Erlang, cualquier k1/4 mediaErlang, k = 16
Erlang, k = 81/2 mediaErlang, k = 4
Erlang, k = 2
mediaErlang, k = 10Constante
Desviación estándarDistribución
media2/1
media8/1
mediak/1
Proceso de LE: Disciplina de cola• Las unidades que llegan van a la instalación del servicio
de acuerdo con la disciplina de la cola (D)• Generalmente es Primero en Entrar, Primero en Salir
PEPS• Pero pueden haber otras reglas o colas con prioridades:
– UEPS: Ultimo en entrar, primero en salir– Privilegios: Embarazadas, ancianos, clientes
frecuentes, documentos importantes, productos perecederos.
– Tandas: Grupos específicos de unidades.– Aleatorio: Cualquiera de la fila
Teoria de colas
Mgp Ing Grover Sánchez Eid 17
Proceso de LE: La cola
• El número de clientes en la cola es el número de clientes que esperan el servicio = Lq
• El número de clientes en el sistema es el número de clientes que esperan en la cola más el número de clientes que actualmente reciben el servicio
Ls = Lq + s
Proceso de LE: La fuente• El número potencial de clientes o fuente de las
llegadas es fundamental para asumir la influencia o independencia en la probabilidad de las llegadas.
• La fuente puede considerarse finita o infinita, según la influencia probabilística a las llegadas.
–INFINITA: Clientes en un banco.–FINITA: Maquinas para mantenimiento.
• El número estadístico límite asumido en general es 30 unidades.
Teoria de colas
Mgp Ing Grover Sánchez Eid 18
Proceso de LE: La cola• La capacidad de la cola es el número máximo de clientes que
pueden estar en la cola = K
• Generalmente se supone que la cola puede ser infinita
• Aunque también la cola puede ser finita, cuando físicamente no se puede soportar nuevas llegadas.
• En el análisis estadístico influye por la consideración de probabilidad de abandono en colas muy largas.
• Capacidad infinita = probabilidad de abandono cero
• La capacidad de cola esta determinada por factores físicos que influyen también en los costos del sistema, para evitar los abandonos
Notación General en LE
-Paralelo-Secuencial
- PEPS (FIFO)
- UEPS (LIFO)
- Aleatorio- Tandas- Jerarquias- Otros
- Finita- Infinita
N < 30 Finito
N => 30 Infinito
s = 1 servidors > 1servidores
múltiples
-Exponen-cial
-Erlang-Constante-General
- Poisson-Exponen-cial
CDKNsμ ó 1/μλ ó 1/λ
Sistema de flujo en la
cola
Disciplina de
atención al cliente
Capacidad de la cola
Tamaño de la
población
Numero de servidores
Función de probabili-dad de los servicios
Función de probabili-dad de las llegadas
Teoria de colas
Mgp Ing Grover Sánchez Eid 19
Modelos de LE: Nomenclatura para distintos modelos
Notación de Kendall: A/B/s• A: Distribución de tiempos entre llegadas• B: Distribución de tiempos de servicio
– M: distribución exponencial– D: distribución degenerada– Ek: distribución Erlang
• s: Número de servidores
Estado del sistema de LE
• En principio el sistema está en un estado inicial.
• Se supone que el sistema de colas llega a una condición de estado estable (nivel normal de operación)
• Existen otras condiciones anormales (horas pico, etc.)
• Lo que interesa es el estado estable
Teoria de colas
Mgp Ing Grover Sánchez Eid 20
Desempeño del sistema de LE
• Para evaluar el desempeño se busca conocer dos factores principales:
1. El número de clientes que esperan en la cola y en el sistema, Lq y Ls
2. El tiempo que los clientes esperan en la cola y en el sistema, Wq y Ws
Medidas del desempeño del sistema de LE
1. Número esperado de clientes en el sistema Ls
2. Número esperado de clientes en la cola Lq
3. Tiempo esperado de espera en la cola Wq
4. Tiempo esperado de espera en el sistema Ws
Teoria de colas
Mgp Ing Grover Sánchez Eid 21
Medidas del desempeño del sistema de LE: fórmulas generales
μλ
λλ
μ
+=
==
+=
qs
ss
qs
LL
WLWL
WW 1
Medidas del desempeño del sistema de LE: ejemplo
• Suponga un lavado de autos al cual llegan en promedio 45 vehículos por hora
• Se tiene capacidad para atender en promedio a 60 clientes por hora
• Se sabe que los clientes esperan en promedio 3 minutos en la cola
Teoria de colas
Mgp Ing Grover Sánchez Eid 22
Medidas del desempeño del sistema de LE: ejemplo
• La tasa media de llegadas λ es 45 clientes por hora o 45/60 = 0.75clientes por minuto
• La tasa media de servicio μ es 60 clientes por hora o 60/60 = 1 cliente por minuto
• Wq = 3 minutos
Medidas del desempeño del sistema de LE: ejemplo
clientesWLclientesWL
WW
W
ss
qs
q
25.2375.03475.0
min41131
min3
=×===×==
=+=+=
=
λλ
μ
Teoria de colas
Mgp Ing Grover Sánchez Eid 23
Medidas del desempeño del sistema de colas: ejercicio
• Suponga un restaurant de comidas rápidas al cual llegan en promedio 100 clientes por hora
• Se tiene capacidad para atender en promedio a 150 clientes por hora
• Se sabe que los clientes esperan en promedio 2 minutos en la cola
• Calcule las medidas de desempeño del sistema.
Probabilidades como medidas del desempeño
• Beneficios:–Permiten evaluar escenarios–Permite establecer metas
• Notación:– Pn : probabilidad de tener n clientes
en el sistema– P(Ws ≤ t) : probabilidad de que un
cliente no espere en el sistema más de t horas
Teoria de colas
Mgp Ing Grover Sánchez Eid 24
Factor de utilización del sistema• Dada la tasa media de llegadas λ y la tasa
media de servicio μ, se define el factor de utilización del sistema ρ: rho.
• Generalmente se requiere que ρ < 1• Un factor ρ ≥ 1 implicaría la formación constante
de cola, con tendencia siempre creciente.• Su fórmula, con un servidor y con s servidores,
respectivamente, es:
μλρ
μλρ
s==
Factor de utilización del sistema -ejemplo
• Con base en los datos del ejemplo anterior, λ = 0.75, μ = 1
• El factor de utilización del sistema si se 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%
Teoria de colas
Mgp Ing Grover Sánchez Eid 25
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 distribución general de tiempos de servicio
• M/D/1: Un servidor con tiempos entre llegadas exponenciales y una distribución degenerada de tiempos de servicio
• M/Ek/1: Un servidor con tiempos entre llegadas exponenciales y una distribución Erlang de tiempos de servicio
Modelo M/M/12
1
(1 ) (1 )
( )1
( )(1 ) ( )
( ) ( )
0, 1
s q
s q
n nn s
t ts q
L L
W W
P P L n
P W t e P W t e
t
μ ρ μ ρ
λ λμ λ μ μ λ
λμ λ μ μ λρ ρ ρ
ρ
ρ
+
− − − −
= =− −
= =− −
= − > =
> = > =
≥ <
Teoria de colas
Mgp Ing Grover Sánchez Eid 26
Modelo M/M/1: ejemplo• Un lavado de autos puede atender uno cada 5
minutos y la tasa media de llegadas es de 9autos por hora
• Obtenga las medidas de desempeño de acuerdo con el modelo M/M/1
• Además la probabilidad de tener 0 clientes en el sistema, la probabilidad de tener una cola de más de 3 clientes y la probabilidad de esperar más de 30 min. en la cola y en el sistema
Modelo M/M/1: ejemplo
17.0)60/30(
22.0)60/30(
32.0)3(25.0)1(
min1525.0)(
min2033.01
25.2)(
3
75.0129,12,9
)1(
)1(
1300
2
==>
==>
==>=−=
==−
=
==−
=
=−
==−
=
====
−−
−−
+
tq
ts
s
q
s
qs
eWP
eWP
LPP
hrsW
hrsW
clientesLclientesL
ρμ
ρμ
ρ
ρρρλμμ
λλμ
λμμλ
μλλ
ρμλ
Teoria de colas
Mgp Ing Grover Sánchez Eid 27
Modelo M/M/1: ejercicio• A un supermercado llegan en promedio 80
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 desempeño de acuerdo con el modelo M/M/1
• Además la probabilidad de tener 2 clientes en el sistema, la probabilidad de tener una cola de más de 4 clientes y la probabilidad de esperar más de 10 min. en la cola
Modelo M/G/1
11
1)1(2
0
222
<=−=
=+=
−+
=+=
ρρρλμ
ρρσλρ
w
qqqs
qqs
PP
LWWW
LLL
Teoria de colas
Mgp Ing Grover Sánchez Eid 28
Modelo M/G/1: ejemplo• Un lavador de autos puede atender un auto
cada 5 min. y la tasa media de llegadas es de 9 autos/hora, σ = 2 min.
• Obtenga las medidas de desempeño de acuerdo con el modelo M/G/1
• Además la probabilidad de tener 0 clientes en el sistema y la probabilidad de que un cliente tenga que esperar por el servicio
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
qs
q
qs
PP
hrsL
W
hrsWW
clientesL
clientesLL
Teoria de colas
Mgp Ing Grover Sánchez Eid 29
Modelo M/G/1: ejercicio• A un supermercado llegan en promedio 80
clientes por hora que son atendidos entre sus 5 cajas.
• Cada caja puede atender en promedio a un cliente cada 3 minutos. Suponga σ = 5 min
• Obtenga las medidas de desempeño de acuerdo con el modelo M/G/1
• Además la probabilidad de tener 0 clientes en el sistema y la probabilidad de que un clientetenga que esperar por el servicio
Modelo M/D/1
1
1)1(2
2
<
=+=
−==
ρλμ
ρρλ
qqqs
qss
LWWW
LWL
Teoria de colas
Mgp Ing Grover Sánchez Eid 30
Modelo M/D/1: ejemplo• Un lavado de autos puede atender uno
cada 5 min.• La tasa media de llegadas es de 9
autos/hora.• Obtenga las medidas de desempeño
de acuerdo con el modelo M/D/1
Modelo M/D/1: ejemplo
min5.7125.0
min5.1221.01
125.1)1(2
875.12
===
==+=
=−
=
==
hrsL
W
hrsWW
clientesL
clientesWL
qs
q
ss
λ
μ
ρρ
λ
Teoria de colas
Mgp Ing Grover Sánchez Eid 31
Modelo M/D/1: ejercicio• A un supermercado llegan en promedio
80 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 desempeño de acuerdo con el modelo M/D/1
Modelo M/Ek/12 ( 1)
2 (1 )1
11
s s q
qs q q
kL W Lk
LW W W
mediak
ρλρ
μ λρ
σ
+= =
−
= + =
<
=
Teoria de colas
Mgp Ing Grover Sánchez Eid 32
Modelo M/Ek/1: ejemplo
• Un lavado de autos 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 desempeño de acuerdo con el modelo M/Ek/1
Modelo M/Ek/1: ejemplo
min25.111875.0
min25.162708.01
6875.1)1(2)1(
437.22
===
==+=
=−+
=
==
hrsL
W
hrsWW
clientesk
kL
clientesWL
qs
q
ss
λ
μ
ρρ
λ
Teoria de colas
Mgp Ing Grover Sánchez Eid 33
Modelo M/Ek/1: ejercicio• A un supermercado llegan en promedio
80 clientes por hora que son atendidos entre sus 5 cajas.
• Cada caja puede atender en promedio a un cliente cada 3 minutos. Suponga k= 4
• Obtenga las medidas de desempeño de acuerdo con el modelo M/Ek/1
Modelos de un servidor: Ejercicio: complete el cuadro ejemplo y ejercicio
M/Ek/1
M/D/1
M/G/1
M/M/1
WqLqWsLsModelo
Teoria de colas
Mgp Ing Grover Sánchez Eid 34
Modelos de varios servidores• M/M/s: s servidores con llegadas Poisson
y tiempos de servicio exponenciales• M/D/s: s servidores con tiempos entre
llegadas exponenciales y una distribución degenerada de tiempos de servicio
• M/Ek/s: s servidores con tiempos entre llegadas exponenciales y una distribución Erlang de tiempos de servicio
M/M/s, una línea de espera
00
0
02
1
0
0
!1,
!
,!
1)()!1(
!!
1
Ps
ss
PknsiPss
P
knsiPn
PWW
LWLLP
ssL
nss
s
P
swsn
n
n
n
nqs
qqqs
s
q
s
n
ns
⎟⎟⎠
⎞⎜⎜⎝
⎛−
=>=
≤=+=
=+=−−
=
+⎟⎟⎠
⎞⎜⎜⎝
⎛−
=
−
−
=∑
λμμρρ
ρμ
λμλ
λμλμρ
ρλμ
μρ
Teoria de colas
Mgp Ing Grover Sánchez Eid 35
M/M/s, una línea de espera
)46)(3(
34
2
2
4
2
3
ρρρρ
ρρ
+−−=
=−
=
=
q
q
L
sSi
L
sSi
Comparación resultados M/M/1 con M/M/2 Lavado de autos
0.01000.2250.02670.6M/M/1dos líneas
0.00270.12270.01940.8727M/M/2
0.05002.250.06673M/M/1
WqLqWsLsModelo
Tasa unitaria μ = 60 u/horaTasa global λ = 45 u/hora
Teoria de colas
Mgp Ing Grover Sánchez Eid 36
Costos de un sistema de LE
1. Costo de espera: Es el costo para el cliente al esperar
– Representa el costo de oportunidad del tiempo perdido.
– Un sistema con un bajo costo de espera es una fuente importante de competitividad.
– El Costo esta dado por:PARA UNA UNIDAD = Ce x WqPARA LOS QUE ESPERAN = λ x Ce x Wq
Costos de un sistema de LE
2. Costo de servicio: Es el costo de operación del servicio brindado
– Es más fácil de estimar, dado que es manejado por el administrador.
– El objetivo de un sistema de colas es encontrar el sistema del costo total mínimo
– El costo del servicio es directamente proporcional al número de servidores.
– Generalmente lineal.CTs = Cs x s