Abstract
Markov decision processes (MDPs) in queues and networks have been an interesting topic in many practical areas since the 1960s. This paper Provides a detailed overview on this topic and tracks the evolution of many basic results. Also, this paper summarizes several interesting directions in the future research. We hope that this overview can shed light to MDPs in queues and networks, and also to their extensive applications in various practical areas.
Quan-Lin Li was supported by the National Natural Science Foundation of China under grants No. 71671158 and 71932002, and by the Natural Science Foundation of Hebei province under grant No. G2017203277. Li Xia was supported by the National Natural Science Foundation of China under grant No. 61573206. The authors thank X.R. Cao and E.A. Feinberg for their valuable comments and suggestions to improve the presentation of this paper.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdel-Gawad, E.F.: Optimal control of arrivals and routing in a network of queues. Ph.D. dissertation, North Carolina State University (1984)
Adlakha, S., Lall, S., Goldsmith, A.: Networked Markov decision processes with delays. IEEE Trans. Autom. Control 57(4), 1013–1018 (2012)
Adusumilli, K.M., Hasenbein, J.J.: Dynamic admission and service rate control of a queue. Queueing Syst. 66(2), 131–154 (2010)
Ahmed, M.H.: Call admission control in wireless networks: a comprehensive survey. IEEE Commun. Surv. Tutorials 7(1), 49–68 (2005)
Ahn, H.S., Duenyas, I., Lewis, M.E.: Optimal control of a two-stage tandem queuing system with flexible servers. Probab. Eng. Inf. Sci. 16(4), 453–469 (2002)
Alsheikh, M.A., Hoang, D.T., Niyato, D., Tan, H.P., Lin, S.: Markov decision processes with applications in wireless sensor networks: a survey, pp. 1–29. arXiv preprint arXiv:1501.00644 (2015)
Altman, E., Nain, P.: Optimal control of the M/G/1 queue with repeated vacations of the server. IEEE Trans. Autom. Control 38(12), 1766–1775 (1993)
Altman, E.: A Markov game approach for optimal routing into a queuing network. Ph.D. dissertation, INRIA (Institut National de Recherche en Informatique et en Automatique) (1994)
Altman, E.: Non zero-sum stochastic games in admission, service and routing control in queueing systems. Queueing Syst. 23(1–4), 259–279 (1996)
Altman, E.: Constrained Markov Decision Processes. CRC Press (1999)
Altman, E.: A Markov game approach for optimal routing into a queuing network. In: Bardi, M., Raghavan, T.E.S., Parthasarathy, T. (eds.) Stochastic and Differential Games, vol. 4, pp. 359–375. Birkhäuser, Boston (1999). https://doi.org/10.1007/978-1-4612-1592-9_9
Altman, E.: Applications of Markov decision processes in communication networks. In: Feinberg, E.A., Shwartz, A. (eds.) Handbook of Markov Decision Processes, vol. 40, pp. 489–536. Springer, Boston (2002). https://doi.org/10.1007/978-1-4615-0805-2_16
Altman, E., Gaujal, B., Hordijk, A.: Discrete-Event Control of Stochastic Networks: Multimodularity and Regularity. Springer, Heidelberg (2003). https://doi.org/10.1007/b93837
Altman, E., Hordijk, A.: Zero-sum Markov games and worst-case optimal control of queueing systems. Queueing Syst. 21(3–4), 415–447 (1995)
Altman, E., Jiménez, T.: Admission control to an M/M/1 queue with partial information. In: Dudin, A., De Turck, K. (eds.) ASMTA 2013. LNCS, vol. 7984, pp. 12–21. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39408-9_2
Altman, E., Jiménez, T., Koole, G.: On optimal call admission control in resource-sharing system. IEEE Trans. Commun. 49(9), 1659–1668 (2001)
Altman, E., Jiménez, T., Nún̄ez Queija, R., Yechiali, U.: Optimal routing among \(\cdot \)/M/1 queues with partial information. Stoch. Models 20(2), 149–171 (2004)
Altman, E., Nain, P.: Optimality of a threshold policy in the M/M/1 queue with repeated vacations. Math. Methods Oper. Res. 44(1), 75–96 (1996)
Altman, E., Stidham, S.: Optimality of monotonic policies for two-action Markovian decision processes, with applications to control of queues with delayed information. Queueing Syst. 21(3–4), 267–291 (1995)
Anderson, M.Q.: Optimal admission pricing and service rate control of an M\(^{\text{ X }}\)/M/s queue with reneging. Naval Res. Logistics 30(2), 261–270 (1983)
Anderson, W.J.: Continuous-Time Markov Chains: An Applications-Oriented Approach. Springer, New York (1991). https://doi.org/10.1007/978-1-4612-3038-0
Argon, N.T., Tsai, Y.C.: Dynamic control of a flexible server in an assembly-type queue with setup costs. Queueing Syst. 70(3), 233–268 (2012)
Asmussen, S.: Applied Probability and Queues. Springer, New York (2003). https://doi.org/10.1007/b97236
Ata, B.: Dynamic control of a multiclass queue with thin arrival streams. Oper. Res. 54(5), 876–892 (2006)
Atan, S.T.: Solution methods for controlled queueing networks. Ph.D. dissertation, Iowa State University (1997)
Atar, R., Mandelbaum, A., Reiman, M.I.: Scheduling a multi class queue with many exponential servers: asymptotic optimality in heavy traffic. Ann. Appl. Probab. 14(3), 1084–1134 (2004)
Balsamo, S., de Nitto Personé, V., Onvural, R.: Analysis of Queueing Networks with Blocking. Springer, Dordrecht (2001). https://doi.org/10.1007/978-1-4757-3345-7
Bartroli, M.: On the structure of optimal control policies for networks of queues. Ph.D. dissertation, University of North Carolina at Chapel Hill (1989)
Baskett, F., Chandy, K.M., Muntz, R.R., Palacios, F.G.: Open, closed, and mixed networks of queues with different classes of customers. J. ACM 22(2), 248–260 (1975)
Bäuerle, N.: Asymptotic optimality of tracking policies in stochastic networks. Ann. Appl. Probab. 10(4), 1065–1083 (2000)
Bäuerle, N.: Optimal control of queueing networks: an approach via fluid models. Adv. Appl. Probab. 34(2), 313–328 (2002)
Bellman, R., Kalaba, R.E.: Dynamic Programming and Modern Control Theory. Academic Press, New York (1965)
Bertsekas, D.P.: Dynamic Programming and Optimal Control. Athena Scientific, Belmont (1995)
Bertsekas, D.P., Tsitsiklis, J.N.: Neuro-Dynamic Programming. Athena Scientific, Belmont (1996)
Bertsimas, D., Paschalidis, I.C., Tsitsiklis, J.N.: Optimization of multiclass queueing networks: polyhedral and nonlinear characterizations of achievable performance. Ann. Appl. Probab. 4(1), 43–75 (1994)
Besbes, O., Maglaras, C.: Revenue optimization for a make-to-order queue in an uncertain market environment. Oper. Res. 57(6), 1438–1450 (2009)
Bhulai, S.: Dynamic routing policies for multiskill call centers. Probab. Eng. Inf. Sci. 23(1), 101–119 (2009)
Bhulai, S., Brooms, A.C., Spieksma, F.M.: On structural properties of the value function for an unbounded jump Markov process with an application to a processor sharing retrial queue. Queueing Syst. 76(4), 425–446 (2014)
Blackburn, J.D.: Optimal control of a single-server queue with balking and reneging. Manage. Sci. 19(3), 297–313 (1972)
Blanc, J.P.C., de Waal, P.R., Nain, P., Towsley, D.: Optimal control of admission to a multiserver queue with two arrival streams. IEEE Trans. Autom. Control 37(6), 785–797 (1992)
Bolch, G., Greiner, S., De Meer, H., Trivedi, K.S.: Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. Wiley, New York (2006)
Bonomi, F.: On job assignment for a parallel system of processor sharing queues. IEEE Trans. Comput. 39(7), 858–869 (1990)
Boucherie, R.J., Van Dijk, N.M. (eds.): Queueing Networks: A Fundamental Approach. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-6472-4
Boucherie, R.J., Van Dijk, N.M. (eds.): Markov Decision Processes in Practice. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-47766-4
Bradford, R.M.: Pricing, routing, and incentive compatibility in multiserver queues. Eur. J. Oper. Res. 89(2), 226–236 (1996)
Bramson, M.: Stability of Queueing Networks. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68896-9
Browne, S., Yechiali, U.: Dynamic priority rules for cyclic-type queues. Adv. Appl. Probab. 21(2), 432–450 (1989)
Browne, S., Yechiali, U.: Dynamic routing in polling systems. Teletraffic Sci. ITC-12, 1455–1466 (1989)
Browne, S., Yechiali, U.: Dynamic scheduling in single-server multiclass service systems with unit buffers. Naval Res. Logistics 38(3), 383–396 (1991)
Brouns, G.A.: Queueing models with admission andtermination control: monotonicity and threshold results. Technische Universiteit Eindhoven, pp. 1–198 (2003)
Brouns, G.A., Van Der Wal, J.: Optimal threshold policies in a two-class preemptive priority queue with admission and termination control. Queueing Syst. 54(1), 21–33 (2006)
Buzacott, J.A., Shanthikumar, J.G.: Stochastic Models of Manufacturing Systems. Prentice Hall (1993)
Cao, F.: Event-based optimization for the continuous-time Markov systems. Doctoral dissertation, Hong Kong University of Science and Technology, Hong Kong (2008)
Cao, P., Xie, J.: Optimal control of an inventory system with joint production and pricing decisions. IEEE Trans. Autom. Control 61(12), 4235–4240 (2016)
Cao, P., Xie, J.: Optimal control of a multiclass queueing system when customers can change types. Queueing Syst. 82(3–4), 285–313 (2016)
Cao, X.R.: Realization Probabilities: The Dynamics of Queuing Systems. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0035250
Cao, X.R.: Basic ideas for event-based optimization of Markov systems. Discrete Event Dyn. Syst. 15(2), 169–197 (2005)
Cao, X.R.: Stochastic Learning and Optimization: A Sensitivity-Based Approach. Springer, Boston (2007). https://doi.org/10.1007/978-0-387-69082-7
Cao, X.R.: Optimization of average rewards of time nonhomogeneous Markov chains. IEEE Trans. Autom. Control 60(7), 1841–1856 (2015)
Cao, X.R.: Optimality conditions for long-run average rewards with underselectivity and nonsmooth features. IEEE Trans. Autom. Control 62(9), 4318–4332 (2017)
Cao, X.R.: Semismooth potentials of stochastic systems with degenerate diffusions. IEEE Trans. Autom. Control 63(10), 3566–3572 (2018)
Cao, X.R.: State classification and multi-class optimization of continuous-time and continuous-state Markov processes. IEEE Trans. Autom. Control, 1–14 (2019)
Cao, X.R.: Stochastic control of multi-dimensional systems with relative optimization. IEEE Tran Autom. Control, 1–15 (2019)
Cao, X.R.: Relative Optimization of Continuous-time and Continuous-state Stochastic Systems. A complete draft of Cao’s new book by Springer (2019)
Cao, X.R., Chen, H.F.: Perturbation realization, potentials, and sensitivity analysis of Markov processes. IEEE Trans. Autom. Control 42(10), 1382–1393 (1997)
Cao, X.R., Yuan, X.M., Qiu, L.: A single sample path-based performance sensitivity formula for Markov chains. IEEE Trans. Autom. Control 41, 1814–1817 (1996)
Cassandra, A.R.: Exact and Approximate Algorithms for Partially Observable Markov Decision Processes. Doctoral Dissertation, Brown University Providence (1998)
Cassandras, C.G., Lafortune, S.: Introduction to Discrete Event Systems. Springer, Boston (2008). https://doi.org/10.1007/978-0-387-68612-7
Çelik, S., Maglaras, C.: Dynamic pricing and lead-time quotation for a multiclass make-to-order queue. Manag. Sci. 54(6), 1132–1146 (2008)
Chang, C.S., Nelson, R., Yao, D.D.: Optimal task scheduling on distributed parallel processors. Perform. Eval. 20(1–3), 207–221 (1994)
Chang, C.S.: Performance Guarantees in Communication Networks. Springer, London (2000). https://doi.org/10.1007/978-1-4471-0459-9
Chao, X., Miyazawa, M., Pinedo, M.: Queueing Networks: Customers. Signals and Product Form Solutions. Wiley, New York (1999)
Chen, H.: Optimal intensity control of a multi-class queue. Queueing Syst. 5(4), 281–293 (1989)
Chen, H., Frank, M.Z.: State dependent pricing with a queue. IIE Trans. 33(10), 847–860 (2001)
Chen, H., Yang, P., Yao, D.D.: Control and scheduling in a two-station queueing network: optimal policies and heuristics. Queueing Syst. 18(3–4), 301–332 (1994)
Chen, H., Yao, D.D.: Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer, New York (2001). https://doi.org/10.1007/978-1-4757-5301-1
Chen, M.: From Markov Chains to Non-equilibrium Particle Systems. World Scientific, Singapore (2004)
Chen, R.R., Meyn, S.: Value iteration and optimization of multiclass queueing networks. Queueing Syst. 32(1–3), 65–97 (1999)
Chou, T.C.K., Abraham, J.A.: Load balancing in distributed systems. IEEE Trans. Software Eng. 4, 401–412 (1982)
Chung, K.L.: Markov Chains. Springer, Boston (1967). https://doi.org/10.1007/1-4020-0611-X
Cohen, J.W.: The Single Server Queue. North-Holland Publishing Company, Amsterdan (1969)
Crabill, T.B.: Optimal control of a service facility with variable exponential service times and constant arrival rate. Manage. Sci. 18(9), 560–566 (1972)
Crabill, T.B., Gross, D., Magazine, M.J.: A survey of research on optimal design and control of queues. No. Serial T-280, Washington DC program in Logistics, George Washington University (1973)
Crabill, T.B., Gross, D., Magazine, M.J.: A classified bibliography of research on optimal design and control of queues. Oper. Res. 25(2), 219–232 (1977)
Daduna, H.: Queueing Networks with Discrete Time Scale: Explicit Expressions for the Steady State Behavior of Discrete Time Stochastic Networks. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44592-7
Dai, J.G.: On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5(1), 49–77 (1995)
De Serres, Y.: Simultaneous optimization of flow control and scheduling in a single server queue with two job classes. Oper. Res. Lett. 10(2), 103–112 (1991)
De Serres, Y.: Simultaneous optimization of flow-control and scheduling in a single server queue with two job classes: numerical results and approximation. Comput. Oper. Res. 18(4), 361–378 (1991)
Deb, R.K.: Optimal control of batch service queues with switching costs. Adv. Appl. Probab. 8(1), 177–194 (1976)
Deb, R.K., Serfozo, R.F.: Optimal control of batch service queues. Adv. Appl. Probab. 5(2), 340–361 (1973)
Delasay, M., Kolfal, B., Ingolfsson, A.: Maximizing throughput in finite-source parallel queue systems. Eur. J. Oper. Res. 217(3), 554–559 (2012)
Demirkan, H., Spohrer, J.C., Krishna, V. (eds.): Service Systems Implementation. Springer, Boston (2011). https://doi.org/10.1007/978-1-4419-7904-9
De Waal, P.: A constrained optimization problem for a processor sharing queue. Naval Res. Logistics 40(5), 719–731 (1993)
Dimitrakopoulos, Y., Burnetas, A.: The value of service rate flexibility in an M/M/1 queue with admission control. IISE Trans. 49(6), 603–621 (2017)
Dimitrakos, T.D., Kyriakidis, E.G.: A semi-Markov decision algorithm for the maintenance of a production system with buffer capacity and continuous repair times. Int. J. Prod. Econ. 111(2), 752–762 (2008)
Dinh, H.T., Lee, C., Niyato, D., Wang, P.: A survey of mobile cloud computing: architecture, applications, and approaches. Wireless Commun. Mob. Comput. 13(18), 1587–1611 (2013)
Disney, R.L., König, D.: Queueing networks: a survey of their random processes. SIAM Rev. 27(3), 335–403 (1985)
Dobrushin, R.L., Kelbert, M.Y., Rybko, A.N., Suhov, Y.M.: Qualitative methods of queueing network theory. In: Dobrushin, R.L., Kryukov, V.M., Toom, A.L. (eds.) Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis, pp. 183–224. University Press, Manchester (1990)
Doob, J.L.: Stochastic Processes. Wiley, New York (1953)
Doshi, B.T.: Continuous time control of the arrival process in an M/G/1 queue. Stoch. Process. Their Appl. 5(3), 265–284 (1977)
Doshi, B.T.: Optimal control of the service rate in an M/G/1 queueing system. Adv. Appl. Probab. 10(3), 682–701 (1978)
Down, D.G., Koole, G., Lewis, M.E.: Dynamic control of a single-server system with abandonments. Queueing Syst. 67(1), 63–90 (2011)
Down, D.G., Lewis, M.E.: Dynamic load balancing in parallel queueing systems: stability and optimal control. Eur. J. Oper. Res. 168(2), 509–519 (2006)
Dshalalow, J.H.: Advances in Queueing Theory, Methods, and Open Problems. CRC Press, Boca Raton (1995)
Dshalalow, J.H.: Frontiers in Queueing: Models and Applications in Science and Engineering. CRC Press, Boca Raton (1997)
Economou, A., Kanta, S.: Optimal balking strategies and pricing for the single server Markovian queue with compartmented waiting space. Queueing Syst. 59(3–4), 237 (2008)
Efrosinin, D.: Controlled queueing systems with heterogeneous servers. Ph.D. dissertation, Universitätsbibliothek (University of Trier) (2004)
Emmons, H.: The optimal admission policy to a multiserver queue with finite horizon. J. Appl. Probab. 9(1), 103–116 (1972)
Erlang, A.K.: The theory of probabilities and telephone conversations. Nyt Tidsskrift for Matematik 20(B), 33–39 (1909)
Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley, New York (2005)
Ettl, M., Feigin, G.E., Lin, G.Y., Yao, D.D.: A supply network model with base-stock control and service requirements. Oper. Res. 48(2), 216–232 (2000)
Farrar, T.M.: Resource allocation in systems of queues. Ph.D. dissertation, University of Cambridge (1992)
Farrar, T.M.: Optimal use of an extra server in a two station tandem queueing network. IEEE Trans. Autom. Control 38(8), 1296–1299 (1993)
Farrell, W.: Optimal switching policies in a non-homogeneous exponential queueing system. Ph.D. dissertation, University of California at Los Angeles (1976)
Federgruen, A., So, K.C.: Optimality of threshold policies in single-server queueing systems with server vacations. Adv. Appl. Probab. 23(2), 388–405 (1991)
Federgruen, A., Zheng, Y.S.: An efficient algorithm for computing an optimal \((r, Q)\) policy in continuous review stochastic inventory systems. Oper. Res. 40(4), 808–813 (1992)
Federgruen, A., Zipkin, P.: An efficient algorithm for computing optimal \((s, S)\) policies. Oper. Res. 32(6), 1268–1285 (1984)
Feinberg, E.A.: Optimality conditions for inventory control. In: Optimization Challenges in Complex, Networked and Risky Systems, pp. 14–45. INFORMS TutORials in Operations Research (2016)
Feinberg, E.A., Kella, O.: Optimality of D-policies for an M/G/1 queue with a removable server. Queueing Syst. 42(4), 355–376 (2002)
Feinberg, E.A., Kim, D.J.: Bicriterion optimization of an M/G/1 queue with a removable server. Probab. Eng. Inf. Sci. 10(1), 57–73 (1996)
Feinberg, E.A., Liang, Y.: Structure of optimal policies to periodic-review inventory models with convex costs and backorders for all values of discount factors. Ann. Oper. Res., 1–17 (2017)
Feinberg, E.A., Shwartz, A. (eds.): Handbook of Markov Decision Processes: Methods and Applications. Springer, New York (2002). https://doi.org/10.1007/978-1-4615-0805-2
Feinberg, E.A., Yang, F.: Optimality of trunk reservation for an M/M/k/N queue with several customer types and holding costs. Probab. Eng. Inf. Sci. 25(4), 537–560 (2011)
Feinberg, E.A., Yang, F.: Dynamic price optimization for an M/M/k/N queue with several customer types. ACM SIGMETRICS Perform. Eval. Rev. 41(3), 25–27 (2014)
Feinberg, E.A., Yang, F.: Optimal pricing for a GI/M/k/N queue with several customer types and holding costs. Queueing Syst. 82(1–2), 103–120 (2016)
Feinberg, E.A., Zhang, X.: Optimal switching on and off the entire service capacity of a parallel queue. Probab. Eng. Inf. Sci. 29(4), 483–506 (2015)
Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, New York (2012). https://doi.org/10.1007/978-1-4612-4054-9
Franken, L.J., Haverkort, B.R.: Reconfiguring distributed systems using Markov-decision models. In: Proceedings of the Workshop on Trends in Distributed Systems, pp. 219–228 (1996)
Gajrat, A., Hordijk, A., Ridder, A.: Large-deviations analysis of the fluid approximation for a controllable tandem queue. Ann. Appl. Probab. 13(4), 1423–1448 (2003)
Gallisch, E.: On monotone optimal policies in a queueing model of M/G/1 type with controllable service time distribution. Ann. Appl. Probab. 11(4), 870–887 (1979)
Gandhi, A.D., Cassandras, C.G.: Optimal control of polling models for transportation applications. Math. Comput. Modell. 23(11–12), 1–23 (1996)
Gans, N., Koole, G., Mandelbaum, A.: Telephone call centers: tutorial, review, and research prospects. Manuf. Serv. Oper. Management. 5(2), 79–141 (2003)
Garavello, M., Piccoli, B.: Traffic Flow on Networks. Springfield: American Institute of Mathematical Sciences (2006)
Gast, N., Gaujal, B.: A mean field approach for optimization in discrete time. Discrete Event Dyn. Syst. 21(1), 63–101 (2011)
Gast, N., Gaujal, B., Le Boudec, J.Y.: Mean field for Markov decision processes: from discrete to continuous optimization. IEEE Trans. Autom. Control 57(9), 2266–2280 (2012)
Gaujal, B., Hordijk, A., Van Der Laan, D.: On the optimal open-loop control policy for deterministic and exponential polling systems. Probab. Eng. Inf. Sci. 21(2), 157–187 (2007)
Gayon, J.P., De Vericourt, F., Karaesmen, F.: Stock rationing in an M/E\(_{\text{ r }}\)/1 multi-class make-to-stock queue with backorders. IIE Trans. 41(12), 1096–1109 (2009)
Gelenbe, E., Pujolle, G., Gelenbe, E., Pujolle, G.: Introduction to Queueing Networks. Wiley, New York (1998)
George, J.M., Harrison, J.M.: Dynamic control of a queue with adjustable service rate. Oper. Res. 49(5), 720–731 (2001)
Ghoneim, H.A., Stidham, S.: Control of arrivals to two queues in series. Eur. J. Oper. Res. 21(3), 399–409 (1985)
Giovanidis, A., Wunder, G., Bühler, J.: Optimal control of a single queue with retransmissions: delay-dropping tradeoffs. IEEE Trans. Wireless Commun. 8(7), 3736–3746 (2009)
Glasserman, P., Ho, Y.C.: Gradient Estimation via Perturbation Analysis. Springer, Boston (1991)
Glasserman, P., Yao, D.D.: Monotone Structure in Discrete-Event Systems. Wiley, New York (1994)
Groenevelt, R., Koole, G., Nain, P.: On the bias vector of a two-class preemptive priority queue. Math. Methods Oper. Res. 55(1), 107–120 (2002)
Guo, X., Hernández-Lerma, O.: Continuous-Time Markov Decision Processes. Springer, Heidelberg (2009)
Ha, A.Y.: Inventory rationing in a make-to-stock production system with several demand classes and lost sales. Manage. Sci. 43(8), 1093–1103 (1997)
Ha, A.Y.: Stock-rationing policy for a make-to-stock production system with two priority classes and backordering. Naval Res. Logistics 44(5), 457–472 (1997)
Ha, A.Y.: Stock rationing in an M/E\(_{\text{ k }}\)/1 make-to-stock queue. Manage. Sci. 46(1), 77–87 (2000)
Hajek, B.: Optimal control of two interacting service stations. IEEE Trans. Autom. Control 29(6), 491–499 (1984)
Hariharan, R., Moustafa, M.S., Stidham, S.: Scheduling in a multi-class series of queues with deterministic service times. Queueing Syst. 24(1–4), 83–99 (1996)
Harrison, J.M.: Dynamic scheduling of a multiclass queue: discount optimality. Oper. Res. 23(2), 270–282 (1975)
Harrison, J.M.: Brownian Motion and Stochastic Flow Systems. Wiley, New York (1985)
Haviv, M., Puterman, M.L.: Bias optimality in controlled queueing systems. J. Appl. Probab. 35(1), 136–150 (1998)
Helm, W.E., Waldmann, K.H.: Optimal control of arrivals to multiserver queues in a random environment. J. Appl. Probab. 21(3), 602–615 (1984)
Hernádez-Lerma, O., Lasserre, J.B.: Discrete-Time Markov Control Processes: Basic Optimality Criteria. Springer, New York (1996). https://doi.org/10.1007/978-1-4612-0729-0
Hernádez-Lerma, O., Lasserre, J.B.: Further Topics on Discrete-Time Markov Control Processes. Springer, New York (1999). https://doi.org/10.1007/978-1-4612-0561-6
Ho, Y.C., Cao, X.R.: Performance sensitivity to routing changes in queuing networks and flexible manufacturing systems using perturbation analysis. IEEE J. Rob. Autom. 1(4), 165–172 (1985)
Ho, Y.C., Cao, X.R.: Perturbation Analysis of Discrete-Event Dynamic Systems. Kluwer Academic Publisher, Boston (1991)
Honhon, D., Seshadri, S.: Admission control with incomplete information to a finite buffer queue. Probab. Eng. Inf. Sci. 21(1), 19–46 (2007)
Hordijk, A., Koole, G.: On the shortest queue policy for the tandem parallel queue. Probab. Eng. Inf. Sci. 6(1), 63–79 (1992)
Hordijk, A., Koole, G.: On the optimality of LEPT and \(\mu \)c rules for parallel processors and dependent arrival processes. Adv. Appl. Probab. 25(4), 979–996 (1993)
Hordijk, A., Passchier, O., Spieksma, F.: Optimal service control against worst case admission policies: a multichained stochastic game. Math. Methods Oper. Res. 45(2), 281–301 (1997)
Hordijk, A., Van Der Duyn Schouten, F.A.: Average optimal policies in Markov decision drift processes with applications to a queueing and a replacement model. Adv. Appl. Probab. 15(2), 274–303 (1983)
Hordijk, A., Spieksma, F.: Constrained admission control to a queueing system. Ann. Appl. Probab. 21(2), 409–431 (1989)
Howard, R.A.: Dynamic Programming and Markov Processes. MIT Press, Cambridge (1960)
Hu, Q.Y., Yue, W.Y.: Markov Decision Processes with Their Applications. Springer, Boston (2007). https://doi.org/10.1007/978-0-387-36951-8
Iravani, S.M., Posner, M.J.M., Buzacott, J.A.: A two-stage tandem queue attended by a moving server with holding and switching costs. Queueing Syst. 26(3–4), 203–228 (1997)
Jackson, J.R.: Networks of waiting lines. Oper. Res. 5(4), 518–521 (1957)
Jackson, J.R.: Jobshop-like queueing systems. Manage. Sci. 10(1), 131–142 (1963)
Jain, A.: Priority and dynamic scheduling in a make-to-stock queue with hyperexponential demand. Naval Res. Logistics 53(5), 363–382 (2006)
Jia, Q.S.: On solving event-based optimization with average reward over infinite stages. IEEE Trans. Autom. Control 56(12), 2912–2917 (2011)
Jo, K.Y., Maimon, O.Z.: Optimal dynamic load distribution in a class of flow-type flexible manufacturing systems. Eur. J. Oper. Res. 55(1), 71–81 (1991)
Jo, K.Y., Stidham, S.: Optimal service-rate control of M/G/1 queueing systems using phase methods. Ann. Appl. Probab. 15(3), 616–637 (1983)
Johansen, S.G., Larsen, C.: Computation of a near-optimal service policy for a single-server queue with homogeneous jobs. Eur. J. Oper. Res. 134(3), 648–663 (2001)
Karlin, S.: A First Course in Stochastic Processes. Academic Press, New York (1968)
Karlin, S., Taylor, H.E.: A Second Course in Stochastic Processes. Elsevier, New York (1981)
Kella, O.: Optimal control of the vacation scheme in an M/G/1 queue. Oper. Res. 38(4), 724–728 (1990)
Kelly, F.P.: Networks of queues. Ann. Appl. Probab. 8(2), 416–432 (1976)
Kelly, F.P.: Reversibility and Stochastic Networks. Cambridge University Press, Cambridge (1979)
Kelly, F.P.: Loss networks. Ann. Appl. Probab. 1(3), 319–378 (1991)
Kemeny, J.G., Snell, J.L., Knapp, A.W.: Denumerable Markov Chains: with a Chapter of Markov Random Fields by David Griffeath. Springer, New York (1976). https://doi.org/10.1007/978-1-4684-9455-6
Kitaev, M.Y., Rykov, V.V.: Controlled Queueing Systems. CRC Press, Boca Raton (1995)
Kitaev, M.Y., Serfozo, R.F.: M/M/1 queues with switching costs and hysteretic optimal control. Oper. Res. 47(2), 310–312 (1999)
Kleinrock, L.: Queueing Systems, Volume 1: Theory. Wiley Interscience, New York (1975)
Kleinrock, L.: Queueing Systems, Volume II: Computer Applications. Wiley Interscience, New York (1976)
Koçağa, Y.L., Ward, A.R.: Admission control for a multi-server queue with abandonment. Queueing Syst. 65(3), 275–323 (2010)
Kofman, E., Lippman, S.A.: An M/M/1 dynamic priority queue with optional promotion. Oper. Res. 29(1), 174–188 (1981)
Kolobov, A.: Planning with Markov decision processes: an AI perspective. Synthesis Lectures on Artificial Intelligence and Machine Learning 6(1), 1–210 (2012)
Koole, G.: On the pathwise optimal Bernoulli routing policy for homogeneous parallel servers. Math. Oper. Res. 21(2), 469–476 (1996)
Koole, G.: The deviation matrix of the M/M/1/\(\infty \) and M/M/1/N queue, with applications to controlled queueing models. In: Proceedings of the 37th IEEE Conference on Decision and Control, vol. 1, pp. 56–59 (1998)
Koole, G., Mandelbaum, A.: Queueing models of call centers: an introduction. Ann. Oper. Res. 113(1–4), 41–59 (2002)
Koole, G.: Convexity in tandem queues. Probab. Eng. Inf. Sci. 18(1), 13–31 (2004)
Koole, G.: Monotonicity in Markov reward and decision chains: theory and applications. Found. Trends Stoch. Syst. 1(1), 1–76 (2007)
Koole, G.: Call Center Optimization (2013). Lulu.com
Koole, G., Nain, P.: On the value function of a priority queue with an application to a controlled polling model. Queueing Syst. 34(1–4), 199–214 (2000)
Krishnamurthy, V.: Partially Observed Markov Decision Processes. Cambridge University Press, Cambridge (2016)
Ku, C.Y., Jordan, S.: Access control of parallel multiserver loss queues. Perform. Eval. 50(4), 219–231 (2002)
Kumar, A.: Task allocation in multiserver systems–a survey of results. Sadhana 15(4–5), 381–395 (1990)
Kumar, R., Lewis, M.E., Topaloglu, H.: Dynamic service rate control for a single-server queue with Markov-modulated arrivals. Naval Res. Logistics 60(8), 661–677 (2013)
Kuo, Y.: Optimal adaptive control policy for joint machine maintenance and product quality control. Eur. J. Oper. Res. 171(2), 586–597 (2006)
Kuri, J., Kumar, A.: Optimal control of arrivals to queues with delayed queue length information. IEEE Trans. Autom. Control 40(8), 1444–1450 (1995)
Kuri, J., Kumar, A.: On the optimal control of arrivals to a single queue with arbitrary feedback delay. Queueing Syst. 27(1–2), 1–16 (1997)
Kushner, H.J.: Heavy Traffic Analysis of Controlled Queueing and Communication Networks. Springer, New York (2001). https://doi.org/10.1007/978-1-4613-0005-2
Kushner, H.J., Martins, L.F.: Heavy traffic analysis of a controlled multiclass queueing network via weak convergence methods. SIAM J. Control Optim. 34(5), 1781–1797 (1996)
Kushner, H.J., Ramachandran, K.M.: Optimal and approximately optimal control policies for queues in heavy traffic. SIAM J. Control Optim. 27(6), 1293–1318 (1989)
Lakshmi, C., Iyer, S.A.: Application of queueing theory in health care: a literature review. Oper. Res. Health Care 2(1–2), 25–39 (2013)
Lamond, B.F.: Optimal admission policies for a finite queue with bursty arrivals. Ann. Oper. Res. 28(1), 243–260 (1991)
Larsen, R.L., Agrawala, A.K.: Control of a heterogeneous two-server exponential queueing system. IEEE Trans. Software Eng. 4, 522–526 (1983)
Larrañaga, M., Ayesta, U., Verloop, I.M.: Index policies for a multi-class queue with convex holding cost and abandonments. ACM SIGMETRICS Perform. Eval. Rev. 42(1), 125–137 (2014)
Latouche, G., Ramaswami, V.: Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM (1999)
Lautenbacher, C.J., Stidham, S.: The underlying Markov decision process in the single-leg airline yield-management problem. Transp. Sci. 33(2), 136–146 (1999)
Lee, N., Kulkarni, V.G.: Optimal arrival rate and service rate control of multi-server queues. Queueing Syst. 76(1), 37–50 (2014)
Leeuwen, D.V., Núnez-Queija, R.: Near-optimal switching strategies for a tandem queue. In: Boucherie, R., van Dijk, N. (eds.) Markov Decision Processes in Practice, vol. 248, pp. 439–459. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-47766-4_17
Legros, B., Jouini, O., Koole, G.: Optimal scheduling in call centers with a callback option. Perform. Eval. 95, 1–40 (2016)
Legros, B., Jouini, O., Koole, G.: A uniformization approach for the dynamic control of queueing systems with abandonments. Oper. Res. 66(1), 200–209 (2018)
Lewis, M.E., Ayhan, H., Foley, R.D.: Bias optimality in a queue with admission control. Probab. Eng. Inf. Sci. 13(3), 309–327 (1999)
Li, J., Kameda, H.: Load balancing problems for multiclass jobs in distributed/parallel computer systems. IEEE Trans. Comput. 47(3), 322–332 (1998)
Li, Q.L.: Constructive Computation in Stochastic Models with Applications: The RG-Factorizations. Springer, Heidelberg and Tsinghua Press (2010). https://doi.org/10.1007/978-3-642-11492-2
Li, Q.L.: Nonlinear Markov processes in big networks. Spec. Matrices 4(1), 202–217 (2016)
Li, Q.L., Dai, G., Lui, J.C.S., Wang, Y.: The mean-field computation in a supermarket model with server multiple vacations. Discrete Event Dyn. Syst. 24(4), 473–522 (2014)
Li, Q.L., Du, Y., Dai, G., Wang, M.: On a doubly dynamically controlled supermarket model with impatient customers. Comput. Oper. Res. 55, 76–87 (2015)
Li, Q.L., Li, Y.M., Ma, J.Y., Liu, H.L.: A complete algebraic transformational solution for the optimal dynamic policy in inventory rationing across two demand classes. Online Publication, pp. 1–62, arXiv:1908.09295 (2019)
Li, Q.L., Liu, L.M.: An algorithmic approach on sensitivity analysis of perturbed QBD processes. Queueing Syst. 48(3–4), 365–397 (2004)
Li, Q.L., Lui, J.C.S.: Block-structured supermarket models. Discrete Event Dyn. Syst. 26(2), 147C–182 (2016)
Liang, H.M., Kulkarni, V.G.: Optimal routing control in retrial queues. In: Shanthikumar, J.G., Sumita, U. (eds.) Applied Probability and Stochastic Processes, vol. 19, pp. 203–218. Springer, Boston (1999). https://doi.org/10.1007/978-1-4615-5191-1_14
Lin, W., Kumar, P.: Optimal control of a queueing system with two heterogeneous servers. IEEE Trans. Autom. Control 29(8), 696–703 (1984)
Lippman, S.A.: Applying a new device in the optimization of exponential queuing systems. Oper. Res. 23(4), 687–710 (1975)
Liu, Z., Nain, P., Towsley, D.: Sample path methods in the control of queues. Queueing Syst. 21(3–4), 293–335 (1995)
Low, D.W.: Optimal pricing for an unbounded queue. IBM J. Res. Dev. 18(4), 290–302 (1974)
Low, D.W.: Optimal dynamic pricing policies for an M/M/s queue. Oper. Res. 22(3), 545–561 (1974)
Lu, F.V., Serfozo, R.F.: M/M/1 queueing decision processes with monotone hysteretic optimal policies. Oper. Res. 32(5), 1116–1132 (1984)
Ma, D.J., Cao, X.R.: A direct approach to decentralized control of service rates in a closed Jackson network. IEEE Trans. Autom. Control 39(7), 1460–1463 (1994)
Ma, J.Y., Xia, L., Li, Q.L.: Optimal energy-efficient policies for data centers through sensitivity-based optimization. Discrete Event Dyn. Syst., 1–40 (2019)
Ma, J.Y., Li, Q.L., Xia, L.: Optimal asynchronous dynamic policies in energy-efficient data centers. Online Publication, 1–63, arXiv:190103371 (2019)
Maglaras, C.: Dynamic scheduling in multiclass queueing networks: stability under discrete-review policies. Queueing Syst. 31(3–4), 171–206 (1999)
Mandelbaum, A., Yechiali, U.: Optimal entering rules for a customer with wait option at an M/G/1 queue. Manage. Sci. 29(2), 174–187 (1983)
Marin, A., Rossi, S.: Power control in saturated fork-join queueing systems. Perform. Eval. 116, 101–118 (2017)
Markov, A.A.: Rasprostranenie zakona bol’shih chisel na velichiny, zavisyaschie drug ot druga. In: Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156 (1906)
Mendelson, H., Yechiali, U.: Controlling the GI/M/1 queue by conditional acceptance of customers. Eur. J. Oper. Res. 7(1), 77–85 (1981)
Menich, R., Serfozo, R.F.: Optimality of routing and servicing in dependent parallel processing systems. Queueing Syst. 9(4), 403–418 (1991)
Meyn, S.P., Tweedie, R.L.: Markov Chains and Stochastic Stability. Springer, London (1996). https://doi.org/10.1007/978-1-4471-3267-7
Miller, B.L.: Finite state continuous time Markov decision processes with applications to a class of optimization problems in queueing theory. Ph.D. dissertation, Stanford University, California, USA (1967)
Mitchell, B.: Optimal service-rate selection in an M/G/1 Queue. SIAM J. Appl. Math. 24(1), 19–35 (1973)
Nadar, E., Akan, M., Scheller-Wolf, A.: Technical note–optimal structural results for assemble-to-order generalized M-systems. Oper. Res. 62(3), 571–579 (2014)
Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. The Johns Hopkins University Press, Baltimore (1981)
Neuts, M.F.: Structured Stochastic Matrices of M/G/1Type and Their Applications. Dekker (1989)
Nishimura, S.: Service mechanism control and arrival control of a two-station tandem queue. J. Oper. Res. Soc. Japan 29(3), 191–205 (1986)
Nobel, R.D., Tijms, H.C.: Optimal control for an M\(^{\text{ X }}\)/G/1 queue with two service modes. Eur. J. Oper. Res. 113(3), 610–619 (1999)
Nobel, R.D., Tijms, H.C.: Optimal control of a queueing system with heterogeneous servers and setup costs. IEEE Trans. Autom. Control 45(4), 780–784 (2000)
Okamura, H., Miyata, S., Dohi, T.: A Markov decision process approach to dynamic power management in a cluster system. IEEE Access 3, 3039–3047 (2015)
Pajarinen, J., Hottinen, A., Peltonen, J.: Optimizing spatial and temporal reuse in wireless networks by decentralized partially observable Markov decision processes. IEEE Trans. Mob. Comput. 13(4), 866–879 (2014)
Papadimitriou, C.H., Tsitsiklis, J.N.: The complexity of optimal queuing network control. Math. Oper. Res. 24(2), 293–305 (1999)
Pascual, R., Martínez, A., Giesen, R.: Joint optimization of fleet size and maintenance capacity in a fork-join cyclical transportation system. J. Oper. Res. Soc. 64(7), 982–994 (2013)
Patrick, J., Begen, M.A.: Markov decision processes and its applications in healthcare. In: Handbook of Healthcare Delivery Systems. CRC (2011)
Perez, A.P., Zipkin, P.: Dynamic scheduling rules for a multiproduct make-to-stock queue. Oper. Res. 45(6), 919–930 (1997)
Piunovskiy, A.B.: Bicriteria optimization of a queue with a controlled input stream. Queueing Syst. 48(1–2), 159–184 (2004)
Plambeck, E., Kumar, S., Harrison, J.M.: A multiclass queue in heavy traffic with throughput time constraints: asymptotically optimal dynamic controls. Queueing Syst. 39(1), 23–54 (2001)
Plum, H.J.: Optimal monotone hysteretic Markov policies in an M/M/1 queueing model with switching costs and finite time horizon. Zeitschrift für Oper. Res. 35(5), 377–399 (1991)
Powell, W.B., Humblet, P.: The bulk service queue with a general control strategy: theoretical analysis and a new computational procedure. Oper. Res. 34(2), 267–275 (1986)
Printezis, A., Burnetas, A.: Priority option pricing in an M/M/m queue. Oper. Res. Lett. 36(6), 700–704 (2008)
Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (1994)
Qiu, Q., Pedram, M.: Dynamic power management based on continuous-time Markov decision processes. In: Proceedings of the 36th annual ACM/IEEE Design Automation Conference, pp. 555–561 (1999)
Robinson, D.R.: Markov decision chains with unbounded costs and applications to the control of queues. Adv. Appl. Probab. 8(1), 159–176 (1976)
Robinson, D.R.: Optimization of priority queues–a semi-Markov decision chain approach. Manage. Sci. 24(5), 545–553 (1978)
Rosberg, Z., Kermani, P.: Customer routing to different servers with complete information. Adv. Appl. Probab. 21(4), 861–882 (1989)
Rosberg, Z., Varaiya, P., Walrand, J.: Optimal control of service in tandem queues. IEEE Trans. Autom. Control 27(3), 600–610 (1982)
Ross, K.W.: Optimal dynamic routing in Markov queueing networks. Automatica 22(3), 367–370 (1986)
Rue, R.C., Rosenshine, M.: Optimal control for entry of many classes of customers to an M/M/1 queue. Naval Res. Logistics 28(3), 489–495 (1981)
Rue, R.C., Rosenshine, M.: Some properties of optimal control policies for entry to an M/M/1 queue. Naval Res. Logistics 28(4), 525–532 (1981)
Rue, R.C., Rosenshine, M.: Optimal control of entry to an M/E\(_{k}\)/1 queue serving several classes of customers. Naval Res. Logistics 30(2), 217–226 (1983)
Rue, R.C., Rosenshine, M.: The application of semi-Markov decision processes to queueing of aircraft for landing at an airport. Transp. Sci. 19(2), 154–172 (1985)
Rykov, V.V.: Controllable queueing systems. Itogi Nauki i Tekhniki. Seriya “Teoriya Veroyatnostei. Matematicheskaya Statistika. Teoreticheskaya Kibernetika” 12, 45–152 (1975) (There is English translation in Journal of Soviet Mathematics). (In Russian)
Rykov, V.V.: Monotone control of queueing systems with heterogeneous servers. Queueing Syst. 37(4), 391–403 (2001)
Rykov, V.V.: Controllable queueing systems: from the very beginning up to nowadays. Reliab. Theor. Appl. 12(2(45)), 39–61 (2017)
Rykov, V.V., Efrosinin, D.: Optimal control of queueing systems with heterogeneous servers. Queueing Syst. 46(3–4), 389–407 (2004)
Rykov, V.V., Efrosinin, D.: On optimal control of systems on their life time. In: Lisnianski, A., Frenkel, I. (eds.) Recent Advances in System Reliability. Springer Series in Reliability Engineering, pp. 307–319. Springer, London (2012). https://doi.org/10.1007/978-1-4471-2207-4_22
Rykov, V.V., Lembert, E.: Optimal dynamic priorities in single-line queueing systems. Eng. Cybern. 5(1), 21–30 (1967)
Sanajian, N., Abouee-Mehrizi, H., Balcıoglu, B.: Scheduling policies in the M/G/1 make-to-stock queue. J. Oper. Res. Soc. 61(1), 115–123 (2010)
Savaşaneril, S., Griffin, P.M., Keskinocak, P.: Dynamic lead-time quotation for an M/M/1 base-stock inventory queue. Oper. Res. 58(2), 383–395 (2010)
Schassberger, R.: A note on optimal service selection in a single server queue. Manage. Sci. 21(11), 1326–1331 (1975)
Sennott, L.I.: Average cost semi-Markov decision processes and the control of queueing systems. Probab. Eng. Inf. Sci. 3(2), 247–272 (1989)
Sennott, L.I.: Stochastic Dynamic Programming and the Control of Queueing Systems. Wiley, New York (2009)
Serfozo, R.F.: Optimal control of random walks, birth and death processes, and queues. Adv. Appl. Probab. 13(1), 61–83 (1981)
Serfozo, R.F.: Introduction to Stochastic Networks. Springer, New York (1999). https://doi.org/10.1007/978-1-4612-1482-3
Shanthikumar, J.G., Yao, D.D.: Stochastic monotonicity in general queueing networks. J. Appl. Probab. 26(2), 413–417 (1989)
Shioyama, T.: Optimal control of a queuing network system with two types of customers. Eur. J. Oper. Res. 52(3), 367–372 (1991)
Sigaud, O., Buffet, O. (eds.): Markov Decision Processes in Artificial Intelligence. Wiley (2013)
e Silva, E.D.S., Gerla, M.: Queueing network models for load balancing in distributed systems. J. Parallel Distrib. Comput. 12(1), 24–38 (1991)
Sobel, M.J.: Optimal operation of queues. In: Clarke, A.B. (ed.) Mathematical Methods in Queueing Theory, vol. 98, pp. 231–261. Springer, Heidelberg (1974). https://doi.org/10.1007/978-3-642-80838-8_12
Solodyannikov, Y.V.: Control and observation for dynamical queueing networks I. Autom. Remote Control 75(3), 422–446 (2014)
Sparaggis, P.D., Towsley, D., Cassandras, C.G.: Optimal control of multiclass parallel service systems. Discrete Event Dyn. Syst. 6(2), 139–158 (1996)
Stidham, S.: On the optimality of single-server queuing systems. Oper. Res. 18(4), 708–732 (1970)
Stidham, S.: Socially and individually optimal control of arrivals to a GI/M/1 queue. Manage. Sci. 24(15), 1598–1610 (1978)
Stidham, S.: Optimal control of admission to a queueing system. IEEE Trans. Autom. Control 30(8), 705–713 (1985)
Stidham, S.: Scheduling, routing, and flow control in stochastic networks. In: Fleming, W., Lions, P.L. (eds.) Stochastic Differential Systems, Stochastic Control Theory and Applications, vol. 10, pp. 529–561. Springer, New York (1988). https://doi.org/10.1007/978-1-4613-8762-6_31
Stidham, S.: Analysis, design, and control of queueing systems. Oper. Res. 50(1), 197–216 (2002)
Stidham, S.: On the optimality of a full-service policy for a queueing system with discounted costs. Math. Methods Oper. Res. 62(3), 485–497 (2005)
Stidham, S.: Optimal Design of Queueing Systems. Chapman and Hall/CRC, Boca Raton (2009)
Stidham, S., Prabhu, N.U.: Optimal control of queueing systems. In: Clarke, A.B. (ed.) Mathematical Methods in Queueing Theory, vol. 98, pp. 263–294. Springer, Heidelberg (1974). https://doi.org/10.1007/978-3-642-80838-8_13
Stidham, S., Weber, R.: A survey of Markov decision models for control of networks of queues. Queueing Syst. 13(1–3), 291–314 (1993)
Sun, L., Dong, H., Hussain, F.K., Hussain, O.K., Chang, E.: Cloud service selection: state-of-the-art and future research directions. J. Netw. Comput. Appl. 45, 134–150 (2014)
Syski, R.: A personal view of queueing theory. In: Frontiers in Queueing: Models and Applications in Science and Engineering, pp. 3–18. CRC Press (1997)
Tassiulas, L., Ephremides, A.: Throughput properties of a queueing network with distributed dynamic routing and flow control. Adv. Appl. Probab. 28(1), 285–307 (1996)
Tijms, H.C.: Stochastic Models: An Algorithmic Approach. Wiley (1994)
Tijms, H.C., van der Duyn Schouten, F.A.: A Markov decision algorithm for optimal inspections and revisions in a maintenance system with partial information. Eur. J. Oper. Res. 21(2), 245–253 (1985)
Tirdad, A., Grassmann, W.K., Tavakoli, J.: Optimal policies of \(M(t)/M/c/c\) queues with two different levels of servers. Eur. J. Oper. Res. 249(3), 1124–1130 (2016)
Towsley, D., Sparaggis, P.D., Cassandras, C.G.: Optimal routing and buffer allocation for a class of finite capacity queueing systems. IEEE Trans. Autom. Control 37(9), 1446–1451 (1992)
Vanberkel, P.T., Boucherie, R.J., Hans, E.W., Hurink, J.L., Litvak, N.: A survey of health care models that encompass multiple departments. Int. J. Health Manag. Inf. 1(1), 37–69 (2010)
Van der Weij, W., Bhulai, S., Van der Mei, R.: Optimal scheduling policies for the limited processor sharing queue. Technical report WS2008-5, Department of Mathematics, Vrije University (2008)
Van Dijk, N.M.: Queueing Networks and Product Forms: A Systems Approach. Wiley (1993)
Van Dijk, N.M., Puterman, M.L.: Perturbation theory for Markov reward processes with applications to queueing systems. Adv. Appl. Probab. 20(1), 79–98 (1988)
Van Nunen, J.A.E.E., Puterman, M.L.: Computing optimal control limits for GI/M/s queuing systems with controlled arrivals. Manage. Sci. 29(6), 725–734 (1983)
Varma, S.: Optimal allocation of customers in a two server queue with resequencing. IEEE Trans. Autom. Control 36(11), 1288–1293 (1991)
Veatch, M.H.: Queueing control problems for production/inventory systems. Ph.D. dissertation, Massachusetts Institute of Technology (1992)
Veatch, M.H., Wein, L.M.: Monotone control of queueing networks. Queueing Syst. 12(3–4), 391–408 (1992)
Vercraene, S., Gayon, J.P., Karaesmen, F.: Effects of system parameters on the optimal cost and policy in a class of multidimensional queueing control problems. Oper. Res. 66(1), 150–162 (2018)
Wakuta, K.: Optimal control of an M/G/1 queue with imperfectly observed queue length when the input source is finite. J. Appl. Probab. 28(1), 210–220 (1991)
Wang, D.X., Cao, X.R.: Event-based optimization for POMDPs and its application in portfolio management. In: Proceedings of the 18th IFAC World Congress, vol. 44, no. 1, pp. 3228–3233 (2011)
Weber, R.R.: On the optimal assignment of customers to parallel servers. J. Appl. Probab. 15(2), 406–413 (1978)
Weber, R.R., Stidham, S.: Optimal control of service rates in networks of queues. Adv. Appl. Probab. 19(1), 202–218 (1987)
White, L.B.: A new policy evaluation algorithm for Markov decision processes with quasi birth-death structure. Stoch. Models 21(2–3), 785–797 (2005)
Winkler, A.: Dynamic scheduling of a single-server two-class queue with constant retrial policy. Ann. Oper. Res. 202(1), 197–210 (2013)
Wu, C.H., Lin, J.T., Chien, W.C.: Dynamic production control in a serial line with process queue time constraint. Int. J. Prod. Res. 48(13), 3823–3843 (2010)
Xia, L.: Service rate control of closed Jackson networks from game theoretic perspective. Eur. J. Oper. Res. 237(2), 546–554 (2014)
Xia, L.: Event-based optimization of admission control in open queueing networks. Discrete Event Dyn. Syst. 24(2), 133–151 (2014)
Xia, L., Cao, X.R.: Performance optimization of queueing systems with perturbation realization. Eur. J. Oper. Res. 218(2), 293–304 (2012)
Xia, L., Chen, S.: Dynamic pricing control for open queueing networks. IEEE Trans. Autom. Control 63(10), 3290–3300 (2018)
Xia, L., He, Q.M., Alfa, A.S.: Optimal control of state-dependent service rates in a MAP/M/1 queue. IEEE Trans. Autom. Control 62(10), 4965–4979 (2017)
Xia, L., Jia, Q.S.: Parameterized Markov decision process and its application to service rate control. Automatica 54, 29–35 (2015)
Xia, L., Jia, Q.S., Cao, X.R.: A tutorial on event-based optimization–a new optimization framework. Discrete Event Dyn. Syst. 24(2), 103–132 (2014)
Xia, L., Shihada, B.: Max-Min optimality of service rate control in closed queueing networks. IEEE Trans. Autom. Control 58(4), 1051–1056 (2013)
Xu, S.H., Righter, R., Shanthikumar, J.G.: Optimal dynamic assignment of customers to heterogeneous servers in parallel. Oper. Res. 40(6), 1126–1138 (1992)
Xu, S.H., Zhao, Y.Q.: Dynamic routing and jockeying controls in a two-station queueing system. Adv. Appl. Probab. 28(4), 1201–1226 (1996)
Xu, J., Hajek, B.: The supermarket game. Stoch. Syst. 3(2), 405–441 (2013)
Yang, R., Bhulai, S., van der Mei, R.: Structural properties of the optimal resource allocation policy for single-queue systems. Ann. Oper. Res. 202(1), 211–233 (2013)
Yao, D.D., Schechner, Z.: Decentralized control of service rates in a closed Jackson network. IEEE Trans. Autom. Control 34(2), 236–240 (1989)
Yechiali, U.: Customers’ optimal joining rules for the GI/M/s queue. Manage. Sci. 18(7), 434–443 (1972)
Yeh, L., Thomas, L.C.: Adaptive control of M/M/1 queues–continuous-time Markov decision process approach. J. Appl. Probab. 20(2), 368–379 (1983)
Yildirim, U., Hasenbein, J.J.: Admission control and pricing in a queue with batch arrivals. Oper. Res. Lett. 38(5), 427–431 (2010)
Yoon, S., Lewis, M.E.: Optimal pricing and admission control in a queueing system with periodically varying parameters. Queueing Syst. 47(3), 177–199 (2004)
Zayas-Cabán, G., Xie, J., Green, L.V., Lewis, M.E.: Dynamic control of a tandem system with abandonments. Queueing Syst. 84(3–4), 279–293 (2016)
Zeng, Y., Chaintreau, A., Towsley, D., Xia, C.H.: A necessary and sufficient condition for throughput scalability of fork and join networks with blocking. ACM SIGMETRICS Perform. Eval. Rev. 44(1), 25–36 (2016)
Zeng, Y., Chaintreau, A., Towsley, D., Xia, C.H.: Throughput scalability analysis of fork-join queueing networks. Oper. Res. 66(6), 1728–1743 (2018)
Zhang, B., Ayhan, H.: Optimal admission control for tandem queues with loss. IEEE Trans. Autom. Control 58(1), 163–167 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Singapore Pte Ltd.
About this chapter
Cite this chapter
Li, QL., Ma, JY., Fan, RN., Xia, L. (2019). An Overview for Markov Decision Processes in Queues and Networks. In: Li, QL., Wang, J., Yu, HB. (eds) Stochastic Models in Reliability, Network Security and System Safety. JHC80 2019. Communications in Computer and Information Science, vol 1102. Springer, Singapore. https://doi.org/10.1007/978-981-15-0864-6_3
Download citation
DOI: https://doi.org/10.1007/978-981-15-0864-6_3
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-0863-9
Online ISBN: 978-981-15-0864-6
eBook Packages: Computer ScienceComputer Science (R0)