Deciding Which Queue to Join: Some Counterexamples

Consider a queueing system with two or more servers, each with its own queue with infinite capacity. Customers arrive according to some stochastic process (e.g., a Poisson process) and immediately upon arrival must join one of the queues, thereafter to be served on a first-come first-served basis, with no jockeying or defections allowed. The service times are independent and identically distributed with a known distribution. Moreover, the service times are independent of the arrival process and the customer decisions. The only information about the history of the system available for deciding which queue to join is the number of customers currently waiting and being served at each server. Joining the shortest queue is known to minimize each customer's individual expected delay and the long-run average delay per customer when the service-time distribution is exponential or has nondecreasing failure rate. We show that there are service-time distributions for which it is not optimal to always join the shortest queue. We also show that if, in addition, the elapsed service times of customers in service are known, the long-run average delay is not always minimized by customers joining the queue that minimizes their individual expected delays.