Teoria de Colas (líneas de espera)

Teor´ıa de Colas

TC: Parte de la Investigaci ´on Operativa que estudia el comportamiento de sistemas

cuyos elementos incluyen l´ıneas de espera (colas).

IO 07/08 - Teor´ıa de Colas 1

Teor´ıa de Colas: ejemplos

• personas esperando por un servicio (bibliotecas, bancos, gasolineras, urgencias

en hospital, . . . ),

• m´aquinas esperando por una reparaci ´on, piezas de un producto esperando a

ser ensambladas,

• programas de ordenador esperando a ser ejecutados por un procesador,

• informaci´on de internet esperando en un nodo para ser transferida a su destino,

• aviones esperando a despegar o aterrizar,

IO 07/08 - Teor´ıa de Colas 2

Teor´ıa de Colas: historia

Se inici ´o con A. K. Erlang, en la compa˜n´ıa telef ´onica estatal de Dinamarca (principios

del siglo XX).

Se analizaron los tiempos de espera de llamadas a centralitas autom´ aticas (congesti

´on de tr ´afico).

• Objetivo: satisfacer la demanda incierta en el sistema telef ´onico con el menor

coste para la compa˜n´ıa.

IO 07/08 - Teor´ıa de Colas 3

Teor´ıa de Colas

Introducci ´on.

Elementos y relaciones en un sistema.

Modelo M/M/1.

Modelo M/M/s.

Modelo M/M/1/k.

Aplicaciones.

IO 07/08 - Teor´ıa de Colas 4

Introducci ´on

Las l´ıneas de espera generan malestar, ineficiencia, retraso y otros problemas,

lo que origina un coste de tiempo y econ´omico.

Es muy importante evaluar el balance entre el aumento del nivel de servicio y el

tama˜no de las colas de espera.

Por tanto, es necesario entender la relaci ´on entre el n´umero de servidores en un

sistema (o eficacia de los mismos) y la cantidad de tiempo gastado en la cola (o

cantidad de clientes en la misma).

En sistemas de colas sencillos dichas relaciones se pueden encontrar anal´ıticamente.

En sistemas m´as complejos se pueden analizar mediante simulaci ´on.

IO 07/08 - Teor´ıa de Colas 5

Introducci ´on

• Elementos m´as importantes en un sistema de colas: clientes y servicio.

Los clientes se caracterizan por los intervalos de tiempo que separan sus llegadas.

El servicio se caracteriza por el tipo y tiempo de servicio, adem´as de por el

n´umero de servidores. El tipo de servicio o disciplina representa el orden en el

que los clientes se seleccionan de la cola.

Las llegadas de clientes pueden ser deterministas o aleatorios (en este caso se

modelan mediante una distribuci ´on estad´ıstica).

Los tiempos de servicio tambi´en pueden ser deterministas o aleatorios (distribuci

´on estad´ıstica).

IO 07/08 - Teor´ıa de Colas 6

Introducci ´ on: tipos de sistemas

Las variaciones en un sistema de colas pueden ser m´ ultiples. S´ olo se pueden

resolver de forma anal´ıtica un conjunto reducido de sistemas.

IO 07/08 - Teor´ıa de Colas 7

Elementos de un sistema: Llegadas

Pueden existir una o varias fuentes.

Se suele asumir independencia entre llegadas.

Intervalos entre llegadas: deterministas o aleatorios.

Tasa de llegadas: _ _ n´umero medio de clientes que acceden al sistema por

unidad de tiempo.

Tiempo medio entre llegadas: 1

_.

IO 07/08 - Teor´ıa de Colas 8

Elementos de un sistema: Fuente de entrada

Puede ser infinita o finita (sistemas abiertos o cerrados, respectivamente).

Ejemplo de sistema abierto: un banco, ya que es pr ´acticamente imposible que

todos los posibles clientes coincidan en su llegada.

Ejemplo de sistema cerrado: un servidor de internet con un n´umero relativamente

peque˜no de usuarios autorizados (es posible que en un momento

determinado se conecten todos los usuarios al servidor).

Si la fuente es finita, entonces el n´umero de clientes en la cola afecta al n´umero

de clientes fuera del sistema.

La llegada puede ser en bloque o de forma unitaria. Frecuentemente el bloque

se trata como un solo cliente.

IO 07/08 - Teor´ıa de Colas 9

Introducci ´ on: Clientes

Pueden ser impacientes.

Por tanto, los clientes se pueden perder, bien porque no entran en el sistema,

bien porque abandonan tras un tiempo en el sistema.

Tambi´en, los clientes pueden percibir un ritmo m´as acelerado en una cola

distinta y por tanto decidir cambiarse.

IO 07/08 - Teor´ıa de Colas 10

Elementos de un sistema: Cola o canal de espera

Puede ser de uno o varios canales.

Puede existir interferencia entre canales.

Puede ser de capacidad limitada.

Disciplina de la cola: orden de selecci ´on en el servicio (FIFO, LIFO, aleatorio,

orden de prioridad, etc.).

IO 07/08 - Teor´ıa de Colas 11

Elementos de un sistema: Servicio

Pueden existir uno o varios servidores.

Se suele asumir independencia entre tiempos de servicio.

Duraci ´on de los servicios: deterministas o aleatorios.

Tasa de servicio: μ _ n´umero medio de clientes que son atendidos por unidad

de tiempo.

Tiempo medio de servicio: 1

μ.

IO 07/08 - Teor´ıa de Colas 12

An´ alisis de sistemas de colas

Una vez caracterizado el sistema, se pueden contestar a las siguientes preguntas:

¿Qu´e proporci´on de tiempo est ´an los servidores desocupados?.

...