Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Limiting the oscillations in queues with delayed information through a novel type of delay announcement

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

Many service systems use technology to notify customers about their expected waiting times or queue lengths via delay announcements. However, in many cases, either the information might be delayed or customers might require time to travel to the queue of their choice, thus causing a lag in information. In this paper, we construct a neutral delay differential equation model for the queue length process and explore the use ofvelocity information in our delay announcement. Our results illustrate that using velocity information can have either a beneficial or detrimental impact on the system. Thus, it is important to understand how much velocity information a manager should use. In some parameter settings, we show that velocity information can eliminate oscillations created by delays in information. We derive a fixed point equation for determining the optimal amount of velocity information that should be used and find closed-form upper and lower bounds on its value. When the oscillations cannot be eliminated altogether, we identify the amount of velocity information that minimizes the amplitude of the oscillations. However, we also find that using too much velocity information can create oscillations in the queue lengths that would otherwise be stable.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24
Fig. 25
Fig. 26
Fig. 27
Fig. 28
Fig. 29
Fig. 30
Fig. 31
Fig. 32
Fig. 33

Similar content being viewed by others

References

  1. Abboud, K., Zhuang, W.: Modeling and analysis for emergency messaging delay in vehicular ad hoc networks. In: GLOBECOM 2009—2009 IEEE Global Telecommunications Conference, pp. 1–6 (2009).https://doi.org/10.1109/GLOCOM.2009.5425839

  2. Armbruster, H., Ringhofer, C., Jo, T.C.: Continuous models for production flows. In: Proceedings of the American Control Conference, vol. 5, pp. 4589–4594 (2004). ISBN 0780383354.https://doi.org/10.1109/ACC.2004.182675

  3. Armony, M., Maglaras, C.: On customer contact centers with a call-back option: customer decisions, routing rules, and system design. Oper. Res.52(2), 271–292 (2004)

    Article  Google Scholar 

  4. Armony, M., Shimkin, N., Whitt, W.: The impact of delay announcements in many-server queues with abandonment. Oper. Res.57(1), 66–81 (2009)

    Article  Google Scholar 

  5. Belhaq, M., Sah, S.I.: Fast parametrically excited van der Pol oscillator with time delay state feedback. Int. J. Non-Linear Mech.43(2), 124–130 (2008)

    Article  Google Scholar 

  6. Bellena, A., Guglielmi, N.: Solving neutral delay differential equations with state-dependent delays. J. Comput. Appl. Math.229(2), 350–362 (2009)

    Article  Google Scholar 

  7. Das, S.L., Chatterjee, A.: Multiple scales without center manifold reductions for delay differential equations near Hopf bifurcations. Nonlinear Dyn.30, 323–335 (2002)

    Article  Google Scholar 

  8. Daw, A., Pender, J.: New perspectives on the Erlang-A queue. Adv. Appl. Probab.51(1), 268–299 (2019)

    Article  Google Scholar 

  9. Dong, J., Yom-Tov, E., Yom-Tov, G.B.: The impact of delay announcements on hospital network coordination and waiting times. Manag. Sci.65(5), 1969–1994 (2019)

    Google Scholar 

  10. Driver, R.D.: Existence and continuous dependence of solutions of a neutral functional-differential equation. Arch. Ration. Mech. Anal.19(2), 149–166 (1965).https://doi.org/10.1007/BF00282279

    Article  Google Scholar 

  11. Eick, S.G., Massey, W.A., Whitt, W.:\(M_t\)/G/\(\infty \) queues with sinusoidal arrival rates. Manag. Sci.39(2), 241–252 (1993)

    Google Scholar 

  12. Eick, S.G., Massey, W.A., Whitt, W.: The physics of the\(M_t\)/G/\(\infty \) queue. Oper. Res.41(4), 731–742 (1993)

    Google Scholar 

  13. Fralix, B.H., Adan, I.J.B.F.: An infinite-server queue influenced by a semi-Markovian environment. Queueing Syst.61(1), 65–84 (2009)

    Article  Google Scholar 

  14. Freund, D., Henderson, S., Shmoys, D.: Minimizing multimodular functions and allocating capacity in bike-sharing systems (2016). arXiv preprintarXiv:1611.09304

  15. Guo, P., Zipkin, P.: Analysis and comparison of queues with different levels of delay information. Manag. Sci.53(6), 962–970 (2007)

    Article  Google Scholar 

  16. Guo, P., Zipkin, P.: The impacts of customers’ delay-risk sensitivities on a queue with balking. Probab. Eng. Inf. Sci.23(3), 409–432 (2009)

    Article  Google Scholar 

  17. Hale, J., Lunel, V.: Introduction to Functional Differential Equations. Springer Science, Berlin (1993)

    Book  Google Scholar 

  18. Hassard, B.D., Kazarinoff, N.D., Wan, Y.H.: Theory and Applications of Hopf Bifurcation. Cambridge University Press, Cambridge (1981)

    Google Scholar 

  19. Hausman, J., McFadden, D.: Specification tests for the multinomial logit model. Econometrica52(5), 1219–1240 (1984)

    Article  Google Scholar 

  20. Helbing, D.: Improved fluid-dynamic model for vehicular traffic. Phys. Rev. E51, 3164–3169 (1995).https://doi.org/10.1103/PhysRevE.51.3164

    Article  Google Scholar 

  21. Ibrahim, R., Armony, M., Bassamboo, A.: Does the past predict the future? The case of delay announcements in service systems. Manag. Sci.63(6), 1657–2048 (2017)

    Article  Google Scholar 

  22. Iglehart, D.L.: Limiting diffusion approximations for the many server queue and the repairman problem. J. Appl. Probab.2(2), 429–441 (1965)

    Article  Google Scholar 

  23. Jouini, O., Aksin, Z., Dallery, Y.: Call centers with delay information: models and insights. Manuf. Serv. Oper. Manag.13(4), 534–548 (2011)

    Article  Google Scholar 

  24. Ko, Y.M., Pender, J.: Strong approximations for time-varying infinite-server queues with non-renewal arrival and service processes. Stochastic Models34(2), 186–206 (2018)

    Article  Google Scholar 

  25. Lazarus, L., Davidow, M., Rand, R.: Periodically forced delay limit cycle oscillator. Int. J. Non-Linear Mech.94, 216–222 (2017)

    Article  Google Scholar 

  26. Lipshutz, D., Williams, R.J.: Existence, uniqueness, and stability of slowly oscillating periodic solutions for delay differential equations with nonnegativity constraints. SIAM J. Math. Anal.47(6), 4467–4535 (2015)

    Article  Google Scholar 

  27. McFadden, D.: Modelling the choice of residential location. Cowles Foundation Discussion Papers 477, Cowles Foundation for Research in Economics, Yale University (1977).https://EconPapers.repec.org/RePEc:cwl:cwldpp:477

  28. Nirenberg, S., Daw, A., Pender, J.: The impact of queue length rounding and delayed app information on Disney world queues. In: Proceedings of the 2018 Winter Simulation Conference. Winter Simulation Conference (2018)

  29. Novitzky, S., Pender, J., Rand, R.H., Wesson, E.: Nonlinear dynamics in queueing theory: Determining size of oscillations in queues with delay. SIAM J. Appl. Dyn. Syst.18, 279–311 (2018)

    Article  Google Scholar 

  30. Pender, J., Rand, R.H., Wesson, E.: Queues with choice via delay differential equations. Int. J. Bifurc. Chaos27(4), 1730016 (2017)

    Article  Google Scholar 

  31. Pender, J., Rand, R.H., Wesson, E.: An asymptotic analysis of queues with delayed information and time varying arrival rates. Nonlinear Dyn.91, 2411–2427 (2018)

    Article  Google Scholar 

  32. Perkins, J., Kumar, P.: Optimal control of pull manufacturing systems. IEEE Trans. Autom. Control40(12), 2040–2051 (1995)

    Article  Google Scholar 

  33. Raina, G., Wischik, D.: Buffer sizes for large multiplexers: TCP queueing theory and instability analysis. In: Next Generation Internet Networks, 2005. IEEE (2005)

  34. Resnick, S., Samorodnitsky, G.: Activity periods of an infinite server queue and performance of certain heavy tailed fluid queues. Queueing Syst.33(1–3), 43–71 (1999)

    Article  Google Scholar 

  35. Smith, H.: An Introduction to Delay Differential Equations with Applications to the Life Sciences. Springer Science, Berlin (2011)

    Book  Google Scholar 

  36. So, Y., Kuhfeld, W.: Multinomial logit models. In: SUGI 20 Conference Proceedings (1995)

  37. Tao, S., Pender, J.: A stochastic analysis of bike sharing systems. arXiv preprintarXiv:1708.08052 (2017)

  38. Train, K.: Discrete Choice Methods with Simulation. Cambridge University Press, Cambridge (2009)

    Google Scholar 

