Optimal Routing in two parallel Queues with exponential service times - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2004

Optimal Routing in two parallel Queues with exponential service times

Emmanuel Hyon
  • Fonction : Auteur
  • PersonId : 755811
  • IdRef : 074658417

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5109.pdf (313.07 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00071473 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00071473 , version 1

Citer

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⟩
174 Consultations
364 Téléchargements

Partager

Gmail Facebook X LinkedIn More