Alumna: Karen García Aquino.

4to. Semestre

Investigación de operaciones.

Carrera: Ing. Gestión Empresarial.

Profesor: Ángel Solano González.

UNIDAD 4

Líneas de espera.

4. Líneas de espera.

Una línea de espera es el efecto resultante en un sistema cuando la demanda de un servicio supera la capacidad de proporcionar dicho servicio. Este sistema está formado por un conjunto de entidades en paralelo que proporcionan un servicio a las transacciones que aleatoriamente entran al sistema. Dependiendo del sistema que se trate, las entidades pueden ser cajeras, máquinas, semáforos, grúas, etcétera, mientras que las transacciones pueden ser: clientes, piezas, autos, barcos, etcétera. Tanto el tiempo de servicio como las entradas al sistema son fenómenos que generalmente tienen asociadas fuentes de variación que se encuentran fuera del control del tomador de decisiones, de tal forma que se hace necesaria la utilización de modelos estocásticos que permitan el estudio de este tipo de sistemas.

Una línea de espera puede modelarse como un proceso estocástico en el cual la variable aleatoria se define como el número de transacciones en el sistema en un momento dado; el conjunto de valores que puede tomar dicha variable es

{O, 1, 2, . . . , N\ y cada uno de ellos tiene asociada una probabilidad de ocurrencia { P0, P1, P2, … , PN }

En las líneas de espera, existen dos costos perfectamente identificados: el costo de las transacciones, que representa la cuantificación monetaria de la pérdida de tiempo al esperar recibir un servicio o la pérdida de clientes por abandono del sistema, y el costo de proporcionar el servicio, que representa la cantidad de dinero que hay que pagar por cuestión de sueldos y salarios, energía, mantenimiento y depreciación del personal o equipo. De tal forma que en un estudio de líneas de espera el objetivo es determinar qué nivel de servicio, ya sea por cantidad de entidades o por la velocidad de ellas, proporcionar para minimizar el costo total del sistema. Este costo está formado tanto por costo de servicio como por el que causa la espera. Matemáticamente podemos representarlo de la siguiente forma:

Min Ct= CeS + CqLq

S=1, 2, 3, 4,…

Lq= ƒ {S, E (t),…}

Donde:S número de servidoresE(t) tiempo promedio de proceso por cliente

Lq número promedio de clientes en la fila

Ct costo total promedio del sistema de líneas de espera por unidad de tiempo

Ce costo promedio de servicio por cliente por unidad de tiempo

Cq costo promedio de espera por cliente por unidad de tiempo

4.1 Estructura básica de los modelos de línea de espera.

Un sistema de espera se representa mediante la llegada de transacciones a un sistema con el fin de recibir un servicio por cualquiera de una o más entidades dispuestas para ello, conocidas como servidores. En caso de que todas las entidades se encuentren ocupadas, la transacción permanece en espera en la fila hasta que decide abandonar la fila sin ser atendido, o bien, es seleccionado de acuerdo con cierta regla para recibir atención. Una vez que el servicio ha sido completamente proporcionado, la transacción sale del sistema y se convierte de nuevo en una transacción potencial.

SERVIDORES Representan al mecanismo por el cual las transacciones reciben de una manera completa el servicio deseado. Estas entidades se encuentran dispuestas en forma paralela a la fila, de tal manera que las transacciones pueden seleccionar a cualquiera de ellas para el suministro de dicho servicio. Las dos características principales de los servidores son: la cantidad asignada por cada fila existente en el sistema y la distribución de probabilidad del tiempo de atención a las

transacciones o de la velocidad de servicio; dentro de las distribuciones más comunes están la exponencial, la Erlang, la hiperexponencial, la degenerada.

TRANSACCIONES POTENCIALES Representan el número total de clientes que podrían requerir el servicio proporcionado por el sistema y es necesario definir dos características para este conjunto de elementos; la primera tiene que ver con el tamaño del conjunto potencial de clientes, dando, en consecuencia, conjuntos limitados o finitos y en otros casos conjuntos ilimitados o infinitos.

La segunda caracterísitica se refiere a la distribución de probabilidad del tiempo entre llegadas o bien a la tasa de entrada promedio. Es común encontrarse la suposición de tasas de llegada que siguen un proceso Poisson, el cual ocurre cuando las llegadas a un sistema se llevan a cabo de forma aleatoria; es importante hacer notar que una de las propiedades de esta distribución es su relación con el tiempo entre llegadas consecutivas, que se representa en forma paralela, de acuerdo con un proceso de tipo exponencial. Existen algunos sistemas donde la tasa de llegadas se ve afectada por la decisión de una transacción de rehusar su entrada al sistema por razones diversas, por ejemplo del tamaño de la fila.

FILA Conjunto de transacciones que espera ser atendido por alguno de los servidores del sistema. Una fila tiene tres características principales, la primera se refiere a la capacidad, o sea, al número máximo de transacciones que pueden permanecer en ella en un mismo instante y de acuerdo con este número se clasifican como finitas o infinitas. Hay que hacer notar que en el caso de los modelos con tamaño finito, la solución es mucho más fácil de encontrar a partir de las ecuaciones generales ya que la solución del modelo se reduce a un sistema de ecuaciones simultáneas y a la evaluación de las medidas de desempeño mediante promedios ponderados, mientras que, en el caso de modelos de tipo ilimitado o infinito, es necesario recurrir a la solución del sistema de ecuaciones así como a la evaluación de las medidas de

desempeño y a algunas series geométricas que dificultan en cierto grado el manejo algebraico de la solución. La segunda característica es el orden en que las transacciones son extraídas de la fila para su atención, en ese caso podemos encontrar: primeras llegadas, primeros servicios, por prioridad, aleatorio, etcétera y, por último/la forma de salir de la fila, que puede darse mediante el proceso de servicio o bien, mediante el abandono por factores como desesperación, etcétera.

4.1.1 Un servidor, una cola. Es el tipo más sencillo de estructura y existen fórmulas directas para resolver el problema con distribución normal de patrones de llegada y de servicio. Cuando las distribuciones no son normales se resuelve con simulaciones.

Este modelo puede aplicarse a personas esperando en una cola para comprar boletos para el cine, a mecánicos que esperan obtener herramientas de un expendio o a trabajos de computadora que esperan tiempo de procesador.

LLEGADAS.Consiste en la entrada al sistema que se supone es aleatoria. No

tienen horario, es impredecible en que momento llegarán . El modelo también supone que las llegadas vienen de una población infinita y llegan una a la vez.

COLA.En este modelo se considera que el tamaño de la cola es infinito. La

disciplina de la cola es primero en llegar, primero en ser servido sin prioridades especiales. También se supone que las llegadas no pueden cambiar lugares en la línea (cola) o dejar la cola antes de ser servidas.

INSTALACIÓN DE SERVICIO.Se supone que un solo servidor proporciona el servicio que varía

aleatoriamente.

SALIDAS.No se permite que las unidades que salgan entren inmediatamente al

servicio.

Características de operación.Un servidor y una cola.Llegada Poisson.Cola infinita, primero en llegar primero en ser servido.

Tiempos de servicio exponenciales.

 COLA   :

Longitud promedio de la línea : 

Tiempo de espera promedio :

Sistema:

Longitud promedio de la línea : 

Tiempo de espera promedio : 

Utilización de la instalación : 

Probabilidad de que la línea exceda a n : 

A = tasa promedio de llegada.

S = tasa promedio de servicio.

4.1.2 N servidores, una cola.

Es considerada una rama de investigación operativa porque sus resultados a menudo son aplicables en una amplia variedad de situaciones como: negocios, comercio, industria, ingenierías, transporte y telecomunicaciones. En la informática y de las nuevas tecnologías estas situaciones de espera son más frecuentes. Así, por ejemplo, los procesos enviados a un servidor para ejecución forman colas de espera mientras no son atendidos, la información solicitada, a través de

Internet, a un servidor Web puede recibirse con demora debido a la congestión en la red, también se puede recibir la señal de línea de la que depende nuestro teléfono móvil ocupada si la central está colapsada en ese momento, etc.

Objetivo:

Identificar el nivel óptimo de capacidad del sistema que minimiza el coste del mismo.

Evaluar el impacto que las posibles alternativas de modificación de la capacidad del sistema tendrían en el coste total del mismo.

Establecer un balance equilibrado (³óptimo´) entre las consideraciones cuantitativas de costes y las cualitativas de servicio.

Prestar atención al tiempo de permanencia en el sistema o en la cola.

FUENTE DE ENTRADA

Una característica de la fuente de entrada es su tamaño. El tamaño es el número total de potenciales clientes que pueden requerir servicio en un determinado momento.

POBLACIÓN INFINITA

Es aquella población que tiene el tamaño suficiente en comparación con el sistema de servicio, para que los cambios en el tamaño de la población, ocasionados por disminuciones o incremento a la población, no afectan de manera sustancial las probabilidades del sistema.

PROCESO DE LLEGADA

Es la forma en que los clientes de la fuente de entrada llegan a solicitar un servicio.La característica más importante del proceso de llegada es el tiempo entre llegadas, que es la cantidad de tiempo entre dos llegadas sucesivas de clientes a un sistema de colas.

COLA

Una cola se caracteriza por el número de clientes que puede admitir. Las colas pueden ser finitas o infinitas.

SELECCIÓN A PARTIR DE LA COLA O LÍNEA DE ESPERA

Disciplina de Cola:

FIFO (PEPS): Primero Entrado, Primero Salido. LIFO (UEPS): Ultimo Entrado, Primero Salido. SEOA: Servicio en Orden Aleatorio.

PROCESO DE SALIDA

Es la forma en la que los clientes abandonan un sistema de colas.

VARIABLES.

4.1.3 N servidores, n colas.

El tercer sistema, en que cada servidor tiene una línea separada, es característico de los bancos y las tiendas de autoservicio. Para este tipo de servicio pueden separarse los servidores y tratarlos como sistemas independientes de un servidor y una cola. Esto sería válido sólo si hubiera muy pocos intercambios entre las colas. Cuando el intercambio es sencillo y ocurre con frecuencia, como dentro de un banco, la separación no sería válida.El problema con este formato es que las diferencias en el tiempo de servicio para cada cliente ocasionan un flujo o velocidad desigual en las colas. Como resultado de esto, algunos clientes son atendidos antes que otros que llegaron primero y además producen cambios de una cola a otra (por ejemplo: las ventanillas de los bancos y las cajas de pago de los supermercados).

4.2 Criterios bajo la distribución de Poisson y Exponencial para la selección del modelo apropiado de líneas de espera.

La distribución de Poisson es una distribución de probabilidad discreta que expresa, a partir de una frecuencia de ocurrencia media, la probabilidad que ocurra un determinado número de eventos durante cierto periodo de tiempo. Supóngase que para cada valor t > 0, que representa el tiempo, el número de sucesos de cierto fenómeno aleatorio sigue una distribución de Poisson de parámetro λt. Entonces, los tiempos transcurridos entre dos sucesos sucesivos sigue la distribución exponencial.

La función de masa o densidad de la distribución de Poisson es: 

Donde:

X es el número de ocurrencias del evento o fenómeno (la función nos da la probabilidad de que el evento suceda precisamente X veces).

λ es un parámetro positivo que representa el número de veces que se espera que ocurra el fenómeno durante un intervalo dado. Por ejemplo, si el suceso estudiado tiene lugar en promedio 4 veces por minuto y estamos interesados en la probabilidad de que ocurra X veces dentro de un intervalo de 10 minutos, usaremos un modelo de distribución de Poisson con λ = 10×4 = 40.

es la base de los logaritmos naturales (e = 2.71828 ...)Tanto el valor esperado como la varianza de una variable aleatoria con distribución de Poisson son iguales a λ. Los momentos de orden superior son polinomios de Touchard en λ cuyos coeficientes tienen una interpretación combinatoria. 

Esta distribución se puede hacer derivar de un proceso experimental de observación en el que tengamos las siguientes características

· Se observa la realización de hechos de cierto tipo durante un cierto periodo de tiempo o a lo largo de un espacio de observación

· Los hechos a observar tienen naturaleza aleatoria; pueden producirse o no de una manera no determinística.

· La probabilidad de que se produzcan un número x de éxitos en un intervalo de amplitud t no depende del origen del intervalo (Aunque, sí de su amplitud)

· La probabilidad de que ocurra un hecho en un intervalo infinitésimo es prácticamente proporcional a la amplitud del intervalo.

· La probabilidad de que se produzcan 2 o más hechos en un intervalo infinitésimo es un infinitésimo de orden superior a dos.

· Si en estas circunstancias aleatorizados de forma que la variable aleatoria X signifique o designe el "número de hechos que se producen en un intervalo de tiempo o de espacio", la variable X se

distribuye con una distribución de parámetro l .Así :     

LLEGADAS DE POISSON.

Las llegadas pueden seguir distintos patrones arbitrarios que forman un proceso de llegadas de Poisson:

   Los tiempos entre llegadas están distribuidos exponencialmente:

                                           P(t ≤ t) = 1 - e-λt

La probabilidad de que lleguen exactamente n clientes en cualquier intervalo de longitud t es:

                                         [e-λt(λt)n] / n!     (n = 0, 1, 2, ...). l Es una tasa promedio de llegadas constante expresada en “clientes

por unidad de tiempo”.

En la mayor parte de los casos de la cola, la llegada de los clientes se hace de una forma totalmente aleatoria. Aleatoriedad quiere decir que la ocurrencia de un evento no está influida por el tiempo que haya transcurrido desde la ocurrencia del evento anterior.

Los tiempos aleatorios entre llegadas se describen en forma cuantitativa, en los modelos de colas, con la distribución exponencial, que se describe como sigue:

Para la distribución exponencial:

Dada la distribución exponencial f(t) que representa el tiempo t entre eventos sucesivos, si S es el intervalo desde la ocurrencia del último evento, la propiedad de amnesia implica que:

P{t > T + S│t > S} P {t > T}

Para demostrar este resultado se observa que el exponencial con media 1/λ

P{t > Y} = 1- P {t < Y} = e- l

Así,

4.3 Aplicación de modelos de decisión en líneas de espera.

La teoría de colas requiere de un estudio matemático del comportamiento de líneas de espera. Estas se presentan cuando "clientes" llegan a un "lugar" demandando un servicio al "servidor", el cual tiene cierta capacidad de atención. Si el servidor no está disponible inmediatamente y el cliente decide esperar, entonces se forma en la "línea de espera". El problema es determinar qué capacidad o tasa de servicio proporciona el balance correcto. Esto no es sencillo, ya que un cliente no llega a un horario fijo, es decir, no se sabe con exactitud en qué momento llegarán los clientes. También el tiempo de servicio no tiene un horario fijo. Las llegadas se describen por su distribución estadística. si las llegadas ocurren con una tasa promedio y que son independientes una de otra, entonces ocurren de acuerdo con una distribución de probabilidades de tipo "poisson”.

Una cola es una línea de espera y la teoría de colas es una colección de modelos matemáticos que describen sistemas de líneas de espera particulares o de sistemas de colas. Los modelos sirven para encontrar un buen compromiso entre costes del sistema y los tiempos promedio de la línea de espera para un sistema dado .Con frecuencia, las empresas deben tomar decisiones respecto al caudal de servicios que debe estar preparada para ofrecer. Sin embargo, muchas veces es imposible predecir con exactitud cuándo llegarán los clientes que demandan el servicio y/o cuanto tiempo será necesario para dar ese servicio; es por eso que esas decisiones implican dilemas que hay que resolver con información escasa. La teoría de colas requiere de un estudio matemático del comportamiento de líneas de espera. Estas se presentan cuando "clientes" llegan a un "lugar" demandando un servicio al "servidor", el cual tiene cierta capacidad de atención. Si el

servidor no está disponible inmediatamente y el cliente decide esperar, entonces se forma en la "línea de espera".

AB C D E F

Modelo

Distribución

Distribución

Número de

Disciplina

Nro. Max de Clientes

Población

de Llegadas

de Salidas Servidores

del Servicio

Permitidos en el Sistema

1 M M 1 PEPS Infinito Infinita2 M M 1 GD N Infinita3 M M S GD Infinito Infinita4 M M S GD N Infinita5 M M 1 GD K K6 M M R GD K K

El modelo 5 y 6, suelen llamarse de servicio cerrado. El servidor atiende a un número constante de máquinas o unidades. Cuando una máquina se rompe, no puede generarse nuevos llamados mientras permanezca en servicio. En el caso del modelo 6 el sistema tiene un total de K máquinas que son atendidas por R operarios.

Notación para Modelos de Cola

(A,B,C,):(D,E,F)

A: distribución de arribos (M=Poisson – D=Determinista – E=Erlang). B: distribución de salidas (M=Poisson – D=Determinista – E=Erlang). C: Número de servidores en paralelo. (

D: Disciplina del servicio.E: Número máximo de clientes permitidos en el sistema (en cola + en servidores).F: Población

Modelo

Notación

1 (M,M,1):(GD,α,α)

2 (M,M,1):(GD,N,α)

3 (M,M,S):(GD,α,α)

4 (M,M,S):(GD,N,α)5 (M,M,1):(GD,K,K)6 (M,M,R):(GD,K,K)

EJEMPLO:

MEDIDAS DE DESEMPEÑO  DEL SISTEMA DE COLAS* Suponga una estación 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 en promedio 3 minutos en la cola La tasa media de llegadas l es 45 clientes por hora o 45/60 = 0.75 clientes por minuto La tasa media de servicio m es 60 clientes por hora o 60/60 = 1 cliente por minuto

* Un lava carros puede atender un auto cada 5 minutos y la tasa media de llegadas es de 9 autos por hora. Obtenga las medidas de desempeño de acuerdo con el modelo M/M/1Ademá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

* Un lava carros  puede atender un auto cada 5 min. y la tasa media de llegadas es de 9 autos/hora, s = 2 min.Obtenga las medidas de desempeño de acuerdo con el modelo M/G/1Además la probabilidad de tener 0 clientes en el sistema y la probabilidad de que un cliente tenga que esperar por el servicio 

 * Un lava carros  puede atender un auto 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

 

4.4 Inferencia de resultados.

Inferencia es la acción y efecto de inferir (deducir algo, sacar una consecuencia de otra cosa, conducir a un resultado). La inferencia surge a partir de una evaluación mental entre distintas expresiones que, al ser relacionadas como abstracciones, permiten trazar una implicación lógica. Al partir de hipótesis o argumentos, es posible inferir una conclusión (que puede resultar verdadera o falsa.

El silogismo es una forma esencial de inferencia. Se trata de una forma de razonamiento deductivo que se forma por dos proposiciones (premisas) y una conclusión. Esta conclusión es la inferencia que necesariamente se deduce de las dos premisas. La veracidad de la conclusión dependerá de las leyes que regulan la relación entre las premisas comparadas. La garantía de verdad del nuevo juicio es la lógica, que deberá establecer distintas clasificaciones de las premisas. No todas las inferencias ofrecen conclusiones verdaderas.

EJEMPLO:

Imagínese un supermercado grande con muchas cajas de salidas. Supóngase que los clientes llegan para que les marquen su cuenta con una tasa de 90 por hora y que hay 10 cajas en operación. Si hay poco intercambio entre las líneas, puede tratarse este problema como 10

sistemas separados de una sola línea, cada uno con una llegada de 9 clientes por hora. Para una tasa de servicio de 12por hora: Dado: A= 9 clientes por hora B= 12 clientes por hora.

Explicación

Entonces, para este ejemplo, el cliente promedio espera 15 minutos antes de ser servido. En promedio, hay un poco más de 2 clientes en la línea o 3 en el sistema. El proceso completo lleva un promedio de 20 minutos. La caja está ocupada el 75% del tiempo. Y finalmente, el 32% del tiempo habrá cuatro personas o más en el sistema.