Download references

Acknowledgements

Funding was provided by Division of Civil, Mechanical and Manufacturing Innovation (Grant No. 1751975).

Author information

Authors and Affiliations

  1. Center for Applied Mathematics, Cornell University, 657 Rhodes Hall, Ithaca, NY, 14853, USA

    Sophia Novitzky

  2. School of Operations Research and Information Engineering, Cornell University, 228 Rhodes Hall, Ithaca, NY, 14853, USA

    Jamol Pender

  3. Department of Mathematics, Sibley School of Mechanical and Aerospace Engineering, Cornell University, 535 Malott Hall, Ithaca, NY, 14853, USA

    Richard H. Rand

  4. Center for Applied Mathematics, Cornell University, Rhodes Hall 657, Ithaca, NY, 14853, USA

    Elizabeth Wesson

Authors
  1. Sophia Novitzky

    You can also search for this author inPubMed Google Scholar

  2. Jamol Pender

    You can also search for this author inPubMed Google Scholar

  3. Richard H. Rand

    You can also search for this author inPubMed Google Scholar

  4. Elizabeth Wesson

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toJamol Pender.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

1.1Uniqueness and existence of the equilibrium

Proof of Theorem 3.2: To check that\(q_i(t)= \frac{\lambda }{N\mu }\) is an equilibrium, plug into Eq. (3.9) to get

