colas

TRANSPARENCIAS

TEORÍA DE COLAS

TEORÍA DE COLAS

• DEFINICIÓN

• IMPORTANCIA DE LA GESTIÓN DE LAS

LÍNEAS DE ESPERA

capacidad de servicio

te

Figura 1.1.

OBJETIVOS DE LA TEORÍA DE COLAS: • CARACTERIZACIÓN CUALITATIVA Y

CUANTITATIVA DE LA LÍNEA DE ESPERA. • OPTIMIZACIÓN DE LA LÍNEA DE ESPERA.

TEORÍA DE COLAS - 1 .

ESTRUCTURA BÁSICA DE UNA LÍNEA DE ESPERA

PoblaciónI

llegada

II

ColaIII

selección

IV

Mecanismode servicio

V

salida

VI

Sistema de Colas

Figura 2.1. 1.- POBLACIÓN • POBLACIÓN FINITA

• POBLACIÓN INFINITA


2.- CARACTERÍSTICAS DEL PROCESO DE LLEGADA AL SISTEMA

Controlable

Incontrolable

Únicas

Lotes

Estructura

Tamaño de las llegadas

Constante

Exponencial o de Poisson

De Erlang

Otra

Distribución

Analiza la situación y decide marcharse

Aguanta un poco y después se va

Nivel de paciencia Paciente (se queda)

Impaciente

Figura 2.2.


3.- CARACTERÍSTICAS DE LA COLA

• NÚMERO DE COLAS

FIFO

LIFO

Primero reservas

Primero emergencias

Mayores beneficios

Menor tiempo de procesado

Otras prioridades

Disciplina de

la cola

Figura 2.7.

• CAPACIDAD DE LAS COLAS 4.- SELECCIÓN DE LA COLA


5.- INSTALACIÓN DE SERVICIO Una fase

Multifase

Una fase

Multifase

De varioscanales a uno

Una fase

Multifase

Rutasalternativas

Única

Multicanal

Mixta

Estructura

Figura 2.8.

• ESTRUCTURA • TASA DE SERVICIO

6.- SALIDA DEL SISTEMA


TERMINOLOGÍA Y NOTACIÓN ....... / ....... / ........ / ........ Distribución de tiempos entre llegadas Distribución de tiempos de servicio Número de servidores Tamaño de la población en donde:

M Distribución exponencial. D Distribución degenerada (tiempos constantes). Ek Distribución Erlang (con parámetro de forma k). G Distribución General (permite cualquier distribución arbitraria)

s = Número de servidores (canales de servicio en paralelo). λn = Tasa media de llegadas µn = Tasa media de servicio para todo el sistema Pn = Probabilidad de que exactamente n clientes se encuentren en el sistema. L = Número esperado de clientes en el sistema.

Lq = Longitud esperada de la cola (excluye los clientes que estén en servicio). W = Tiempo de espera en el sistema (incluido el tiempo de servicio), para cada cliente.

Tiempo de espera en la cola (se excluye el tiempo de servicio), para cada cliente. Wq =


PROCESOS DE NACIMIENTO Y MUERTE 1. Dado N(t)=n , la distribución de probabilidad actual del tiempo que falta para el próximo

nacimiento (llegada) es exponencial con parámetro λn (n=0,1,2,...). 2. Dado N(t)=n , la distribución de probabilidad actual del tiempo que falta para la próxima

muerte (terminación del servicio) es exponencial con parámetro µn (n=0,1,2,...). 3. Solo un nacimiento o una muerte pueden ocurrir en un mismo instante.


P

Cnn

0

1

1

1=

+=

∞

∑ donde Cn

n n

n n

= − −

−

λ λ λ λµ µ µ µ

1 2 1 0

1

1 2

K

KL P P P n P n Pn n

n= ⋅ + ⋅ + ⋅ + + ⋅ + = ⋅

=

∞

∑0 1 20 1 20

K K PL n sq nn s

