7/24/2019 12_t_cola_rs

1/9

Teora de Colas

Modelo G/M/1 y G/M/k

Rodrigo Salas Fuentes

Universidad Tecnica Federico Santa Mara

Departamento de Informatica

Profesor: Hector Allende

1 Introduccion

En este trabajo se estudia el modelo mediante el cual los clientes llegan alos servidores en forma aleatoria. Cuando llegan deben esperar en una colahasta que son servidos, una vez servidos se supone que ellos dejan el sistema.

Se considera el modelo con tiempo de servicio exponencial, pero el tiempoentre llegadas de los clientes tienen una distribucion arbitraria.

Algunos definiciones basicas de colas son las siguientes:

L : es el numero promedio de clientes en el sistema.

LQ: es el numero promedio de clientes esperando en la cola.

W:tiempo promedio que el cliente pasa en el sistema.

WQ: tiempo promedio que el cliente pasa esperando en la cola.

Razon promedio a la cual el sistema gana=amonto promedio que pagaun cliente entrante.

a es la razon promedio de llegada de un cliente entrante.

N(t): es el numero de clientes que llegan en un tiempo t.

Luego se tiene lo siguiente:

a = limt

N(t)

t

7/24/2019 12_t_cola_rs

2/9

Si se supone que cada cliente paga $1 por unidad de tiempo en el sistema,

entonces tenemos la formula de Little:L= aWSimilarmente, si se paga $1 cuando se encuentra en la cola:LQ= aWQLuego, el numero de clientes en servicio = aE[s] donde E[s] es definido

como el tiempo promedio que un cliente gasta en servicio.

1.1 Probabilidades de Estado Estacionario

SeaX(t) el numero de clientes en el sistema en el tiempo t, y sea Pn,n >0definido por:

Pn = limt

P{X(t) =n}

Donde Pn es la probabilidad a largo plazo de que habra exactamenten clientes en el sistema. Alguna veces se denomina como probabilidad deestado estacionario de exactamente n clientes en el sistema.

Ademas se tiene:

an = proporcion de clientes que encuentran n en el sistema cuandoellos llegan.

dn =proporcion de clientes que dejan atras n en el sistema cuando

ellos se van.

2 El Modelo G/M/1

El modelo G/M/1 asume que el tiempo entre llegadas sucesivas poseen unadistribucion arbitraria G. El tiempo de servicio se distribuye exponencial-mente con razon m y existe solo un servidor.

La dificultad en el analisis de este problema se basa en el hecho de que elnumero de clientes en el sistema no son suficientes para servir como espaciode estado. Se necesita conocer el numero en el sistema y el tiempo queha pasado desde la ultima llegada. Para abordar este problema se debera

mirar al sistema cuando el cliente llega; entonces definamos Xn, n 1 por:Xnel numero en el sistema como se ve en la llegada n-esima.El proceso {Xn, n 1 } es una cadena de Markov. Para calcular las

probabilidades de transicion Pij, primero hay que notar que, a medida deque existan clientes para ser servidos, el numero de servicios en cualquiertramo de tiempo es una variable aleatoria de Poisson con esperanza t. Esto

7/24/2019 12_t_cola_rs

3/9

se debe a que el tiempo entre servicios sucesivos es exponencial, por lo tanto,

el numero de servicios constituyen un proceso de Poisson. Es decir,

Pi,i+1j =

0et

(t)j

j! dG(t)

j = 0, 1,...,iya que si en una llegada encuentra i en el sistema, entonces en la pr oxima

llegada encontrara i+1 menos el numero servido, y la probabilidad de que jsea servido facilmente se ve que iguala el lado derecho de arriba ( a traves delcondicionamiento en el tiempo entre llegadas sucesivas). La formula paraP0(la probabilidad de que al menos i+1 eventos de Poisson ocurren en untiempo aleatorio teniendo distribucion G) es un poco diferente y pude ser

obtenido como:

Pi0= 1i

j=0

Pi,i+1j

Las probabilidades lmites k, k=0,1,..., puede ser obtenido como solucionunica de:

k =i

iPik

, k 0

k

k = 1

la cual en este caso se reduce a:

k =

i=k1 i

0 et (t)

