LINES

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
Una persona que brinda el servicio y personas que esperan ser atendidas, siempre hay un costo asociado tanto para la persona que brinda el servicio y los clientes, ya que el tiempo de los clientes es importante, no pueden esperar mucho tiempo, hay un tiempo que están dispuestos a esperar
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
Con que distribución llegan los clientes? Con cual se los atiende?
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) Consideramos que cambia el estado del sistema cuando llega alguien o se va alguien
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
Para definir el tipo de líneas de espera
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:
Dependiendo de estos parámetros los modelos difieren
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. Mas comun
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
Ej cajas de supermercado, si hay 3 cajas c=3
LINEAS DE ESPERA EN SERIE O L. DE ESPERA 
SUCESIVAS
Se recibe el servicio en forma sucesiva, ej mantenimiento de
Auto pasa por varias estaciones
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), 
Cola normal
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., ej una estación de servicio que tiene espacio para 5 autos
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, ej en un banco, puede crecer 
infinitamente
Numero máximo admisible de clientes que puede contener la línea de espera
f
Fuente de Entrada (llegadas)
FUENTE INFINITA
 FUENTE FINITA
Cuando una llegada afecta la tasa de llegada
de nuevos clientes. Ej en un sistema de maquinas para 
Arreglar, no puedo arreglar todas
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, es decir números de servidores hasta que sea menor a 1, para poder llegar al estado estable
De la definición de pn:
<= 1
s: número de servidores
Velocidad de llegada
Velocidad de salida
n : Clientes en el sistema
pn: Probabilididad qie haya n clientes en el sistema
Lq=Lc
Ls=L
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 intervalode 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 pueden presentarse 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:
Costo esperado en el se incurre al dar el servicio
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:				
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
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 
Esperado
Nivel de servicio
E (CT)= E (CS)+E (CE)
Costo E de esperar
E (CE)
Mínimo
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 , o sea el optimo es s=2 , que tiene un costo menor
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 camionesen 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 $21.096
	 sin la ampliación es de $24192
	 por lo tanto si conviene hacerla
1
2
Clientes que llegan Clientes que salen
:
c
Sistema
x x x x x x x x x
Instalación
de servicio
Cola o línea
de espera
å
å
¥
+
=
¥
=
-
=
=
1
0
)
(
c
n
n
q
n
n
s
p
c
n
L
np
L
m
l
r
s
=
(
)
,...
2
,
1
,
0
;
!
)
(
=
=
-
n
n
e
t
t
p
t
n
n
a
a
0
t
;
)
(
³
-
=
t
e
t
f
a
a
N = ng(n)Png(n)PnPng(n)Pn
100,2146-$ 0,3680 0
200,2146-$ 0,3680 0
300,1931-$ 0,1656 0
41000,154515,45$ 0,0662 6,62
52000,108121,62$ 0,0232 4,64
63000,064919,47$ 0,0070 2,1
74000,032412,96$ 0,0017 0,68
85000,01306,50$ 0,0003 0,15
96000,00392,34$ 0,0001 0,06
107000,00080,56$ - 0
118000,00010,08$ 0
E(CE)78,98$ E(CE)14,25$ 
s=1s=2
Hoja1
	
							s=1		s=2
					N = n	g(n)	Pn	g(n)Pn	Pn	g(n)Pn
					1	0	0.2146	$ - 0	0.3680	0
					2	0	0.2146	$ - 0	0.3680	0
					3	0	0.1931	$ - 0	0.1656	0
					4	100	0.1545	$ 15.45	0.0662	6.62
					5	200	0.1081	$ 21.62	0.0232	4.64
					6	300	0.0649	$ 19.47	0.0070	2.1
					7	400	0.0324	$ 12.96	0.0017	0.68
					8	500	0.0130	$ 6.50	0.0003	0.15
					9	600	0.0039	$ 2.34	0.0001	0.06
					10	700	0.0008	$ 0.56	- 0	0
					11	800	0.0001	$ 0.08		0
							E(CE)	$ 78.98	E(CE)	$ 14.25
Hoja2
	
Hoja3
	
ss CsL24 LE (CE)CTE
21405,45130,8270,8410,8Minimo
32102,0448,96258,96468,96
≥42801,7341,52321,52531,52
Hoja1
	
							s=1		s=2
					N = n	g(n)	Pn	g(n)Pn	Pn	g(n)Pn
					1	0	0.2146	$ - 0	0.3680	0
					2	0	0.2146	$ - 0	0.3680	0
					3	0	0.1931	$ - 0	0.1656	0
					4	100	0.1545	$ 15.45	0.0662	6.62
					5	200	0.1081	$ 21.62	0.0232	4.64
					6	300	0.0649	$ 19.47	0.0070	2.1
					7	400	0.0324	$ 12.96	0.0017	0.68
					8	500	0.0130	$ 6.50	0.0003	0.15
					9	600	0.0039	$ 2.34	0.0001	0.06
					10	700	0.0008	$ 0.56	- 0	0
					11	800	0.0001	$ 0.08		0
							E(CE)	$ 78.98	E(CE)	$ 14.25
					s	s Cs	L	24 L	E (CE)	CTE
					2	140	5.45	130.8	270.8	410.8	Minimo
					3	210	2.04	48.96	258.96	468.96
					≥4	280	1.73	41.52	321.52	531.52
Hoja2
	
Hoja3