1
$\begingroup$

The Problem

Consider the following system:

  • Customers arrive according to a Poisson process with intensity $\lambda$ over a time period $[0,T]$.

  • There are two servers $X$ and $Y$ that can serve the customers; the service times of $X$ and $Y$ are exponentially distributed with intensities $\lambda_X$, $\lambda_Y$.

When a customer arrives, there are three scenarios:

  • if $X$ is empty, he gets served by $X$.
  • if $X$ is not empty and $Y$ is, he gets served by $Y$.
  • if both $X$ and $Y$ are busy, he sits in line and goes to the first available server. In line, first come first serve.

Q1: What is the probability that $Y$ never serves a customer over $[0,T]$?

Q2: More generally, what is the probability that $Y$ serves $K$ customers over $[0,T]$?


Attempts

For question 1, we can observe that this is equivalent to the serving time always being smaller than the inter-arrival time. If $p = \lambda_X/(\lambda_X+\lambda)$ is the probability that the customer gets served before the next one arrives, we can express the answer to Q1 as something along the lines of

$$ \exp(-\lambda T) + \sum_{n = 1}^{\infty} \frac{\exp(-\lambda T)(\lambda T)^{n}}{n!} \times p^{n - 1} $$ because conditional on zero or one customers we have probability $1$, while conditional on $n>1$ customers we need to serve before the next arrival. This does not seem very promising.

I wrote a small simulation for the system in python, and plotting the probability over 10000 samples against $\lambda$ for fixed $\lambda_X=1$ and $T=1$ we obtain something like this:

enter image description here

This seems nice and smooth, so maybe an easy closed formula exists. If you want to tinker with this script, I can make it public.

After this, I get stuck; I don't really understand how I should be treating the various conditional probabilities on the events that define the problem. Any effort, even partial, would be much appreciated.

I'm not very familiar with queueing theory and this problem just came to my mind, so there may be some relevant literature or names for objects that I am not aware of. If you could point to something, I would be grateful.

$\endgroup$
1
$\begingroup$

This is a quick thought on you first question (Q1). It can be approached as follows.

I assume that initially X is empty. Introduce the following notation. Let

$R(i,x)$ be the probability of the event "during period $[0,x]$ exactly $i$ new customers arrive, X is empty at $t=0$, Y never serves customers during $[0,x]$";

$Q(i,x)$ be the probability of the event "during period $[0,x]$ exactly $i$ new customers arrive, X is busy at $t=0$, Y never serves customers during $[0,x]$".

The case $i=0$ is simple. We have $$ R(0,x)=e^{-\lambda x}, \ Q(0,x)=e^{-\lambda x}. $$

Let $H_k$ denote the event "during $[0,T]$ exactly $k$ customers arrive". Let $A$ denote the event "Y never serves a customer during $[0,T]$". Clearly, $$ P(A)=\sum_{k=0}^\infty P(A \cap H_k). $$ Here $A \cap H_k$ denotes the intersection of two events, meaning that both of them occur. Events $A$ and $H_k$ are dependent. Let us compute the probability $P(A \cap H_k)$ in terms of $R(i,x)$ and $Q(i,x)$. From the law of total probability we get: $$ P(A \cap H_0)=R(0,T), $$ $$ P(A \cap H_k)=\int_0^T \lambda e^{-\lambda y} Q(k-1,T-y) dy, \ k \ge 1. $$

Putting all together, we get: $$ \tag{1} \label{eq1} P(A)=e^{-\lambda T} + \int_0^T \lambda e^{-\lambda y} \sum_{k=0}^\infty Q(k,T-y) dy. $$

Now what is left unknown, is the relation for $\sum_{k=0}^\infty Q(k,x)$. Let us write out the relations for $R(i,x)$ and $Q(i,x)$. For any $x\in [0,T]$ we have $$ Q(i,x)=\int_0^x \underbrace{\mu e^{-\mu y}}_{service \ ends \ at \ y < x \ \ } \underbrace{e^{-\lambda y}}_{no \ arrival \ until \ service \ completion} R(i,x-y) dy $$ $$ + \underbrace{\int_x^\infty \mu e^{-\mu y} dy}_{if \ service \ ends \ after \ x, \ any \ arrival \ will \ go \ to \ Y} \times 0= $$ $$ \tag{2} \label{eq2} =\int_0^x \mu e^{-(\lambda+\mu) y} R(i,x-y) dy, \ i \ge 1. $$ By using the same argumentation for $R(i,x)$, we get: $$ \label{eq3} \tag{3} R(i,x)=\int_0^x \lambda e^{-\lambda y} Q(i-1,x-y) dy, \ i \ge 1. $$

So, equations \eqref{eq1}, \eqref{eq2}, \eqref{eq3} solve the question Q1 (if i haven't made a mistake somewhere :-) ). Probably one can simplify everything by doing the integration step by step. But I did not do that. In fact I have serious doubts that something simpler will show up.

The reason is the following. Denote $Q(x)=\sum_{k=0}^\infty Q(k,x)$, $R(x)=\sum_{k=1}^\infty R(k,x)$. Note that from \eqref{eq2} for $Q(x)=\sum_{k=0}^\infty Q(k,x)$ we have the following Fredholm equation of the second kind: $$ Q(x) = e^{-\lambda x} (1- e^{-\mu x}) + \int_0^x \mu e^{-(\lambda+\mu) y} R(x-y) dy. \label{eq4} \tag{4} $$ From \eqref{eq3} for $R(x)=\sum_{k=1}^\infty R(k,x)$ we have the Fredholm equation of the first kind: $$ \label{eq5} \tag{5} R(x) = \int_0^x \lambda e^{-\lambda y} Q(x-y)dy. $$

Functions $Q(x)$ and $R(x)$ consistute the system of integral equations. I am not aware of explicit solutions to such systems of integral equations like \eqref{eq4}-\eqref{eq5}.

B.w.t. Your question Q2 can be approached in a similar manner.

$\endgroup$
  • $\begingroup$ Many thanks for your input. I was beginning to suspect this. In fact, I was able to compute the series mentioned in the question, but this proved to be only a good approximation when $\lambda >> \mu$; I believe this is due to the effect of truncation. I will post an edit with some more thoughts soon, but I agree that no closed form solution seems to exist. $\endgroup$ – Lonidard Nov 1 '18 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.