Optimal routing in two parallel queues

Bruno Gaujal 1 Emmanuel Hyon 2 Alain Jean-Marie 3, 4
1 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
4 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper deals with the problem of the computation of the optimal routing sequence in a queuing system made of two parallel queues with exponential service times. The optimal policy (minimizing the expected waiting time) is a Sturmian sequence. An algorithm to compute the optimal routing sequence is proposed together with an extensive set of experiments which show several interesting features of the optimal policy with apparent discontinuities and a fractal behavior. Several good approximations using fast heuristics are given at the end.
Type de document :
Communication dans un congrès
WODES'04: 7th Workshop on Discrete Event Systems, 2004, Reims, France. IFAC, pp.6, 2004
Liste complète des métadonnées

https://hal.inria.fr/inria-00100135
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:14:30
Dernière modification le : vendredi 25 mai 2018 - 01:40:40

Identifiants

  • HAL Id : inria-00100135, version 1

Citation

Bruno Gaujal, Emmanuel Hyon, Alain Jean-Marie. Optimal routing in two parallel queues. WODES'04: 7th Workshop on Discrete Event Systems, 2004, Reims, France. IFAC, pp.6, 2004. 〈inria-00100135〉

Partager

Métriques

Consultations de la notice

251