Abstract
In 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Altman E (2001). Markov decision processes, models, methods, directions, and open problems, chapter applications of Markov decision processes in communication networks: a survey. Kluwer, pp 488–536.
Altman E, Gaujal B, Hordijk A (2000a). Balanced sequences and optimal routing. J Assoc Comput Mach 47:752–775.
Altman E, Gaujal B, Hordijk A (2000b). Multimodularity, convexity and optimization properties. Math Oper Res 25:324–347.
Altman E, Gaujal B, Hordijk A (2002). Discrete-event control of stochastic networks: multimodularity and regularity. Springer, to appear.
Baccelli F, Bremaud P (1992). Elements of queueing theory. Springer.
Combe M, Boxma O (1994). Optimization of static traffic allocation policies. Theor Comp Sci 125:17–43.
Gaujal B, Hyon E (2001). Optimal routing policies in two deterministic queues. Réseaux et systèmes répartis, Calculateurs Parallèles 13(6):601–633.
Gaujal B, Hyon E (2002). Optimal routing policies in deterministic queues in tandem. WODES, IEEE, pp 251–257.
Gross D, Harris C (1985). Fundamentals of queueing theory. 2nd edn, Wiley.
Hajek B (1984). Optimal control of two interacting service stations. IEEE Trans Automat Contr 29:491–499.
Hajek B (1985). Extremal splittings of point processes. Math Oper Res 10(4):543–556.
Hordijk A, van der Laan D (2003). Note on the convexity of the stationary waiting time as a function of the density. Probab Eng Inf Sci 17:503–508.
Hordijk A, Koole G, Loeve J (1994). Analysis of a customer assignment model with no state information. Probab Eng Inf Sci 8:419–429.
Latouche G, Ramaswami V (1993). A logarithmic reduction algoritm for quasi-birth-death processes. J Appl Probab 30:650–674.
Liu Z, Righter R (1998). Optimal load balancing on distributed homogeneous unreliable processors. J Oper Res 46:563–573.
Loeve JA (1995). Markov decision chains with partial information. PhD thesis. Leiden University.
Lothaire M (2002). Algebraic combinatorics on words, chapter sturmian words. Cambridge University Press.
Milito R, Fernandez-Gaucherand E (1995a). Open-loop routing of n arrivals to m parallel queues. IEEE Trans Automat Contr 40:2108–2114.
Milito R, Fernandez-Gaucherand E (1995b). Routing arrivals to m parallel queues. Conference on decision and control. IEEE, pp 1415–1420.
Neuts M (1981). Matrix-geometric solutions in stochastic models an algoritmic approach. John Hopkins University Press.
Neuts M (1989). Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker.
van der Laan D (2003). The structure and performance of optimal routing sequences. PhD thesis, Leiden University.
Ye Q (2002). On Latouche-Ramaswami's logarithmic reduction algorithm for quasi-birth-and-death processes. Stochastics models 18:449–467.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gaujal, B., Hyon, E. & Jean-Marie, A. Optimal Routing in Two Parallel Queues with Exponential Service Times. Discrete Event Dyn Syst 16, 71–107 (2006). https://doi.org/10.1007/s10626-006-6179-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10626-006-6179-3