Problem 10.5

4.13.1 Problem 10.5

Solution

In the above, $i$ is the number of broken machines in the queue. $m$ is maximum capacity of the operating room. The goal is to keep this room ﬁlled to its capacity. In other words, to keep $m$ machines in operations. $n$ is the capacity of the spare room.

Calculating arrival rates:

Need to determine $p_{i,i+1}\left ( h\right ) .$ This can happen when one machine fails, but no server completes its service meanwhile. Hence we do not need to consider the servers part in this analysis. There are 2 cases to consider:

$i\leq n$ (there are $m$ machines in operations)
\[ p_{i,i+1}\left ( h\right ) =\begin {pmatrix} m\\ 1 \end {pmatrix} \left ( \lambda h+o\left ( h\right ) \right ) \left ( 1-\lambda h+o\left ( h\right ) \right ) ^{m-1}+o\left ( h\right ) \]
In the above, the last term $o\left ( h\right ) $ accounts for other possible conditions under which $i$ can increase by one but which is considered to be less likely, such as 2 machines break down and one server completes its service. In the above, $\left ( 1-\lambda h+o\left ( h\right ) \right ) ^{m-1}$ simpliﬁes to zero when $h$ is very small, hence the above equation becomes
\[ p_{i,i+1}\left ( h\right ) =m\lambda h+o\left ( h\right ) \]
Comparing the above with the Hence we see $p_{ij}\left ( h\right ) =q_{ij}h+o\left ( h\right ) $ we see that$\ q_{i,i+1}=m\lambda $ or in other words,
\[ \fbox {$\lambda _{i}=m\lambda \ \ \ \ \ \ \ \ \ i\leq n$}\]
$n<i\leq n+m$ (there are less than $m$ machines in operations)
\begin{align*} p_{i,i+1}\left ( h\right ) & =\begin {pmatrix} m-\left ( i-n\right ) \\ 1 \end {pmatrix} \left ( \lambda h+o\left ( h\right ) \right ) \left ( 1-\lambda h+o\left ( h\right ) \right ) ^{m-\left ( i-n\right ) -1}+o\left ( h\right ) \\ & =\left ( m+n-i\right ) \lambda h+o\left ( h\right ) \end{align*}

Hence we see that $q_{i,i+1}=\left ( m+n-i\right ) $ or in other words,
\[ \fbox {$\lambda _{i}=\left ( m+n-i\right ) \ \ \ \ \ \ \ \ \ \ \ \ \ n<i\leq n+m$}\]

Calculating departure rates:

Need to determine $p_{i,i-1}$, this can happen when a server completes its job but no machine fails meanwhile, Hence we only need to consider the servers. There are 2 cases to consider:

$1\leq i<s$ (Queue is empty and not all servers at working on ﬁxing machines at hand)
\begin{align*} p_{i,i-1}\left ( h\right ) & =\begin {pmatrix} i\\ 1 \end {pmatrix} \left ( \mu h+o\left ( h\right ) \right ) \left ( 1-\mu h+o\left ( h\right ) \right ) ^{i-1}+o\left ( h\right ) \\ & =i\mu h+o\left ( h\right ) \end{align*}

Hence $q_{i,i-1}=i\mu $, or since this is a birth/death process, we write
\[ \mu _{i}=i\mu \ \ \ \ \ \ \ \ 1\leq i<s \]
$s\leq i$ (All servers at busy)
\begin{align*} p_{i,i-1}\left ( h\right ) & =\begin {pmatrix} s\\ 1 \end {pmatrix} \left ( \mu h+o\left ( h\right ) \right ) \left ( 1-\mu h+o\left ( h\right ) \right ) ^{s-1}\left ( 1-\lambda h+o\left ( h\right ) \right ) ^{m-\left ( i-n\right ) }+o\left ( h\right ) \\ & =s\mu h+o\left ( h\right ) \end{align*}

Hence $q_{i,i-1}=s\mu $, Hence
\[ \mu _{i}=s\mu \ \ \ \ \ \ \ \ s\leq i \]

Therefore, we summarize all the above as follows

Arrival rate $\lambda _{i}=m\lambda $ for $i\leq n$ and $\lambda _{i}=\left ( m+n-i\right ) \ \lambda $ for $\ \ n<i\leq n+m$

$.$

Departure rate $\mu _{i}=i\mu $ for $\ 1\leq i<s$ and $\mu _{i}=s\mu $ for $s\leq i$

