Optimal Routing in two parallel Queues with exponential service times

Bruno Gaujal 1 Emmanuel Hyon 2 Alain Jean-Marie 3
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper we investigate the problem of the effective computation of the optimal routing sequence in a queuing system made of two queues with exponential service time in parallel. We first show that the optimal policy (minimizing the expected waiting time) is a Sturmian sequence and we establish several qualitative properties of this policy (monotonicity, continuity, convexity) Then, we propose an algorithm to compute the optimal routing sequence. We address the issues of time complexity as well as numerical stability of this algorithm. We then run an extensive set of experiments which show several interesting features of the optimal policy with apparent discontinuities and a fractal behavior.
Document type :
Reports
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071473
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:40:08 PM
Last modification on : Tuesday, November 13, 2018 - 2:38:01 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:17:37 PM

Identifiers

  • HAL Id : inria-00071473, version 1

Citation

Bruno Gaujal, Emmanuel Hyon, Alain Jean-Marie. Optimal Routing in two parallel Queues with exponential service times. [Research Report] RR-5109, INRIA. 2004. ⟨inria-00071473⟩

Share

Metrics

Record views

412

Files downloads

350