Poisson Process Queueing System!

**kingwinner** · March 31st 2011, 07:47 PM

Hi!

Consider a two-server parallel queueing system where customers arrive according to a Poisson process with rate λ, and where the service times are exponential with rate μ. Moreover, suppose that arrivals finding both servers busy immediately depart without receiving service (such a customer is said to be lost), whereas those finding at least one free server immediately enter service and then depart when their service is completed.

a)If both servers are presently busy, find the expected time until the next customer enters the system. [answer: 1/(2μ) + 1/λ]

b)Starting empty, find the expected time until both servers are busy. [answer: 2/λ + μ /λ^2]
=========================================

I'm really really confused by this problem, to the point of being desperate.

First of all, I think I'm a little confused about the question itself (i.e. the setup). I believe the situation here is that we have one line and two parallel servers. But then what does it mean by "customers arrive according to a Poisson process with rate λ"? Arriving at where? Arriving at the line or the servers?

Next, for part a, I don't understand how we can rigorously justify the answer. Why is it not just 1/(2μ)?

I am seriously puzzled and really need your help.
Thanks in advance!

**SpringFan25** · April 1st 2011, 03:26 AM

I would assume that customers arrive at the queue according to the poisson process, and then decide whether to enter the queue or leave as per the rules in the question.

for (a)
I interpret "enter the system" as "join the queue".

The expected time for this will be
E(time until there is a free slot) + E(time for someone to arrive once a slot is free).

Noting that the additional time taken for someone to arrive once a spot is free is independant of the time that the slot became free (memorylessness property of poisson process)

The waiting time of a $Poisson(\lambda)$ is $exp(\lambda)$ with mean $\frac{1}{\lambda}$

$E(\text{Time someone enters the system})=\frac{1}{2\mu} + \frac{1}{\lambda}$

Your post suggests you already understand where $\frac{1}{2\mu}$ comes from.

**kingwinner** · April 1st 2011, 08:33 AM

Originally Posted by SpringFan25

I would assume that customers arrive at the queue according to the poisson process, and then decide whether to enter the queue or leave as per the rules in the question.

for (a)
I interpret "enter the system" as "join the queue".

The expected time for this will be
E(time until there is a free slot) + E(time for someone to arrive once a slot is free).

Noting that the additional time taken for someone to arrive once a spot is free is independant of the time that the slot became free (memorylessness property of poisson process)

The waiting time of a $Poisson(\lambda)$ is $exp(\lambda)$ with mean $\frac{1}{\lambda}$

$E(\text{Time someone enters the system})=\frac{1}{2\mu} + \frac{1}{\lambda}$

Your post suggests you already understand where $\frac{1}{2\mu}$ comes from.

Hi, thanks for your time and effort in providing a response. Your help is much appreciated.

By "join the queue", do you mean a new customer (sucessfully) enters one of the two servers?

Also, I'm not sure if I understand why this is a Poisson process and the meaning of N(t) in this particular setting.

For a Poisson process, N(t)~Poisson(λt), so N(t) would have possible values 0,1,2,3,... . But how can that be the case here? There can't be more than one person on the line (becuase customers will immediately leave if there is no free server). Is the random variable N(t) representing the number of custmoers who sucessfully entered into one of the two servers in the time interval [0,t]? Or does it also include the lost (i.e.depart without receiving service) custmoers? For example, if N(t)=5, what does that actually mean in words for our problem?

I think I need some clarifications on these matters before moving on. I do have a follow up question on part a, but I think it be most effective if I first of all understand the situation more clearly.

Thanks.

**SpringFan25** · April 1st 2011, 10:14 AM

To avoid ambiguity, lets have these definitions (which are not intended to be consistent with terms used in my earlier post):

Arrive at the system: Customer appears. He will either enter the system or walk away if all servers are full.

Enter the system: There was space at one of the servers so the customer goes to that server

My interpretation of the question would be that $N(t) \sim Po(\lambda t)$ is the number of customers who have arrived at the system up to time t.

**kingwinner** · April 2nd 2011, 10:14 AM

Originally Posted by SpringFan25

To avoid ambiguity, lets have these definitions (which are not intended to be consistent with terms used in my earlier post):