i+1k

(i+1k)!dG(t) k 1 (1)

0

k = 1

Para resolver la ecuacion (1), intentemos una solucion de la forma k =ck. Se sustituye en (1), y luego se obtiene lo siguiente:

ck =c

i=k1

i

0et

(t)i+1k

(i + 1 k)!dG(t)

=c

0etk1

i=k1

(t)i+1k

(i + 1 k)!dG(t) (2)

7/24/2019 12_t_cola_rs

4/9

Sin embargo,

i=k1

(t)i+1k

(i + 1 k)!=

j=0

(t)j

j! =et

y la ecuacion 2 se reduce a:

k =k1

0et(1)dG(t)

o

=

0et(1)dG(t) (3)

La constante c puede ser obtenida de

k

k = 1

, lo cual implica que:

c0

k = 1

oc= 1 Comok es la unica solucion de (1), yk = (1)

k satisface, entonces:

k = (1 )k

, k 0donde es la solucion de la ecuacion (3), donde los valores de son

obtenidos numericamente.Comok es la probabilidad lmite en que una llegada ve k en el sistema

cuando un cliente llega. Entonces:W =

kE[tiempo en el sistemallegada ve k](1 )

k

=k

k+ 1

(1 )k

Ya que si una llegada ve k, entonces el gasta k+1 perodos de servicios enel sistema.

= 1

(1 )

Ya que se usa0

kxk = x

(1 x)2

7/24/2019 12_t_cola_rs

5/9

y

WQ= W 1 =

(1)

L= W = (1)

LQ= WQ= (1)

(4)

donde es el recproco del intervalo de tiempo medio. Esto es:

1

=

0xdG(x)

Por lo tanto:W es exponencial con razon(1 ),

WQ=

0 con probabilidad 1 - exponencial con razon(1 ) con probabilidad

donde W y WQ es el tiempo que el cliente pasa en el sistema y en lacola, respectivamente.

Sin embargo, ak = (1)k es la probabilidad que una llegada vea k

en el sistema, no es igual a la proporcion de tiempo durante el cual hay ken el sistema, ya que el proceso de llegada no es Poisson. Para obtenerPk,primero hay que ver que la razon por la cual el numero en el sistema cambiade k-1 a k debe ser igual a la razon a la cual cambia de k a k-1. Luego, larazon a la cual cambia de k-1 a k es igual a la razon de llegadamultiplicado

por la proporcion de llegadas que encuentran k-1 en el systema. Esto es:La razon en la cual el sistema va de k-1 a k = ak1De forma similar, la razon por la cual el numero cambia en el sistema

de k a k-1 es igual a la proporcion de tiempo durante el cual existe k en elsistema multiplicado por la razon de servicio (constante). Esto es:

La razon en la cual el sistema va de k a k-1 = PkCalculando estas razones, nos lleva a:

Pk =

ak1k 1

Luego,

Pk =

(1 )k1k 1

y, como P0= 1

k=1 Pk obtenemos:

P0= 1

7/24/2019 12_t_cola_rs

6/9

2.1 Los perodos ociosos y ocupados del G/M/1

Supongase que una llegada ha encontrado el sistema vaco (entonces comienzael perodo ocupado), y sea N el numero de clientes servidos en el perodoocupad9o. Como la llegada N-esima encontrara tambien el sistema vaco,entonces N es el numero de transiciones en la cadena de Markov para ir delestado 0 al estado 0. Por lo tanto, 1/E[N] es la proporcion de transicionesque toma a la cadena de Markov en el estado 0; o equivalentemente, es laproporcion de llegadas que encuentran el sistema vaco. Por lo tanto,

E[N] = 1

a0=

1

1

Tambien, como el proximo perodo ocupado comienza despues de la lle-gada N-esima, entonces el tiempo de ciclo(es decir, la suma de los perodosociosos y ocupados) es igual al tiempo hasta la llegada N-esima. En otraspalabras, la suma de los perodos ocupados y ociosos puede ser expresadocomo la suma de los tiempos de N llegadas. Por lo tanto, si Ti es el timepode llegada i-esima despues que el perodo ocupado comienza, entonces

E[Ocupado] + E[ocioso] =E[Ni=1

Ti]

