Joining the right queue: A state-dependent decision rule

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 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 whre 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 of the number of servers being different, with the individual servers all alike in the different queues, then the shortest queue rule does better than theseparable rule in most instances.