Teoría de Colas

Introducción a los Sistemas de Espera

Los sistemas de espera, también conocidos como sistemas de colas, son un área fundamental en la investigación operativa y la simulación. Estos sistemas se utilizan para modelar y analizar situaciones en las que existe una demanda por un servicio que no siempre puede ser satisfecha de inmediato, lo que genera la formación de colas.

Elementos de un Sistema de Espera

Existen diversos elementos que caracterizan a un sistema de espera:

• Proceso de Llegada: Describe cómo los clientes llegan al sistema. Se considera el Tiempo entre Llegadas, que puede ser determinístico o probabilístico (asociado a una distribución de probabilidad). También se considera si las llegadas son individuales o en grupos (batches).
• Proceso de Atención: Representado por el Tiempo de Servicio, que puede ser determinístico o probabilístico. Se define si la atención es individual o en grupos.
• Número de Servidores: Un sistema puede tener uno o varios servidores en paralelo. También existen sistemas con servidores en serie, con una o varias colas.
• Capacidad del Sistema: Un sistema con capacidad infinita no tiene límite en el tamaño de la cola.
• Disciplina de Atención: Define cómo se seleccionan los clientes de la cola para ser atendidos. La disciplina FIFO (First In, First Out) es la más común, pero también existen estrategias de prioridad o aleatoria.

Simbología General

Elementos generales

Servidores

• c = Número de servidores.
• ƒÊ = Tasa de servicio (número promedio de clientes atendidos por unidad de tiempo).
• Disciplina de atención a clientes (FIFO, LIFO, Prioridad, Aleatoria).
• Colocación de los servidores (en Paralelo, en Serie o en Red).
• Atención individual o en grupos.

Clientes

• n = Número de clientes en el sistema (en cola y en los servidores).
• N = Número máximo permisible de clientes en el sistema.
• ƒÉ = Tasa de Llegadas (número promedio de llegadas de clientes por unidad de tiempo).
• Población finita o infinita.
• Llegadas individuales o en grupos.

Cola

• Lq = Número promedio de clientes en cola.
• L = Número promedio de clientes en el sistema (en cola y en servicio).
• Tamaño de la Cola (Finita o Infinita).
• Forma de Salir de la Cola.

Indicadores para Evaluar el Rendimiento de un Sistema de Colas

Relacionados con el Tiempo:

• W = Tiempo promedio de permanencia de un cliente en el sistema (en cola y en servicio).
• Wq = Tiempo promedio de espera de un cliente en cola.

Relacionados con el Número de Clientes:

• L = Número promedio de clientes en el sistema.
• Lq = Número promedio de clientes en la cola.
• Pw = Probabilidad de que un cliente que llega tenga que esperar.
• Pn = Probabilidad de que existan n clientes en el sistema.
• Po = Probabilidad de que no hayan clientes en el sistema.
• Pd = Probabilidad de negación de servicio (probabilidad de que un cliente que llega no pueda entrar al sistema porque la cola está llena).

Otros Indicadores:

• U = Utilización de los servidores (número de clientes promedio atendidos por servidor por unidad de tiempo).
• ƒÏ = Intensidad de tráfico del sistema.

Naturaleza estocástica de los sistemas de espera

Cualquier sistema de colas pasa por dos fases: la fase transitoria y la fase estable.

En la Fase Transitoria se suelen analizar procesos de Nacimiento Puro (solo se analizan llegadas de clientes) o Muerte Pura (solo se analizan salidas de clientes del sistema).

En la Fase Estable se estudian los procesos de Nacimiento y Muerte, siendo los más abordados los sistemas de colas con distribución probabilística Poisson y servidores en paralelo.

El Fenómeno Poisson

El comportamiento probabilístico tipo Poisson es común en las líneas de espera. Existe una estrecha relación entre la distribución exponencial y la Poisson.

Relación analítica entre la Poisson y la Exponencial

Proceso de Llegada de Clientes

