Teoria de colas

Sistemas de colas: clase 1
Amedeo R. Odoni 10 de octubre de 2001

Temas de teoría de colas
9. Introducción a las colas: ley de Little; M/M/1 10. Colas de nacimiento y muerte de Markov 11. Cola M/G/1 y extensiones 12. Colas de prioridad: representaciones de estados 13. Precio de congestión 14. Comportamiento dinámico de las colas 15. Sistema de colas hipercubo 16. Motor de inferencia decolas: psicología de las colas

Esquema
• Introducción a los sistemas de colas • Representación conceptual de • • • • • • •

los sistemas de colas Códigos para modelos de colas Terminología y notación Ley de Little y relaciones básicas Procesos de nacimiento y muerte Sistema de colas M/M/1 Diagramas de transición Probabilidades de estado estacionario

Colas
• La teoría de colas es la rama dela investigación

operativa que estudia las listas de espera (retardo/congestión) • Un sistema de colas está formado por un origen de usuario, una cola de espera y posibilidades de servicio con uno o varios servidores paralelos idénticos • La red de colas es un conjunto de sistemas de colas conectados entre sí • Parámetros básicos de un sistema de colas: Tasa de demanda Capacidad (tasa deservicio) Tiempos de demanda entre llegadas/Tiempos de servicio Capacidad y disciplina de la cola (finita/infinita; FIFO/FCFS, SIRO, LIFO, prioridades) Numerosos detalles (retroalimentación, “jockeying”, etc.)

Sistema de colas genérico
Servidores Punto de llegada al sistema Cola

C C C C C C C

Punto de salida del sistema

Origen de usuarios/ clientes

C C C C C C

Proceso de llegadasTamaño de origen de usuario Disciplina de cola y capacidad Proceso de servicio Número de servidores

Red de colas formada por cinco sistemas de colas

Sistema de colas 2 Llegada Sistema de colas 1 Punto de elección de de los usuarios

Sistema de colas 3 Punto en el que los usuarios se fusionan Sistema de colas 5 Salida

+

Sistema de colas 4

Aplicaciones de la teoría de colas
•Algunos ejemplos de colas: _ Facturación en aeropuertos _ Cajeros automáticos _ Restaurantes de comida rápida _ Esperas en líneas de atención telefónica _ Intersecciones de tráfico _ Peajes _ Aviones en espera para aterrizar _ Llamadas a la policía o a compañías de servicios públicos • Estándares de calidad del servicio (LOS) • Análisis económicos que incluyan comparaciones

entre costes deexplotación, inversiones de capital y LOS

Importancia de los modelos de colas en los análisis de inversiones de capital
Coste Coste total

Coste óptimo

Coste de crear la capacidad

Coste de pérdidas por esperas

Capacidad“óptima”

Capacidad del aeropuerto

Ventajas e inconvenientes de la teoría de colas
• Los modelos de colas implican siempre aproximaciones a la realidad y unasimplificación de ésta • Los resultados permiten apreciar el orden de importancia, los cambios con relación a un punto de referencia y las tendencias más probables • Resultados "cerrados" limitados casi siempre a situaciones de“estado estacionario" y obtenidos sobre todo (aunque no exclusivamente) para su aplicación a sistemas de nacimiento y muerte y de “fase” • Proporciona algunas cotas útiles parasistemas más generales en estado estacionario • Cada vez hay más soluciones numéricas disponibles para sistemas dinámicos
P

Código para modelos de colas: A/B/m
Distribución del tiempo de servicio Número de servidores Sistema de colas

–/–/–
Distribución del tiempo entre llegadas Usuarios

C C CCCCCC C C
Cola

S S S S

Posibilidad de servicio

• Algunos códigos de letras estándar para Ay B: _ M: Exponencial negativa _ D: Determinista _ Ek:Distribución de Erlang en orden k _ G: Distribución general
• Modelo tratado en esta clase: M/M/1

Terminología y notación
• Estado del sistema: número de usuarios • • • • •

que hay en el sistema Longitud de la cola : número de usuarios en espera de servicio N(t) = número de usuarios en el sistema en un tiempo t Pn(t) = probabilidad...