Lineas de Espera

Vista previa del material en texto

INVESTIGACION OPERATIVA
Tema 10 - Teoría y Aplicaciones de Líneas de Espera
Terminología y elementos básicos. Modelado de los 
procesos de llegadas y de servicio, para uno y varios 
canales, en paralelo y en serie, con longitud infinita y 
finita de la línea de espera, con fuente infinita y finita. 
Análisis de líneas de espera por cadenas de Markov. 
Modelos de decisión. Aplicaciones.
LINEAS DE ESPERA
TEORÍA
Imagine las siguientes situaciones
Clientes que esperan a ser atendidos en las cajas registradoras
de un supermercado.
Pacientes que esperan a ser atendidos en una clínica.
Aviones que esperan para despegar en un aeropuerto.
Máquinas descompuestas que esperan ser reparadas por
un técnico.
Cartas que esperan ser redactadas por una secretaria.
Programas que esperan ser procesados por una computadora.
 
Automóviles que esperan avanzar en un semáforo.
Los protagonistas principales en una 
situación de espera son:
Servidor Cliente
El proceso básico consiste en: 
Clientes que requieren un servicio y se generan por una
fuente de entrada, ingresan al sistema, formando una 
línea de espera. 
Se selecciona un cliente por medio de un criterio de 
disciplina de la atención, se proporciona el servicio y 
el cliente sale del sistema.
Se estudia la interacción entre el cliente y el 
servidor. 
Las llegadas y los tiempos de servicio de clientes 
se resumen en términos de distribuciones de 
probabilidad conocidas como:
Distribuciones de tiempos de llegada
Distribuciones de tiempo de servicios
Los clientes
pueden 
ser atendidos
Individualmente(Bancos, Supermercados)
En grupos(Restaurantes, Ascensores)
Se conocen como
 líneas de espera masivas