Si la variable aleatoria X (número de clientes que llegan al sistema de espera por unidad de tiempo) se distribuye Poisson, entonces:

Proceso de Salida de Clientes

Si el número de clientes atendidos por unidad de tiempo se distribuye Poisson con media µ (promedio de clientes servidos por unidad de tiempo), entonces el tiempo entre dos salidas consecutivas o el tiempo de servicio se distribuye exponencial con parámetro 1/µ.

Si el número de eventos (por ejemplo, llegadas) en un momento dado se distribuye Poisson con una tasa media de eventos ƒÉ (eventos por unidad de tiempo), entonces el tiempo entre dos eventos consecutivos (tiempo entre llegadas) se distribuye exponencial con media 1/ƒÉ unidades de tiempo (o al revés).

Un supuesto general en sistemas de espera es que los tiempos entre llegadas y los tiempos de servicio se comporten según la función exponencial.

Pertinencia del Fenómeno Poisson en sistemas de espera

La teoría analítica de colas busca estudiar sistemas de espera que tiendan a la congestión. La tendencia a la congestión sugiere el supuesto general asociado al fenómeno Poisson.

Los Sistemas de Espera y las Cadenas de Markov

Las colas asociadas a fenómenos estocásticos Poisson se consideran procesos totalmente aleatorios, similar a las Cadenas de Markov Ergódicas en tiempo discreto.

Los procesos de nacimiento y muerte (sistemas de colas) se comportan como un proceso estocástico enmarcado dentro del concepto de Cadenas de Markov en Tiempo Continuo, que asume que los cambios de estado pueden ocurrir en un tiempo ƒ¢T pequeño.

Un Sistema de Espera puede modelarse como un proceso estocástico markoviano en el cual la variable aleatoria se define como el número de clientes en el sistema, n, en un momento dado, donde los distintos valores de n son los estados del proceso estocástico markoviano.

El conjunto de valores que puede tomar la variable n es {0, 1, 2, …, N} y cada uno tiene asociada una probabilidad de ocurrencia {P0, P1, P2, …, PN}. Estas probabilidades se denominan probabilidades de estado estable del sistema de espera y se calculan dentro de un proceso markoviano asumiendo ergodicidad.

Cálculo de las probabilidades Pn en Sistemas de Espera

Considerando un proceso markoviano en tiempo continuo, se define un intervalo ƒ¢t muy pequeño que asegure el cumplimiento del siguiente postulado:

! Solamente puede ocurrir una llegada o una salida entre un t y t + Ģt

Notación Kendall-Lee

Sistema de Colas M/D/15 : DG/N/‡

• M: llegadas tipo Poisson (markovianas).
• D: tiempo de servicio o de salidas determinístico (constante).
• 15: 15 servidores en paralelo.
• DG: disciplina de servicios general.
• N: el sistema solo puede alojar a un máximo de N clientes.
• ‡: población de clientes infinita o fuente de llegada de clientes infinita.

Sistema de Colas M/M/4 : DG/‡/‡

• Sistema con llegadas y salidas Poisson.
• 4: 4 servidores en paralelo.
• DG: disciplina de servicio general.
• ‡: el sistema tiene capacidad ilimitada para recibir clientes y tiene una población de clientes infinita.

Sistema de Colas M/M/R : DG/K/K (R<K)

• Ejemplo: modelo de servicio de reparación de máquinas.
• R: técnicos en reparaciones.
• K: máquinas.
• Fuente de llamadas finita.
• Proceso de llegadas y de servicio probabilísticos y de Markov.

Sistema de Colas G/D/2 : DG/10/‡

• Sistema de líneas de espera con un proceso de llegadas arbitrario.
• Tiempo de atención determinístico (constante).
• 2: 2 servidores.
• 10: capacidad máxima de recepción de clientes de 10.
• ‡: fuente de clientes potenciales infinita.

Modelos Básicos de Líneas de Espera

Sistemas de Espera [M/M/1 : DG/‡/‡]

Sistemas de Espera [M/M/c : DG/‡/‡]