(7.1)

To show uniqueness, we will argue by contradiction. Suppose there is another equilibrium given by\({\bar{q}}_i\),\(1\le i \le N\), and for somei we have\(q^*_i \ne {\bar{q}}_i\). The following condition must hold:

(7.2)

Hence, the mean of\({\bar{q}}_i\) is\(\frac{\lambda }{N\mu } \) and, since\({\bar{q}}_i\) cannot all be equal to each other, there must exist some\({\bar{q}}_s\) that is smaller than the mean, and some\({\bar{q}}_g\) that is greater than the mean:

$$\begin{aligned} {\bar{q}}_s = \frac{\lambda }{\mu N} - \gamma , \qquad {\bar{q}}_b = \frac{\lambda }{N\mu } + \epsilon , \qquad \gamma , \epsilon > 0. \end{aligned}$$
(7.3)

This leads to a contradiction:

(7.4)
(7.5)
(7.6)
(7.7)
(7.8)

Since, then\({\bar{q}}_i(t)\) is not an equilibrium, and the equilibrium (3.12) is unique.

1.2Approximation to amplitude of oscillations in queues

To see how the velocity information affects the behavior of the queues after a Hopf bifurcation occurs, we need to develop approximations for the amplitude of oscillations. In Sect. 5, we find a first-order approximation to the amplitude but observe that it is not sufficiently accurate. Hence, we require a second-order approximation. The steps to determine the second-order approximation are outlined below.

This process is very closely related to the steps taken in Theorem 5.1. We begin with Eq. (5.7), and expand the time\(\tau = \omega t\). Then expand our functions of interest in\(\epsilon \) to the second order:

$$\begin{aligned}&x(\tau ) = x_0(\tau ) + \epsilon x_1 (\tau ) + + \epsilon ^2 x_2 (\tau ),\\&\quad \Delta = \Delta _0 + \epsilon \Delta _1 + \epsilon ^2 \Delta _2, \quad \omega = \omega _0 + \epsilon \omega _1 + \epsilon ^2 \omega _2, \end{aligned}$$

