Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T13:29:41.488Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal control of random walks, birth and death processes, and queues

Published online by Cambridge University Press:  01 July 2016

Richard Serfozo
Richard Serfozo*
Affiliation:
Bell Laboratories
*
∗Postal address: Bell Laboratories, Holmdel, NJ 07733, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

This is a study of simple random walks, birth and death processes, and M/M/s queues that have transition probabilities and rates that are sequentially controlled at jump times of the processes. Each control action yields a one-step reward depending on the chosen probabilities or transition rates and the state of the process. The aim is to find control policies that maximize the total discounted or average reward. Conditions are given for these processes to have certain natural monotone optimal policies. Under such a policy for the M/M/s queue, for example, the service and arrival rates are non-decreasing and non-increasing functions, respectively, of the queue length. Properties of these policies and a linear program for computing them are also discussed.

Keywords

RANDOM WALKBIRTH AND DEATH PROCESSM/M/s QUEUEMARKOV DECISION PROCESSDYNAMIC PROGRAMMINGMONOTONE OPTIMAL POLICYSUPERMODULARITY
Type
Research Article
Information
Advances in Applied Probability , Volume 13 , Issue 1 , March 1981 , pp. 61 - 83
Copyright
Copyright © Applied Probability Trust 1981 

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.)

Footnotes

Part of this research was supported by Air Force Grant AFOSR-74-2627 and NSF Grant ENG-75-13653.

References