= −=

∞

∑ ( )

FORMULAS DE LITTLE L W

L Wq q

= ⋅= ⋅

λλ

MODELOS DE COLAS BASADOS EN LOS PROCESOS DE NACIMIENTO Y MUERTE 1.- MODELO M/M/s s=1 s>1

P =1-0 ρ P = (1- )nnρ ρ

P(L > z) (z+1)= ρ P(W > t) = e tP(W > t) = e t

q- (1 )t

- (1 )t

ρ µ ρ

µ ρ

−

−

≥≥

⎧⎨⎩

00

L( - )

q

2

= λµ µ λ

W =( - )qλ

µ µ λ

L =-λ

µ λ W = 1

µ λ−

P 11n!

+ 1S!

SS -n=0

S-1 n S0 =⎛⎝⎜

⎞⎠⎟

⎛⎝⎜

⎞⎠⎟⎛⎝⎜

⎞⎠⎟∑ λ

µλµ

µµ λ

PS S

P para

Pn!

P para n

n n S

n

n

n

=⎛⎝⎜

⎞⎠⎟

=⎛⎝⎜

⎞⎠⎟

⎧

⎨

⎪⎪

⎩

⎪⎪

−

1

1

0

0

! ( )λµ

λµ

n S

< S

≥

L(S -1)! (S - )

Pq

S

2=⎛⎝⎜

⎞⎠⎟

10

λµ

λµµ λ

L L= +qλµ

W

Lq

q=λ

W W= + 1q µ


2.- MODELO M/M/s CON FUENTE DE POBLACIÓN FINITA s=1 s>1 λn=(m-n)λ para n = 0, 1, 2, ...,m λn=(m-n)λ para n = 0, 1, 2, ...,m λn=0 para n ≥ m λn=0 para n ≥ m µn=µ para n = 1, 2, ... µn=nµ para n = 1, 2, ..., s µn=sµ para n = s, s+1, s+2, ... PP

= m!(m - n)

nn

0 !λµ

⎛⎝⎜

⎞⎠⎟ P = 1

PPn=0

mn

0

0∑

P mm n n

P para 0 n S

P m!(m - n)! S! S P para S < n m

n

n

n n S

n

0

=−

⎛⎝⎜

⎞⎠⎟ ≤ ≤

=⎛⎝⎜

⎞⎠⎟ ≤

⎧

⎨

⎪⎪

⎩

⎪⎪ −

!( )! !

( )

λµ

λµ

0 P 1PPn=0

mn

0

0

=

∑

L = m - + (1-P )q

λ µλ 0

0 L =L +(1-P )q L = (n - S)Pqn=S

m

n∑ L = nPn=0

m

n∑

W =L

(1-P )qq

µ 0

W = W + 1q µ

W = Wq +1µ

W =L

m Lqq

λ( )−


3.- MODELO M/M/s/Q CON COLA DE ESPACIO LIMITADO s=1 s>1 λn=λ para n = 0, 1, 2, ...,Q-1 λn=λ para n = 0, 1, 2, ...,Q-1 λn=0 para n ≥ m λn=0 para n ≥ m µn=µ para n = 1, 2, ... µn=nµ para n = 1, 2, ..., s µn=sµ para n = s, s+1, s+2, ...

P = Q0 11

1−

− +

ρρ

P =n Qn1

1 1−

−⎛⎝⎜

⎞⎠⎟+

ρρ

ρ

∑∑+=

−

⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎟⎠

⎞⎜⎜⎝

⎛⎟⎟⎠

⎞⎜⎜⎝

⎛=

Q

Sn

SnSnS

=n SS!1+

n!1

1P

10

0

µλ

µλ

µλ

PS S

P para n S

Pn!

P para n S

n n S

n

n

n

=⎛⎝⎜

⎞⎠⎟ =

=⎛⎝⎜

⎞⎠⎟ =

⎧

⎨

⎪⎪

⎩

⎪⎪

