Optimal Routing to M parallel queues with no buffers

Eitan Altman 1 Sandjai Bhulai Bruno Gaujal 2 Arie Hordijk
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper we study the assignment of packets to M parallel heterogeneous servers with no buffer. The controller does not have knowledge on the state of the servers and bases all 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. We 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 further show under quite general conditions on cost functions that only a finite number of states have to be considered in this MDP, which then implies the optimality of periodic policies. For the case of two servers we obtain a more detailed structure of the cost and optimal policies. In particular we show that the average cost function is multimodular. Finally we present an application to optimal robot scheduling for web search engines.
Type de document :
Communication dans un congrès
33rd Allerton Conference on Communication, Control, & Computing, 1999, Allerton, Illinois/USA, 10 p, 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00098807
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:38:45
Dernière modification le : samedi 27 janvier 2018 - 01:31:35

Identifiants

  • HAL Id : inria-00098807, version 1

Collections

Citation

Eitan Altman, Sandjai Bhulai, Bruno Gaujal, Arie Hordijk. Optimal Routing to M parallel queues with no buffers. 33rd Allerton Conference on Communication, Control, & Computing, 1999, Allerton, Illinois/USA, 10 p, 1999. 〈inria-00098807〉

Partager

Métriques

Consultations de la notice

333