[1] Albright, S. C. and Winston, W. (1977) A birth–death model of advertising and pricing. Adv. Appl. Prob. 11, 134–152.Google Scholar
[2] Bather, J. (1973) Optimal decision procedures for finite Markov chains. Adv. Appl. Prob. 5, 328–339; 521–540; 541–553.Google Scholar
[3] Beja, A. and Teller, A. (1975) Relevant policies for Markovian queueing systems with many types of service. Management Sci. 21, 1049–1054.CrossRefGoogle Scholar
[4] Chernoff, H. and Petkau, A. (1978) Optimal control of a Brownian motion. SIAM. J. Appl. Math. 34, 717–731.Google Scholar
[5] Çinlar, E. (1975) Introduction to Stochastic Processes. Prentice-Hall, New Jersey.Google Scholar
[6] Crabill, T. (1972) Optimal control of a service facility with variable exponential service time and constant arrival rate. Management Sci. 18, 560–566.CrossRefGoogle Scholar
[7] Crabill, T., Gross, D. and Magazine, M. (1977) A Classified bibliography of research on optimal design and control of queues. Operat. Res. 25, 219–232.Google Scholar
[8] Deb, R. (1976) Optimal control of batch service queues with switching costs. Adv. Appl. Prob. 8, 177–194.Google Scholar
[9] Derman, C. (1962) On sequential decisions and Markov chains. Management Sci. 9, 16–24.Google Scholar
[10] Derman, C. (1970) Finite State Markovian Decision Processes. Academic Press, New York.Google Scholar
[11] Deshmukh, S. and Winston, W. (1977) A controlled birth–and–death process model of optimal product pricing under stochastically changing demand. J. Appl. Prob. 14, 328–339.CrossRefGoogle Scholar
[12] Doshi, B. (1977) Continuous time control of the arrival process in an M/G/1 queue. Stoch. Proc. Appl. 5, 265–284.Google Scholar
[13] Feller, W. (1971) Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn. Wiley, New York.Google Scholar
[14] Gallisch, E. (1979) On monotone optimal policies in a queueing model of M/G/1 type with controllable service distribution. Adv. Appl. Prob. 11, 870–887.Google Scholar
[15] Gallisch, E. (1979) On the computation of an average cost optimal policy in an M/G/1-model with controllable service time. Technical Report, Bonn.Google Scholar
[16] Getz, W. (1975) Optimal control of a birth–and–death process population model. Math. Biosci. 23, 87–111.Google Scholar
[17] Heyman, D. (1968) Optimal operating policies for M/G/1 queueing systems. Operat. Res. 16, 363–382.Google Scholar
[18] Hinderer, K. (1970) Foundations of Non-Stationary Dynamic Programming with Discrete Time Parameter. Lecture Notes in Operations Research and Mathematical Sciences 33, Springer-Verlag, New York.Google Scholar
[19] Hordijk, A. (1974) Dynamic Programming and Markov Potential Theory. Mathematical Center Tract No. 51, Amsterdam.Google Scholar
[20] Hordijk, A. (1971) A sufficient condition for the existence of an optimal policy with respect to the average cost criterion in Markovian decision processes. Trans. 6th Prague Conf. Information Theory, Prague (1973).Google Scholar
[21] Howard, R. (1960) Dynamic Programming and Markov Processes. Wiley, New York.Google Scholar
[22] Kakumanu, P. (1977) Relation between continuous and discrete-time Markovian decision problems. Naval Res. Logist. Quart. 24, 431–441.Google Scholar
[23] Karlin, S. and Taylor, H. (1975) A First Course in Stochastic Processes, 2nd edn. Academic Press, New York.Google Scholar
[24] Klein, C. and Gruver, W. (1978) On the optimal control of a single-server queueing system: Comment. J. Optimization Theory Appl. 26, 457–462.Google Scholar
[25] Lippman, S. (1975) Applying a new device in the optimization of exponential queueing systems. Operat. Res. 23, 687–710.CrossRefGoogle Scholar
[26] Lippman, S. and Stidham, S. (1977) Individual versus social optimization in exponential congestion systems. Operat. Res. 25, 233–247.Google Scholar
[27] Low, D. (1974a) Optimal dynamic pricing policies for an M/M/s queue. Operat. Res. 22, 545–561.Google Scholar
[28] Low, D. (1974b) Optimal pricing for an unbounded queue. IBM J. Research and Development 18, 290–302.Google Scholar
[29] Orkenyi, P. (1976) Optimal control of the M/G/1 queueing system with removable server–linear and non-linear holding cost function. Technical Report, Stanford University.Google Scholar
[30] Porteus, E. (1975) Bounds and transformations for discounted finite Markov decision chains. Operat. Res. 23, 761–784.CrossRefGoogle Scholar
[31] Rath, J. (1978) Optimal control of a Brownian motion. SIAM J. Appl. Math. 34, 717–731.Google Scholar
[32] Robin, M. (1976) Some optimal control problems for queueing systems. Stochastic Systems: Modelling, Identification and Optimization, II. Mathematical Programming Study 6, North-Holland, New York, 154–169.Google Scholar
[33] Robinson, D. (1976) Markov decision chains with unbounded costs and applications to the control of queues. Adv. Appl. Prob. 8, 159–176.Google Scholar
[34] Ross, S. (1970) Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.Google Scholar
[35] Sabeti, H. (1973) Optimal selection of service rates in queueing with different costs. J. Operat. Res. Soc. Japan 16, 15–35.Google Scholar
[36] Schäl, M. (1975) Conditions for optimality in dynamic programming for the limit of n-stage policies to be optimal. Z. Wahrscheinlichkeitsth. 32, 179–196.Google Scholar
[37] Schäl, M. (1977) On negative dynamic programming with irreducible Markov chains and the average cost criterion. Technical Report, University of Bonn.Google Scholar
[38] Schal, M. (1978) On the M/G/1-queue with controlled service rate. Optimization and Operations Research, ed. Henn, R. and Korte, B., Springer-Verlag, Berlin, 233–240.Google Scholar
[39] Scheng, D. (1978) Some Problems in the Optimal Control of Diffusions. Ph.D. dissertation, Stanford University.Google Scholar
[40] Schweitzer, P. (1971) Iterative solution of the functional equations of undiscounted Markov renewal programming. J. Math. Anal. Appl. 34, 495–501.Google Scholar
[41] Serfozo, R. (1976) Monotone optimal policies for Markov decision processes. Stochastic Systems: Modelling Identification and Optimization, II, Mathematical Programming Study 6, North-Holland, New York, 202–216.Google Scholar
[42] Serfozo, R. (1979) An equivalence between continuous and discrete time Markov decision processes. Operat. Res. 27, 616–620.Google Scholar
[43] Sobel, M. J. (1969) Optimal average cost policies for a queue with start-up and shut-down costs. Operat. Res. 17, 145–162.Google Scholar
[44] Sobel, M. J. (1974) Optimal operation of queues. In Mathematical Methods in Queueing Theory, Lecture Notes in Economic and Mathematical Systems 98, Springer-Verlag, New York, 231–261.Google Scholar
[45] Stidham, S. and Prabhu, N. U. (1974) Optimal control of queueing systems. In Mathematical Methods in Queueing, Lecture Notes in Economics and Mathematical Systems 98, Springer-Verlag, New York, 263–294.Google Scholar
[46] Stidham, S. (1978) Socially and individually optimal control of arrivals to a GI/M/1 queue. Management Sci. 24, 1598–1610.Google Scholar
[47] Tijms, H. and Van Der Duyn Schouten, F. (1978) Inventory control with two switch-over levels for a class of M/G/1 queueing systems with variable arrival and service rate. Stoch. Proc. Appl. 6, 213–222.Google Scholar
[48] Topkis, D. (1978) Minimizing a submodular function on a lattice. Operat. Res. 26, 305–321.Google Scholar
[49] Veinott, A. (1969) Discrete dynamic programming with sensitive discount optimality criteria. Ann. Math. Statist. 40, 1635–1660.CrossRefGoogle Scholar
[50] Widder, D. (1946) The Laplace Transform. Princeton University Press, Princeton, N.J. Google Scholar
[51] Winston, W. (1978) Optimality of monotonic policies for multiple-server exponential queueing systems with state-dependent arrival rates. Operat. Res. 26, 1089–1093.Google Scholar
[52] Yechiali, V. (1971) On optimal balking rules and toll charges in a GI/M/1 queueing process. Operat. Res. 19, 349–370.Google Scholar