Skip to main content
Erschienen in: Queueing Systems 1-2/2020

03.12.2019

Stationary distribution convergence of the offered waiting processes for \(GI/GI/1+GI\) queues in heavy traffic

verfasst von: Chihoon Lee, Amy R. Ward, Heng-Qing Ye

Erschienen in: Queueing Systems | Ausgabe 1-2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A result of Ward and Glynn (Queueing Syst 50(4):371–400, 2005) asserts that the sequence of scaled offered waiting time processes of the \(GI/GI/1+GI\) queue converges weakly to a reflected Ornstein–Uhlenbeck process (ROU) in the positive real line, as the traffic intensity approaches one. As a consequence, the stationary distribution of a ROU process, which is a truncated normal, should approximate the scaled stationary distribution of the offered waiting time in a \(GI/GI/1+GI\) queue; however, no such result has been proved. We prove the aforementioned convergence, and the convergence of the moments, in heavy traffic, thus resolving a question left open in 2005. In comparison with Kingman’s classical result (Kingman in Proc Camb Philos Soc 57:902–904, 1961) showing that an exponential distribution approximates the scaled stationary offered waiting time distribution in a GI / GI / 1 queue in heavy traffic, our result confirms that the addition of customer abandonment has a non-trivial effect on the queue’s stationary behavior.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat Asmussen, S.: Applied Probability and Queues. Applications of Mathematics, vol. 51, 2nd edn. Springer, New York (2003) Asmussen, S.: Applied Probability and Queues. Applications of Mathematics, vol. 51, 2nd edn. Springer, New York (2003)
2.
Zurück zum Zitat Baccelli, F., Boyer, P., Hébuterne, G.: Single-server queues with impatient customers. Adv. Appl. Probab. 16(4), 887–905 (1984)CrossRef Baccelli, F., Boyer, P., Hébuterne, G.: Single-server queues with impatient customers. Adv. Appl. Probab. 16(4), 887–905 (1984)CrossRef
3.
Zurück zum Zitat Billingsley, P.: Convergence of Probability Measures, 2nd edn. Wiley, Hoboken (1999)CrossRef Billingsley, P.: Convergence of Probability Measures, 2nd edn. Wiley, Hoboken (1999)CrossRef
4.
Zurück zum Zitat Bramson, M.: State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst. Theory Appl. 30(1–2), 89–148 (1998)CrossRef Bramson, M.: State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst. Theory Appl. 30(1–2), 89–148 (1998)CrossRef
5.
Zurück zum Zitat Bramson, M.: Stability of queueing networks. Probab. Surv. 5, 169–345 (2008)CrossRef Bramson, M.: Stability of queueing networks. Probab. Surv. 5, 169–345 (2008)CrossRef
6.
Zurück zum Zitat Budhiraja, A., Lee, C.: Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34(1), 45–56 (2009)CrossRef Budhiraja, A., Lee, C.: Stationary distribution convergence for generalized Jackson networks in heavy traffic. Math. Oper. Res. 34(1), 45–56 (2009)CrossRef
7.
Zurück zum Zitat Chen, H., Yao, D.D.: Fundamentals of Queueing Networks. Applications of Mathematics, vol. 46. Springer, New York (2001)CrossRef Chen, H., Yao, D.D.: Fundamentals of Queueing Networks. Applications of Mathematics, vol. 46. Springer, New York (2001)CrossRef
8.
Zurück zum Zitat Chen, H., Ye, H.-Q.: Asymptotic optimality of balanced routing. Oper. Res. 60(1), 163–179 (2012)CrossRef Chen, H., Ye, H.-Q.: Asymptotic optimality of balanced routing. Oper. Res. 60(1), 163–179 (2012)CrossRef
9.
Zurück zum Zitat Dai, J.G.: On positive Harris recurrence of queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49–77 (1995)CrossRef Dai, J.G.: On positive Harris recurrence of queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49–77 (1995)CrossRef
10.
Zurück zum Zitat Dai, J.G., Dieker, A.B., Gao, X.: Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Queueing Syst. 78(1), 1–29 (2014)CrossRef Dai, J.G., Dieker, A.B., Gao, X.: Validity of heavy-traffic steady-state approximations in many-server queues with abandonment. Queueing Syst. 78(1), 1–29 (2014)CrossRef
11.
Zurück zum Zitat Dai, J.G., Meyn, S.P.: Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Autom. Control 40, 1889–1904 (1995)CrossRef Dai, J.G., Meyn, S.P.: Stability and convergence of moments for multiclass queueing networks via fluid limit models. IEEE Trans. Autom. Control 40, 1889–1904 (1995)CrossRef
12.
Zurück zum Zitat Davis, M.H.A.: Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models. J. R. Stat. Soc. Ser. B 46(3), 353–388 (1984). (With discussion) Davis, M.H.A.: Piecewise-deterministic Markov processes: a general class of nondiffusion stochastic models. J. R. Stat. Soc. Ser. B 46(3), 353–388 (1984). (With discussion)
13.
Zurück zum Zitat Gamarnik, D., Zeevi, A.: Validity of heavy traffic steady-state approximations in open queueing networks. Ann. Appl. Probab. 16(1), 56–90 (2006)CrossRef Gamarnik, D., Zeevi, A.: Validity of heavy traffic steady-state approximations in open queueing networks. Ann. Appl. Probab. 16(1), 56–90 (2006)CrossRef
14.
Zurück zum Zitat Huang, J., Gurvich, I.: Beyond heavy-traffic regimes: universal bounds and controls for the single-server queue. Oper. Res. 66(4), 1168–1188 (2018)CrossRef Huang, J., Gurvich, I.: Beyond heavy-traffic regimes: universal bounds and controls for the single-server queue. Oper. Res. 66(4), 1168–1188 (2018)CrossRef
15.
Zurück zum Zitat Kang, W., Ramanan, K.: Asymptotic approximations for stationary distributions of many-server queues with abandonment. Ann. Appl. Probab. 22(2), 477–521 (2012)CrossRef Kang, W., Ramanan, K.: Asymptotic approximations for stationary distributions of many-server queues with abandonment. Ann. Appl. Probab. 22(2), 477–521 (2012)CrossRef
16.
Zurück zum Zitat Kingman, J.F.C.: The single server queue in heavy traffic. Proc. Camb. Philos. Soc. 57, 902–904 (1961)CrossRef Kingman, J.F.C.: The single server queue in heavy traffic. Proc. Camb. Philos. Soc. 57, 902–904 (1961)CrossRef
17.
Zurück zum Zitat Kingman, J.F.C.: On queues in heavy traffic. J. R. Stat. Soc. Ser. B 24, 383–392 (1962) Kingman, J.F.C.: On queues in heavy traffic. J. R. Stat. Soc. Ser. B 24, 383–392 (1962)
18.
Zurück zum Zitat Krichagina, E.V., Taksar, M.I.: Diffusion approximation for \(GI/G/1\) controlled queues. Queueing Syst. Theory Appl. 12(3–4), 333–367 (1992)CrossRef Krichagina, E.V., Taksar, M.I.: Diffusion approximation for \(GI/G/1\) controlled queues. Queueing Syst. Theory Appl. 12(3–4), 333–367 (1992)CrossRef
19.
Zurück zum Zitat Mandelbaum, A., Momcilovic, P.: Queue with many servers and impatient customers. Math. Oper. Res. 37(1), 41–65 (2012)CrossRef Mandelbaum, A., Momcilovic, P.: Queue with many servers and impatient customers. Math. Oper. Res. 37(1), 41–65 (2012)CrossRef
20.
Zurück zum Zitat Mandelbaum, A., Stolyar, A.L.: Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized \(c\mu \)-rule. Oper. Res. 52(6), 836–855 (2004)CrossRef Mandelbaum, A., Stolyar, A.L.: Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized \(c\mu \)-rule. Oper. Res. 52(6), 836–855 (2004)CrossRef
21.
Zurück zum Zitat Meyn, S.P., Down, D.: Stability of generalized Jackson networks. Ann. Appl. Probab. 4(1), 124–148 (1994)CrossRef Meyn, S.P., Down, D.: Stability of generalized Jackson networks. Ann. Appl. Probab. 4(1), 124–148 (1994)CrossRef
22.
Zurück zum Zitat Meyn, S.P., Tweedie, R.L.: Stability of Markovian processes II: continuous-time processes and sampled chains. Adv. Appl. Probab. 25(3), 487–517 (1993)CrossRef Meyn, S.P., Tweedie, R.L.: Stability of Markovian processes II: continuous-time processes and sampled chains. Adv. Appl. Probab. 25(3), 487–517 (1993)CrossRef
23.
Zurück zum Zitat Meyn, S.P., Tweedie, R.L.: Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes. Adv. Appl. Probab. 25(3), 518–548 (1993)CrossRef Meyn, S.P., Tweedie, R.L.: Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes. Adv. Appl. Probab. 25(3), 518–548 (1993)CrossRef
24.
Zurück zum Zitat Palm, C.: Etude des delais d’attente. Ericsson Tech. 5, 37–56 (1937) Palm, C.: Etude des delais d’attente. Ericsson Tech. 5, 37–56 (1937)
26.
Zurück zum Zitat Reed, J.E., Tezcan, T.: Hazard rate scaling of the abandonment distribution for the \(GI/M/n+GI\) queue in heavy traffic. Oper. Res. 60(4), 981–995 (2012)CrossRef Reed, J.E., Tezcan, T.: Hazard rate scaling of the abandonment distribution for the \(GI/M/n+GI\) queue in heavy traffic. Oper. Res. 60(4), 981–995 (2012)CrossRef
27.
Zurück zum Zitat Reed, J.E., Ward, A.R.: Approximating the \(GI/GI/1+GI\) queue with a nonlinear drift diffusion: hazard rate scaling in heavy traffic. Math. Oper. Res. 33(3), 606–644 (2008)CrossRef Reed, J.E., Ward, A.R.: Approximating the \(GI/GI/1+GI\) queue with a nonlinear drift diffusion: hazard rate scaling in heavy traffic. Math. Oper. Res. 33(3), 606–644 (2008)CrossRef
28.
Zurück zum Zitat Roussas, G.G.: An Introduction to Measure-Theoretic Probability. Academic Press, Cambridge (2014) Roussas, G.G.: An Introduction to Measure-Theoretic Probability. Academic Press, Cambridge (2014)
29.
Zurück zum Zitat Stolyar, A.L.: Max-weight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1), 1–53 (2004)CrossRef Stolyar, A.L.: Max-weight scheduling in a generalized switch: state space collapse and workload minimization in heavy traffic. Ann. Appl. Probab. 14(1), 1–53 (2004)CrossRef
30.
Zurück zum Zitat Ward, A.R., Glynn, P.W.: Properties of the reflected Ornstein–Uhlenbeck process. Queueing Syst. 44(2), 109–123 (2003)CrossRef Ward, A.R., Glynn, P.W.: Properties of the reflected Ornstein–Uhlenbeck process. Queueing Syst. 44(2), 109–123 (2003)CrossRef
31.
Zurück zum Zitat Ward, A.R., Glynn, P.W.: A diffusion approximation for a \(GI/GI/1\) queue with balking or reneging. Queueing Syst. 50(4), 371–400 (2005)CrossRef Ward, A.R., Glynn, P.W.: A diffusion approximation for a \(GI/GI/1\) queue with balking or reneging. Queueing Syst. 50(4), 371–400 (2005)CrossRef
32.
Zurück zum Zitat Ye, H.-Q., Yao, D.D.: A stochastic network under proportional fair resource control-diffusion limit with multiple bottlenecks. Oper. Res. 60(3), 716–738 (2012)CrossRef Ye, H.-Q., Yao, D.D.: A stochastic network under proportional fair resource control-diffusion limit with multiple bottlenecks. Oper. Res. 60(3), 716–738 (2012)CrossRef
33.
Zurück zum Zitat Ye, H.-Q., Yao, D.D.: Diffusion limit of fair resource control—stationarity and interchange of limits. Math. Oper. Res. 41(4), 1161–1207 (2016)CrossRef Ye, H.-Q., Yao, D.D.: Diffusion limit of fair resource control—stationarity and interchange of limits. Math. Oper. Res. 41(4), 1161–1207 (2016)CrossRef
34.
Zurück zum Zitat Ye, H.-Q., Yao, D.D.: Justifying diffusion approximations for stochastic processing networks under a moment condition. Ann. Appl. Probab. 28(6), 3652–3697 (2018)CrossRef Ye, H.-Q., Yao, D.D.: Justifying diffusion approximations for stochastic processing networks under a moment condition. Ann. Appl. Probab. 28(6), 3652–3697 (2018)CrossRef
35.
Zurück zum Zitat Zhang, T.-S.: On the strong solutions of one-dimensional stochastic differential equations with reflecting boundary. Stoch. Process. Appl. 50(1), 135–147 (1994)CrossRef Zhang, T.-S.: On the strong solutions of one-dimensional stochastic differential equations with reflecting boundary. Stoch. Process. Appl. 50(1), 135–147 (1994)CrossRef
Metadaten
Titel
Stationary distribution convergence of the offered waiting processes for queues in heavy traffic
verfasst von
Chihoon Lee
Amy R. Ward
Heng-Qing Ye
Publikationsdatum
03.12.2019
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 1-2/2020
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-019-09641-y

Weitere Artikel der Ausgabe 1-2/2020

Queueing Systems 1-2/2020 Zur Ausgabe

Premium Partner