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 K.R. Krishman and T.J. Ott (Proc. 25th IEEE Conf. Decision Contr. Dec. 1986, p.2124-8) 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 the 'join the shortest queue' rule to the case of dissimilar queues, reducing to the shortest queue rule when the queues are all alike. 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 only of the numbers of servers being different, then the shortest queue rule does better than the separable rule in most instances.>