Joining the right queue: A Markov decision-rule
Kishoor Santhana Krishnan · 1987
The problem of assigning customers to one of several parallel queues so as to minimize the average time spent in the system (sojourn time) is studied as a Markov decision process. It is shown how the approach developed by Krishnan and Ott [7] to investigate state-dependent routing of voice-traffic for blocking minimization can also be used for sojourn-minimization for data traffic. For queues in parallel, this approach produces a rule, called the 'separable' rule, which is a generalization of "join the shortest queue" rule to the case of dissimilar queues, reducing to the shortest-queue rule when the queues are all alike - the case for which the shortest-queue rule is, in fact, optimum. Numerical results show that in cases where the queues are dissimilar in both the service rates and numbers of their servers, the 'separable' rule is strikingly superior to the shortest-queue rule; if the dissimilarities are limited to differences in the service rates, the 'separable' rule practically always is better than the shortest-queue rule; if the dissimilarities consist in the numbers of servers being different, with the individual servers all alike in the different queues, then the shortest-queue rule does better than the separable rule in most instances.