miércoles, 13 de octubre de 2010

 Sistemas de colas

Modelo básico

Un sistema de colas puede dividirse en sus dos componentes de mayor importancia, la cola y la instalación de servicio . Las llegadas son las unidades que entran en el sistema para recibir el servicio. Siempre se unen primero a la cola ; si no hay línea de espera se dice que la cola esta vacía . De la cola, las llegadas van a la instalación de servicio de acuerdo con la disciplina de la cola, es decir, de acuerdo con la regla para decidir cuál de las llegadas se sirve después. El primero en llegar primero en ser servido es una regla común, pero podría servir con prioridades o siguiendo alguna otra regla. Una vez que se completa el servicio, las llegadas se convierten en salidas. 


Estructuras típicas de sistemas de colas

Una Linea - Un Servidor
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.


Una Linea - Múltiples servidores
El modelo de una línea con múltiples servidores es típico de una peluquería o una panadería en donde los clientes toman un número al entrar y se les sirve cuando les llega el turno. 

Varias Lineas - Múltiples servidores
Este modelo se caracteriza porque 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.  

Una Linea - Servidores secuenciales 
"info"imagen
Costos de un sistema de colas 
Un sistema tienen costos asociados que deben de considerarse

Costo de Espera

Esperar significa desperdicio de algún recurso activo que bien se puede aprovechar en otra cosa y esta dado por:

 Costo total de espera = CwL , donde
·          Cw = costo de espera por hora (en pesos) por llegada por unidad de tiempo
·          L= longitud promedio de la línea.  

Costo de Servicio

Es el costo de operación del servicio brindado este en la mayoría se trata de comprar varias instalaciones de servicio , en estos casos solo se ocupan los costos comparativos o diferenciales.  
Sistema de costo mínimo 

Aquí hay que tener en cuenta que para tasas bajas de servicio, se experimenta largas colas y costos de espera muy altos. Conforme aumenta el servicio disminuyen los costos de espera, pero aumenta el costo de servicio y el costo total disminuye, sin embargo, finalmente se llega a un punto de disminución en el rendimiento. Entonces el propósito es encontrar el balance adecuado para que el costo total sea el mínimo. 

Sistemas de colas

Las llegadas
 
Es el número de clientes que llegan a las instalaciones de servicio.
El proceso de llegada es la forma en que los clientes llegan a solicitar un servicio. La característica más importante del proceso es el tiempo entre llegadas, que es la cantidad de tiempo entre dos llegadas sucesivas. Este lapso es importante porque mientras menor sea el intervalo de tiempo, con más frecuencia llegan los clientes, lo que aumenta la demanda de servidores disponibles.


El número esperado de llegadas por unidad de tiempo se llama tasa media de llegadas (λ), el tiempo esperado entre llegadas es 1/λ. 
Por ejemplo, si la tasa media de llegadas es λ = 20 clientes por hora, entonces el tiempo esperado entre llegadas es 1/λ = 1/20 = 0.05 horas o 3 minutos.
Además es necesario estimar la distribución de probabilidad de los tiempos entre llegadas generalmente se supone una distribución exponencial esto depende del comportamiento de las llegadas.

Las llegadas – Distribución exponencial

La forma algebraica de la distribución exponencial es:
 

Donde t representa una cantidad expresada en de tiempo unidades de tiempo (horas, minutos, etc.) 

La distribución exponencial supone una mayor probabilidad para tiempos entre llegadas pequeños , en general, se considera que las llegadas son aleatorias  y que la última llegada no influye en la probabilidad de llegada de la siguiente.

Las llegadas - Distribución  de Poisson 

Su forma algebraica es:

Donde:

P(k) : probabilidad de k llegadas por unidad de tiempo 
λ : tasa media de llegada
e = 2,7182818…


Sistemas de colas
La cola  

El número de clientes en la cola es el número de clientes que esperan el servicio este número de clientes en el sistema es el número de clientes que esperan en la cola más el número de clientes que actualmente reciben el servicio, la capacidad de la cola es el número máximo de clientes que pueden estar en la cola generalmente se supone que la cola es infinita aunque también la cola puede ser finita, cada cola tiene una disciplina de la cola, esta se refiere al orden en que se seleccionan los miembros de la cola para comenzar el servicio, la más común es PEPS: primero en llegar, primero en servicio de igual forma se puede dar una selección aleatoria teniendo en cuenta las prioridades, UEPS, entre otras.

Sistemas de colas
El servicio  

El servicio puede ser brindado por un servidor o por servidores múltiple este tiene un tiempo de servicio que varía de cliente a cliente, el tiempo esperado de servicio depende de la tasa media de servicio (µ), este tiempo esperado de servicio equivale a 1/µ.
Por ejemplo, si la tasa media de servicio es de 25 clientes por hora Entonces el tiempo esperado de servicio es 1/µ = 1/25 = 0.04 horas, o 2.4 minutos.
Es necesario seleccionar una distribución de probabilidad para los tiempos de servicio, existen dos distribuciones que representarían puntos extremos:  La distribución exponencial (σ=media) y el Tiempos de servicio constantes (σ=0). Una distribución intermedia es la distribución Erlang  Esta distribución posee un parámetro de forma k que determina su desviación estándar:


Si k = 1, entonces la distribución Erlang es igual a la exponencial
Si k = ∞, entonces la distribución Erlang es igual a la distribución degenerada con tiempos constantes 
La forma de la distribución Erlang varía de acuerdo con k
 



Distribución Erlang


Sistemas de colas

Etiquetas para distintos modelos

David G. Kendall introdujo una notación de colas A/B/C en 1953. La notación de Kendall sirve para describir las colas y sus características. 
A: Distribución de tiempos entre llegadas 
B: Distribución de tiempos de servicio
  • M: distribución exponencial 
  • D: distribución degenerada
  • Ek: distribución Erlang 
c: Número de servidores

Desempeño del sistema de cola 

Para poder evaluar el desempeño es necesario conocer dos factores principales:  

     1.  El número de clientes que esperan en la cola  
     2.  El tiempo que los clientes esperan en la cola y en el sistema

Medidas del desempeño del sistema de colas

  1. Número esperado de clientes en la cola Lq
  2. Número esperado de clientes en el sistema Ls
  3. Tiempo esperado de espera en la cola Wq
  4. Tiempo esperado de espera en el sistema Ws
Fórmulas generales

Veamos el siguiente ejemplo!

Suponga una estación de gasolina a la cual llegan en promedio 45 clientes por hora, te 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 λ 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.




Probabilidades como medidas del desempeño 

la probabilidad como medida de desempeño no trae consigo una serie de beneficios como permitirnos evaluar escenarios o establecer distintas metas.
Notación: 
 
Pn : probabilidad de tener n clientes en el sistema
P(Ws t) : probabilidad de que un cliente no espere en el sistema más de t horas
Factor de utilización del sistema 
Dada la tasa media de llegadas λ y la tasa media de servicio µ, se define el factor de utilización del sistema ρ.
Generalmente se requiere que ρ < 1
Su fórmula, con un servidor y con s servidores, respectivamente, es:


 
Veamos el siguiente ejemplo!

Con base en los datos del ejemplo anterior, λ = 0.75, µ = 1  

El factor de utilización del sistema si se mantuviera un servidor es:

ρ= λ/µ = 0.75/1 = 0.75 = 75%    

Con dos servidores (s = 2):

ρ= λ/sµ = 0.75/(2*1) = 0.75/2 = 37,5%