El modelo de cola M/M/c

Teor´ıa de las colas
R´emi BESSON
21 de Enero de 2015

1

Introduci´
on
Vamos a necesitar los siguientes resultados generales de cadenas de Markov continua
y procesos de nacimiento y muerte en el estudio de la cola M/M/c.
Sea X una cadena de Markov continua.
pi,j (t) = P [X(t) = j | X(0) = i]
P (t) = [pi,j (t)], i, j ∈ S
El teorema de Chapman-Kolmogorov: ∀t, T > 0, pi,j (T + t) =lo cual se expresa de forma matricial P [T + t] = P [T ]P [t].

k

Definimos la matriz de densidad de transici´on como Q = l´ımh→0

P (h)−I
h

pi,k (T )pk,j (t)

pi,j (h)−pi,j (0)
p (h)
= l´ımh→0 i,jh
h
p (h)−p (0)
p (h)−1
l´ımh→0 i,i h i,i = l´ımh→0 i,i h

Tenemos qi,j = l´ımh→0
qi,i =

Utilizando el teorema de Chapman-Kolmogorov tenemos
pi,j (h + t) = k pi,k (h)pk,j (t) =k=i pi,k (h)pk,j (t) + pi,i (h) + pi,j (t)
Entonces

pi,j (h+t)−pi,j (t)
h

=

k=i

pi,k (h)
h pk,j (t)

+

pi,i (h)−1
pi,j (t)
h

pi,j (h+t)−pi,j (t)
h
pi,k (h)
p (h)−1
l´
ım
(
)p
ımh→0 ( i,i h )pi,j (t)
h→0
k,j (t) + l´
k=i
h

Y pi,j (t) = l´ımh→0
=
=

k=i qi,k pk,j (t)

+ qi,i pi,j (t)

Es decir P (t) = QP (t) llamada ecuaci´on backward deChapman-Kolmogorov.
De manera an´
aloga pi,j (t + h) = k pi,k (t)pk,j (h)
= k=j pi,k (t)pk,j (h) + pi,j (t)pj,j (h)
Y entonces

pi,j (t+h)−pi,j (t)
h

=

k=j

pi,k (t)pk,j (h) + pi,j (t)(pj,j (h) − 1)

pi,j (h+t)−pi,j (t)
h
pk,j (h)
p (h)−1
l´
ım
p
(t)
+ pi,j (t) j,j h
h→0
i,k
k=j
h
k=j pi,k (t)qk,j + pi,j (t)qj,j

pi,j (t) = l´ımh→0
=
=

Es decir P (t) = P (t)Q llamadaecuaci´on forward de Chapman Kolmogorov.
Las cadenas de Markov continuas tienen una importante subclase que son los procesos
de nacimientos y muertes. En esos procesos solo se puede pasar de un estado a un estado
vecino.
Suponemos que nuestra cadena de Markov X(t) es un proceso de nacimiento y muerte de
tasa:
2

3
qi,i+1 = λi y qi,i−1 = µi , qi,j = 0 si j = i y j = i + 1 y j = i − 1 y qi,i = −(λi+ µi )
La ecuaci´
on forward de Chapman Kolmogorov da:
pi,j (t) =
k=j pi,k (t)qk,j + pi,j (t)qj,j = pi,j−1 (t)qj−1,j + pi,j+1 (t)qj+1,j + pi,j (t)qj,j =
pi,j−1 (t)λj−1 + pi,j+1 (t)µj+1 − (λj + µj )pi,j (t)
pi,0 = −λ0 pi,0 (t) + µ1 pi,1 (t)
Si escribimos Pj (t) = P (X(t) = j) y que suponemos que al tiempo t = 0 el sistema
empeza a i, tal que Pj (0) = P (X(0) = j) = δi,j
Entonces Pj (t) =pi,j (t)
Y la ecuaci´
on forward de Chapman Kolmogorov se puede escribir como:
Pj (t) = Pj−1 (t)λj−1 + Pj+1 (t)µj+1 − (λj + µj )Pj (t) (∗)
P0 (t) = −λ0 P0 (t) + µ1 P1 (t)

2

El modelo M/M/c, estudio de la
funci´
on de probabilidad
estacionaria
El modelo M/M/c significa que tenemos un sistema donde el tiempo entre dos llegadas
de los clientes sigue una ley exponencial (es un procesode Poisson) de tasa λ
Notamos Ti el momento en el cual llega el cliente n´
umero i, Ti → Exp(λ)
Suponemos adem´
as que el tiempo de servicio sigue tambi´en una ley exponencial de tasa
µ independiente del tiempo entre llegadas.
Por fin suponemos que nuestro sistema tiene una sola cola y c servicios. Aplicaremos tambi´en el principio FIFO (first in first out).
El caso c = 1 ya ha sido tratadoen clase.

La siguiente nota es importante para aplicar los resultados de la teor´ıa de los procesos
de nacimiento y muerte a M/M/c.
Si hay n clientes con n < c, n servicios son ocupados, el intervalo de tiempo entre dos
servicios cumplidos, es decir el tiempo entre dos salidas, sigue una ley exponencial de tasa
nµ.
En efecto si se anota Si el tiempo entre la llegada y la salida delcliente n´
umero i,
Si → Exp(µ) por hip´
otesis. Y tenemos que mini∈[1,n] [Si ] → Exp(nµ).
En efecto lo vamos a demostrar por n = 2:
S1 → Exp(µ) y S2 → Exp(µ) entonces Z = min[S1 , S2 ] → Exp(2µ)
FZ (t) = P (Z ≤ t) = 1−P (Z > t) = 1−P (S1 > t)P (S2 > t) = 1−(1−FS1 (t))(1−FS2 (t)) =
1 − exp(−µt) exp(−µt) = 1 − exp(−2µt) por t > 0.
Si hay n clientes siendo n ≥ c todos los servicios est´an...