Teoria de colas

TEORIA DE COLAS

MODELOS Y SIMULACIÓN

TEMA No. 6

Docente:Jaqueline Martínez Calderón 1

TEORIA DE COLAS


La teoría de colas es el estudio matemático del comportamiento de líneas de

espera. Esta se presenta, cuando los “clientes” llegan a un “lugar”

demandando un servicio a un “servidor”, el cual tiene una cierta capacidad de

atención. Si el servidor no está disponible inmediatamente y el cliente decide

esperar, entonces se forma la línea de espera.

Una cola es una línea de espera y la teoría de colas es una colección de

modelos matemáticos que describen sistemas de línea de espera particulares o

sistemas de colas. Los modelos sirven para encontrar un buen compromiso

entre costes del sistema y los tiempos promedio de la línea de espera para un

sistema dado.

OBJETIVOS DE LA TEORIA DE COLAS


¿ 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.

• Hay que prestar atención al tiempo de permanencia en el sistema o en la

cola: la “paciencia” de los clientes depende del tipo de servicio específico

considerado y eso puede hacer que un cliente “abandone” el sistema.

ELEMENTOS DE LA TEORIA DE COLAS


Fuente de entrada o población potencial: Es un conjunto de individuos (no

necesariamente seres vivos) que pueden llegar a solicitar el servicio en

cuestión.

Cliente: Es todo individuo de la población potencial que solicita servicio.

Capacidad de la cola: Es el máximo número de clientes que pueden estar

haciendo cola (antes de comenzar a ser servidos).

Disciplina de la cola: Es el modo en el que los clientes son seleccionados

para ser servidos. Las disciplinas más habituales son:

La disciplina FIFO (first in first out), también llamada FCFS (first come first

served): según la cual se atiende primero al cliente que antes haya llegado.

ELEMENTOS DE LA TEORIA DE COLAS


La disciplina LIFO (last in first out), también conocida como LCFS (last

come first served) o pila: que consiste en atender primero al cliente que ha

llegado el último.

La RSS (random selection of service), o SIRO (service in random order), que

selecciona a los clientes de forma aleatoria.

Mecanismo de servicio: Es el procedimiento por el cual se da servicio a los

clientes que lo solicitan.

La cola, propiamente dicha, es el conjunto de clientes que hacen espera, es

decir los clientes que ya han solicitado el servicio pero que aún no han

pasado al mecanismo de servicio.

SISTEMA DE COLAS


Fuente de Entrada

Llegada de un

Cliente

Cola

Disciplina de la Cola

Sistema de la Cola

Mecanismo de Servicio

Servicio

TEORIA DE COLAS


¿Donde esta la espera?

Instalaciones de Servicio

Restaurantes de comida rapida

Oficina de correos

Supermercados

Bancos

Manufactura

Equipo esperando a ser reparado

Telefono o red de computo

Ordenes de Producto

¿Por que hay espera?

Características del Sistema


Numero de Servidores

• Forma de arribo y servicio

• Comportamiento de la linea

Medicion del Sistema

Promedio del numero de clientes en espera

• tiempo promedio de espera del cliente

• Utilizacion del sistema

Numero de Servidores


Un servidor

Multiples

servidores

Multiples Servidores

sencillos

Forma de llegada


Usualmente se asume una distribucion Poisson:

0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3

C u s t o m e r s p e r t i m e u n i t

. 0 2

. 0 4

. 0 6

. 0 8

. 1 0

. 1 2

. 1 4

. 1 6

. 1 8

Relative Frequency

Tiempo de Servicio


Una distribucion exponencial es asumida:

Service Time

Relative Frequency (%)

Comportamiento de la linea de espera


Primeras entradas – Primeras Salidas (FCFS, FIFO):

Prioridades Multiples:

Algunos Modelos


1. Un servidor, tiempo de servicio exponencial (M/M/1)

2. Un servidor, tiempo de servicio general (M/G/1)

3. Servidores multiples, tiempo de servicio exponencial (M/M/s)

Nomenclatura

A / B / s

Distribucion Distribucion Numero de

De llegada de servicio Servidores

donde

M = distribucion exponencial (“Markovian”)

D = deterministica (constante)

G = distribucion general

Datos conocidos

l = Tasa de llegada del cliente

