Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-08T00:08:34.513Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal service-rate control of M/G/1 queueing systems using phase methods

Published online by Cambridge University Press:  01 July 2016

Kyung Y. Jo  and
Shaler Stidham Jr
Kyung Y. Jo*
Affiliation:
George Mason University
Shaler Stidham Jr*
Affiliation:
North Carolina State University
*
∗Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030, U.S.A.
∗∗Department of Industrial Engineering and Graduate Program in Operations Research, North Carolina State University, Box 5511, Raleigh, NC 27650, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

A new approach to the optimal control of the service rate in M/G/1 queues is introduced using the method of phases. Each customer's work requirement is approximated by a random number of exponential phases with (possibly) different parameters (a generalized hyper-Erlang distribution). Using a semi-Markov decision-process formulation, we establish monotonicity properties of optimal policies for the finite-horizon problem, by induction on the horizon length. The analysis is then extended to the discounted infinite-horizon and the long-run average-return problems. In contrast to the models in previous papers, our model is appropriate for situations where the system controller has partial information about the work requirement of a customer, specifically the number of phases (tasks) to be performed. Because it requires a multidimensional state description, the analysis of the phase-type control model may be viewed as a first step toward the solution of control models for networks of queues.

Keywords

M/G/1 QUEUECONTROL OF QUEUESSERVICE-RATE CONTROLSEMI-MARKOV DECISION PROCESSDYNAMIC PROGRAMMINGPHASE-TYPE DISTRIBUTION
Type
Research Article
Information
Advances in Applied Probability , Volume 15 , Issue 3 , September 1983 , pp. 616 - 637
Copyright
Copyright © Applied Probability Trust 1983 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Cox, D. R. (1955) A use of complex probabilities in the theory of stochastic processes. Proc. Camb. Phil. Soc. 51, 313–319.Google Scholar
[2] Crabill, T. B. (1974) Optimal control of a maintenance system with variable service rates. Operat. Res. 22, 736–745.Google Scholar
[3] Doshi, B. T. (1978) Optimal control of the service rate in an M/G/1 queueing system. Adv. Appl. Prob. 10, 682–701.CrossRefGoogle Scholar
[4] Gallisch, R. (1979) On monotone optimal policies in a queueing model of M/G/1 type with controllable service time distribution. Adv. Appl. Prob. 11, 870–887.Google Scholar
[5] Harrison, J. H. (1972) Discrete dynamic programming with unbounded rewards. Ann. Math. Statist. 43, 636–644.Google Scholar
[6] Heyman, D. (1968) Optimal operating policies for M/G/1 queueing systems. Operat. Res. 16, 362–382.Google Scholar
[7] Hinderer, K. (1970) Foundations of Non-Stationary Dynamic Programming with Discrete Time Parameter. Lecture Notes in Operations Research and Mathematical Systems 33, Springer-Verlag, New York.CrossRefGoogle Scholar
[8] Langen, H. J. (1982) Applying the method of phases in the optimization of queueing systems. Adv. Appl. Prob. 14, 122–142.Google Scholar
[9] Lippman, S. A. (1973) Semi-Markov decision processes with unbounded rewards. Management Sci. 19, 717–731.Google Scholar
[10] Lippman, S. A. (1975) Applying a new device in the optimization of exponential queueing systems. Operat. Res. 23, 687–710.CrossRefGoogle Scholar
[11] Mitchell, W. (1973) Optimal service-rate selection in an M/G/1 queue. SIAM J. Appl. Math. 24, 19–35.Google Scholar
[12] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore.Google Scholar
[13] Ross, S. M. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
[14] Schäl, M. (1975) Conditions for optimality in dynamic programming and for the limit of n-stage optimal policies to be optimal. Z. Wahrscheinlichkeitsth. 32, 179–196.CrossRefGoogle Scholar
[15] Schassberger, R. (1973) Warteschlangen. Springer-Verlag, Berlin.CrossRefGoogle Scholar
[16] Schassberger, R. (1975) A note on optimal service selection in a single server queue. Management Sci. 21, 1326–1331.CrossRefGoogle Scholar
[17] Serfozo, R. F. (1976) Monotone optimal policies for Markov decision processes. Math. Programming Study 6, North-Holland, Amsterdam, 202–215.Google Scholar
[18] Serfozo, R. F. (1979) An equivalence between continuous and discrete time Markov decision processes. Operat. Res. 27, 616–620.Google Scholar
[19] Serfozo, R. F. (1981) Optimal control of random walks, birth and death processes, and queues. Adv. Appl. Prob. 13, 61–83.Google Scholar
[20] Sobel, M. J. (1982) The optimality of full-service policies. Operat. Res. 30, 636–649.Google Scholar
[21] Tijms, H. C. (1980) An algorithm for average cost denumerable state semi-Markov decision problems with applications to controlled production and queueing systems. In Recent Developments in Markov Decision Processes, Academic Press, London, 143–179.Google Scholar
[22] Topkis, D. (1978) Minimizing a submodular function on a lattice. Operat. Res. 26, 305–321.Google Scholar
[23] Van Der Duyn Schouten, F. (1979) Markov decision processes with continuous time parameter. Mathematisch Centrum, Amsterdam.Google Scholar