Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-18T16:53:41.020Z Has data issue: false hasContentIssue false
  • English
  • Français

On the value function of the M/Cox(r)/1 queue

Part of: Special processes Stochastic systems and control

Published online by Cambridge University Press:  14 July 2016

Sandjai Bhulai
Sandjai Bhulai*
Affiliation:
Vrije Universiteit Amsterdam
*
∗Postal address: Vrije Universiteit Amsterdam, Faculty of Sciences, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a single-server queueing system at which customers arrive according to a Poisson process. The service times of the customers are independent and follow a Coxian distribution of order r. The system is subject to costs per unit time for holding a customer in the system. We give a closed-form expression for the average cost and the corresponding value function. The result can be used to derive nearly optimal policies in controlled queueing systems in which the service times are not necessarily Markovian, by performing a single step of policy iteration. We illustrate this in the model where a controller has to route to several single-server queues. Numerical experiments show that the improved policy has a close-to-optimal value.

Keywords

Coxian distributionM/Cox(r)/1 queueone-step policy improvementoptimal routeingPoisson equationvalue function

MSC classification

Primary: 93E25: Other computational methods
Secondary: 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 43 , Issue 2 , June 2006 , pp. 363 - 376
Copyright
© Applied Probability Trust 2006 

Footnotes

Supported by the Netherlands Organization for Scientific Research (NWO).

References

Asmussen, S., Nerman, O. and Olsson, M. (1996). Fitting phase-type distributions via the EM algorithm. Scand. J. Statist. 23, 419–441.Google Scholar
Bhulai, S. and Koole, G. M. (2003). On the structure of value functions for threshold policies in queueing models. J. Appl. Prob. 40, 613–622.Google Scholar
Bhulai, S. and Spieksma, F. M. (2003). On the uniqueness of solutions to the Poisson equations for average cost Markov chains with unbounded cost functions. Math. Meth. Operat. Res. 58, 221–236.Google Scholar
Dekker, R. (1985). Denumerable Markov decision chains: optimal policies for small interest rates. , Leiden University.Google Scholar
Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. 1. John Wiley, New York.Google Scholar
Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. 2. John Wiley, New York.Google Scholar
Hernández-Lerma, O. and Lasserre, J. B. (1999). Further Topics on Discrete-Time Markov Control Processes. Springer, New York.Google Scholar
Kendall, D. G. (1951). Some problems in the theory of queues. J. R. Statist. Soc. 13, 151–173.Google Scholar
Koole, G. M. and Nain, P. (2004). An explicit solution for the value function of a priority queue. Queueing Systems 47, 251–282.CrossRefGoogle Scholar
Marbach, P., Mihatsch, O. and Tsitsiklis, J. N. (2000). Call admission control and routing in integrated services networks using neuro-dynamic programming. IEEE J. Sel. Areas Commun. 18, 197–208.Google Scholar
Marie, R. (1980). Calculating equilibrium probabilities for λ(m)/{C}_k/1/{N} queues. In Joint International Conference on Measurement and Modeling of Computer Systems (Proc. 1980 Internat. Symp., Toronto), Association for Computing Machinery, New York, pp. 117–125.Google Scholar
Nordstrom, E. and Carlstrom, J. (1995). A reinforcement learning scheme for adaptive link allocation in ATM networks. In Proc. Internat. Workshop Appl. Neural Networks Telecommun., eds Alspector, J. et al., Lawrence Erlbaum, Mahwah, NJ, pp. 88–95.Google Scholar
Norman, J. M. (1972). Heuristic Procedures in Dynamic Programming. Manchester University Press.Google Scholar
Ott, T. J. and Krishnan, K. R. (1992). Separable routing: a scheme for state-dependent routing of circuit switched telephone traffic. Ann. Operat. Res. 35, 43–68.Google Scholar
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley, New York.Google Scholar
Sassen, S. A. E., Tijms, H. C. and Nobel, R. D. (1997). A heuristic rule for routing customers to parallel servers. Statist. Neerlandica 51, 107–121.Google Scholar
Schassberger, R. (1973). Warteschlangen. Springer, Vienna.Google Scholar
Tijms, H. C. (1994). Stochastic Models: An Algorithmic Approach. John Wiley, New York.Google Scholar
Tong, H. and Brown, T. X. (2000). Adaptive call admission control under quality of service constraints: a reinforcement learning solution. IEEE J. Sel. Areas Commun. 18, 209–221.CrossRefGoogle Scholar
Towsley, D., Hwang, R. H. and Kurose, J. F. (2000). MDP routing for multi-rate loss networks. Computer Networks 34, 241–261.Google Scholar