Sistemas en condiciones 
transitorias o de estado estable
Condiciones transitorias: Prevalecen cuando el 
comportamiento del sistema sigue dependiendo del 
tiempo. (Ej. Nacimiento)
Condiciones de estado estable: Las líneas de espera
con llegadas y salidas combinadas inician en 
condiciones transitorias y llegan gradualmente al 
estado estable después de haber transcurrido un 
tiempo suficientemente grande.
Consideramos una situación de espera en la cual el 
número de llegadas y salidas durante un intervalo 
de tiempo es controlado por:
Condición 1: la probabilidad de que un evento ocurra 
entre
los tiempos t y t+Δt depende únicamente de la 
longitud Δt.Condición 2: la probabilidad de que un evento 
ocurra durante un intervalo de tiempo muy 
pequeño Δt es positiva y menor que 1.
Condición 3: cuando mucho puede ocurrir un 
evento durante un intervalo de tiempo muy 
pequeño Δt (una salida o un arribo)
Hipótesis para los procesos de 
nacimiento y muerte
Los elementos básicos de un modelo de 
espera depende de:
a. Distribución de llegadas
b. Distribución del tiempo de servicio
c. Diseño de la instalación de servicio
d. Disciplina de servicio
e. Tamaño de la línea de espera
f. Fuente de llegadas
Notación de Kendall
Notación de Kendall
( a / b / c ) : ( d / e / f )
Es una notación que resume las características principales
de las líneas de espera en paralelo:
a: distribución de llegadas
b: distribución del tiempo de servicio (o de salidas)
c: numero de servidores en paralelo (c = 1, 2,…,inf.)
d: disciplina de servicio ( FCFS, LCFS, SIRO)
e: numero máximo admitido en el sistema
f: tamaño de la fuente de llegada 
Distribución de 
llegadas y 
servicios
Según corresponda la distribución, los símbolos a y b 
son reemplazados por los siguientes códigos:
M: distribución de llegadas o salidas de Poisson.
D: tiempos entre llegadas o de servicio constante o 
determinística.
Ek: distribución de Erlang o gamma de la distribución de 
tiempo
entre llegadas o de servicio con el parámetro k.
GI: distribución de llegadas general independientes
G: distribución de llegadas general
a y b
c Diseño de la instalación
# SERVIDORES PARALELOS
Varios servidores ofrecen e mismo servicio
# LINEAS DE ESPERA EN SERIE O L. DE ESPERA 
SUCESIVAS
Se recibe el servicio en forma sucesiva
# LINEAS DE ESPERA EN RED (paralelo y serie)
Combinación de ambos
Consiste en el mecanismos del servicio 
que pueden ser del tipo:
Líneas de espera con canales en paralelo
d Disciplina de servicio
Es el orden en el que se seleccionan los miembros de la cola 
para recibir el servicio.
# FCFS (el primero en llegar es el primero en ser atendido), 
# LCFS (el último en llegar es el primero en ser atendido)
# SIRO (atención en orden aleatorio)
Líneas de espera con prioridad
También es posible incluir:
e Tamaño de la línea de espera
# FINITAS
# INFINITAS
Solo se admite un numero limitado de clientes,
generalmente por limitaciones de espacio.
Se admite un numero ilimitado de clientes. 
En la mayoría de los casos se supone una cola infinita, 
aunque en realidad no lo sea
Numero máximo admisible de clientes que puede 
contener 
f Fuente de Entrada (llegadas)
# FUENTE 
INFINITA
# FUENTE FINITA
Cuando una llegada afecta la tasa de llegada
de nuevos clientes.
Cuando una llegada no afecta la tasa de llegada
de nuevos clientes.
Una característica es el tamaño, que el numero total 
de clientes que podría requerir el servicio (clientes 
potenciales).
Puede suponerse:
Una vez definido el modelo, mediante la notación de 
Kendall, se calculan los parámetros característicos. 
Los más generales están disponibles en la 
bibliografía.
La notación de Kendal para el modelo mas general 
seria:
(M,M,1) : (PEPS;∞; ∞)
⮚ Distribución de Llegadas: Exponencial
⮚ Distribución de Servicios: Exponencial
⮚ Canales de atención : 1
⮚ Disciplina cola: PEPS
⮚ Tamaño de la cola: Infinita
⮚ Población: Infinita
Medidas de desempeño de estado estable
Una vez calculado pn podemos calcular la medida de desempeño 
de estado estable de líneas de espera de forma directa.
⮚ Factor de transito : 
para que el sistema sea estable; si no se cumple se deberían 
agregar canales
De la definición de pn:
<= 1 s: número de 
servidores
En caso de no contar con un modelo desarrollado, se plantea el 
modelo mediante los proceso de nacimiento y muerte, 
evolucionando el sistema a través de cada estado.
La probabilidades de cada estado se calculan a partir del 
desarrollo de Cadenas de Markov de parámetro continuo.
Una vez obtenidas las probabilidades, se obtiene las medidas de
desempeño: L; Lq; W y Wq
Se puede calcular parámetros de interés como:
H: Grado de ocupación de cada canal: porcentaje de tiempo 
que el servidor esta trabajando o esta ocupado (sin trabajar), 
cuando existen estados bloqueados
Modelo de Colas resuelto mediante 
Cadenas de Markov de parámetro 
continuo
B=p.A = B
Modelo con cola infinita y un 
canal
Modelo generalizado de Poisson
1
Modelo con cola infinita y canales en paralelo
Modelo con cola finita y canales en paralelo
λ´ tasa efectiva de 
ingreso 
 para cola finita
0,
1
Si se cumplen las condiciones dadas:
El número de eventos (arribos o servicios) durante un intervalo 
de tiempo dado, sigue la distribución de Poisson:
Entonces, el intervalo de tiempo entre eventos sucesivos 
responde a la distribución exponencial:
Ej: la tasa de arribos es de λ =  = 10 clientes/hora; 
entonces tiempo entre arribos, Ta = 1/ λ = 1/10 cl/hs = 0,1 
hs/clientes = 6 min/cliente; 
es decir que ingresa al sistema 1 cliente cada 6 minutos
INVESTIGACION OPERATIVA
Tema 10 - Teoría y Aplicaciones de Líneas 
de Espera
Terminología y elementos básicos. Modelado de 
los procesos de llegadas y de servicio, para uno 
y varios canales, en paralelo y en serie, con 
longitud infinita y finita de la línea de espera, 
con fuente infinita y finita. Análisis de líneas de 
espera por cadenas de Markov. Modelos de 
decisión. Aplicaciones.
APLICACIONES EN LINEAS DE ESPERA
Las situaciones de líneas de espera en las que se 
requiere tomar decisiones surgen de una amplia 
variedad de contextos, por lo que no se puede 
presentar un solo modelo para todas las situaciones.
Las siguientes corresponden a algunas alternativas 
de decisión que puedenpresentarse de manera 
individual o combinada:
⮚ Número de servidores en un medio de servicio
⮚ Eficiencia de los servidores
⮚ Número de servicios
Las variables que intervienen en estos modelos en 
términos de teoría de colas, son: 
✓ s , número de servidores
✓ λ , tasa media de llegadas
✓ μ , tasa media de servicio por servidor ocupado
 El nivel apropiado de servicio en un sistema de colas 
