Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Queueing Systems
Published in: Queueing Systems 1-2/2024

05-01-2024

Adaptive service rate control of an M/M/1 queue with server breakdowns

Authors: Yi Zheng, Juxihong Julaiti, Guodong Pang

Published in: Queueing Systems | Issue 1-2/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study service rate control problems for an M/M/1 queue with server breakdowns in which the breakdown rate is assumed to be a function of the service rate. Assuming that the queue has infinite capacity, we first establish the optimality equations for the discounted cost problem and characterize the optimal rate control policies. Then, we characterize the ergodicity of the controlled queue and establish the optimality conditions for the average-cost (ergodic) control problem using the vanishing discounted method. We next study the ergodic control problem when the queue has a finite capacity and establish a verification theorem by directly involving the stationary distribution of the controlled Markov process. For practical applications, we consider the adaptive service rate control problem for the model with finite capacity. Studying this problem is useful because the relationship between the server breakdown rate and the service rate is costly to observe in practice. We propose an adaptive (self-tuning) control algorithm, assuming that the relationship between the server breakdown rate and the service rate is linear with unknown parameters. We prove that the regret vanishes under the algorithm and the proposed policies are asymptotically optimal. In addition, numerical experiments are conducted to validate the algorithm.
previous article Exact and asymptotic analysis of infinite server batch service queues with random batch sizes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Abernethy, J., Bartlett, P.L., Hazan, E.: Blackwell approachability and no-regret learning are equivalent. In: Proceedings of the 24th Annual Conference on Learning Theory, pp. 27–46 (2011)
2.
Adusumilli, K.M., Hasenbein, J.J.: Dynamic admission and service rate control of a queue. Queueing Syst. 66(2), 131–154 (2010)MathSciNetCrossRef
3.
Alvarez-Mena, J., Hernández-Lerma, O.: Convergence and approximation of optimization problems. SIAM J. Optim. 15(2), 527–539 (2004)MathSciNetCrossRef
4.
Arapostathis, A., Pang, G., Zheng, Y.: Optimal scheduling of critically loaded multiclass GI/M/n+M queues in an alternating renewal environment. Appl. Math. Optim. 84(2), 1857–1901 (2021)MathSciNetCrossRef
5.
Ata, B.: Dynamic power control in a wireless static channel subject to a quality-of-service constraint. Oper. Res. 53(5), 842–851 (2005)MathSciNetCrossRef
6.
Ata, B., Shneorson, S.: Dynamic control of an M/M/1 service system with adjustable arrival and service rates. Manage. Sci. 52(11), 1778–1791 (2006)CrossRef
7.
Avi-Itzhak, B., Naor, P.: Some queuing problems with the service station subject to breakdown. Oper. Res. 11, 303–320 (1963)MathSciNetCrossRef
8.
Badian-Pessot, P., Lewis, M.E., Down, D.G.: Optimal control policies for an M/M/1 queue with a removable server and dynamic service rates. Probab. Engrg. Inf. Sci. 35(2), 189–209 (2021)MathSciNetCrossRef
9.
Besbes, O., Zeevi, A.: On the (surprising) sufficiency of linear models for dynamic pricing with demand learning. Manage. Sci. 61(4), 723–739 (2015)CrossRef
10.
Besbes, O., Zeevi, A.: Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms. Oper. Res. 57, 1407–1420 (2009)MathSciNetCrossRef
11.
12.
Borkar, V., Varaiya, P.: Adaptive control of Markov chains. I. Finite parameter set. IEEE Trans. Automat. Control 24(6), 953–957 (1979)MathSciNetCrossRef
13.
Borkar, V.: Recursive self-tuning control of finite markov chains. Applicationes Mathematicae 24(2), 169–188 (1997)MathSciNetCrossRef
14.
Borkar, V., Varaiya, P.: Identification and adaptive control of Markov chains. SIAM J. Control. Optim. 20(4), 470–489 (1982)MathSciNetCrossRef
15.
16.
Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press (2006)
17.
Chelst, K., Tilles, A.Z., Pipis, J.S.: A coal unloader: a finite queueing system with breakdowns. INFORMS J. Appl. Anal. 11(5), 12–25 (1981)CrossRef
18.
Chen, B., Chao, X., Shi, C.: Nonparametric learning algorithms for joint pricing and inventory control with lost sales and censored demand. Math. Oper. Res. 46(2), 726–756 (2021)MathSciNetCrossRef
19.
Chen, Q., Jasin, S., Duenyas, I.: Nonparametric self-adjusting control for joint learning and optimization of multiproduct pricing with finite resource capacity. Math. Oper. Res. 44(2), 601–631 (2019)MathSciNetCrossRef
20.
21.
Crites, R.H., Barto, A.G.: Improving elevator performance using reinforcement learning. Adv. Neural. Inf. Process. Syst. 690, 1017–1023 (1996)
22.
den Boer, A., Zwart, B.: Simultaneously learning and optimizing using controlled variance pricing. Manage. Sci. 60(3), 770–783 (2014)CrossRef
23.
den Boer, A.V., Zwart, B.: Mean square convergence rates for maximum quasi-likelihood estimators. Stoch. Syst. 4(2), 375–403 (2014)MathSciNetCrossRef
24.
Drabik, E., Stettner, L.: On adaptive control of markov chains using nonparametric estimation. Applicationes Mathematicae 27(2), 143–152 (2000)MathSciNetCrossRef
25.
Duncan, T., Pasik-Duncan, B., Stettner, L.: Adaptive control of a partially observed discrete time markov process. Appl. Math. Optim. 37, 269–293 (1998)MathSciNetCrossRef
26.
27.
Feinberg, E.A., Lewis, M.E.: Optimality inequalities for average cost Markov decision processes and the stochastic cash balance problem. Math. Oper. Res. 32(4), 769–783 (2007)MathSciNetCrossRef
28.
Gaver, D.P., Jr.: A waiting line with interrupted service, including priorities. J. Roy. Statist. Soc. Ser. B 24, 73–90 (1962)MathSciNet
29.
George, J.M., Harrison, J.M.: Dynamic control of a queue with adjustable service rate. Oper. Res. 49(5), 720–731 (2001)MathSciNetCrossRef
30.
Ghosh, A.P., Weerasinghe, A.P.: Optimal buffer size and dynamic rate control for a queueing system with impatient customers in heavy traffic. Stoch. Process. Appl. 120(11), 2103–2141 (2010)MathSciNetCrossRef
31.
Groover, M.P.: Fundamentals of Modern Manufacturing: Materials, Processes, and Systems. Wiley (2010)
32.
He, Q.-M.: Fundamentals of Matrix-Analytic Methods. Springer, New York (2014)CrossRef
33.
Hernández-Lerma, O., Marcus, S.I.: Adaptive control of service in queueing systems. Syst. Control Lett. 3(5), 283–289 (1983)MathSciNetCrossRef
34.
Hernàndez-Lerma, O., Marcus, S.I.: Optimal adaptive control of priority assignment in queueing systems. Syst. Control Lett. 4(2), 65–72 (1984)MathSciNetCrossRef
35.
Heyde, C.C.: Quasi-Likelihood and its Application. A General Approach to Optimal Parameter Estimation. Springer Series in Statistics, Springer, New York (1997)
36.
Keskin, N.B., Zeevi, A.: Dynamic pricing with an unknown demand model: asymptotically optimal semi-myopic policies. Oper. Res. 62(5), 1142–1167 (2014)MathSciNetCrossRef
37.
Koçağa, Y.L.: An approximating diffusion control problem for dynamic admission and service rate control in a G/M/N + G queue. Oper. Res. Lett. 45(6), 538–542 (2017)MathSciNetCrossRef
38.
Koçağa, Y.L., Ward, A.R.: Admission control for a multi-server queue with abandonment. Queueing Syst. 65, 275–323 (2010)MathSciNetCrossRef
39.
Kruglov, V.M.: Strong law of large numbers, Vol. 3. In: Stability Problems for Stochastic Models: Proceedings of the Fifteenth Perm Seminar Perm, Russia, June 2-6, 1992, pp. 139–150 (2020)
40.
Kumar, P.R., Lin, W.: Optimal adaptive controllers for unknown Markov chains. IEEE Trans. Automat. Control 27(4), 765–774 (1982)MathSciNetCrossRef
41.
Kumar, R., Lewis, M.E., Topaloglu, H.: Dynamic service rate control for a single-server queue with Markovmodulated arrivals. Naval Res. Logist. 60(8), 661–677 (2013)MathSciNetCrossRef
42.
Kuo, C.-C., Wang, K.-H., Lee, S.-L.: Optimal control of the p, N-policy M/G/1 queue with server breakdowns and general startup times. Int. J. Inf. Manage. Sci. 20(4), 565–577 (2009)MathSciNet
43.
Lee, N., Kulkarni, V.G.: Optimal arrival rate and service rate control of multi-server queues. Queueing Syst. 76, 37–50 (2014)MathSciNetCrossRef
44.
Lippman, S.A.: Semi-Markov decision processes with unbounded rewards. Manage. Sci. 19, 717–731 (1972/73)
45.
Lippman, S.A.: Applying a new device in the optimization of exponential queuing systems. Oper. Res. 23(4), 687–710 (1975)MathSciNetCrossRef
46.
Liu, B., Xie, Q., Modiano, E.: Reinforcement learning for optimal control of queueing systems. In: 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 663–670 (2019)
47.
Mandl, P.: On self-optimizing control of Markov processes, Mathematical Control Theory, pp. 345–360 (1985)
48.
Neuts, M.F.: Matrix-geometric solutions in stochastic models. An algorithmic approach, Corrected reprint of the 1981 original. Dover Publications, Inc., New York (1994)
49.
Pang, G., Whitt, W.: Heavy-traffic limits for many-server queues with service interruptions. Queueing Syst. 61(2–3), 167–202 (2009)MathSciNetCrossRef
50.
Pang, G., Whitt, W.: Service interruptions in large-scale service systems. Manage. Sci. 55(9), 1499–1512 (2009)CrossRef
51.
Raeis, M., Tizghadam, A., Leon-Garcia, A.: Reinforcement learning-based admission control in delay-sensitive service systems. In: GLOBECOM 2020-2020 IEEE Global Communications Conference, pp. 1–6 (2020)
52.
Sennott, L.I.: Average cost semi-Markov decision processes and the control of queueing systems. Probab. Eng. Inf. Sci. 3(2), 247–272 (1989)MathSciNetCrossRef
53.
Shi, C., Chen, W., Duenyas, I.: Technical note-nonparametric data-driven algorithms for multiproduct inventory systems with censored demand. Oper. Res. 64(2), 362–370 (2016)MathSciNetCrossRef
54.
Shwartz, A., Makowski, A.M.: An optimal adaptive scheme for two competing queues with constraints. In: Analysis and Optimization of Systems: Proceedings of the Seventh International Conference on Analysis and Optimization of Systems, Antibes, June 25–27, pp. 515–532 (1986)
55.
Stettner, L.: On nearly self-optimizing strategies for a discrete-time uniformly ergodic adaptive model. Appl. Math. Optim. 27, 161–177 (1993)MathSciNetCrossRef
56.
Walton, N., Xu, K.: Learning and information in stochastic networks and queues. Informs Tutorials in Operations Research, pp. 161–198 (2021)
57.
Weerasinghe, A.: Diffusion approximations for G/M/n + GI queues with state-dependent service rates. Math. Oper. Res. 39(1), 207–228 (2014)MathSciNetCrossRef
58.
59.
Yeh, L.: A finite algorithm for optimal solutions of adaptive queueing control. J. Math. Anal. Appl. 125(1), 218–233 (1987)MathSciNetCrossRef
Metadata
Title
Adaptive service rate control of an M/M/1 queue with server breakdowns
Authors
Yi Zheng
Juxihong Julaiti
Guodong Pang
Publication date
05-01-2024
Publisher
Springer US
Published in
Queueing Systems / Issue 1-2/2024
Print ISSN: 0257-0130
Electronic ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-023-09900-z

Premium Partner

    Image Credits