Abstract
The queueing problem with Poisson arrivals and two identical parallel Erlang servers is analyzed for the case of shortest expected delay routing. This problem may be represented as a random walk on the integer grid in the first quadrant of the plane. An important aspect of the random walk is that it is possible to make large jumps in the direction of the boundaries. This feature gives rise to complicated boundary behavior. Generating function approaches to analyze this type of random walk seem to be extremely complicated and have not been successful yet. The approach presented in this paper directly solves the equilibrium equations. It is shown that the equilibrium distribution of the random walk can be written as an infinite linear combination of products. This linear combination is constructed in a compensation procedure. The starting solutions for this procedure are found by solving the shortest expected delay problem with instantaneous jockeying. The results can be used for an efficient computation of performance criteria, such as the waiting time distribution and the moments of the waiting time and the queue lengths.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I.J.B.F. Adan and J. Wessels, Analysing shortest expected delay routing for erlang servers, Memorandum COSOR 93-38, Department of Mathematics and Computing Science, Eindhoven University of Technology (1993).
I.J.B.F. Adan, J. Wessels and W.H.M. Zijm, Analysis of the symmetric shortest queue problem,Stochastic Models 6 (1990) 691–713.
I.J.B.F. Adan, J. Wessels and W.H.M. Zijm, Analysis of the asymmetric shortest queue problem with threshold jockeying,Stochastic Models 7 (1991) 615–627.
I.J.B.F. Adan, J. Wessels and W.H.M. Zijm, Analysis of the asymmetric shortest queue problem,Queueing Systems 8 (1991) 1–58.
I.J.B.F. Adan, J. Wessels and W.H.M. Zijm, A compensation approach for two-dimensional Markov processes,Adv. Appl. Probab. 25 (1993) 783–817.
I.J.B.F. Adan, W.A. van de Waarsenburg and J. Wessels, AnalyzingE k /E r /c queues,EJOR 92 (1996) 112–124.
I.J.B.F. Adan, G.J. van Houtum, J. Wessels and W.H.M. Zijm, A compensation procedure for multiprogramming queues,O. R.-Spektrum 15 (1993) 95–106.
O.J. Boxma and G.J. van Houtum, The compensation approach applied to a 2 × 2 switch,Probab. Engrg. Inform. Sci. 7 (1993) 471–493.
J.W. Cohen and O.J. Boxma,Boundary Value Problems in Queueing System Analysis (North-Holland, Amsterdam, 1983).
J.W. Cohen, On a class of two-dimensional nearest neighbour random walks, in:Studies in Applied Probability, ed. J. Gani,J. Appl. Prob. (Sp. Vol.) A31 (1994) 207–237.
L. Flatto and H.P. McKean, Two queues in parallel,Comm. Pure Appl. Math. 30 (1977) 255–263.
F.G. Foster, On the stochastic matrices associated with certain queueing processes,Ann. Math. Statist. 24 (1953) 355–360.
F.A. Haight, Two queues in parallel,Biometrika 45 (1958) 401–410.
A. Hordijk and G. Koole, On the optimality of the generalized shortest queue policy,Probab. Engrg. Inform. Sci. 4 (1990) 477–487.
J.F.C. Kingman, Two similar queues in parallel,Ann. Math. Statist. 32 (1961) 1314–1323.
H.C. Tijms,Stochastic Modelling and Analysis: A Computational Approach (Wiley, Chichester, 1986).
R.R. Weber, On the optimal assignment of customers to parallel queues,J. Appl. Probab. 15 (1978) 406–413.
R.W. Wolff, Poisson arrivals see time averages,Oper. Res. 30 (1982) 223–231.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Adan, I., Wessels, J. Shortest expected delay routing for Erlang servers. Queueing Syst 23, 77–105 (1996). https://doi.org/10.1007/BF01206552
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01206552