Siguiente:El sistema M/M/1/kNivel anterior:Modelos de colas estocásticosPrevia:Modelos de colas estocásticos

El modelo M/M/1

En primer lugar, se describe el modelo:

1.

$M/\cdot/\cdot$: El proceso de llegadas es de Poisson homógeneo con tasa $\lambda >0$.

Sea T la variable aleatoria que representa el tiempo entre dos llegadas consecutivas.

Sea t>0 y representemos por n(t) el número de llegadas al sistema hasta el instante t.

Como los incrementos son independientes:

$$P(T\leq t) = 1 - P(T\geq t) =1- P(n(t)=0) =1- e^{-\lambda t},$$

luego $T\equiv Exp(\lambda)$. Recíprocamente, se tiene el siguiente resultado:

Si $T_1,T_2 \ldots$ son independientes, siendo T_i  el tiempo transcurrido entre las llegadas (i-1)-ésima e i-ésima, todas ellas con distribución $Exp(\lambda)$, entonces $n(t)\equiv P(\lambda t)$.

Demostración:
 
 

$$P(n(t)\leq n)=P(T_1+T_2+\dots + T_n +T_{n+1}>t)=\int_t^\infty {e^{-\lambda x}\frac{\lambda^{n+1}x^n}{n!}dx}=$$ $$=\left\vert \begin{array}{ccc}v & = & x-t \\dv & = & d......ty {e^{-\lambda (v+t)} \frac {(v+t)^n \lambda^{n+1}}{n!} dv} =$$ $$=\int_0^\infty {e^{-\lambda (v+t)}\frac {\lambda^{n+1}}{n!}......mbda (v+t)} \frac {\lambda^{n+1} t^iv^{n-i}}{i!(n-i)!} dv} =$$ $$=\sum_{i=0}^n \frac {\lambda^{n+1} t^i}{i!(n-i)!}e^{-\lambd...... \\dv & = & \frac {du}{\lambda}\end{array} \right\vert =$$ $$\sum_{i=0}^n \frac {\lambda^{n+1} t^i}{i!(n-i)!}e^{-\lambda......} du} = \sum_{i=0}^n \frac{\lambda^i t^i}{i!} e^{-\lambda t}.$$

(El último paso se hace considerando la expresión de la función gamma)
 

2.

$\cdot /M/ \cdot$: Siempre que el servidor esté ocupado, el proceso de salida es de Poisson homogéneo de tasa $\mu>0$.

Razonando como antes, se tiene que los tiempos de servicio son $Exp(\mu)$.

3.

$\cdot / \cdot / 1 / \infty$: El sistema tiene un único servidor y capacidad infinita.

Se trata de un proceso de nacimiento y muerte con tasa de nacimiento $\lambda_n=\lambda$,$n\geq 0$ y tasa de muerte $\mu_n=\mu$,$n\geq 1$.

Debe observarse que la distribución exponencial tiene ausencia de memoria, es decir, si $T\equiv$ Exp($\lambda$), entonces

$$P(T\geq t+s \vert T>s) = P(T\geq t) \ \forall t,s>0.$$

La demostración de esta propiedad es inmediata observando la expresión de la función de distribución asociada.

Ahora se puede proceder a analizar el comportamiento del sistema. Se define la intensidad del tráfico como

$$\rho = \frac{\lambda}{\mu}.$$

Si $\rho\geq 1$, no se alcanza el estado estacionario, mientras que si $\rho<1$, entonces sí que se llega a este estado.

Sea P_n(t)=P(N(t)=n) la probabilidad de que en el instante t haya n clientes en el sistema. Yendo a las ecuaciones que se obtuvieron para un proceso de nacimiento y muerte, tenenos que