depende de dos factores:
1.Costo esperado en el se incurre al dar el servicio
2.La magnitud (Costo esperado) de la espera para 
ese servicio
Costo esperado del 
servicio como una 
función del nivel de 
servicio
Costo 
Esperado
Nivel de 
servicio
Costo esperado de 
esperar como una 
función del nivel de 
servicio
Costo 
total
APLICACIONES EN LINEAS DE ESPERA
Se crean situaciones conflictivas:
El objetivo de reducir los costos de servicio, 
Recomienda un nivel mínimo de servicio
Los largos tiempos de espera, son indeseables (
costosos),
 
Recomienda un nivel alto de servicio
El problema consiste en obtener el mínimo de la 
curva, que de el mejor balance entre el demora
promedio en ser atendido y el costo de 
proporcionar el servicio.
APLICACIONES EN LINEAS DE ESPERA
Por lo tanto se debe estimar el 
COSTO ESPERADO DE ESPERAR
Debe considerar los desembolsos o sus equivalentes en
impacto a largo plazo, medido por un costo 
relacionado. 
Ejemplos: 
• Pérdida de ingresos por ventas, porque los clientes abandonan 
la cola, por superar el tiempo que están dispuestos a esperar.
• Operarios que reciben un salario, por esperar a que se arregle 
una herramienta por parte de otro sector de la planta
En algunos casos no puede traducirse a Costo de espera, pero 
puede relacionarse con: 
“el tiempo admisible que el cliente estaría dispuesto a esperar 
antes de abandonar el sistema”
APLICACIONES EN LINEAS DE ESPERA
Existen diversas situaciones:
1. Los clientes son externos a la organización
 Es necesario diferenciar si el servicio se está 
proporcionando
 para obtener:
