On a New Numerical Analysis for the Symmetric Shortest Queue Problem

Authors: Tayeb Lardjane, Rabah Messaci

Abstract:

We consider a network of two M/M/1 parallel queues having the same poisonnian arrival stream with rate λ. Upon his arrival to the system a customer heads to the shortest queue and stays until being served. If the two queues have the same length, an arriving customer chooses one of the two queues with the same probability. Each duration of service in the two queues is an exponential random variable with rate μ and no jockeying is permitted between the two queues. A new numerical method, based on linear programming and convex optimization, is performed for the computation of the steady state solution of the system.

Keywords: Steady state solution, matrix formulation, convex set, shortest queue, linear programming.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1062910

References:

[1] Adan, I.J.B.F. and Wessels, J. and Zijm W.H.M. , Analysis of the symmetric shortest queueing problem, Stoch. Models, 1990 6, 691-713 .
[2] Cohen, J.W. and Boxma, O.J. , Boundary Problems in Queuing Systems Analysis, North- Holland, Amsterdam, 1983
[3] Flatto, L. and McKean, H.P. , Two queues in parallel, Comm. Pure. Appl. Math, 1977 30, 255-263 .
[4] Gertsbakh, I. , The shorter queue problem: A numerical study using the matrix geometric solution, European J. Operation Research, 1984 15, 374-381.
[5] Haight, F.A. , Two queues in parallel, Biometrika, 1958 48, 401-410 .
[6] Halfin, S. , The shortest queue problem, J. Appl. Probab., 1985 22, 865- 878 .
[7] Kingman, J.F.C. . Two similar queues in parallel, Ann. Math. Stat., 1961 32, 1314-1323.
[8] Lardjane, T. and Messaci, R. , On a new numerical computation of the steady state solution of two infinite server parallel queues, Applied Mathematical Sciences, 2011 Vol 5, 78, 3875-3891.
[9] Neuts, M. F. , Matrix geometric Solutions in Stochastic Models. John Hopkins University Press, Baltimore, 1980
[10] Tarabia, A.M.K., Analysis of two queues in parallel with jockeying and restricted capacities, Appl. Math.Modell., 2008 32(5), 802-810.
[11] Wang, P. and Locker, V.F. , Steady state distributions of parallel queues, INFOR, 2001 39(1).
[12] Yao, H. and Knessl, C. , On the infinite server shortest queue problem: symmetric case, Stochastic Models, 2005 21(1), 101-132
[13] Zhao, Y. and Grassman, W.K. , A numerically stable algorithm for two server queue model, Queueing Systems, 1991, 8, 59-79 .