−

1

1

0

0

! ( )λµ

λµ

+1, ... , Q

1, 2, ... ,

L = L Pq − +1 0 ( )[ ]( )( )L =Q QQ Q

Q

ρ ρ ρ

ρ ρ

1 11 1

1

1

− + + ⋅

− −

+

+ L = n S Pq

n S

Q

n( )− ⋅=∑ L = n P

n

Q

n=∑ ⋅

0

W = L

λ W =

Lq

q

λ ( )P λ λ= Q1− W = L

λ W =

Lq

q

λ ( )λ λ= PQ1−


4.- MODELO M/M/s CON POBLACIÓN FINITA Y COLA DE ESPACIO LIMITADO 5.- MODELO M/M/s CON TASA DE LLEGADA Y/O TASA DE SERVICIO

DEPENDIENTES DEL ESTADO DEL SISTEMA

TASA DE SERVICIO DEPENDIENTE DEL ESTADO DEL SISTEMA Sea µn = ncµ1 para n = 1, 2, ... donde:

n número de clientes en el sistema. µn tasa media de servicio cuando hay n clientes en el sistema. µ1 tasa de servicio “normal” esperada (1/µ1 es el tiempo esperado para servir a un cliente

cuando es el único en el sistema). c “coeficiente de presión”, constante positiva que indica el grado en el que la tasa de

servicio del servidor resulta afectada por el estado del sistema.

TASA DE LLEGADA DEPENDIENTE DEL ESTADO DEL SISTEMA

λn = (n+1)-b λ0 para n = 0, 1, 2, ... TEORÍA DE COLAS - 11 .

Figura 5.7. Valores de P0 para el modelo dependiente del estado.

Ls=2s=1

Figura 5.8. Valores de L para el modelo dependiente del estado.

MODELOS DE COLAS CON DISTRIBUCIONES NO EXPONENCIALES MODELO M/G/1

• Entrada Poisson (tiempos entre llegadas exponenciales), con una tasa media de llegadas λ. • Los tiempos de servicio son independientes, con la misma distribución de probabilidad, que

puede ser cualquiera. Solo es necesario conocer (o estimar) la media 1/µ y la varianza σ2 de la distribución.

P0 1= − ρ

( )Lq =⋅ +

−λ σ ρ

ρ

2 2 2

2 1 ( FÓRMULA DE POLLACZEK-KHINTCHINE )

LL WL

qq=λ

W Wq= +1µ

q= +ρ

MODELO M/G/s

• No se ha llegado a resultados manejables TEORÍA DE COLAS - 12 .

MODELO M/D/1

• Entrada Poisson (tiempos entre llegadas exponenciales), con una tasa media de llegadas λ.

• El servidor realiza para todos los clientes una labor rutinaria que es siempre la misma por lo que tiende a haber poca variabilidad en el tiempo de servicio requerido. Por lo tanto se puede suponer que el tiempo de servicio es una constante fija (distribución de tiempos de servicio DEGENERADA), con valor 1/µ y varianza σ2 = 0.

• Para 1 sólo servidor, se trata de un caso particular del modelo anterior (M/G/1), con σ2 = 0 , con lo que las fórmulas quedan:

Figura 6.1. Distribución degenerada (M/D/s).

P0 1= − ρ ( )Lq = −ρ

ρ

2

2 1 W

Lq

q=λ

LL W Wq= +1µ

q= +ρ

MODELO M/D/s


MODELO M/Ek/1 El modelo M/Ek/1 será una caso especial del modelo M/G/1 donde los tiempos de servicio tienen una distribución Erlang de parámetro k. Aplicando las fórmulas de Pollaczek-Khintchine con σ2=1/kµ2

Figura 6.2. Tiempo de servicio Erlang y s=2.

( ) ( )L k k

kq =⋅

+

−= =

+⋅

−

λµ

ρ

ρλ

µ µ λ

2

22

2

2 112

