Colas

Esperando filas

Una cola (o colas) se puede describir de la siguiente manera: los clientes (hombres, tareas, mensajes, etc.) llegan a un servicio, esperan en una cola si no pueden ser atendidos de inmediato y se van después de haber recibido el servicio.

El modelo, creado originalmente por Erlang para el sistema telefónico de 1909, se utiliza para modelar la gestión del tráfico, la planificación y el dimensionamiento de la infraestructura y el mecanizado.

Notación de Kendall

Una cola tiene 6 criterios señalados por: T / X / C / K / P / Z

• T: la distribución de probabilidad del tiempo entre llegadas. Los clientes pueden irse si llegan mientras la fila está llena. T puede tomar los siguientes valores
  • M para proceso de Markoviano / ley exponencial
  • G de la ley general
  • D ley determinista
  • E (k) para la ley de Erlang
  • etc.

• X: distribución de probabilidad del tiempo de servicio. Un cliente es tomado directamente por un servidor gratuito, una vez que se completa el servicio, el cliente se retira. La distribución está representada por los mismos símbolos que en T.
• C: el número de servidores. En colas únicas, todos los servidores tienen la misma distribución de probabilidad de tiempo de actividad.

• K: la capacidad de la cola. Si la cola es un número finito, el cliente se pierde cuando la cola está llena. Los servidores cuentan para la capacidad de la cola (1 por servidor).

• P: el tamaño de la población. El tamaño de la población es finito o infinito. En el caso de una población finita, la tasa de llegada de clientes es una función del número de clientes en el sistema.
• Z: disciplina de servicio
  • FCFS / FIFO (primero en llegar, primero en ser servido / primero en entrar, primero en salir): primero en llegar, primero en ser servido
  • LCFC / FILO (último en llegar, primero en ser servido / primero en entrar, último en salir): último en llegar, primero en ser servido / primero en llegar, último en ser servido
  • RANDOM: atención al cliente aleatoria en lista de espera
  • HL (espera en línea): si llega un cliente "importante", ocupa el primer lugar en la cola (dependiendo de la "importancia" de los primeros clientes)
  • PR (preferencia): si llega un cliente "importante", se le atiende directamente y el cliente "menos importante" abandona el servicio para ir a la cola
  • PS (procesador compartido): todos los clientes son atendidos al mismo tiempo con una velocidad inversamente proporcional al número de clientes
  • etc.

Una cola puede ser atravesada por diferentes clases de clientes caracterizados por:

• Diferentes procesos de llegada
• Diferentes tiempos de servicio
• Diferentes costos
• a Planificación en la cola según su clase

Usaremos la notación T / X / C cuando la cola sea de capacidad infinita, el tamaño de la población sea infinito y el servicio sea disciplina FIFO. Esto es equivalente a escribir T / X / C / ∞ / ∞ / FIFO.

Medidas de desempeño

El propósito de estudiar una cola es calcular o estimar el rendimiento de un sistema. Este cálculo se realiza en modo estacionario para calcular: la velocidad X, el número de clientes Q, la tasa de uso del servidor U, el tiempo de respuesta R. En general, se calculan las expectativas de estos parámetros.

En el contexto de colas individuales, el sistema es ergódico. Luego buscamos calcular la estabilidad del sistema. Tomemos lo siguiente:

• A (T): número de llegadas al sistema entre 0 y T
• D (T): número de salidas del sistema entre 0 y T
• Xe (T) = A (T) / T: caudal medio de entrada entre 0 y T
• Xs (T) = D (T) / T: caudal medio de salida entre 0 y T
• Q (T): número medio de clientes entre 0 y T
• R_k: llegó el tiempo de residencia del k-ésimo cliente
• : tiempo medio de residencia entre 0 y T

una cola es estable si y solo si el límite cuando T se acerca al infinito de la tasa de entrada promedio es igual al límite cuando T se acerca al infinito de la tasa de salida promedio. En otras palabras, cuando el límite cuando T se acerca al infinito de D (T) / A (T) = 1. En una cola estable, el número de clientes sigue siendo finito.

Sea Q el número promedio de clientes, R el tiempo de respuesta promedio y X el rendimiento promedio, la ley de Little garantizada en estado estable para un sistema estable que Q=RX (entonces ya no se tiene en cuenta T).