Queue theory - M/D/k - Probability of never having a queue before a time T

Question

This is probably a known result, but I couldn't find any resource pointing directly to the issue I'm trying to solve.

Suppose you start a logistic mission that needs that during its time $T_m$ a given object is always working. At the beginning of your mission, you have an instance of this object working plus $k$ spare items that could replace the object if a random failure (that happens with a given rate $\lambda$) occurs. Furthermore, after the occurrence of a failure, the broken instance is repaired in a fixed time $T_r$.

A mission is successful if there is at least one item working for its entire time.

What I want to calculate is the probability that the mission is successful. It is obvious that this problem is a queue problem. In fact:

• The failures are the calls (or the customers) arriving at the desk;
• the spare items are the number of operators;
• $T_r$ is the duration of the call (which is fixed, in this case).

However, I'm not interested in the probability at the equilibrium that I'm running out of items nor in the average number of items under repair, which are the quantities that are most often found in queue theory. I'm interested in the following:

What is the probability that there is no queue in a M/D/k system before a fixed $T_m$ time?

We can say that the system is initially empty, since the $k$ spare items are all brand-new and ready to replace a broken item.

This is where I'm in at the moment:

• If $T_m<T_r$ than the mission is successful if $k$ or less failures occur, so we have:

$$P(\text{success}) = \sum_{i=0}^k e^{-\lambda T_m} \frac{(\lambda T_m)^i}{i!}$$

• For $k=1$, after doing some calculations, I found that:

$$P(\text{success}) = e^{-\lambda T} \sum_{j=0}^{n+1} \frac{\lambda^j}{j!} (T_m-(j-1)T_r)^j$$

where $n=\lfloor\frac{T_m}{T_r}\rfloor$.

The last result matches with a simulation that covers the general case (with arbitrary $k$) that I wrote in R (if requested, I could provide it). I'm not arriving at the general result.

Answer 1

The analytic results for the $M/D/k$ queue, from the paper by G.J.Franx (cited above by Ritz), may provide a solution. But it seems to me that just the law of total probability may work here.

Here is the idea for the case $k=1$.

Let $T=T_m$ be that fixed time instant, which you need. And let $\lambda$ be the Poisson failure rate and $d=T_r$ be the repair time (which is a constant).

Introduce two probabilities: $$ P_0(u,T)=\mathbb{P}(\max_{t\in[u,T]}X(t)\le 1|X(u)=0), $$ $$ P_1(u,T)=\mathbb{P}(\max_{t\in[u,T]}X(t)\le 1|X(u)=1). $$

There is a delicate difference in these probabilities.

$P_0(u,T)$ is the probability that the total number of customers in the system will never be greater than 1, if at instant $t=u$ there were $0$ customers in the system.

$P_1(u,T)$ is the probability that the total number of customers in the system will never be greater than 1, if at instant $t=u$ there was $1$ customer in the system and its service has just started.

Right now it looks to me (it means that I may be wrong) that the probabilities $P_0(u,T)$ and $P_1(u,T)$ are related by the following integral equations (which follow from the law of total probability and the fact that the service time is constant): $$ P_0(u,T) = e^{-\lambda(t-u)} + \int_u^T \lambda e^{-\lambda y} P_1(y,T)dy, $$ $$ P_1(u,T) = \mathbf{1}_{\{T-u<d\}} e^{-\lambda(T-u)} + \mathbf{1}_{\{T-u>d\}} e^{-\lambda d} P_0(u+d,T). $$

Here $\mathbf{1}_{\{A\}}$ is the indicator function, meaning that $\mathbf{1}_{\{A\}}=1$ if $A$ is true and $0$ otherwise. The values on the boundaries are: $P_0(T,T)=1$, $P_0(T,T)=1$.

These equations for sure can be solved numerically (I cannot see any analytic solution right away. Laplace transform technique does not seem to be of great help here due to finite integration region. Still numerical inversion may work.). The quantity that you need is $P_0(0,T)$.

The case $k\ge 2$ surely will be more tricky (and hard) since we have to remember the remaining service time of $(k-1)$ customers (i.e. the total number of arguments in the integral equation will be $k$). Thus it is hard to say now if this idea leads to any feasible solution for a general $k$.