1
$\begingroup$

Consider a simple queue model like the one described in http://en.wikipedia.org/wiki/M/M/1_model. The article states what the expected waiting time is before a request enters the queue.

Assuming that the actual queue length is unknown, does the expected value of "time left to wait" for a given request change over time while the request is in the queue?

Clarification: is it true that the expected time until a request is served stays constant, regardless of how long it has already spent in the queue?

$\endgroup$
1
  • $\begingroup$ R. Pandharipande has frequently expressed the view that, after a wait of x minutes to be served in a restaurant, the expected time f(x) remaining before actually being served is nonconstant, and indeed -f(x) is a unimodal function... $\endgroup$ Jun 3, 2010 at 15:22

2 Answers 2

2
$\begingroup$

I am not entirely sure what you are asking but ...

The model you reference in the wiki article has a memory-less distribution for waiting time and inter-arrival time. Thus, the total time for a request to get processed is not dependent on time.

$\endgroup$
4
  • $\begingroup$ What I was really trying to ask is whether a request "loses out" by leaving the queue and joining it later, assuming that being in the queue has a cost. The way I interpret your answer is that it doesn't matter how long a request has already spent in the queue; the expected time until it's served stays constant. Correct? $\endgroup$
    – romkyns
    Jun 2, 2010 at 12:41
  • $\begingroup$ Well the cost associated with waiting in the queue before leaving is sunk. So, from an economic standpoint, the only relevant cost to consider in order to decide whether to leave or not is the expected time to be served if the request chooses to leave the queue and re-join later vis-a-vis the expected time to be served if the request chooses not to leave the queue. For an M/M/1 model, the expected time in both situations is the same and hence the request does not lose by leaving the queue. $\endgroup$
    – vad
    Jun 2, 2010 at 13:12
  • $\begingroup$ The memoryless distribution is the waiting time for one customer to be served. If one knows, e.g. the average queue length, but one does not know the current queue length, what is the distribution of the waiting time until one gets served? I wouldn't think that would be the same as the distribution of the waiting time for just one customer. My guess is it's not memoryless. $\endgroup$ Jun 2, 2010 at 17:43
  • $\begingroup$ The easiest way to check this is to do a small simulation. See also the wiki article for stationary behavior of an M/M/1 queue which suggests that distribution of waiting time is not dependent on queue length. I am too lazy right now to lay out rigorous arguments. :-) $\endgroup$
    – vad
    Jun 2, 2010 at 19:23
0
$\begingroup$

M/M/1 model assumes Poisson arrivals + exponentially distributed service times. Confirming previous answer - if you're waiting in the queue and there is a person (product) being served right now, the expected finishing time for that person from now on $E(X|X>t)=E(X)+t$.

Overall the formula for expected waiting time in any queue model (1 server, infinite buffer...) is:

$EW_q = \rho * ES * (c(A)^2 + c(S)^2) / ( 2*(1-\rho) )$

$\rho = ES/EA$, Expected Service time / Expected Arrivals in 1 time unit.

$c(S)^2 = E(S^2) / (ES)^2$ - variation of S (service time), the same for A (Arrival rate).

$\rho<1$ otherwise the queue will grow -> infty.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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