Optimal routing in two parallel Queues with Exponential service times

International audienceIn this paper we investigate the problem of the effective computation of the optimal routing sequence in a queuing system made of two parallel queues with exponential service times. 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 efficiently. 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 and we provide several good approximations by using fast heuristics