A heuristic rule for routing customers to parallel servers

Authors:

Abstract
A practically important problem is the assignment of stochastically arriving service requests to one of several parallel service groups so as to minimize the long‐run average sojourn time per service request. An exact solution of this multi‐dimensional optimization problem is computationally infeasible. A simple heuristic solution method yielding a good suboptimal rule will be given for the case of server groups with different and generally distributed service times. This solution method is based on a decomposition approach and first principles from Markov decision theory. The main idea of the heuristic method is to apply one step of policy improvement to the best Bernoulli‐splitting rule.