=E[N]E[T]

= 1(1 )

(5)

Ademas se tiene:

1 P0= E[ocupado]

E[Ocioso] + E[ocupado]

y como P0= 1

y reemplazando con (5), entonces:

E[ocupado] = 1

(1 )

E[ocioso] =

(1 )

7/24/2019 12_t_cola_rs

7/9

3 El Modelo G/M/k

En este modelo se suponen k servidores, los cuales sirven con una razonexponencial . Sin embargo, no se permite que el tiempo entre llegadassucesivas tenga distribucon arbitraria. Para asegurar que existe una dis-tribucion de estado estable, se asume las condiciones 1/G < k donde Ges la media de G

Si se defineXncomo el numero en el sistema en el momento de la n-esimallegada, entonces:

Xn+1= Xn+ 1 Yn

n 0donde Yn es el numero de salidas durante los tiempos llegadas entre la

llegada n y la n+1. Por lo que las probabilidades de transicion se puedencalcular como:

Caso 1: j > i + 1 entonces Pij = 0

Caso 2: j i + 1 k

En este caso si una llegada ve i en el sistema, entonces como i < k,entonces la nueva llegada entrara inmediatamente al servicio. Por esto,la proxima llegada encontrara j si los i+1 servicios, exactamente i+1-j

son completados durante los tiempos entre llegadas. Condicionandosobre los tiempos entre los tiempos entre llegadas, nos lleva a:

Pij =P{i+1j de i + 1 servicios son completados entre los tiempos de llegadas

=

0P{i+1j de i + 1 son completados |el tiempo entre llegadas t}dG(t)

=

0(i+1j )(1 e

t)i+1j(et)jdG(t)

donde la ultima igualdad se debe a que el numero de servicios comple-tados en un tiempo t tiene una distribucion binomial.

Caso 3: i + 1 j k

Para evaluar Pij en este caso, primero vemos que cuando todos losservidores estan ocupados, el proceso de partida es un proceso de Pois-son con razonk. Por esto, condicionando sobre los tiempos entre lasllegadas se tiene:

7/24/2019 12_t_cola_rs

8/9

Pij =P{i + 1j departures}

=

0P{i + 1jsalidas en el tiempo t}dG(t)

=

0ekt

(kt)i+1j

(i + 1j)!dG(t)

Caso 4: i + 1 k > jEn este caso, como todos los servidores se encuentran ocupados, elproceso de partida es un proceso de Poisson, entonces el tiempo paraque existan solo k en el sistema tendra una distribucion gama conparametros i+ 1 k,k (el tiempo hasta el evento i+ 1 k de unproceso de Poisson con razonkocurre si tiene una distribucion gamacon parametros i+ 1 k,k). Condicionando primero en el tiempoentre llegadas hasta cuando existan solo k en el sistema, entonces:

Pij =

0P{i + 1j salidas en el tiempo t}dG(t)

=

0

t0

P{i+1j salidas en el tiempo t|Tk = s}keks (ks)

ik

(i k)!dsdG(t)

=

0

t0

(kj )(1 e(ts))kj(e(ts))jkeks

(ks)ik

(i k)!dsdG(t)

donde la ultima igualda se debe a que como k personas en serviciosen el tiempo s, el numero cuyo servico terminara en el tiempo t esbinomial con parametros k y 1 e(ts).

Ahora se puede verificar que las probabilidades lmites de esta cadenade Markov es de la siguiente forma:

k1+j =cj, j=0,1,. . .

Sustituyendo dentro de la ecuacion j =

i iPij cuando j > k nosda que esta dado por:

7/24/2019 12_t_cola_rs

9/9

=

0ekt(1)dG(t)

Los valores de 0, 1, 2, . . . , k2, puede ser obtenido resolviendo re-cursivamente las primeras k-1 ecuaciones del estado estacionario, y cpuede ser calculado usando

0 i= 1

Si WQ denota el tiempo que un cliente pasa en la cola, entonces:

WQ=

0 con probabilidad

k10 i= 1

c1

Exp(k(1 )) con probabilidadk i= 1 c1

dondeExp(k(1)) es una variable aleatoria exponencial con razonk(1 )