investigaciÓn de operaciones ii · • la espera de pacientes en la recepciónde un consultorio,...
TRANSCRIPT
MODELOS DE
FILAS DE ESPERA
Introducción a la Teoría de Colas
Ejemplos de la teoría de Colas
• La espera de los pasajeros en la sala para abordaje en unaeropuerto,
• La cantidad de inventario de producto en procesoalmacenado temporalmente en espera de ser procesado,
• La espera de pacientes en la recepción de un consultorio,
• La cola de camiones esperando a ser atendidos por personalespecializado en los muelles de cargue y descargue en ciertocentro de despachos,
• Observe que en general las esperas aquí señaladas no sondel todo deseables, siendo en todo caso ideal que la esperade los clientes sea nula y que por tanto no existan colas.
Introducción a la Teoría de ColasEl desear que los usuarios de un sistema nunca tenganque esperar, etc., es algo que generalmente se quedasólo en deseos, ya que en la practica es difícil delograr.
•Lo que si se puede hacer es minimizar la espera
•En la mayoría de sistemas empresariales la condiciónde “no cola” o “no espera” es algo que se lograría conmuy altos niveles de eficiencia, donde normalmente elcosto de lograr esa eficiencia es mayor que el costoasociado a las citadas esperas.
•Entonces, es bastante pertinente estudiar losindicadores del sistema de espera en cuestión,siempre tratando de mejorar la eficiencia global.
Definiciones
• Una cola es una línea de espera y
• La teoría de colas es una colección demodelos matemáticos que describensistemas de línea de espera particulares osistemas de colas.
• Los modelos sirven para encontrar un buenbalance entre costos del sistema y lostiempos promedio de la línea de esperapara un sistema dado.
Otros Elementos a considerar
• Proceso de Llegada: representa la forma en que la
llegada de clientes ocurre.
• Un dato importante que se maneja en el proceso
de llegada es el Tiempo entre Llegadas de
clientes, el cual puede ser determinístico
(constante), o probabilístico (asociado a cierta
distribución de probabilidad).
• También se considera si las llegadas de clientes
son individuales o por grupos (batches), en cuyo
caso se debe tener el dato del tamaño del batch.
Proceso de Llegada de Clientes
• Sea la variable aleatoria X igual al número de clientes que lleganal sistema de espera por unidad de tiempo. Si esta variablediscreta se distribuye Poisson, entonces:
= número promedio de llegadas por unidad de tiempoT = número promedio de llegadas en un intervaloespecifico de tiempo TSe cumple que el tiempo entre dos llegadas consecutivas
se distribuye exponencial con media b =1/
... , 0,1
ksi
,!k
eT)kX(P
Tk
Cuál es la probabilidad de que dos clientes lleguen en lospróximos 10 min.
Por ejemplo, suponga que es igual a 20 clientes porhora, entonces, la probabilidad de que lleguen dosclientes en los próximos 10 minutos, viene dada por:
198190
2
036011111
2
6120
2
61202
..*.
!
e*
!k
eT)X(P
*Tk
Ejemplo de proceso de llegadas
¿Cuál es la probabilidad de que lleguen tres clientes en la
próxima hora si en las tres horas anteriores llegaron nueve?
22404180
3
319
3
3193
.!
e*
!k
eT)X(P
*Tk
Se debe hacer reflexión acerca de la perdida de memoria del sistema
Proceso de Llegada de ClientesSea la variable aleatoria Y el tiempo entre llegadas. Estavariable continua tiene la siguiente función deprobabilidad:
0 t,e)tY(P T
0
t ,e
)tY(P/t
b
b
Si el número de eventos (llegadas) en un momento dado se
distribuye Poisson con una tasa media de eventos λ (eventos
por unidad de tiempo), entonces el tiempo entre dos eventos
consecutivos (tiempo entre llegadas) se distribuye
exponencial con media 1/ unidades de tiempo. (o al revés).
Otros Elementos a considerar
• Proceso de Atención: El proceso de atención serepresenta generalmente por el tiempo que tarda laatención de un cliente o Tiempo de Servicio.
• Este tiempo puede ser determinístico, es decir,cualquier cliente es atendido en un tiempoexactamente igual, o probabilístico, en cuyo casodebe definirse la distribución de probabilidad deltiempo de atención de un cliente.
• También se define si la atención se hace individual opor batches.
Otros Elementos a considerar
• Numero de Servidores: Un sistema puede tener unsolo servidor o varios en paralelo como el caso dealgunas entidades financieras.
• Puede, además existir sistemas de servidores enserie, con una común o en cambio varias colas.
Número de Servidores que el Sistema puede tener
Otros Elementos a considerarNúmero de Servidores que el Sistema puede tener
Otros Elementos a considerar
• Capacidad del Sistema: Un sistema de espera se diceque tiene capacidad infinita cuando no tienerestricciones respecto al tamaño de la cola.
• La cola se vuelve de capacidad finita por motivos derestricciones de espacio.
• Por ejemplo, la cola de ordenes de compra en unDepartamento de Compras (documentos a procesar)es de capacidad infinita, ya que físicamente es posiblealmacenar un gran número de ordenes de comprapendientes por procesar en un archivador o en unarchivo electrónico en el computador.
• Caso contrario, en un banco pueden no caber más de50 personas en fila
• Disciplina de Atención: La forma en que seseleccionan los clientes de la cola con el fin deatenderlos.
• Lo usual es que se use la disciplina FIFO o atenciónen orden de llegada.
• Otra estrategia es con, el enfoque de prioridad yotra aleatoria.
• El análisis de sistemas de espera a través de laTeoría de Colas se justifica mayormente en virtud deque los mencionados sistemas operen en formaaleatoria: la llegada de un cliente y su tiempo deatención no se conocen con anticipación, o sontotalmente probabilísticos.
Otros Elementos a considerar
Proceso de Salida de Clientes• El número de clientes atendidos por unidad de tiempo se
distribuye Poisson con media μ (promedio de clientesservidos por unidad de tiempo), si W es la variable aleatoria,se tiene que la probabilidad de que W sea igual a k, vienedada por:
,...1,0,!
)()(
ksik
eTkWP
Tk
El tiempo entre dos salidas consecutivas o el tiempo de
servicio se distribuye exponencial con parámetro
b=1/μ unidades de tiempo.
0,)( b
b
te
tZft
0,)( tetZf
t
Preguntas de Análisis
• Cuál es el tiempo promedio que un cliente tieneque esperar en la fila antes de ser atendido?
• Cuánto demora el Servidor en atender al cliente oen procesar un producto?
• Cuáles son el número promedio y el máximo declientes que esperan en la fila?
• Cuántos recursos o servidores deben emplearsepara proporcionar un servicio aceptable?
• Los clientes esperaran en una fila o en varias filas?
• Qué tanto espacio se necesita para que los clienteso productos puedan esperar?
Simbología General
Servidores
• c = Número de servidores.
• = Tasa de servicio o el número promedio declientes que se atienden por unidad de tiempo.
• Disciplina de atención a clientes (FIFO, LIFO,Prioridad Aleatoria).
• Colocación de los servidores (en Paralelo, enSerie o en Red).
• Atención individual o en grupos.
Simbología General
Clientes
• n = Número de clientes en el sistema (tanto en filacomo en los servidores)
• N = Número máximo permisible de clientes en elsistema
• = Tasa de Llegadas o Número promedio dellegadas de clientes por unidad de tiempo
• Población finita o infinita
• Llegadas individuales o en grupos
Simbología General
Cola
• Lq = Número promedio de clientes en cola
• L = Número promedio de clientes en elsistema (en cola y en servicio)
• Tamaño de la Cola (Finita o Infinita)
• Forma de Salir de la Cola.
Indicadores para Evaluar el Rendimiento de un Sistema de Colas
Otros Indicadores:
• U = utilización de los servidores o número de clientes promedio atendidos por servidor por unidad de tiempo
• r = intensidad de tráfico del sistema
Relacionados con el Tiempo
W = Tiempo promedio de permanencia de uncliente en el sistema (tanto en cola como enservicio)
Wq = Tiempo promedio de espera de un clienteen cola
Indicadores para Evaluar el Rendimiento de un Sistema de Colas
Relacionados con el Número de Clientes:
• L = Número promedio de clientes en el sistema
• Lq = Número promedio de clientes en la cola
• Pw = Probabilidad de que un cliente que llega tengaque esperar.
• Pn = Probabilidad de que existan “n” clientes en elsistema.
• Po = Probabilidad de que no hayan clientes en elsistema.
• Pd = Probabilidad de negación de servicio, oprobabilidad de que un cliente que llega no puedaentrar al sistema debido que la “cola esta llena”
Notación de Kendall-LeeEsta notación es aplicable a servidores en paralelo y
fue propuesta en 1951 por Kendall y mejorada en 1953
por el trabajo de Kendall-Lee
Notación de Kendall-Lee
La simbología A/ B /C : D /E /F, intenta caracterizarplenamente a un sistema de espera con servidores enparalelo, donde:A: Distribución probabilística de las llegadas: M (Poisson),D (determinística), Ek (Erlang), G (General).B: Distribución del tiempo de servicio: M (Exponencial), D(determinística), Ek (Erlang), G (General).C = Número de servidores en paralelo: c = 1, 2, 3, ...,infinitoD = Disciplina de servicio: FIFO, LIFO, Aleatoria, Prioridad,Disciplina General-DG.E = Número máximo admitido de clientes en todo elsistema: N, InfinitoF = Tamaño de la población de clientes: FINITO (K), Infinito
Modelos de una cola y un servidor
• M/M/1: Un servidor con llegadas de Poisson ytiempos de servicio exponenciales
• M/G/1: Un servidor con tiempos entre llegadasexponenciales y una distribución general detiempos de servicio
• M/D/1: Un servidor con tiempos entre llegadasexponenciales y una distribución degenerada detiempos de servicio
• M/Ek/1: Un servidor con tiempos entre llegadasexponenciales y una distribución Erlang de tiemposde servicio
Relaciones entre medidas de rendimientoTiempo
promedio en el sistema
Tiempo promedio de
espera
Tiempo promedio de
servicio
W Wq 1/
Número promedio de clientes en el
sistema
Número promedio de llegadas por unidad de
tiempo
Tiempo promedio en el
sistema
L W
Número promedio de clientes en la
cola
Número promedio de llegadas por unidad de
tiempo
Tiempo promedio en la
cola
Lq WqEs
Modelo M/M/1
)(Lq
2
nUtilizació de Tasa
L
n
n )(P 1
)(Wq
1W
t)(e)tW(P 1
1 n)nL(P
10 ,t
t)(
q e)tW(P 1
Ejemplo Práctico
Manolo Jiménez, está preocupado por el desempeño de su negocio untaller automotriz. Para ver qué puede hacer para resolver el problema,le pide ayuda a un experto en teoría de colas. Después de una primeratoma de tiempos se obtiene la siguiente información:
• Las llegadas al taller se producen de forma aleatoria, según unadistribución Poisson de media 4 llegadas al día (1 día = 8 horas dejornada laboral).
• La tasa de atención a clientes es 1,75 clientes por hora
• Se cuenta con un solo equipo para reparar los automóviles.
• Además del vehículo que está reparando, sólo caben 3 más en eltaller. Si llegan más, debe estacionarlos en la vía pública, con elconsiguiente deterioro en la calidad de servicio.
• Los vehículos se retiran del taller inmediatamente después de serreparados.
Ejemplo PrácticoCon estos datos, se solicita un análisis inicial de la situación.
a) ¿Qué fracción de tiempo estará el taller en funcionamiento?
b) ¿Cuál es el número promedio de clientes en espera dereparación de su vehículo?
c) ¿Cuál es el número promedio de vehículos esperando aser reparados (incluye el que está siendo atendido)?
%..
. entofuncionami en tiempo de fraccion La 5728
751
50
11420
50751751
50 22
.
)..(.
.
)(Lcola en clientes de Numero q
6860
7511114201
.
./.LL sistemael en clientes de Numero q
Ejemplo Práctico
f) ¿Cuánto tiempo transcurrirá, en promedio, desde que el
vehículo llega al taller hasta que comienza la reparación?
e) ¿Cuánto tiempo transcurrirá, por término medio, desde que
el vehículo llega al taller hasta que se acaba la reparación?
d) ¿Cuál es la probabilidad de que deban estacionarse vehículos
en la calle?
0019040
1
.4.5X10-0.0166-0.0583-0.2040-0.7143-1
P(4)-P(3)-P(2)-P(1)-P(0)4)P(x
sistemael en clientes mas o cuatro haya que de adprobabilid la Es
3-
8050751
11.
.. W sistemael en promedio Tiempo
2290.0.5
0.11428
LW cola en promedio Tiempo
q
q
Modelo M/M/1: ejemplo
• Un lavadero de carros puede atender un auto cada 5minutos y la tasa media de llegadas es de 9 autos porhora.
• Obtenga las medidas de desempeño de acuerdo con elmodelo M/M/1.
• Además la probabilidad de tener 0 clientes en elsistema, la probabilidad de tener una cola de más de 3clientes y la probabilidad de esperar más de 30 min.en la cola y en el sistema.
Modelo M/M/1: ejemplo
, , 129
clientesL 3
hr.W 3301
2501 0
0 .)(P
316403 13 .)L(P
223106030 60307501121 .ee)/W(P
).(t)(
1673480 7506030 60307501121 .e.e)/W(P
).(t)(
q
75012
9.
clientes.)(
Lq 2522
hrs.)(
Wq 250
0.25 0.75 -1 -1
a equivale También
Modelo M/M/1: ejercicio
• A un supermercado llegan en promedio 16 clientes
por hora que son atendidos por una caja.
• La 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