Teoría de colas

¿Qué son las colas y que es la teoría de colas?

Las colas son modelos de sistemas reales que pueden representar a clientes, maquinaria, sistemas logísticos, o flujos de trabajo donde se espera que estas reciban un servicio y cambien del mismo una vez se ha recibido.

Representan una línea de estudio matemático importante dentro de las operaciones, así como en los sistemas. 

En la vida real, al no haber una sincronía absoluta (es imposible que la exista) o espera quien presta el servicio o espera quien lo va a recibir.

Se produce siempre una espera, puesto que la sincronía absoluta no existe.

La espera es habitual en muchísimos casos ordinarios y cada uno tiene unas características que lo definen.

Encontramos reflejada la teoría de colas en los procesos de las fábricas, en la cola del banco, en cualquier transporte público, en la cola del supermercado. Se estudia mucho para los diseños de Call center. En Servidores de internet,o incluso en nuestra bandeja de entrada de correo.

Este resumen está realizado a partir de notas para el estudio de una asignatura sobre teoría de colas. Si quieres ver un ejemplo de cálculo, al final del mismo lo incluyo. Por supuesto, se acepta toda matización o apreciación al mismo, y me gustaría citar una fuente de estudio, quizás la mejor que existe en Castellano para dicha materia, como son los apuntes «Aplicando Teorı́a de Colas en Dirección de Operaciones» de José Pedro García Sabater.( DOE UPV)

Elementos de las colas:

Veremos la Población, la Entrada, La Cola,

– Población

La población en una cola es quien quiere hacer uso del servicio en el sistema. Puede ser finita o infinita. Y pueden haber varios tipos o un sólo tipo de población (clientes).

– Entrada

