Hostname: page-component-745bb68f8f-b6zl4 Total loading time: 0 Render date: 2025-01-15T07:56:37.020Z Has data issue: false hasContentIssue false
  • English
  • Français

Average Cost Semi-Markov Decision Processes and the Control of Queueing Systems

Published online by Cambridge University Press:  27 July 2009

Linn I. Sennott
Linn I. Sennott
Affiliation:
Department of Mathematics illinois State University Normal, Illinois 61761
Get access Rights & Permissions [Opens in a new window]

Abstract

Semi-Markov decision processes underlie the control of many queueing systems. In this paper, we deal with infinite state semi-Markov decision processes with nonnegative, unbounded costs and finite action sets. Axioms for the existence of an expected average cost optimal stationary policy are presented. These conditions generalize the work in Sennott [22] for Markov decision processes. Verifiable conditions for the axioms to hold are obtained. The theory is applied to control of the M/G/l queue with variable service parameter, with on-off server, and with batch processing, and to control of the G/M/m queue with variable arrival parameter and customer rejection. It is applied to a timesharing network of queues with a single server and finally to optimal routing of Poisson arrivals to parallel exponential servers. The final section extends the existence result to compact action spaces.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 3 , Issue 2 , April 1989 , pp. 247 - 272
Copyright
Copyright © Cambridge University Press 1989

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

REFERENCES

Ash, R.B. (1972). Real analysis and probability. New York: Academic Press.Google Scholar
Bertsekas, D.P. (1987). Dynamic programming: deterministic and stochastic models. Englewood Cliffs, New Jersey: Prentice-Hall.Google Scholar
Cavazos-Cadena, R. & Sennott, L.I. Comparing recent assumptions for the existence of average optimal stationary policies in Markov decision processes. (submitted).Google Scholar
Deb, R.K. & Serfozo, R.F. (1973). Optimal control of batch service queues. Advances in Applied Probability 5: 340–361.CrossRefGoogle Scholar
Deb, R.K. (1976). Optimal control of batch service queues with switching costs. Advances in Applied Probability 8: 177–194.CrossRefGoogle Scholar
Federgruen, A., Hordijk, A., & Tijms, H.C. (1979). Denumerable state semi-Markov decision processes with unbounded costs, average cost criterion. Stochastic Processes and their Applications 9: 223–235.CrossRefGoogle Scholar
Federgruen, A., Schweitzer, P.J., & Tijms, H.C. (1983). Denumerable undiscounted semiMarkov decision processes with unbounded rewards. Mathematics of Operations Research 8: 298–313.CrossRefGoogle Scholar
Gallisch, E. (1979). On monotone optimal policies in a queueing model of M/G/l type with controllable service-time distribution. Advances in Applied Probability 11: 870–887.CrossRefGoogle Scholar
Heyman, D.P. & Sobel, M.J. (1982). Stochastic models in operations research, Vol. I. New York: McGraw-Hill.Google Scholar
Hillman, A.P., Alexanderson, G.L., & Grassi, R.M. (1987). Discrete and combinatorial mathematics. San Francisco, California: Dellen.Google Scholar
Hordijk, A. (1974). Dynamic programming and Markov potential theory. Mathematical Centre Tracts 51.Google Scholar
Kleinrock, L. (1975). Queueing systems, Vol. 1. New York: Wiley and Sons.Google Scholar
Klimov, G.P. (1974). Time-sharing service systems, 1. Theory of Probability and Applications 19: 532–551.CrossRefGoogle Scholar
Knopp, K. (1956). Infinite sequences and series. New York: Dover.Google Scholar
Lppman, S.A. (1975). On dynamic programming with unbounded rewards. Management Science 21:1225–1233.CrossRefGoogle Scholar
Lippman, S.A. (1973). On dynamic programming with unbounded rewards. Working Paper 212, University of California, Los Angeles, California.Google Scholar
Lu, F.V. & Serfozo, R.F. (1984). M/M/1 queueing decision processes with monotone hysteretic control policies. Operations Research 32:1116–1132.CrossRefGoogle Scholar
Mitchell, B. (1973). Optimal service-rate selection in an M/G/l queue. SIAM Journal of Applied Mathematics 24:19–35.CrossRefGoogle Scholar
Ross, S.M. (1970). Applied probability models with optimization applications. San Francisco, California: Holden-Day.Google Scholar
Sennott, L. I. (1986). A new condition for the existence of optimal stationary policies in average cost Markov decision processes. Operations Research Letters 5:17–23.CrossRefGoogle Scholar
Sennott, L. I. (1986). A new condition for the existence of optimum stationary policies in average cost Markov decision processes-unbounded cost case. Proceedings of the 25th IEEE Conference on Decision and Control. Athens, Greece, pp. 1719–1721.CrossRefGoogle Scholar
Sennott, L. I. Average cost optimal stationary policies in infinite state Markov decision processes with unbounded costs. Operations Research (to appear).Google Scholar
Stidham, S. Jr, (1978). Socially and individually optimal control of arrivals to a GI/M/I queue. Management Science 24:1598–1610.CrossRefGoogle Scholar
Weber, R.R. & Stidham, S. Jr (1987). Optimal control of service rates in networks of queues. Advances in Applied Probability 19:202–218.CrossRefGoogle Scholar
Widder, D.V. (1946). The Laplace transform. New Jersey: Princeton University Press.Google Scholar