Teoria De Las Colas

TEORÍA DE COLAS

Nota Técnica de Apoyo nº 1.1

1ª Ley de Harper

No importa en qué cola se sitúe: la otra siempre avanzará más rápido

2ª Ley de Harper

Y si se cambia de cola, aquélla en que estaba al principio empezará a ir más deprisa

1. Introducción

La Teoría de Colas es un formulación matemática para la optimización de sistemas en que interactúan dos procesos normalmente aleatorios: un proceso de “llegada de clientes” y un proceso de “servicio a los clientes”, en los que existen fenómenos de “acumulación de clientes en espera del servicio”, y donde existen reglas definidas (prioridades) para la “prestación del servicio”.

La Teoría de Colas es una aproximación matemática potente para la optimización del problema, y tiene aplicaciones (crecientes) en sistemas donde las llegadas y el servicio admiten una representación matemática (probabilística); en problemas que no admiten esta representación existen otras técnicas, como muestra la tabla siguiente:

Menos Complejidad / Coste de análisis Más

Heurísticos

Modelos de aproximación lineal

Teoría de Colas: modelos analíticos

Simulación (benchmarking)

Heurísticos: reglas derivadas de la experiencia que no tratan de optimizar el problema sino de dar directrices simples para una aplicación “razonablemente eficaz”. Por ejemplo, se suele utilizar una regla heurística en el pre-diseño de circuitos electrónicos con canales de E/S, consistente en dimensionar los canales E/S de forma que su ocupación no supere el 35% en aplicaciones con acceso on-line a sistemas de almacenamiento externo, o del 40% si las aplicaciones son batch.

Modelos lineales: obtienen valores “medios” de representación de las variables, y bajo las hipótesis de comportamiento lineal ante variaciones en los flujos se extrapolan los niveles de capacidad / utilización.

Simulación: construcción de modelos detallados de simulación por ordenador. En particular, donde el modelo se basa en datos obtenidos de aplicaciones reales se habla de técnicas de “benchmarking”: por ejemplo, en el diseño de las oficinas bancarias.

Colas: concepto intuitivo de línea de espera, equivalente al británico (queues) y al americano (waiting lines).

Origen de la Teoría de Colas: trabajos de A. K. Earlang (Dinamarca, 1.905) estudiando el problema de dimensionamiento de líneas y centrales de conmutación telefónica para el servicio de llamadas.

Los problemas de “Colas” se presentan permanentemente en todas las aplicaciones de la vida diaria: un estudio de EE.UU. concluyó que un ciudadano medio pasa 5 años de su vida esperando en distintas Colas, y de ellos casi 6 meses parado en los semáforos. Problemas típicos de Teoría de Colas son:

Programación de actividades de despegue / aterrizaje en un aeropuerto

Sistema de consulta médica

Piezas en un taller donde pasan por diferentes máquinas en el proceso de mecanizado

Sistema de cajas en una oficina bancaria

2. Costes asociados a un sistema de Colas

¿Por qué es necesario contar con herramientas de optimización para los problemas de Colas?

Normalmente en cualquiera de estos sistemas existen dos familias de costes:

a) Los costes asociados a la espera de los clientes

Por ejemplo, el valor del tiempo perdido o la gasolina malgastada en los atascos o los semáforos, o las horas perdidas en las Colas de las urnas electorales (valor normalmente estimado).

La hipótesis natural establece que estos costes de la espera decrecen conforme aumenta la capacidad de servicio del sistema: por ejemplo, conforme aumenta el número de médicos de cabecera en un ambulatorio más corto es el tiempo de espera de los pacientes, y el coste de oportunidad del tiempo perdido decrece.

b) Los costes asociados a la expansión de la capacidad de servicio

Contra la reducción anterior de costes de espera, es también normal que el coste asociado a incrementar la capacidad de servicio crezca con alguna proporcionalidad en relación a esta capacidad; en el ejemplo anterior, los costes de salarios, despachos, enfermeras ayudantes, etc. ligados al aumento del número de médicos son casi directamente proporcionales al número de médicos (o con una parte fija y otra directamente proporcional).

c) Los costes totales del sistema de servicio

La suma de los dos costes anteriores da una función de costes totales del sistema en función de la capacidad, que tendrá una forma similar a la siguiente:

Teoría de colas

3. Objetivos de la Teoría de Colas

Dada la función de costes anterior, los objetivos de la Teoría de Colas consisten en:

Identificar el nivel óptimo de capacidad del sistema que minimiza el coste global 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.

El objetivo de coste es claro; entre los objetivos de servicio se suelen plantear aspectos medibles (llamados medidas “duras”) y hay otros (medidas “blandas”) que hay que valorar externamente; algunas medidas “duras” típicas de sistemas de Colas son:

Tasa de ocupación de las estaciones de servicio: las ocupaciones admisibles dependen del tipo de sistema, y es claro que no son estándares: la ocupación permanente de un sistema automático como una barrera de aparcamiento no puede ser la misma que la de un médico en una consulta.

Número de clientes en el sistema o en la Cola: hay límites (en ocasiones hasta físicos) al tamaño de una Cola, que también dependen del tipo de servicio. En casos en que hay restricciones al tamaño de la Cola (por ejemplo en una gasolinera en el centro de la ciudad) una medida importante será la proporción de clientes servidos en relación a los potenciales (llegados al sistema).

Tiempo de permanencia en el sistema o en la Cola: la “paciencia” de los clientes depende del tipo de servicio específico considerado.

4. Elementos de un Sistema de Colas

El Sistema de Colas incluye tanto las estaciones de servicio y los clientes en ellas, como la propia

...