Notice that arrival rate does not depend on the number of servers $s$.

The following state transition diagram illustrates the above result, with arrows leaving/entering states show the rate of arrival and departure on them per the above result. To make the diagram easier to make, I assume the following values: $s=3,m=5,n=2$

Notice that $\mu _{0}=0$ and $\lambda _{n+m}=0$ as expected.

Now compute the steady state distribution $\pi $ (This is not asked for in this problem, but need to do this to solve problem 12.3 later on and implement it)

Starting with the balance equation, where to balance the rate out of a state, with the rate into a state. We have

\[ \pi _{j}v_{j}={\displaystyle \sum \limits _{k\neq j}} q_{kj}\pi _{k}\]

Hence for state $i=0$ we have

\[ \pi _{0}v_{0}=q_{1,0}\pi _{1}\]

But $v_{0}=\lambda _{0}$ and $q_{1,0}=\mu _{1}$ hence

\begin{equation} \pi _{0}\lambda _{0}=\mu _{1}\pi _{1} \tag {1}\end{equation}

For state $i=1$ we have

\[ \pi _{1}v_{1}=q_{0,1}\pi _{0}+q_{2,1}\pi _{2}\]

but $v_{1}=\lambda _{1}+\mu _{1}$, $q_{0,1}=\lambda _{0},q_{2,1}=\mu _{2},$hence the above becomes

\begin{align*} \pi _{1}\left ( \lambda _{1}+\mu _{1}\right ) & =\lambda _{0}\pi _{0}+\mu _{2}\pi _{2}\\ \pi _{1}\lambda _{1}+\pi _{1}\mu _{1} & =\lambda _{0}\pi _{0}+\mu _{2}\pi _{2}\end{align*}

But from (1) we have $\mu _{1}\pi _{1}=\lambda _{0}\pi _{0}$, hence the above becomes

\begin{align} \pi _{1}\lambda _{1}+\lambda _{0}\pi _{0} & =\lambda _{0}\pi _{0}+\mu _{2}\pi _{2}\nonumber \\ \pi _{1}\lambda _{1} & =\mu _{2}\pi _{2} \tag {2}\end{align}

Continue this way, we obtain that

\[ \pi _{i}\lambda _{i}=\mu _{i+1}\pi _{i+1}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=0,1,2,\cdots ,n+m \]

From the above, if we solve in terms of $\pi _{0}$ we obtain that

\begin{equation} \pi _{i}=\frac {\lambda _{0}\lambda _{1}\cdots \lambda _{i-1}}{\mu _{1}\mu _{2}\cdots \mu _{i}}\pi _{0}\ \ \ \ \ \ \ \ \ \ \ \ i=0,1,2,\cdots ,n+m \tag {3}\end{equation}

and with the equation $\pi _{0}+\pi _{1}+\cdots +\pi _{n+m}=1$ we can now solve for all $\pi _{i}$ as follows

\begin{align*} \pi _{0} & =1-\left ( \pi _{1}+\cdots +\pi _{n+m}\right ) \\ & =1-\left ( \frac {\lambda _{0}}{\mu _{1}}+\frac {\lambda _{0}\lambda _{1}}{\mu _{1}\mu _{2}}+\cdots +\frac {\lambda _{0}\lambda _{1}\cdots \lambda _{n+m-1}}{\mu _{1}\mu _{2}\cdots \mu _{n+m}}\right ) \pi _{0}\end{align*}

Hence

\begin{align*} \pi _{0}\left ( 1+\left ( \frac {\lambda _{0}}{\mu _{1}}+\frac {\lambda _{0}\lambda _{1}}{\mu _{1}\mu _{2}}+\cdots +\frac {\lambda _{0}\lambda _{1}\cdots \lambda _{n+m-1}}{\mu _{1}\mu _{2}\cdots \mu _{n+m}}\right ) \right ) & =1\\ \pi _{0} & =\frac {1}{1+\left ( \frac {\lambda _{0}}{\mu _{1}}+\frac {\lambda _{0}\lambda _{1}}{\mu _{1}\mu _{2}}+\cdots +\frac {\lambda _{0}\lambda _{1}\cdots \lambda _{n+m-1}}{\mu _{1}\mu _{2}\cdots \mu _{n+m}}\right ) }\end{align*}

Now that $\pi _{0}$ is found, we can ﬁnd the remaining $\pi _{i}$ using (3)

[next] [front] [up]