The paper considers 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 it presents here differs from results in the literature in two significant ways: (a) the paper addresses the nonstationary problem of open-loop routing for N<• arrivals, and (b) it does 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 infeasible approaches for realistic values of the parameters N an M. Examination of the necessary conditions for optimality as given by Pontryagin’s maximum principle leads to the formulation of a policy iteration algorithm. 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. Some variants of the basic policy iteration algorithm are also discussed.
