# Average wait time for multiple queues where arrivals enter shortest queue

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.

• 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. Dec 28 '10 at 23:14
• See papers citing jstor.org/pss/3213954 Dec 29 '10 at 1:42
• 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. Dec 29 '10 at 12:23