O arrival, esta vendría caracterizada por la tasa de entrada, la distribución entre entradas y si tiene lotes o no.
– La tasa de entrada: la definimos como el número de clientes que pueden entrar por unidad de tiempo. ( 
– Distribución entre entradas consecutivas.
– ¿Tiene Lotes? SÍ / NO.

Ejemplo de lotes: Si un barco descarga todos los elementos en un puerto concreto, sería un lote de contenedores. 

– Cola (Queue)

Es el elemento donde se espera en función de que los servidores tengan capacidad para atender. Las podemos clasificar en cola única o múltiple, por tipo de disciplina: FIFO, LIFO, RSS, Priority, WFQ, así como por la tasa de abandono.

• Cola Única / Cola múltiple. Esto define la disciplina de cola, pueden ser varias colas en paralelo u otros sistemas donde una única cola puede suministrar varios servicios. Por ejemplo podemos tener varias colas para coches, alguna para vehículos pesados, otra para motos.
  
  

Tipos de disciplinas de la cola

FIFO: First-in First-out:

Primero en entrar, primero en salir: En esta disciplina atendemos por orden de llegada. En una cola simple FIFO, los «paquetes» que llegan deben ponerse al final y esperar su turno para ser procesados, la forma de vaciado es coger el paquete que hace más tiempo que se encuentra en la cola. Todos los paquetes tienen el mismo tratamiento y por ende, no se puede garantizar servicios adicionales como calidad de servicio en ciertos paquetes. 

LIFO: Last-In First-Out:

Las LIFO, también conocidas como Pilas ( o Stack) es una disciplina de cola donde el último en entrar es el primero en salir
Atendemos primero el último cliente. En una cola LIFO, la forma de vaciado será coger el paquete último en entrar. Es parecido a una pila, donde vamos apilando elementos y cuando hay que vaciar cogemos el último que hemos apilado.

Colas Random (RSS):

También conocidas como RSS, este tipo de nomenclatura se usa cuando la disciplina usa una seleccion aleatoria. 

Colas Priority:

La nomenclatura de colas Priority se usa cuando existe una prioridad dentro de la cola.
Dentro de prioridad, podemos tener con o sin interrupción, según si llega un cliente con prioridad se interrumpe el trabajo en curso o no.

En este tipo de colas los paquetes que llegan se clasifican por clases de prioridad.

Esta clase de prioridad debe estar marcada de alguna forma. Cada clase de prioridad tendría su cola virtual independiente. Cuando toque procesar un paquete se elegirá el paquete de la clase más alta de una cola no vacía. Cada cola trabajará a partir del criterio FIFO para elegir el paquete a procesar.

También se pueden hacer disciplinas más complejas, puesto que dentro de cada prioridad se pueden aplicar a su vez disciplinas random, LIFO, o FIFO, por ejemplo otro tipo sería

Colas WFQ:

WFQ (Weighted Fair Queing) es la disciplina donde los paquetes se clasifican en clases y se colocan a su cola correspondiente. Se va dando servicio a cada clase de forma circular e igualitaria usando un algoritmo del tipo Round Robin.

En sistema WFQ asigna más capacidad a las colas más llenas, pero, sin dejar de atender a las colas más libres. Ajusta la disciplina de atención a cada cola según la ponderación del servicio de cada clase usando pesos (W) en función de la cantidad de elementos. También puede hacerse en funcion de la cantidad de servicios solicitados por cada flujo. Este sistema permite procesar distintas necesidades sin penalizar ninguna.

Tasa de abandono:

Tenemos que tener en cuenta que en algunos sistemas también puede haber clientes que abandonan la cola. Deberemos modelizar correctamente dicha tasa de abandono.

Servicios (s)
Distribución del tiempo de atención. Media y desviación típica. 
Tipos de clientes
Procesa por lotes o no en su gestión. 
Salida (d) representa el flujo de salida 

Al diseñar el sistema hay que dimensionarlo bien y decidir los recursos que vamos a invertir. Como número de servidores

Disciplina o capacidad
Para acertar en ese dimensionamiento deberemos estudiar la disponibilidad de recursos que tenemos así como que calidad de servicio (y por tanto coste derivado) estamos dispuestos a dar en el sistema. 

Deberemos tener en cuenta para conocer el rendimiento del sistema, que puede ser que existan servidores esperando sin ser utilizados, o que si tenemos el sistema lleno podemos perder clientes y que habrá un tiempo de espera que puede superar cierto requisito del cliente. 

Teorema de little:

El tiempo medio de estancia del sistema (representado por W), multiplicado por la tasa de entrada del sistema (Lambda) es igual a la cantidad de personas o clientes esperando el servicio (representado por L)

Este teorema se aplica para la cola, o para un sistemas de colas.

Nivel de saturacion (RO) = lambda / numero de servidores y tiempo de servicios. 

Libros recomendados:
Factory Physics, 
Manufacturing systems and modeling analytics

Sistemas de colas simples. 

La notación de Kendall nos permite escribir las características de los sistemas de colas.

M/M/1 equivalente a M/M/1/inf/FIFO/1

Es decir sería una cola de una única de etapa sin límite de capacidad. 

Una población infinita, trata de acceder a un servicio ofrecido por un único servidor. 
La entrada sigue una distribución de Poisson de media Lambda 

El tiempo de servicio es una distribución negativa exponencial. de media 1/mu
La saturación del sistema es ro=lambda / mu. tendremos que el número de elementos en el sistema promedio= L. ro / 1- ro.

W=L/lambda = 1 / mu – lambda. 
El tiempo que cada cliente de promedio está en el sistema.

Por tanto podemos saber cuánto tiempo estarán en la cola, que será igual al tiempo que estarán en el sistema menos el tiempo en el que serán atendidos.

Wqueue= W – 1 / mu = ro / mu – lambda


El tiempo de estancia en cola. 

Aplicando la formula de little.
Lq (tamaño medio de cola) = lambda cuadrado / mu (mu -lambda)

M/M/1 tiene un servidor
M/M/c tiene c servidores. 

La saturación del sistema será ro = lambda / c . debe ser menor que 1 para que sea estable.

Se puede calcular Lq
Wq con la formula de little. 

Por último a nivel práctico podemos comentar que existe un problema en los sistemas reales cuando el uso se acerca al 90% de capacidad, entonces empiezan los problemas de calidad de servicio, 

— 
Ejemplo práctico de teoría de colas:
Centro de reparación Apple Store

El servicio técnico de la tienda Apple Store debe hacer todos los cambios de batería del Iphone, pero hay algunos casos en los que se complica ya que deben por política de empresa, cambiar la pantalla.
El tiempo de reparación está distribuido de forma exponencial con una media de 30 minutos por teléfono entre abrir cambiar la batería, cerrar y comprobar. 

A pesar de que hay cita previa, nadie llega exactamente a la hora y los clientes con su teléfono van llegando durante todo el día.

Asumiremos por facilidad, que ese día no sacan ningún teléfono nuevo, y los clientes llegan de forma más o menos escalonada. Para reparaciones: Llegan de media 10 al día en las 8 horas que está abierta la tienda.

Queremos conocer cuál es la capacidad de reparación y cuanto tiempo está el servicio técnico sin reparar teléfonos. 

Como la tasa de llegada de teléfonos (lambda) es de 10/8 teléfonos a la hora. 
MU (tasa de reparación) es de 2 teléfonos a la hora. 

ro = lambda / mu = 
Ro0= 1- lambda / mu = 1 – 5/8=3/8

¿De media cuantos teléfonos hay por reparar? 

L = ro / 1- ro = 
¿Cuál es el tiempo medio total que un usuario con su teléfono está en la Apple store para una reparación?

W= 1 / mu ( 1-ro)) tantos minutos. 

Agradecimientos

Me gustaría agradecer públicamente:

Al Catedrático Antonio Rufián de la Universidad de Sevilla, por su tiempo, valoración, revisión y sus ánimos para extender el artículo.

Al Catedrático de la Universidad de Málaga Ezequiel López, por su revisión y sugerencias.

A mi tutor de la UOC Eduard García, por su revisión y recomendaciones.