IDEAS home Printed from https://ideas.repec.org/a/eee/spapps/v157y2023icp279-307.html
   My bibliography  Save this article

Fluid limits for earliest-deadline-first networks

Author

Listed:
  • Atar, Rami
  • Shadmi, Yonatan

Abstract

This paper analyzes fluid scale asymptotics of two models of generalized Jackson networks employing the earliest deadline first (EDF) policy. One applies the ‘soft’ EDF policy, where deadlines are used to determine priority but jobs do not renege, and the other implements ‘hard’ EDF, where jobs renege when deadlines expire, and deadlines are postponed with each migration to a new station. The arrival rates, deadline distribution and service capacity are allowed to fluctuate over time at the fluid scale. Earlier work on EDF network fluid limits, used as a tool to obtain stability of these networks, addressed only the soft version of the policy, and moreover did not contain a full fluid limit result. In this paper, tools that extend the notion of the measure-valued Skorokhod map are developed and used to establish for the first time fluid limits for both the soft and hard EDF network models.

Suggested Citation

  • Atar, Rami & Shadmi, Yonatan, 2023. "Fluid limits for earliest-deadline-first networks," Stochastic Processes and their Applications, Elsevier, vol. 157(C), pages 279-307.
    • Handle: RePEc:eee:spapps:v:157:y:2023:i:c:p:279-307
    DOI: 10.1016/j.spa.2022.12.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304414922002642
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.spa.2022.12.006?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. Yonatan Shadmi, 2022. "Fluid limits for shortest job first with aging," Queueing Systems: Theory and Applications, Springer, vol. 101(1), pages 93-112, June.
    2. Martin I. Reiman, 1984. "Open Queueing Networks in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 9(3), pages 441-458, August.
    3. Atar, Rami & Dupuis, Paul, 1999. "Large deviations and queueing networks: Methods for rate function identification," Stochastic Processes and their Applications, Elsevier, vol. 84(2), pages 255-296, December.
    4. Atar, Rami & Biswas, Anup & Kaspi, Haya, 2018. "Law of large numbers for the many-server earliest-deadline-first queue," Stochastic Processes and their Applications, Elsevier, vol. 128(7), pages 2270-2296.
    5. Rami Atar & Haya Kaspi & Nahum Shimkin, 2014. "Fluid Limits for Many-Server Systems with Reneging Under a Priority Policy," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 672-696, August.
    6. Rami Atar & Anup Biswas & Haya Kaspi, 2015. "Fluid Limits of G / G /1+ G Queues Under the Nonpreemptive Earliest-Deadline-First Discipline," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 683-702, March.
    7. J. T. Chang & D. Pollard, 1997. "Conditioning as disintegration," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 51(3), pages 287-317, November.
    8. S. Ramasubramanian, 2000. "A Subsidy-Surplus Model and the Skorokhod Problem in an Orthant," Mathematics of Operations Research, INFORMS, vol. 25(3), pages 509-538, 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. Atar, Rami & Biswas, Anup & Kaspi, Haya, 2018. "Law of large numbers for the many-server earliest-deadline-first queue," Stochastic Processes and their Applications, Elsevier, vol. 128(7), pages 2270-2296.
    2. Ramasubramanian, S., 2006. "An insurance network: Nash equilibrium," Insurance: Mathematics and Economics, Elsevier, vol. 38(2), pages 374-390, April.
    3. I. Venkat Appal Raju & S. Ramasubramanian, 2016. "Risk Diversifying Treaty Between Two Companies with Only One in Insurance Business," Sankhya B: The Indian Journal of Statistics, Springer;Indian Statistical Institute, vol. 78(2), pages 183-214, November.
    4. Cohen, Asaf & Saha, Subhamay, 2021. "Asymptotic optimality of the generalized cμ rule under model uncertainty," Stochastic Processes and their Applications, Elsevier, vol. 136(C), pages 206-236.
    5. Avishai Mandelbaum & Petar Momčilović, 2017. "Personalized queues: the customer view, via a fluid model of serving least-patient first," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 23-53, October.
    6. Josh Reed & Yair Shaki, 2015. "A Fair Policy for the G / GI / N Queue with Multiple Server Pools," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 558-595, March.
    7. Saulius Minkevičius & Igor Katin & Joana Katina & Irina Vinogradova-Zinkevič, 2021. "On Little’s Formula in Multiphase Queues," Mathematics, MDPI, vol. 9(18), pages 1-15, September.
    8. Beare, Brendan K. & Seo, Juwon, 2014. "Time Irreversible Copula-Based Markov Models," Econometric Theory, Cambridge University Press, vol. 30(5), pages 923-960, October.
    9. Muralidharan, Ajith & Pedarsani, Ramtin & Varaiya, Pravin, 2015. "Analysis of fixed-time control," Transportation Research Part B: Methodological, Elsevier, vol. 73(C), pages 81-90.
    10. Ad Ridder & Adam Shwartz, 2005. "Large deviations without principle: join the shortest queue," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 62(3), pages 467-483, December.
    11. Mor Armony & Constantinos Maglaras, 2004. "On Customer Contact Centers with a Call-Back Option: Customer Decisions, Routing Rules, and System Design," Operations Research, INFORMS, vol. 52(2), pages 271-292, April.
    12. Saulius Minkevičius & Edvinas Greičius, 2019. "Heavy Traffic Limits for the Extreme Waiting Time in Multi-phase Queueing Systems," Methodology and Computing in Applied Probability, Springer, vol. 21(1), pages 109-124, March.
    13. Ad Ridder & Adam Shwartz, 2005. "Large Deviations Methods and the Join-the-Shortest-Queue Model," Tinbergen Institute Discussion Papers 05-016/4, Tinbergen Institute.
    14. Nathan Canen & Kyungchul Song, 2020. "A Decomposition Approach to Counterfactual Analysis in Game-Theoretic Models," Papers 2010.08868, arXiv.org, revised Jul 2024.
    15. Heifetz, Aviad, 2006. "The positive foundation of the common prior assumption," Games and Economic Behavior, Elsevier, vol. 56(1), pages 105-120, July.
    16. Georg Nöldeke & Larry Samuelson, 2018. "The Implementation Duality," Econometrica, Econometric Society, vol. 86(4), pages 1283-1324, July.
    17. Biswas, Anup & Budhiraja, Amarjit, 2011. "Exit time and invariant measure asymptotics for small noise constrained diffusions," Stochastic Processes and their Applications, Elsevier, vol. 121(5), pages 899-924.
    18. Avi Mandelbaum & Kavita Ramanan, 2010. "Directional Derivatives of Oblique Reflection Maps," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 527-558, August.
    19. Yamada, Keigo, 1999. "Two limit theorems for queueing systems around the convergence of stochastic integrals with respect to renewal processes," Stochastic Processes and their Applications, Elsevier, vol. 80(1), pages 103-128, March.
    20. Ward Whitt & Wei You, 2020. "Heavy-traffic limits for stationary network flows," Queueing Systems: Theory and Applications, Springer, vol. 95(1), pages 53-68, 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:eee:spapps:v:157:y:2023:i:c:p:279-307. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/505572/description#description .

    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.