Open-loop routing of N arrivals to M parallel queues

Distribution of arrivals to queues in parallel is a basic problem with a number of applications in computer communication networks. In this paper, we consider the problem of routing N arrivals to M queues in parallel when no information other than the prior statistics are available for the decision process. The work we present here differs from results in the literature in two significant ways: (a) We address the nonstationary problem of open-loop routing for N<∞ arrivals; (b) we do not decompose the problem into an allocation phase, and a routing phase, but look instead for an overall optimal policy. Exhaustive enumeration and dynamic programming turn out to be computationally unfeasible approaches for realistic values of the parameters N and M. Examination of the necessary conditions for optimality as given by Pontryagin´s maximum principle leads to the formulation of a policy iteration algorithm. The algorithm exploits the local nature of the maximum principle for computational advantage. Convergence of the algorithm in a finite number of iterations, as well as monotonicity results, are established. While only convergence to a local minimum is guaranteed, extensive computational experimentation points to its near-optimality