$$\left\{ \begin{array}{ccc}P_0'(t) & = & -\lambda P_0(t)-\m......{n-1}(t)+\muP_{n+1}(t)\ \forall n\geq 1\end{array}\right.$$

En el estado estacionario (a partir de aquí suponemos ya $\rho<1$) se tiene el siguiente sistema, denominado ecuaciones de equilibrio:

$$\left\{ \begin{array}{ccc}0 & = & -\lambda P_0+\mu P_1\\......n+\lambda P_{n-1}+\mu P_{n+1}, \n\geq 1\end{array}\right.$$ $$\left\{ \begin{array}{ccc}0 & = & -\rho P_0+ P_1\\0 & = ......+\rho )P_n+\rho P_{n-1}+P_{n+1}, \ n\geq 1\end{array}\right.$$ $$\left\{ \begin{array}{ccc} P_1 & = & \rho P_0\\ P_2 & = & \......\\ \vdots\\ P_{n+1} & = & \rho^{n+1} P_0\end{array}\right.$$

Así, como la suma de todas las probabilidades debe ser uno y $\rho<1$, se tiene

$$1=\sum_{n=0}^{+\infty} P_n = \sum_{n=0}^{+\infty} \rho^n P_0 =\frac {P_0}{1-\rho}\Rightarrow$$ $$P_0 = 1-\rho.$$

Luego

$$P_n = (1-\rho)\rho^n\ , \ n\geq0.$$

En consecuencia, la variable N (distribución estacionaria del número de clientes en el sistema) sigue una distribución geométrica $G(1-\rho)$. Se sigue que

$$E(N)=\frac{\rho}{1-\rho} \quad \quad Var(N)=\frac{\rho}{(1-\rho)^2}.$$

De igual modo, si por L se representa el número de clientes en cola en el estdo estacionario, entonces

$$\begin{array}{rl} L= & \left\{ \begin{array}{ccc}0 & si & N=0,\ 1\\N-1 & si & N\geq 2.\end{array}\right. \end{array}$$

Las probabilidades asociadas son

$$P(L=0)=P(N=0)+P(N=1)=P_0 + P_1=1-\rho+(1-\rho)\rho=1-\rho^2.$$ $$P(L=l)=P(N=l+1)=P_{l+1}=(1-\rho)\rho^{\thinspace l+1}, \l\ge 1.$$

La esperanza de esta variable es

$$E(L)=\sum_{l=1}^\infty{lP(L=l)}=\sum_{l=1}^\infty{l(1-\rho)......=1}^\infty{l (1-\rho) \rho^l}=\rhoE(N)=\frac{\rho^2}{1-\rho}.$$

Finalmente, consideremos la variable V, tiempo de espera virtual en estdo estacionario. Se trata de una variable mixta:

$$\begin{array}{rl}V = &\left\{ \begin {array}{ccccc}0 & ......+ S_n & si & N & = & n\geq 1.\end{array} \right.\end{array}$$

S'₁ es el tiempo de servicio restante del cliente que está en el servidor. Haciendo uso de la propiedad de pérdida de memoria de la variable exponencial (pues $S_1 \equiv Exp(\mu)$) se tiene

$$P(S'_1\ge t) = P(S_1\geq s+t \vert S_1\geq s)= P(S_1\geq t),$$

por lo que $S'_1\equiv Exp(\mu)$ y es indistinto considerar la variable S₁ o la variable S'₁ a efectos de calcular probabilidades.

Ahora ya podemos calcular la función de distribución F_V  asociada a la variable V.

Si v=0 entonces

$$F_V(0)=P(N=0)=1-\rho.$$

Si v>0, haciendo uso del teorema de la probabilidad compuesta (pues el valor n asociado a v es aleatorio) y del hecho de que

$$S_1+\dots+S_n \equiv \Gamma(n,\mu),$$

se tiene

$$F_V(v) = P(V\leq v) = \sum_{n=0}^{+\infty} P(V\leq v \vert N=n) P(N=n)=$$ $$= P(V\leq v \vert N=0) P(N=0) + \sum_{n=1}^{+\infty} P(V \leqv \vert N=n) P(N=n) =$$ $$=1 \cdot (1-\rho) + \sum_{n=1}^{+\infty}P(S_1 + \dots + S_n \leq v) (1-\rho) \rho^n =$$ $$=1 - \rho + \sum_{n=1}^{+\infty} (1-\rho) \rho^n \int_0^v e^{......)} \sum_{n=1}^{+\infty} \frac {\lambda ^n t^{n-1}}{(n-1)!} dt =$$ $$= (1-\rho) + (1-\rho)\lambda \int_0^v e^{-\mu t} e^{\lambda t......}{\lambda - \mu} \right] _0^v = 1 - \rho e^{(\lambda - \mu) v}.$$

Luego

$$F_V(v) = 1-\rho e^{(\lambda - \mu) v} \ , \ v\geq 0.$$

Análisis de los ciclos de ocupación y desocupación

Sea T₀= la longitud de un ciclo de desocupación y sea T₁= la longitud de un ciclo de ocupación. La longitud (media) de un ciclo de ocupación y desocupación (en estado estacionario) será E(T₀+T₁). Como, por la propiedad de pérdida de memoria, se tiene que $T_0 \equiv Exp(\lambda)$, entonces $E(T_0)=\frac{1}{\lambda}$. Por otra parte, como P₀ representa la proporción de tiempo que el servidor está desocupado (o lo que es lo mismo, el sistema está vacío) en estado estacionario, entonces

$$\frac{E(T_0)}{E(T_0+T_1)} = P_0 = 1-\rho\Rightarrow$$ $$E(T_0+T_1)=\frac {\frac{1}{\lambda}}{1-\rho} = \frac {1}{\lambda(1-\rho)} = \frac {1}{\rho (\mu - \lambda)}.$$

Diagrama de flujos para M/M/1

Definimos un grafo como sigue:

• cada nodo representa un estado,
• cada arco representa una transición entre estados,
• en los arcos se indica la tasa de cambio.

 

Ahora vemos que se obtienen las mismas ecuaciones que se tenían anteriormente, pues considerando que se produce una conservación de flujos en el grafo se tiene:

$$\begin{array}{cccccc}&\text{Nodo \enspace} 0 & : & \lambda ......mbda + \mu)P_n & = &\lambda P_{n-1} + \mu P_{n+1} \end{array}$$

Interpretación: como $\lambda$ y $\mu$ son, respectivamente, el número medio de llegadas y el de servicios por unidad de tiempo, entonces $\lambda P_n$,$\mu P_n$ y $(\lambda + \mu) P_n$ son a su vez el número de llegadas, el de servicios y el de sucesos por unidad de tiempo en el estado n.
 

Control de una cola con un solo servidor

Vamos a tratar de optimizar el funcionamiento de un sistema M/M/1 en el que el servidor se ausenta a veces.

El servidor está atendiendo clientes hasta que el sistema se vacía. Entonces él se retira y no vuelve a ofrecer su servicio hasta que en la cola hay un número Q de clientes.

La tasa de llegadas es $\lambda$ y la de servicio es $\mu$, siendo$\rho<1$.

Se definen los siguientes costes del sistema:

• coste de k unidades monetarias cada vez que el servidor vuelve (es un coste fijo).
• coste de h unidades monetarias por cada cliente en el sistema y unidad de tiempo (coste de mantenimiento).

Se trata de determinar el valor de Q para que el sistema funciona a coste mínimo por unidad de tiempo.

El coste de mantenimiento por unidad de tiempo (en promedio) es $E(N) \cdot h$.

El coste fijo por unidad de tiempo es $\frac {k}{E(T_0+T_1)}$, pues E(T₀+T₁) es la longitud media de un ciclo de ocupación y desocupación.

Así, la función objetivo es

$$hE(N) + \frac {k}{E(T_0+T_1)}.$$

El diagrama de flujos asociado es el siguiente:
 
 

Además, para este problema se usa la siguiente notación:

• P_n=P(N=n),
• P_n(1)=P(N=n y hay servidor),
• P_n(0)=P(N=n y no hay servidor).

Es inmediato que P_n=P_n(0)+P_n(1).

Se obtienen las siguientes ecuaciones:

(Nodos de arriba)
 
 

$$\left\{ \begin{array}{ccrccc}(n & = & 0) & \mu P_1(1) & = ......ambda P_{Q-2}(0) & = & \lambda P_{Q-1}(0)\end{array} \right.$$

(Nodos de abajo)
 
 

$$\left \{ \begin{array}{lcrccc} (n & = & Q) & \lambdaP_{Q-1}......u P_{n+1}(1) & = &(\lambda + \mu) P_n(1)\end{array} \right.$$

En definitiva:

$$\left \{ \begin{array}{cccccccc}\lambda P_0(0) & = & \lamb......a + \mu)P_n(1) & , \ n\geq 2, n \neq Q\end{array} \right.$$

Para resolver este sistema vamos a utilizar la función generatriz de probabilidades G(s) asociada a la variable aleatoria N.

Sea $\vert s\vert\leq 1$.

$$G(s) = \sum_{n=0}^{+\infty} P_n s^n \quad \left (=\sum_{n=0}^{Q-1} P_n(0) s^n + \sum_{n=1}^{+\infty} P_n(1) s^n\right) .$$

Si se define

$$G_0(s) = \sum_{n=0}^{Q-1} P_n(0) s^n \quad \quadG_1(s)= \sum_{n=1}^{+\infty} P_n(1) s^n$$

entonces

G(s) = G₀(s) + G₁(s).

Como además

$$G'(s) = \sum_{n=1}^{+\infty} n P_n s^{n-1},$$

se tiene que

$$G(1)=1 \quad \quad G'(1)=E(N).$$

Si ahora se multiplica por sⁿ⁺¹ la ecuación n-ésima en el sistema que se obtuvo:

$$\left \{ \begin{array}{ccc}s \mu P_1(1) & = & \lambda P_0(0...... s^{n+1} \\(\ n \geq2 \ , \ n \neq Q)\end{array} \right.$$

Sumando ahora todas estas igualdades:

$$s \mu P_1(1) + \lambda \sum_{n=2}^{+\infty} P_{n-1}(1) s^{n+1......} \lambda P_0(0) + \mu \sum_{n=1}^{+\infty} P_{n+1}s^{n+1} =$$ $$=(\lambda + \mu) \sum_{n=1}^{+\infty} P_n(1)s^{n+1} + \lambda P_0(s)\Rightarrow$$ $$\lambda s^2 G_1(s) + \lambda s^{Q+1} P_0(0) + \mu G_1(s) =(\lambda+ \mu) s G_1(s) + \lambda s P_0(0)\Rightarrow$$ $$G_1(s) = \frac {\rho s}{1-\rho s} (1+s+\dots+s^{Q-1})P_0(0).$$

Por otra parte,

$$G_0(s) = \sum_{n=0}^{Q-1} s^n P_n(0) = \sum_{n=0}^{Q-1} s^nP_0(0) = (1+s+\dots+s^{Q-1})P_0(0).$$

Así, evaluando G(s) en s=1 se tiene que

$$P_0(0) = \frac {1-\rho}{Q},$$

por lo que

$$G(s) = G_0(s)+G_1(s) = \dots = \frac {1+s+\dots+s^{Q-1}}{Q}\frac {1-\rho}{1-\rho s}.$$

Ahora debemos calcular E(N) y E(T₀+T₁).

$$G'(1)=\frac{Q-1}{2}+\frac{\rho}{1-\rho}=E(N).$$

E(T₀)= tiempo medio para que el sistema pase de 0 a Q clientes.

Como el tiempo entre llegadas sigue una $Exp(\lambda)$ y esta distribución tiene pérdida de memoria, entonces es equivalente a calcular Q veces el tiempo medio para que llegue un cliente.

$$E(T_0) = Q E[Exp(\lambda)] = Q \ \frac {1}{\lambda} = \frac{Q}{\lambda}.$$

$\frac {E(T_0)}{E(T_0+T_1)} =$ probabilidad de que haya 0,1,..., Q-1 clientes en el sistema en estado estacionario y no haya servidor

$$=P_0(0)+P_1(0)+\dots +P_{Q-1}(0)=Q P_0(0).$$ $$E(T_0+T_1) = \frac {E(T_0)}{Q P_0(0)} = \frac {Q \frac{1}{\...... {1}{\lambda \frac {1-\rho}{Q}} =\frac {Q}{\lambda (1-\rho)}.$$

Así

$$f(Q) = h E(N) + \frac {k}{E(T_0+T_1)} = h \left ( \frac {Q-1}......\rho} \right) + \frac {k \lambda (1-\rho)}{Q} ,Q=1,2,3 \dots$$

Buscamos el valor donde f alcance su mínimo; si Q tomara valores reales,

$$f'(Q)=\frac {h}{2} - \frac {k \lambda (1-\rho)}{Q^2} = 0\Rightarrow$$ $$\tilde{Q} = \sqrt{\frac{2k \lambda (1-\rho)}{h}}.$$

Como

$$f''(\tilde{Q}) = \frac {3h}{2} \sqrt {\frac{h}{2k\lambda (1-\rho)}}>0,$$

entonces $\tilde{Q}$ sería mínimo local y global.

Como Q sólo toma valores naturales y la función f es convexa, entonces la solución óptima Q^* será la que dé el mínimo de entre f([Q^*]) y f([Q^*]+1).

El valor

$$Q^*= \sqrt{\frac{2k \lambda (1-\rho)}{h}}$$

se denomina tamaño de lote de Wilson.