m = tasa de servicio (1/m = tiempo de servicio promedio)

s = numero de servidores

Se calcula

Lq = numero promedio de clientes en la linea

L = numero promedio de clientes en el sistema

Wq = tiempo promedio de espera en la linea

W = Tiempo pormedio de espera (incluyendo tiempo de servicio)

Pn = Probabilidad de tener n clientes en el sistema

r = Utilizacion del sistema


Conceptos básicos


Las siguientes ecuaciones se aplican para todos los tipos

de modelos

• Utilizacion del sistema

• Numero promedio de clientes en el sistema

• Tiempo promedio de espera en la linea

• Tiempo total de espera (incluyendo servicio)

r l

sm

L Lq l

m

Wq Lq

l

W Wq 1

m

Modelo 1 (M/M/1)


Formulas

Probabilidad que el sistema este vacio:

Probabilidad de n clientes en el sistema:

Numero promedio en la linea:

P0 1l

m

Pn P0l

m

n

Lq l2

m m l

Modelo 2 (M/G/1)

Formulas

Numero promedio en linea:

Probabilidad de que le sistema este vacio:

(Caso especial: M/D/1

Lq l2 2 r2

2 1 r

P0 1l

m

Lq l2

2m m l


Model 3 (M/M/s)


Formulas

Probabilidad que sistema este vacio :

Probabilidad de n clientes en el sistema:

Probabilidad de que un nuevo cliente vaya a esperar:

Numero promedio en linea:

P0 1

l / m n

n!

l / m s

s!(1 r)n0

s1

Pn

(l / m)n

n!P0 for n 1 , s

l / m n

s!snsP0 for n s

Pw l

m

sP0

s!(1 r)

Lq P0

(l / m)s1

(s 1)!(s l / m)2

Aplicación de teoría de Colas


Se pueden usar los resultados de

teoria de colas para tomasr las

siguientes decisiones:

Cuantos servidores usar

Usar un servidor rapido o

varios servidores lentos

Tener un servidor general o un

servidor para una tarea

especifica

Objetivo:

Minimizar costo total = costo del servidor + costo de espera

Cost of

Service Capacity

Cost of customers

waiting

Total Cost

Optimum

Service Capacity

Cost

Aplicación de teoría de Colas

Problema:

Simulación del tiempo de espera de un cliente en la fila de un

banco antes de que sea atendido


Tiempo Tiempo Tiempo del Tiempo de

Cliente llegada salida servidor espera

1 0.4 2.4 2 0

2 1.6 3.1 0.7 0.8

3 2.1 3.3 0.2 1

4 3.8 4.9 1.1 0

5 4.0 5.2 0.3 0.9

6 5.6 8.6 3 0

NA=0 (No. De clientes atendidos)

NNA=0 (No. De clientes no atendidos)

NS=1 (No. De servidores)

T=600 minutos (tiempo servicio) L=20 (cantidad personas máximo en la fila) Dist. Poisson para llegadas

Dist. Exponencial para salida

S =0 (Estado del servidor)

Wq=0 (T. promedio espera en fila) Lq=0 (T. promedio clientes en fila)

Tts=0 (Tiempo total del servicio)

Ttl=0 (Tiempo total de llegadas)

Tto=0 (Tiempo total)

Cf=0 (No. De clientes en la fila)

Inicio

S=0 No

Si

t. llegadas

4

4

l

Tto=Tto+Ttl

L<20 Si

No

cf=cf+1

NNA=NNA+1 t. servicio

t>600

No

Fin de la simulación

NA=0 (No. De clientes atendidos)

NNA=0 (No. De clientes no atendidos)

t=600 minutos (tiempo servicio)

L=20 (cantidad personas máximo en la fila) Dist. Poisson para llegadas

Dist. Exponencial para salida

Wq=0 (T. promedio espera en fila)

Lq=0 (T. promedio clientes en fila)

tts=0 (Tiempo total del servicio)

tl=0 (Tiempo total de llegadas)

tt=0 (Tiempo total)

cf=0 (No. De clientes en la fila)

4

4

l

t. salidas

Dist. Exponencial

Para llegadas λ=4

Return

t. llegadas

Dist. Poisson para llegadas λ=4

Return


Teoria de colas

Education

Transcript of Teoria de colas