• UTILIDAD
• SIN FINES DE LUCRO
En el caso de pérdidas de utilidad, puede ocurrir, 
que sea:
• DE INMEDIATO
• EN EL FUTURO
Para estimar los costos asociados, es necesario 
asumir criterios, como la distribución tolerable de
probabilidad de los tiempos de espera.
APLICACIONES EN LINEAS DE ESPERA
2. Los clientes son internos de la 
organización que proporciona el servicio
Pueden ser: 
• MÁQUINAS 
• EMPLEADOS
En estos casos se puede identificar directamente 
algunos o todas los costos vinculados con la 
ociosidad de los clientes.
Por ejemplo, consideremos que los clientes son 
los operadores de las máquinas. Lo que se 
estaría perdiendo es la contribución a la 
ganancia que el operador hubiera hecho a la 
empresa.
Seria también necesario considerar el valor de 
todos los recursos económicos que estarían 
ociosos como consecuencia de esta espera.
APLICACIONES EN LINEAS DE ESPERA
El objetivo seria entonces:
“Determinar el nivel de servicio que minimice el total del 
costo esperado del servicio y el costo esperado para la 
espera de ese servicio”
Minimizar E (CT)= E (CS)+E (CE)
Donde : 
E (CS), costo esperado de servicio
E (CE), costo esperado de esperar
Costo E del
servicio
E (CS)
Costo 
Espera
do
Nivel de 
servicio
E (CT)= E (CS)+E (CE
)
Costo E de 
esperar
E (CE)
Mínim
o
APLICACIONES EN LINEAS DE ESPERA
1. En el caso de que los clientes forman colas internas
de la organización, el costo de la espera puede ser 
La utilidad perdida debido a la productividad perdida
La tasa a la cual se pierde el rendimiento productivo, puede ser 
proporcional al número de clientes en el sistema de colas.
La tasa actual a la cual se está incurriendo en los costos de 
espera es: 
N: número de clientes en el sistema
Por lo tanto la forma de la función del 
costo de espera es g (N)
g (N)
Costo de la
espera por 
unidad de 
tiempo
Número de clientes en el 
sistema
1 2 3
E (CE) = E {g (N)
}
N, variable 
aleatoria 
E (CE) = Σ g (n) 
Pn
APLICACIONES EN LINEAS DE ESPERA
Cuando g(N) es una función lineal, la tasa de espera es 
proporcional a N
g(N) = Cw N
Cw , es el costo de espera por unidad de tiempo de cada cliente
En este caso
E (CE) = Cw Σ n Pn = Cw L
Ejemplo: Una empresa tiene 10 máquinas, pero solo 8 operarios 
disponibles, por lo que se cuenta con 2 máquinas en reserva. 
Por cada cliente adicional (maquina en reparación), la utilidad 
perdida es de 100$/maq. En la actualidad solo dispone de un 
operario para arreglarlas, pero desea determinar si debería 
contratar otro operario. Dispone de la tasa de rotura λ = 1/20
(una maquina cada 20 días), tasa de reparación µ= ½ (una 
maquina cada 2 días).
La función de costo de espera sería:
g(n) = 0 para n= 0,1,2
g(n) = 100 (n-2) para n= 3,4,…10
Se debe calcular E(CE) para s = 1; 2; es decir cantidad de 
operarios que reparan
APLICACIONES EN LINEAS DE ESPERA
APLICACIONES EN LINEAS DE ESPERA
Por lo tanto a la empresa le conviene contratar otro 
operario para reparar las máquinas
2. En el caso que los clientes del sistema de colas 
sean externos a la organización que brinda el 
servicio, por ejemplo:
• Social
• Transporte 
• Comercial
En el caso de los servicios sociales, el costo primario de espera 
puede estar en la forma de un costo social
El costo de espera en el que se esta 
Incurriendo es: 
W : tiempo de espera en el sistema
 para los clientes
 
Costo de 
la espera 
por cliente
Tiempo de espera en el 
sistema
 h (W)
E {h(w)} = ∫ h(w) fw (w) dw
fw (w) es la función de densidad 
de probabilidades de W
E (CE) = λE {h(w)} = λ ∫ h(w) fw
(w) dw
APLICACIONES EN LINEAS DE ESPERA
Cuando h(W) es una función lineal
h(W) = Cw W
Cw es el costo de espera por unidad de tiempo de cada cliente
En este caso
E (CE) = λ E (CwW) = Cw (λ W) = Cw L
Igual que en el caso anterior. Por lo tanto el costo esperado de 
la espera en el que se incurre en el sistema de colas, es 
proporcional al tiempo total en el sistema, (no importa si se 
usa la forma de g(N) o h(W)).
Ejemplo: Una empresa tiene un costo por reparador de 70 $/día
y el costo de esperar es de 24 $/hora , por lo tanto el costo 
esperado de espera por hora sería:
E (CE) = 24 L
La tasa de rotura es de λ = 5 reparaciones/hora y μ = 3 
reparaciones/hora.
APLICACIONES EN LINEAS DE ESPERA
APLICACIONES EN LINEAS DE ESPERA
Primero debemos verificar ρ ≤ 1, por lo tanto 
debemos poner al menos 2 operarios para la 
reparación.
El costo total esperado será:
E (CT) = s Cs + E (CE)
E (CT) = 70 s + 24 L
Se debe calcular L para cada número de servidores y 
el óptimo es el que corresponde al costo total 
esperado mínimo 
Por lo tanto a la empresa le conviene contratar 3 
reparadores para brindar el servicio.
Mínimo
Ejemplo
El numero promedio de camiones en el 
sistema es de 6 y en la cola de 5,14
18 *0,2 =
3,6
El costo con la ampliación es de 21096 y sin 
la ampliación es de 24192, por lo tanto si 
conviene hacerla