IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v104y2023i3d10.1007_s11134-023-09878-8.html
   My bibliography  Save this article

Externalities in the M/G/1 queue: LCFS-PR versus FCFS

Author

Listed:
  • Royi Jacobovic

    (University of Amsterdam)

  • Nikki Levering

    (University of Amsterdam)

  • Onno Boxma

    (Eindhoven University of Technology)

Abstract

Consider a stable M/G/1 system in which, at time $$t=0$$ t = 0 , there are exactly n customers with residual service times equal to $$v_1,v_2,\ldots ,v_n$$ v 1 , v 2 , … , v n . In addition, assume that there is an extra customer c who arrives at time $$t=0$$ t = 0 and has a service requirement of x. The externalities which are created by c are equal to the total waiting time that others will save if her service requirement is reduced to zero. In this work, we study the joint distribution (parameterized by $$n,v_1,v_2,\ldots ,v_n,x$$ n , v 1 , v 2 , … , v n , x ) of the externalities created by c when the underlying service distribution is either last-come, first-served with preemption or first-come, first-served. We start by proving a decomposition of the externalities under the above-mentioned service disciplines. Then, this decomposition is used to derive several other results regarding the externalities: moments, asymptotic approximations as $$x\rightarrow \infty $$ x → ∞ , asymptotics of the tail distribution, and a functional central limit theorem.

