LINEA DE ESPERA

LINEA DE ESPERA

Introducción

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

Modelo de Formación de Colas

Se forman debido a un desequilibrio temporal entre la demanda del servicio y la capacidad del sistema para suministrarlo.

En las formaciones de colas se habla de clientes, tales como máquinas dañadas a la espera de ser rehabilitadas. Los clientes pueden esperar en cola debido a que los medios existentes sean inadecuados para satisfacer la demanda del servicio; en este caso, la cola tiende a ser explosiva, es decir, a ser cada vez más larga a medida que transcurre el tiempo. Los clientes puede que esperen temporalmente, aunque las instalaciones de servicio sean adecuadas, porque los clientes llegados anteriormente están siendo atendidos.

OBJETIVOS

Los objetivos de la teoría de colas consisten en:

• 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 de espera.

Elementos Existentes En La Teoría De Colas

 Proceso Básico De Colas: Los clientes que requieren un servicio se generan en una fase de entrada. Estos clientes entran al sistema y se unen a una cola. En determinado momento se selecciona un miembro de la cola, para proporcionarle el servicio, mediante alguna regla conocida como disciplina de servicio. Luego, se lleva a cabo el servicio requerido por el cliente en un mecanismo de servicio, después de lo cual el cliente sale del sistema de colas.

 Fuente De Entrada O Población Potencial: Una característica de la fuente de entrada es su tamaño. El tamaño es el número total de clientes que pueden requerir servicio en determinado momento. Puede suponerse que el tamaño es infinito o finito.

Cliente: Es todo individuo de la población potencial que solicita servicio como por ejemplo una lista de trabajo esperando para imprimirse.

NOMENCLATURA

S = número de servidores

n= número de clientes en el sistema

N =número máximo de clientes permitidos en el sistema

A,,t =flujo de clientes que entran cuando hay n clientes en el sistema

u,7l =capacidad del servidor cuando hay n clientes en el sistema.

E(t)= tiempo promedio de proceso por cliente

V(t)= variancia del tiempo de proceso

E(á) = tiempo promedio entre llegadas

V(a) = variancia del tiempo entre llegadas

CQ = coeficiente cuadrado de variación del flujo de clientes que entran al sistema