where\(\Delta _0\) and\(\omega _0\) are the delay and frequency at bifurcation, so\(\Delta _0 = \Delta _\mathrm{cr}\) and\(\omega _\mathrm{cr}\). By collecting all the terms with the like powers of\(\epsilon \) into separate equations, we get equations from which we can solve for\(x_0\) and\(x_1\). From the equation for\(\epsilon ^0\), we find that\(x_0(\tau ) = A \cos (\tau )\) is a solution. Next, we use the equation for\(\epsilon ^1\) terms to solve forA, which has the expression given by Eq. (5.35). We can now find\(x_1\) that has a solution of the form\(x_1(\tau ) = a_1 \sin (\tau ) + a_2 \cos (\tau ) + a_3 \sin (3 \tau ) + a_4 \cos (3 \tau )\). The coefficients\(a_3\) and\(a_4\) are determined from the equation for\(\epsilon ^1\) terms. We impose the initial condition\(x'(0) = 0\) to ensure that the maximum amplitude is at 0, which implies\(a_1 = - 3 a_3\). Lastly, we determine\(a_2\) by eliminating the secular terms from the equation for\(\epsilon ^2\) terms. Therefore, the second-order approximation of the amplitude of oscillations can be deduced from

$$\begin{aligned} x(\tau )\approx & {} x_0(\tau ) + \epsilon x_1(\tau ) \end{aligned}$$
(7.9)
$$\begin{aligned}= & {} A \cos (\tau ) + \epsilon \big ( a_1 \sin (\tau ) + a_2 \cos (\tau ) + a_3 \sin (3 \tau ) + a_4 \cos (3 \tau ) \big ),\qquad \end{aligned}$$
(7.10)

where the coefficients are given below:

$$\begin{aligned} A= & {} \sqrt{ \frac{4 \Delta _1 (\lambda ^2\theta ^2 - 4 \mu ^2)(4 - \delta ^2 \lambda ^2\theta ^2)^2}{\theta ^2(1 - \delta ^2\mu ^2)(16\mu + \lambda ^2\theta ^2(4\Delta _0 -4\delta + \delta ^3\lambda ^2\theta ^2 - 4\delta ^2\mu -4\delta ^2 \Delta _0\mu ^2))}}, \\ \omega _1= & {} \frac{4 \Delta _1 \theta ^2 \lambda ^2 \left( \delta ^2 \mu ^2-1\right) \sqrt{\theta ^2 \lambda ^2-4 \mu ^2}}{\sqrt{4-\delta ^2 \theta ^2 \lambda ^2} \left( \theta ^2 \lambda ^2 \left( \delta \left( \delta ^2 \theta ^2 \lambda ^2-4 \delta \mu ({\Delta 0} \mu +1)-4\right) +4 {\Delta 0}\right) +16 \mu \right) }, \\ a_1= & {} - 3 a_3 = -\Big (2 A^3 \theta ^2 \omega _0^3 \left( \theta ^2 \lambda ^2 \mu \left( \delta ^2 \omega _0^2+1\right) ^3-4 \delta ^3 \left( \mu ^2+\omega _0^2\right) ^3\right) \Big )\\&/\Big (\theta ^4 \lambda ^4 \left( \delta ^2 \omega _0^2+1\right) ^3 \left( \mu ^2+9 \omega _0^2\right) +16 \left( 9 \delta ^2 \omega _0^2+1\right) \left( \mu ^2+\omega _0^2\right) ^3 \\&+8 \theta ^2 \lambda ^2 \big (-9 \delta ^4 \omega _0^8-6 \mu ^2 \omega _0^2 \left( \delta ^2 \mu ^2+1\right) +2 \delta ^2 \omega _0^6 (\delta \mu (9 \delta \mu -32)+9) \\&+3 \omega _0^4 \left( \delta ^4 \mu ^4-12 \delta ^2 \mu ^2+1\right) -\mu ^4\big )\Big ), \\ a_4= & {} -\frac{1}{12}\Big (A^3 \theta ^2 \left( \theta ^2 \lambda ^2 \left( \delta ^2 \omega _0^2+1\right) ^3 \left( \mu ^4+6 \mu ^2 \omega _0^2-3 \omega _0^4\right) \right. \\&\left. +4 \left( 3 \delta ^4 \omega _0^4-6 \delta ^2 \omega _0^2-1\right) \left( \mu ^2+\omega _0^2\right) ^3\right) \Big ) \\&/\Big (\theta ^4 \lambda ^4 \left( \delta ^2 \omega _0^2+1\right) ^3 \left( \mu ^2+9 \omega _0^2\right) +16 \left( 9 \delta ^2 \omega _0^2+1\right) \left( \mu ^2+\omega _0^2\right) ^3 \\&+8 \theta ^2 \lambda ^2 \big (-9 \delta ^4 \omega _0^8-6 \mu ^2 \omega _0^2 \left( \delta ^2 \mu ^2+1\right) +2 \delta ^2 \omega _0^6 (\delta \mu (9 \delta \mu -32)+9) \\&+3 \omega _0^4 \left( \delta ^4 \mu ^4-12 \delta ^2 \mu ^2+1\right) -\mu ^4\big )\Big ), \\ a_2= & {} \frac{1}{12}\Big (A^5 \theta ^4 \left( \delta ^2 \omega _0^2+1\right) ^2 \left( \delta ^2 \mu \omega _0^2+\mu ^2 \left( \delta \left( \delta \Delta _0 \omega _0^2, -1\right) +\Delta _0\right) \right. \\&\left. +\omega _0^2 \left( \delta \left( \delta \Delta _0 \omega _0^2-1\right) +\Delta _0\right) +\mu \right) \\&-12 A^3 \theta ^2 \omega _0 \big (\omega _1 \left( \delta \left( 3 \delta ^3 \Delta _0 \omega _0^4+\delta \omega _0^2 (\delta (\delta \mu (2 \Delta _0 \mu +3)-3)\right. \right. \\&\left. \left. +4 \Delta _0)+\delta \mu (-2 \delta \mu +2 \Delta _0 \mu +3)-1\right) +\Delta _0\right) \\&-\Delta _1 \omega _0 \left( \delta ^2 \mu ^2-1\right) \left( \delta ^2 \omega _0^2+1\right) \big ) +12 A^2 \theta ^2 \big (a_1 \omega _0 \left( \delta ^2 \mu ^2-1\right) \left( \delta ^2 \omega _0^2+1\right) \\&+a_3 \omega _0 \left( \delta ^2 \left( \omega _0^2 (\delta \mu (-3 \delta \mu +8 \Delta _0 \mu +8)-5)+8 \delta \Delta _0 \omega _0^4+\mu ^2\right) -1\right) \\&+a_4 (3 \delta ^4 \Delta _0 \omega _0^6+3 \delta ^2 \omega _0^4 (\delta (\delta \mu (\Delta _0 \mu +1)-1)-2 \Delta _0)\\&+\omega _0^2 (\delta (\delta \mu (5 \delta \mu -6 \Delta _0 \mu -6)+1)-\Delta _0) \\&+\mu (\delta \mu -\Delta _0 \mu -1))\big ) -96 A \big (2 \Delta _1 \omega _0 \omega _1 (\mu \left( \mu \left( 2 \delta ^2\right. \right. \\&\left. \left. -2 \delta \Delta _0+\Delta _0^2\right) -\delta +\Delta _0\right) +\delta ^2 \Delta _0^2 \omega _0^4 \\&+\Delta _0 \omega _0^2 (\delta (\delta \mu (\Delta _0 \mu +1)-2)+\Delta _0)-1) +\Delta _0 \omega _1^2 (\delta ^2 \Delta _0^2 \omega _0^4\\&+\Delta _0 \omega _0^2 (\delta (\delta \mu (\Delta _0 \mu +1)-3)+\Delta _0) \\&+\mu (2 \delta -\Delta _0) (\delta \mu -\Delta _0 \mu -1))+\Delta _1^2 \omega _0^2 (\delta ^2 \Delta _0 \omega _0^4 \end{aligned}$$
$$\begin{aligned}&+\omega _0^2 (\delta (\delta \mu (\Delta _0 \mu +1)-1)+\Delta _0) \\&+\mu (-\delta \mu +\Delta _0 \mu +1))\big )-192 a_1 \big (\omega _1 (\delta ^2 \Delta _0^2 \omega _0^4\\&+\Delta _0 \omega _0^2 (\delta (\delta \mu (\Delta _0 \mu +2)-2)+\Delta _0)\\&+(-\delta \mu +\Delta _0 \mu +1)^2)+\Delta _1 \omega _0 \left( \delta ^2 \Delta _0 \omega _0^4+\omega _0^2 (\delta (\delta \mu (\Delta _0 \mu +1)\right. \\&\left. -1)+\Delta _0)+\mu (-\delta \mu +\Delta _0 \mu +1)\right) \big )\Big ) \\&/\Big (3 A^2 \theta ^2 \left( \delta ^2 \omega _0^2+1\right) \left( \delta ^2 \Delta _0 \omega _0^4+\omega _0^2 (\delta (\delta \mu (\Delta _0 \mu +1)\right. \\&\left. -1)+\Delta _0)+\mu (-\delta \mu +\Delta _0 \mu +1)\right) \\&+16 \Delta _1 \omega _0^2 \left( \delta ^2 \mu ^2-1\right) \Big ). \end{aligned}$$

To reproduce our numerical results from Sects. 5.3–5.4, set\(\epsilon = 1\) and\(\Delta _1 = \frac{1}{\epsilon }(\Delta - \Delta _0)\), with\(\Delta _0\) given by Eq. (3.52). Note that in the equations above there is no presence of\(\Delta _2\), because we have set\(\Delta _2 = 0\). There is no equation that determines\(\Delta _2\) and\(\Delta _1\) uniquely, and the only restriction is that\(\Delta = \Delta _0 + \epsilon \Delta _1 + \epsilon ^2 \Delta _2\). Prior to choosing\(\Delta _2 \) to be 0, we experimented numerically with different combinations of\(\Delta _1\) and\(\Delta _2\) and determined that the pair\(\Delta _1 = \frac{1}{\epsilon }(\Delta - \Delta _0)\) and\(\Delta _2 = 0\) results in nearly the most accurate approximation.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Novitzky, S., Pender, J., Rand, R.H.et al. Limiting the oscillations in queues with delayed information through a novel type of delay announcement.Queueing Syst95, 281–330 (2020). https://doi.org/10.1007/s11134-020-09657-9

Download citation

Keywords

Mathematics Subject Classification

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp