Threshold policies for controlled retrial queues with heterogeneous servers. (English) Zbl 1114.90020

Summary: Retrial queues are an important stochastic model for many telecommunication systems. In order to construct competitive networks it is necessary to investigate ways for optimal control. This paper considers \(K\)-server retrial systems with arrivals governed by Neuts’ Markovian arrival process, and heterogeneous service time distributions of general phase-type. We show that the optimal policy which minimizes the number of customers in the system is of a threshold type with threshold levels depending on the states of the arrival and service processes. An algorithm for the numerical evaluation of an optimal control is proposed on the basis of Howar’s iteration algorithm. Finally, some numerical results will be given in order to illustrate the system dynamics.


90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
93E20 Optimal stochastic control


Full Text: DOI


[1] Asmussen, S., O. Nerman, and M. Olsson. (1996), ”Fitting Phase-Type Distributions Via the EM Algorithm.” Scand. J. Stat. 23(4), 419–441. · Zbl 0898.62104
[2] Breuer, L. (2001). ”The Periodic BMAP/PH/c Queue.” Queueing Systems 38(1), 67–76. · Zbl 1017.90014
[3] Breuer, L. (2002). ’An EM Algorithm for Batch Markovian Arrival Processes and its Comparison to a Simpler Estimation Procedure.” Annals of Operations Research 112, 123–138. · Zbl 1088.62511
[4] Breuer, L., A. Dudin, and V. Klimenok. (2002). ”A Retrial BMAP/PH/N System.” Queueing Systems 40(4), 431–455.
[5] Efrosinin, D.V. (2004). Controlled Queueing Systems with Heterogeneous Servers. Ph.D. Dissertation, Trier University, Germany. · Zbl 1061.90035
[6] Howard, R.A. (1960). Dynamic Programming and Markov Processes. Wiley. · Zbl 0091.16001
[7] Kitaev, M.Y. and V.V. Rykov. (1995). Controlled Queueing Systems. CRC Press: New York. · Zbl 0876.60077
[8] Lerma, O.H. and J.B. Lassere. (1996). ”Discrete-Time Markov Control Processes.” Applications of Mathematics, New-York.
[9] Lin, W. and P.R. Kumar. (1984). ”Optimal Control of a Queueing System with two Heterogeneous Servers.” IEEE Trans. on Autom. Control 29, 696–703. · Zbl 0546.90035
[10] Lucantoni, D.M. (1991). ”New Results on the Single Server Queue with a Batch Markovian Arrival Process.” Commun. Stat., Stochastic Models 7(1), 1–46. · Zbl 0733.60115
[11] Luh, H.P. and I. Viniotis. (1990). Optimality of Threshold Policies for Heterogeneous Server Systems. Raleign, North Carolina State University. · Zbl 1037.90010
[12] Naoumov, V., U.R. Krieger, and D. Wagner. (1997). Analysis of a Multiserver Delay-Loss System with a General Markovian Arrival Process. In Matrix-analytic methods in stochastic models (Flint, MI), pp. 43–66. Dekker, New York. · Zbl 0872.60070
[13] Neuts, M.F. (1978). ”Markov Chains with Applications in Queueing Theory, Which Have a Matrix-Geometric Invariant Probability Vector.” Adv. Appl. Probab. 10, 185–212. · Zbl 0382.60097
[14] Neuts, M.F. (1981). Matrix-Geometric Solutions in Stochastic Models. Baltimore, London: The Johns Hopkins University Press. · Zbl 0469.60002
[15] Neuts, M.F. (1989). Structured Stochastic Matrices of M/G/1 Type and Their Applications. New York etc.: Marcel Dekker. · Zbl 0695.60088
[16] Nobel, R. and H.C. Tijms. 2000. ”Optimal Control of a Queueing System with Heterogeneous Servers.” IEEE Transactions on Autom. Control 45(4). · Zbl 0988.90007
[17] Puterman, M.L. (1994). Markov Decision Process. Wiley series in Probability and Mathematical Statistics.
[18] Rosberg, Z. and A.M. Makowski. (1990). ”Optimal Routing to Parallel Heterogeneous Servers–Small Arrival Rates.” Transactions on automatic control, 35(7), 789–796. · Zbl 0705.60090
[19] Ross, Sh. (1970). Applied Probability Models with Optimization Applications. Holden Day, San Francisco. · Zbl 0213.19101
[20] Rykov, V.V. (1975). Controllable Queueing Systems. In Itogi nauki i techniki. Teoria verojatn. Matem. Sftatist. Teoretich. Kibern. 12, 45–152 (In Russian). There is an English translation in Journ. of Soviet Math.
[21] Rykov, V.V. (2001). ”Monotone Control of Queueing Systems with Heterogeneous Servers.” QUESTA 37: 391–403. · Zbl 1017.90026
[22] Rykov, V.V. (1966) ”Markov Decision Processes with Finite State and Decision Spaces.” Probability Theory and its Applications 11(2), 302–311. · Zbl 0262.60063
[23] Rykov, V.V. and D.V. Efrosinin. (2002). ”Numerical Analysis of Optimal Control Polices for Queueing Systems with Heterogeneous Servers.” Information Processes 2(2), 252–256.
[24] Sennott, L. (1999). Stochastic Dynamic Programming and Control of Queueing Systems. New York, Wiley, 328. · Zbl 0997.93503
[25] Tijms, H.C. (1994). Stochastic Models. An Algorithmic Approach. John Wiley and Sons. · Zbl 0838.60075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.