CS`=  coeficiente cuadrado de variación del tiempo de servicio

Cp = coeficiente cuadrado de variación del flujo de clientes que salen del sistema PIJ probabilidad de que el sistema cambie de un estado i a un estado y después de un intervalo de tiempo.

Pn=  probabilidad en estado estable de que existan n clientes en el sistema

L = número promedio de clientes en el sistema

Lq = número promedio de clientes en la fila

W = tiempo promedio de permanencia en el sistema

Wq= tiempo promedio de permanencia en la fila

p =utilización promedio del servicio

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

Capacidad de la cola: Es el máximo número de clientes que pueden estar haciendo cola (antes de comenzar a ser servidos). De nuevo, puede suponerse finita o infinita.

 Disciplina de la cola: La disciplina de la cola se refiere al orden en el que se seleccionan sus miembros para recibir el servicio. Por ejemplo, puede ser:

• FIFO (first in first out) primero en entrar, primero en salir, según la cual se atiende primero al cliente que antes haya llegado.
• LIFO (last in first out) también conocida como pila que consiste en atender primero al cliente que ha llegado el último.
• RSS (random selection of service) que selecciona los clientes de manera aleatoria, de acuerdo a algún procedimiento de prioridad o a algún otro orden.
• Processor Sharing – sirve a los clientes igualmente. La capacidad de la red se comparte entre los clientes y todos experimentan con eficacia el mismo retraso.

 Mecanismo de servicio: El mecanismo de servicio consiste en una o más instalaciones de servicio, cada una de ellas con uno o más canales paralelos de servicio, llamados servidores.

 Redes de colas: Sistema donde existen varias colas y los trabajos fluyen de una a otra. Por ejemplo: las redes de comunicaciones o los sistemas operativos multitarea.

referencia: Tijms, H.C, "Algorithmic Analysis of Queues", Capítulo 9 en A First Course in Stochastic Models, Wiley, Chichester, 2003.

FILA

Es el 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, hastío, etcétera.

ECUACIONES GENERALES

Las medidas de desempeño con que se trabaja en teoría de colas son principalmente las siguientes:

Utilización del Servicio

Representa el porcentaje de tiempo en que los servidores atienden a los clientes y se calcula como la razón entre la tasa promedio de llegadas y la capacidad total del sistema para proporcionar el servicio.

Modelo del Sistema de Cola  M/M/1

Supuestos

• La linea de espera tiene 1 sólo canal
• las llegadas tienen una distribución Poisson
• Los tiempos de servicio tienen una distribución exponencial

FORMULAS

• Factor de Utilización

• Probabilidad que no existan unidades en el sistema

Modelo del sistema de cola M/M/K

Supuestos

• La linea de espera tiene 2 o más canales
• las llegadas tienen una distribución Poisson
• Los tiempos de servicio tienen una distribución exponencial

  FORMULAS

λ= Tasa media de llegadas del sistema

µ= Tasa media de servicio de cada canal

K= Número de canales

• Probabilidad que no existan unidades en el sistema

• Numero promedio de unidades en cola

• Numero promedio de unidades en el sistema

Tiempo promedio que dura una unidad en cola

• Tiempo promedio que dura una unidad en el sistema

• Probabilidad que exista N unidades en el sistema cuando

• Probabilidad que existan N unidades en el sistema cuando

Numero promedio de unidades en el sistema

• Numero promedio de unidades en cola

Tiempo promedio que una unidad pasa en cola

Tiempo promedio que una unidad pasa en el sistema

Probabilidad que existan N unidades en el sistema

                                         EJEMPLOS

Ejemplo 1:

El numero de tarros de cerveza pedidos en el Dick's Pub sigue una distribución de Poisson con promedio de 30 cervezas por hora.

1. Calcule la probabilidad de que se pidan exactamente 60 cervezas entre las 10 p.m. y las 12

    de la noche.

2. Determine el promedio y la desviación estándar del número de cervezas pedidas entre las

    9 p.m. y la 1 a.m.

3. Calcule la probabilidad de que el tiempo entre dos pedidos consecutivos sea entre 1 y 3    

     minutos.

Solución:

1. El número de cervezas pedido entre las 10 p.m. y las 12 de la noche sigue una distribución 

    de Poisson con parámetro 2(30) = 60. La probabilidad de que se pidan 60 cervezas entre  

    las 10 p.m. y la medianoche es:

2. λ = 30 cervezas por hora; t = 4 horas. Entonces, el número promedio de cervezas pedidas

   entre las 9 p.m. y la 1 am es 4(30) = 120 cervezas. La desviación estándar del número de 

   cervezas pedido entre las 9 p.m. y la 1 a.m. es (120)1/2 = 10.95.

3. Sen X el tiempo en minutos entre pedidos sucesivos de cerveza. El tiempo promedio de    

    pedidos por minuto es exponencial con parámetro, o razón, 30/60 = .5 cervezas por minuto. 

    Entonces la función de densidad de probabilidad del tiempo ente pedidos de cerveza es:

Ejemplo 2:

A un cajero bancario o automático sólo llega un promedio de 10 vehículos por hora. Suponga que los tiempos promedio de servicio para cada cliente es 4 minutos, y que los tiempos entre llegadas y los de servicio son exponenciales Conteste las siguientes preguntas:

    1. ¿Cuál es la probabilidad de que el cajero automático se encuentre vacío?

    2. ¿Cuál es el número promedio de automóviles que esperan en la cola su turno? Se

         considera que un vehículo que está ocupando el cajero automático, no está en la cola

         esperando.

   3. ¿Cuál es el tiempo promedio que un cliente pasa en el estacionamiento del banco, 

        incluyendo el tiempo en el servicio? 

   4. En promedio, ¿cuántos clientes por hora serán atendidos por el cajero automático

Solución:

Suponemos que nos ocupa un sistema de colas M/M/1/DG/∞/∞. para el cual λ = 10 automóviles por hora y μ= 15 automóviles por hora. Entonces ρ = 2/3

    1. Según la ecuación:

        

        0π= 1-ρ = 1- 2/3= 1/3. 

        

        Entonces el cajero automático se encontrará sin clientes un promedio de la tercera parte 

        del tiempo.

    2. Queremos conocer Lq:

    

    3. Buscamos saber W. 

        Según la ecuación :  W= L/λ

      

       Así, W= 2/10 = 1/5 hora, unos 12 minutos.

   4. Si el cajero automático estuviera ocupado siempre, podría atender un promedio de μ=15

       clientes por hora. De la parte 1 sabemos que sólo está ocupado dos tercer partes de su 

       tiempo. Así, durante cada hora, el cajero atenderá aun promedio de 2/3 *15 = 10 cliente.

       Debe ser así, porque el estado estable llegan 10 clientes cada hora y por lo tanto deben 

       salir  10 clientes del sistema cada hora.

Ejemplo 3:

En una peluquería hay un peluquero y un total de 10 asientos. Los tiempos de llegada tienen distribución exponenciales, y llega un promedio de 20 clientes posibles por hora. Los que llegan cuando la peluquería está llena no entran. El peluquero larda un promedio de 12 minutos en atender a cada cliente. Los tiempos de corte de pelo tienen distribución exponencial.

   1. En promedio, ¿cuántos corles de pelo por hora hará el peluquero?

   2. En promedio, ¿cuánto tiempo pasará un cliente en la peluquería cuando entra?

Solución

1. Una fracción 10π de las llegadas encuentra que está llena la peluquería. Por lo tanto, 

    entrará a ella un promedio de (1-10π)λ por hora. Todos los clientes que desean que se les 

    corle el cabello, y por lo tanto, el peluquero hará un promedio de (1-10π)λ cortes por hora.

    En nuestro problema, c = 10, λ=20 clientes por hora y μ= 5 clientes /h. Entonces ρ= 20/5 = 4

  

Así, los cortes de pelo son en promedio 20(1 – ¾ )  =  5/h. 

Esto significa que un promedio de 20 - 5 = 15 clientes posibles no entran cada hora.

2. Para calcular W:

Entonces da como resultado:

Ejemplo 4:

Un banco tiene dos cajeros. Llegan al banco un promedio de 80 clientes por hora y esperan en una sola cola para que los atiendan. El tiempo promedio que se necesita para atender a un cliente es 1.2 minutos. Suponga que los tiempos entre llegadas y los de servicio son exponenciales. Calcule:

   1. Número esperado de clientes en el banco.

   2. Tiempo esperado que pasa un cliente en el banco.

   3. La fracción del tiempo que determinado cajero esta desocupado.

Solución

1. Tenemos un sistema M/M/2/DG/∞/∞. con λ = 80 clientes/h y μ = 50 clientes/h. Así

     

y, por lo tanto, existe el estado estable. 

Si λ ≥ 100, no existiría estado estable. 

De la Tabla P(J ≥ 2) = .71.

Tabla para un sistema P ( j ≥ s) M/M/s/DG/∞/∞ :

Entonces de la Ecuación:

 L= 2.84+ 80/50 = 4.44 clientes.

2. Como W= λ/L: 

    

    W=4.44/80 = .055 horas = 3.3 minutos

3. Para calcular la fracción del tiempo que determinado cajero está desocupado, nótese que 

    esta desocupado durante lodo el tiempo que j = O, y la mitad del tiempo, por simetría, que 

   j=1. 

  La probabilidad que una ventanilla esté ociosa está dada por :

  

  

  Aplicando el hecho de que P(j ≥ 2) = .71, obtenemos:

  

  

  y según esta ecuación  da como resultado:

  

 Así, la probabilidad de que una ventanilla este vacía es :

Ejemplo 5:

Suponga que los nacimientos en un país están separados en el tiempo, de acuerdo con una distribución exponencial, presentándose un nacimiento cada 7 minutos en promedio.

Solución:

Como el tiempo promedio entre arribos (entre nacimientos) es de 7 minutos, la tasa de nacimiento en el país se calcula como:

El número de nacimientos en el país por año está dado por:

    λ t  = 205.7x365 = 75080 nacimientos/año

La probabilidad de ningún nacimiento en cualquier día es:

Suponga que nos interesa la probabilidad de emitir 45 actas de nacimiento al final de un periodo de 3 horas, si se pudieron emitir 35 actas en las primeras 2 horas.

Observamos que debido a que los nacimientos ocurren según un proceso de Poisson, la probabilidad requeridas reduce a tener 45-35=10 nacimientos en una hora (3-2 =1). 

Dado  λ=60/7=8.57 nacimientos/hora, obtenemos: