Suppose, there is a queue A having i customers initially. The service time of the queue is Exponentially distributed with parameter $\mu$ (i.e., mean service time of one customer in Queue A is 1/$\mu$). Arrival to queue A has Poisson distribution with mean $\lambda$. What is the expected time before queue A becomes empty for the first time?

My approach:

For the queue to be empty, service time of j customers should be less than the arrival time of $(j+1)^{th}$ customer (for j>=i).


How do I proceed after this since the sums are Erlang distributed and I'm not able to tackle this.

  • 1
    $\begingroup$ What if you define $T_k$ as the expected time to empty, given you start with $k$ jobs, and $T_0=0$. Can you write a recursive relationship between $\{T_i\}_{i=0}^{\infty}$? For example, can you write an expression for $T_1$ in terms of $T_1$ and $T_2$? $\endgroup$ – Michael May 4 '17 at 22:00
  • 1
    $\begingroup$ [Another classic and clever way to solve is to assume all departures are in Last-in-first-out (LIFO) order, and use insights from that (where each buffered packet is associated with a certain string of services until that packet leaves), but the above may be more direct.] $\endgroup$ – Michael May 4 '17 at 22:07
  • 1
    $\begingroup$ Let the random variable $C_{n}$ be the time till the system is empty again if there are now n customers present in the system. Clearly, $C_1$ is the length of a busy period, since a busy period starts when the first customer after an idle period arrives and it ends when the system is empty again. The random variables $C_{n}$ satisfy the following recursion relation. Suppose there are n(> 0) customers in the system. Then the next event occurs after an exponential time with parameter $\lambda$ + $\mu$. I used this to find a recursive relation and it worked. Thanks a lot. :) $\endgroup$ – RSA May 6 '17 at 4:35
  • 1
    $\begingroup$ Nice. Thanks for letting me know you solved it. In the future you can use @[username] to direct comments to particular individuals. If you want, you can answer your own question and mark it "best answer": This is standard practice on stackexchange when you solve a problem based on suggestions in the comments. $\endgroup$ – Michael May 6 '17 at 17:28
  • 1
    $\begingroup$ PS: Note that the LIFO scheduling idea is to notice that each of the initial $n$ packets generates its own busy period (one after the other). Of course, this intuition usually comes after solving the problem the direct way. But this LIFO intuition is valuable since it lets you easily solve the problem even for M/G/1 queues, where the Markov chain approach would be more difficult. $\endgroup$ – Michael May 6 '17 at 17:29

Your Answer

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

Browse other questions tagged or ask your own question.