Suggested Citation

  • Royi Jacobovic & Nikki Levering & Onno Boxma, 2023. "Externalities in the M/G/1 queue: LCFS-PR versus FCFS," Queueing Systems: Theory and Applications, Springer, vol. 104(3), pages 239-267, August.
    • Handle: RePEc:spr:queues:v:104:y:2023:i:3:d:10.1007_s11134-023-09878-8
    DOI: 10.1007/s11134-023-09878-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-023-09878-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-023-09878-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Royi Jacobovic, 2022. "Regulation of a single-server queue with customers who dynamically choose their service durations," Queueing Systems: Theory and Applications, Springer, vol. 101(3), pages 245-290, August.
    2. Cline, D. B. H. & Samorodnitsky, G., 1994. "Subexponentiality of the product of independent random variables," Stochastic Processes and their Applications, Elsevier, vol. 49(1), pages 75-98, January.
    3. Yue Hu & Carri W. Chan & Jing Dong, 2022. "Optimal Scheduling of Proactive Service with Customer Deterioration and Improvement," Management Science, INFORMS, vol. 68(4), pages 2533-2578, April.
    4. Royi Jacobovic, 2022. "Internalization of externalities in queues with discretionary services," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 453-455, April.
    5. Asmussen, Søren & Klüppelberg, Claudia & Sigman, Karl, 1999. "Sampling at subexponential times, with queueing applications," Stochastic Processes and their Applications, Elsevier, vol. 79(2), pages 265-286, February.
    6. Zhang, Yi & Shen, Xinmei & Weng, Chengguo, 2009. "Approximation of the tail probability of randomly weighted sums and applications," Stochastic Processes and their Applications, Elsevier, vol. 119(2), pages 655-675, February.
    7. Jaap Geluk & Qihe Tang, 2009. "Asymptotic Tail Probabilities of Sums of Dependent Subexponential Random Variables," Journal of Theoretical Probability, Springer, vol. 22(4), pages 871-882, December.
    8. Baltrunas, A. & Daley, D. J. & Klüppelberg, C., 2004. "Tail behaviour of the busy period of a GI/GI/1 queue with subexponential service times," Stochastic Processes and their Applications, Elsevier, vol. 111(2), pages 237-258, June.
    9. Moshe Haviv & Ya'acov Ritov, 1998. "Externalities, Tangible Externalities, and Queue Disciplines," Management Science, INFORMS, vol. 44(6), pages 850-858, June.
    10. Junfei Huang & Boaz Carmeli & Avishai Mandelbaum, 2015. "Control of Patient Flow in Emergency Departments, or Multiclass Queues with Deadlines and Feedback," Operations Research, INFORMS, vol. 63(4), pages 892-908, August.
    11. Predrag R. Jelenković & Petar Momčilović, 2004. "Large Deviations of Square Root Insensitive Random Sums," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 398-406, May.
    12. A. P. Zwart, 2001. "Tail Asymptotics for the Busy Period in the GI/G/1 Queue," Mathematics of Operations Research, INFORMS, vol. 26(3), pages 485-493, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yang, Yang & Ignatavičiūtė, Eglė & Šiaulys, Jonas, 2015. "Conditional tail expectation of randomly weighted sums with heavy-tailed distributions," Statistics & Probability Letters, Elsevier, vol. 105(C), pages 20-28.
    2. Dan Zhu & Ming Zhou & Chuancun Yin, 2023. "Finite-Time Ruin Probabilities of Bidimensional Risk Models with Correlated Brownian Motions," Mathematics, MDPI, vol. 11(12), pages 1-18, June.
    3. Wang, Yinfeng & Yin, Chuancun, 2010. "Approximation for the ruin probabilities in a discrete time risk model with dependent risks," Statistics & Probability Letters, Elsevier, vol. 80(17-18), pages 1335-1342, September.
    4. Philip A. Ernst & Søren Asmussen & John J. Hasenbein, 2018. "Stability and busy periods in a multiclass queue with state-dependent arrival rates," Queueing Systems: Theory and Applications, Springer, vol. 90(3), pages 207-224, December.
    5. Kamphorst, Bart & Zwart, Bert, 2019. "Uniform asymptotics for compound Poisson processes with regularly varying jumps and vanishing drift," Stochastic Processes and their Applications, Elsevier, vol. 129(2), pages 572-603.
    6. Yoni Nazarathy & Zbigniew Palmowski, 2022. "On busy periods of the critical GI/G/1 queue and BRAVO," Queueing Systems: Theory and Applications, Springer, vol. 102(1), pages 219-225, October.
    7. Sun, Ying & Wei, Li, 2014. "The finite-time ruin probability with heavy-tailed and dependent insurance and financial risks," Insurance: Mathematics and Economics, Elsevier, vol. 59(C), pages 178-183.
    8. Robert, Christian Y. & Segers, Johan, 2008. "Tails of random sums of a heavy-tailed number of light-tailed terms," Insurance: Mathematics and Economics, Elsevier, vol. 43(1), pages 85-92, August.
    9. Predrag R. Jelenković & Petar Momčilović, 2004. "Large Deviations of Square Root Insensitive Random Sums," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 398-406, May.
    10. Li, Xiaohu & Wu, Jintang, 2014. "Asymptotic tail behavior of Poisson shot-noise processes with interdependence between shock and arrival time," Statistics & Probability Letters, Elsevier, vol. 88(C), pages 15-26.
    11. Royi Jacobovic, 2022. "Internalization of externalities in queues with discretionary services," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 453-455, April.
    12. Zhang, Chenhua, 2014. "Uniform asymptotics for the tail probability of weighted sums with heavy tails," Statistics & Probability Letters, Elsevier, vol. 94(C), pages 221-229.
    13. Yang, Haizhong & Sun, Suting, 2013. "Subexponentiality of the product of dependent random variables," Statistics & Probability Letters, Elsevier, vol. 83(9), pages 2039-2044.
    14. Serguei Foss & Andrew Richards, 2010. "On Sums of Conditionally Independent Subexponential Random Variables," Mathematics of Operations Research, INFORMS, vol. 35(1), pages 102-119, February.
    15. Yang, Yingying & Hu, Shuhe & Wu, Tao, 2011. "The tail probability of the product of dependent random variables from max-domains of attraction," Statistics & Probability Letters, Elsevier, vol. 81(12), pages 1876-1882.
    16. Robert, Christian Y., 2013. "Some new classes of stationary max-stable random fields," Statistics & Probability Letters, Elsevier, vol. 83(6), pages 1496-1503.
    17. Shen, Xinmei & Lin, Zhengyan, 2008. "Precise large deviations for randomly weighted sums of negatively dependent random variables with consistently varying tails," Statistics & Probability Letters, Elsevier, vol. 78(18), pages 3222-3229, December.
    18. S. Foss & A. Sapozhnikov, 2004. "On the Existence of Moments for the Busy Period in a Single-Server Queue," Mathematics of Operations Research, INFORMS, vol. 29(3), pages 592-601, August.
    19. Yang, Xiangfeng, 2015. "Exact upper tail probabilities of random series," Statistics & Probability Letters, Elsevier, vol. 99(C), pages 13-19.
    20. Kaas, Rob & Tang, Qihe, 2005. "A large deviation result for aggregate claims with dependent claim occurrences," Insurance: Mathematics and Economics, Elsevier, vol. 36(3), pages 251-259, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:queues:v:104:y:2023:i:3:d:10.1007_s11134-023-09878-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.