Arrive at the system: Customer appears. He will either enter the system or walk away if all servers are full.

Enter the system: There was space at one of the servers so the customer goes to that server

My interpretation of the question would be that $N(t) \sim Po(\lambda t)$ is the number of customers who have arrived at the system up to time t.

OK, this greatly clarifies the situation and the setup of the problem.

a) Let's first talk about the first copmonent, E(time until there is a free slot).

We are given that "both servers are presently busy". Let's call the "present time" time 0. Say customer 1 is at server 1 and customer 2 is at server 2.
Let S1=the service time for customer 1 as measured from time 0.
S2=the service time for customer 2 as measured from time 0.
Then S1~exp(μ), S2~exp(μ) => min{S1,S2}~exp(2μ)
=> E(time until there is a free slot)=E[min{S1,S2}]=1/(2μ) ?

However, I'm worrying that this might be wrong?

The statement of the problem seems to suggest the TOTAL service time for a customer is exponential(μ), i.e. time is measured from the point when customer 1 FIRST enters server 1. Customer 1 may have entered server 1 before time 0.
But the distribution we need is the distribution of "the service time for customer 1 as measured from time 0". How can we find it?

This is the first thing I do not understand.

Thanks for explaining!

**SpringFan25** · April 2nd 2011, 11:05 AM

We are given that "both servers are presently busy". Let's call the "present time" time 0. Say customer 1 is at server 1 and customer 2 is at server 2.
Let S1=the service time for customer 1 as measured from time 0.
S2=the service time for customer 2 as measured from time 0.
Then S1~exp(μ), S2~exp(μ) => min{S1,S2}~exp(2μ)
=> E(time until there is a free slot)=E[min{S1,S2}]=1/(2μ) ?

Yes. I assume you know or have proven that Min(S1,S2) ~ exp(2u).

However, I'm worrying that this might be wrong? The statement of the problem seems to suggest the TOTAL service time for a customer is exponential(μ), i.e. time is measured from the point when customer 1 FIRST enters server 1. Customer 1 may have entered server 1 before time 0.
But the distribution we need is the distribution of "the service time for customer 1 as measured from time 0". How can we find it?

This is an impressive observation!

We are indeed interested in the distrubution of serving times from time 0. However, this is the same as the distribution of the serving time from any other point (given that they are still waiting at time 0). This is because the exp() is memoryless.

Formally:

$Let~ X\sim exp(\mu)$

f(x) is the pdf of x
F(x) is the cdf of x
F(X|x>t) is the cdf of X, given x>t

by definition:
$F(X|X>t) = P(X<g|x>t) = \displaystyle \frac{\int_t ^{g} f(x) dx}{P(X>t)}$

$P(X<g|x>t) = \displaystyle \frac{\int_t ^{g} f(x) dx}{1-F(t)}$

$P(X<g|x>t) = \displaystyle \frac{\int_t ^{g} \mu e^{-\mu x} dx}{e^{-\mu t}}$

$P(X<g|x>t) = \displaystyle \frac{\left[-e^{-\mu x}\right]_t^{g}}{e^{-\mu t}}$

$P(X<g|x>t) = \displaystyle \frac{\left[-e^{-\mu g} + e^{-\mu t}\right]}{e^{-\mu t}}$

$P(X<g|x>t) = \displaystyle 1- e^{-\mu (g-t)} ~~~~~~[1]$

$F(X|X>t) = \displaystyle 1- e^{-\mu (x-t)} ~~~~~~[1]$

So far so good. Now, define the waiting time after t as w.
$w=X-t$ (provided X>t)

$P(W<w|X>t) = P(X<w+t|x>t)$

we can use (1) to get the probability on the right hand side
$P(W<w|X>t) = P(X<w+t|x>t) = 1- e^{-\mu (w+t-t)$

$P(W<w|X>t) = P(X<w+t|x>t) = 1- e^{-\mu w}$

But this is just an exponential cdf, with parameter mu.

So we conclude that the remaining waiting time from any point is distributed as an exponential with parameter mu.

**kingwinner** · April 3rd 2011, 06:11 AM

Thank you for your great explanation!

a) Let X=time until there is a free slot
Y=time until the first arrival once a slot is free
S1=the service time for customer 1 as measured from time 0.
S2=the service time for customer 2 as measured from time 0.