KK ( )W kkq =+

⋅−

12

λµ µ λ

W Wq= +1µ

L = λ W

MODELO M/Ek/s Uso de tablas TEORÍA DE COLAS - 14 .

MODELOS SIN ENTRADAS POISSON

G/M/s no se supone ninguna restricción para el tiempo entre llegadas. D/M/s todos los tiempos entre llegadas son iguales a una constante fija, lo que representa

a un sistema de colas en el que se programan las llegadas a intervalos regulares (figura 6.3.).

Ek/M/s se supone una distribución de Erlang para los tiempos entre llegadas (figura 6.4.).

Figura 6.4. Modelo Ek/M/s.

Figura 6.3. Modelo D/M/s.


REDES DE COLAS 1.- SISTEMA DE COLAS EN SERIE

Propiedad de Equivalencia. Supóngase que una instalación de servicio tiene ‘s’ servidores, un proceso de entrada Poisson con parámetro λ, y la misma distribución de los tiempos de servicio para cada servidor con parámetro µ (M/M/s), en donde ρ=λ/sµ<1. Entonces, la salida en estado estable de esta instalación de servicio también es un proceso de Poisson de media λ.


2.- REDES DE JACKSON Una red de Jackson es un sistema de m instalaciones donde la instalación i (i=1,2,...,m) tiene:

1. Una cola de capacidad infinita. 2. Clientes que llegan de fuera del sistema de acuerdo a un proceso de entrada Poisson de

parámetro ai. 3. Un número de servidores si, con la misma distribución exponencial con parámetro µi, para

los tiempos de servicio. 4. Un cliente que deja la instalación i, puede salir del sistema o bien puede ir a otra

instalación j (j=1,2,...,m y j≠i), con probabilidad Pij. La probabilidad de salir del sistema es: qi

jj i

= −=≠

∑11

Pij

m

Las Redes de Jackson reciben ese nombre debido a que fue Jackson quien descubrió una propiedad que es vital para el análisis:

Bajo condiciones de estado estable, cada instalación j (j=1,2,...,m) de una red, se comporta como si fuera un sistema de colas M/M/s independiente, con tasa de llegadas

m

λ λj jii j

a= + ⋅=≠

∑ i ij

P1

donde sjµj>λj. TEORÍA DE COLAS - 17 .

MODELOS DE COLAS CON DISCIPLINA DE PRIORIDADES 1.- SISTEMA DE PRIORIDADES SIN INTERRUPCIÓN

WA B Bk

k k

=⋅ ⋅

+−

1 1 para k = 1, 2, ..., N 1 µ

en donde: A s s

rrj

ss

j

j

s

= ⋅−⎛

⎝⎜⎞⎠⎟

+=

−

∑!!

µ λµ

0

1

si s = 1 A =2

→⎛⎝⎜

⎞⎠⎟

µλ

B0 = 1

Bsk

ii

k

= − =∑

1 1λ

µ para k = 1, 2, ..., N

s = número de servidores. µ = tasa media de servicio por servidor ocupado. λi = tasa media de llegadas para la clase de prioridad i, para i = 1, 2, ..., N.

N

λ λ ==∑ ii 1

r = λµ

Todos estos resultados suponen que λ µi

i

k

s=∑ <

1


2.- SISTEMA DE PRIORIDADES CON INTERRUPCIÓN

WB Bk

k k

=⋅−

1

1

µ para k = 1, 2, ..., N.

para el caso de 1 servidor (s = 1). Cuando s>1, Wk se puede calcular mediante un proceso iterativo que se ilustrará con el ejemplo siguiente. Lk, Lqk y Wqk se pueden obtener igual que para el caso de prioridades sin interrupción.

L Wk k k= λ para k = 1, 2, ..., N. W Wqk k= −

1µ

para k = 1, 2, ..., N

L Wqk k qk= λ para k = 1, 2, ..., N TEORÍA DE COLAS - 19 .

colas

Documents