I have been able to find, and understand reasonably well, expressions and derivations for the average wait times for (1) $s$ independent $M/M/1$ queues each with arrival rate $\lambda/s$ and service rate $\mu$, and (2) an $M/M/s$ queue with arrival rate $\lambda$ and service rate $\mu$. (See this recent discussion for details. Motivation for this question is the anecdotal result that "one long line" is better than "many individual lines.")

But what if customers arrive with rate $\lambda$ and join the shortest of $s$ queues, each with service rate $\mu$? Is there an expression (preferably with derivation as well, I'm not looking for a recipe) for the average wait time in this case? Simulation of this approach suggests that the average wait time is worse than $M/M/s$... but not that much worse. I would like to figure out how to tackle this analytically.

Perhaps a side effect of an answer might simply be recommendation of a good queuing theory text. My challenge has been that there seems in some cases (online sources, etc.) to be no distinction, or at least confusion, between this "join the shortest line" situation and the $s$ x $M/M/1$ case. But simulation and my intuition at least suggests that they are very different.

  • 2
    $\begingroup$ keyword: "shortest queue problem". A quick research reveals that the policy that consists in choosing the shortest queue has been proven to be optimal (maximum throughput) - nevertheless, even in the case of only 2 servers, the invariant distribution is not tractable. $\endgroup$
    – Alekk
    Dec 28 '10 at 23:14
  • 1
    $\begingroup$ See papers citing jstor.org/pss/3213954 $\endgroup$ Dec 29 '10 at 1:42
  • $\begingroup$ Both of these comments are helpful; I am new here, and would like to "accept an answer" but these seem to be comments vs. answers. Let me know if I'm missing something. I would like to understand "optimal maximum throughput" better. How does throughput vary at all as long as $\lambda < s\mu$? E.g., consider the policy of choosing a queue at random instead of the shortest queue. This yields worse latency (I think this is equiv. to (1) in the OP), but throughput hasn't changed. That is, I may still get a newspaper every morning, but they might always be two weeks old. $\endgroup$ Dec 29 '10 at 12:23

There is also a paper by Vvedenskaya, Dobrushin, and Karpelevich "Queueing System with Selection of the Shortest of Two Queues: An Asymptotic Approach" (Problems of Information Transmission, 1996, 32:1, 15–27; a Russian original is freely available at http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=298&option_lang=eng).

They consider a policy in which each customer chooses two queues at random and then, among them, the shortest one. Considering the limit of a large number of servers they are then able to derive an equation for the asymptotic stationary distribution, which turns out to be a discrete approximation to the Hopf (inviscid Burgers) equation.

As far as I know there was some development of this work for the case of more than two queues, but it is better to ask Nikita Vvedenskaya directly (ndv AT iitp DOT ru; I've asked her permission to post this address).


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.