Then
E(time until the next customer enters the system)
=E(X+Y)
=E(X)+E(Y)
=E[min{S1,S2}] +E(Y)
=1/(2μ) +E(Y)

Now to calculate E(Y), we need the distribution of Y. Does it matter WHEN the previous customer arrived at the system (and leaved because all servers were busy)? Say a free slot frees up at time 8, and the last arrival of customers in the time interval [0,8] may be at time 7.9, or it may be at time 7. Is this going to affect our calculations? Why or why not?

Or maybe I should rephrase my question: For a Poisson process {N(t): t>=0} with rate λ, the "interarrival times" of events are all i.i.d. exp(λ). So in particular, the time until the occurrence of the first event as measured from time 0 is exp(λ). But now let's say we are at time 5, then what is the distribution of the time until the occurrence of the next event as measured from time 5? Is it still always going to be exp(λ)? Why or why not?

I'm guessing that these may possibly be related to the memoryless property, but I'm still finding it to a bit sloppy or unclear.
The memoryless property says: for all s,t>0, P(X>s+t|X>s)=P(X>t). I just don't exactly see how this connects to and answers my questions above.

Any further explanation would be much appreciated!

**SpringFan25** · April 3rd 2011, 08:25 AM

Now to calculate E(Y), we need the distribution of Y. Does it matter WHEN the previous customer arrived at the system (and leaved because all servers were busy)? Say a free slot frees up at time 8, and the last arrival of customers in the time interval [0,8] may be at time 7.9, or it may be at time 7. Is this going to affect our calculations? Why or why not?

it wont because waiting time is exponentially distributed. We already proved that the remaining waiting time from any point is also exponential with the same parameter. (We proved it for the servers, but it applies to any exponential distribution).

Is it still always going to be exp(λ)? Why or why not?

As per the comments above it will always be exp(λ). This follows from the fact that the poisson process which drives everything is memoryless.

Getting the above result from memorylessness property

Im sure its possible to show the above using the memory property of the poisson process. i had a look and didn't come up with a simple way. Its easier to consider the waiting times as in the previous post.

**kingwinner** · April 3rd 2011, 11:51 AM

OK, now I understand part a. Thank you.

How can we solve part b?
I have the solution to this example but it is very brief and with not much explanations, so I'm really lost and confused and I can't understand the reasoning of the solution.

Would someone be kind enough to explain the solution to part b from scratch?? The answer provided for part b is 2/λ + μ /λ^2.

In the solution, they defined the following random variable:
T_i = the time until both servers are busy when starting with i busy servers.
They also defined an indicator random variable and calcualted some expecations based on that, but I just can't understand. And then they solved a system of 2 equations in 2 unknowns to arrive at the answer.

Thanks in advance!

**kingwinner** · April 4th 2011, 08:09 PM

For Part b:
Maybe I should type out the solution...

Let T_i = the time until both servers are busy when starting with i busy servers.

E(T_0)= 1/λ +E(T_1) --------------(1)
T_1 = time until the first event + additional time after the first event = T+Y
E(T_1) = E(T)+E(Y)
E(T_1) = 1/(λ+μ) + E[Y|I=1] λ/(λ+μ) + E[Y|I=0] μ/(λ+μ)
E(T_1) = 1/(λ+μ) + E(T_0) μ/(λ+μ) ----------------(2)

Solve (1) and (2) simultaneously => E(T_0)=2/λ + μ /λ^2 (final answer)
=======================

However, I'm really confused about this solution and I think I'm lost right from the beginning...

Why is E(T_0)= 1/λ +E(T_1) ? What is the reasoning behind it?

Why is T_1 = time until the first event + additional time after the first event? I don't understand what is the meaning of "time until the first event" and why is this equation true?

If someone understands this, can you please explain the solution?
Thanks a lot!

Thread: Poisson Process Queueing System!

LinkBack

Thread Tools

Display

Poisson Process Queueing System!

Similar Math Help Forum Discussions

Little's law Queueing system

Poisson Process

Poisson Square Wave (PSW) and Filtered Poisson Process (FP)

Birth Process/Poisson Process

Queueing system

Search Tags