Open-loop routeing to M parallel servers with no buffers

In this paper we study the assignment of packets to M parallel heterogeneou s servers with no buffers. The controller does not have knowledge on the st ate of the servers and bases ail decisions on the number of time slots ago that packets have been sent to the different servers. The objective of the controller is to minimize the expected average cost. Wi:consider a general stationary arrival process, with no independence assumptions. We show that the problem can be transformed into a Markov Decision Process (MDP). We fur ther show under quite general conditions on cost functions that only a fini te number of states have to be considered in this MDP, which then implies t he optimality of periodic policies. For the case of two servers we obtain a more derailed structure of the cast and optimal policies. In particular we show that the average cost function is multimodular, and we obtain express ions for the cost for MMPP and MAP processes. Finally we present an applica tion to optimal robot scheduling for Web search engines.