IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v106y2024i3d10.1007_s11134-024-09904-3.html
   My bibliography  Save this article

Efficient scheduling in redundancy systems with general service times

Author

Listed:
  • Elene Anton

    (Universite de Pau et des Pays de l’Adour, E2S UPPA, LIUPPA)

  • Rhonda Righter

    (University of California)

  • Ina Maria Verloop

    (CNRS-IRIT
    Université de Toulouse - INP)

Abstract

We characterize the impact of scheduling policies on the mean response time in nested systems with cancel-on-complete redundancy. We consider not only class- and state-oblivious policies such as FCFS and ROS, but also class-based, and, in particular, redundancy-aware policies of the form $$\Pi _1-\Pi _2$$ Π 1 - Π 2 , where $$\Pi _1$$ Π 1 discriminates among job classes based on their degree of redundancy (e.g., Least-Redundant-First (LRF), Most-Redundant-First (MRF)) and $$\Pi _2$$ Π 2 discriminates among jobs of the same class. Assuming that jobs have independent and identically distributed (i.i.d.) copies we prove the following: (i) When jobs have exponential service times, LRF policies outperform any other policy. (ii) When service times are New-Worse-than-Used, MRF-FCFS outperforms LRF-FCFS as the variability of the service time grows infinitely large. (iii) When service times are New-Better-than-Used, LRF-ROS (resp. MRF-ROS) outperforms LRF-FCFS (resp. MRF-FCFS) in a two-server system. Statement (iii) also holds when job sizes follow a general distribution and have identical copies (all the copies of a job have the same size). Moreover, we show via simulation that, for a large class of redundancy systems, class-based (and, in particular, redundancy-aware) policies can considerably improve the mean response time compared to policies that ignore the class. We also explore the effect of redundancy on the stability region.

Suggested Citation

  • Elene Anton & Rhonda Righter & Ina Maria Verloop, 2024. "Efficient scheduling in redundancy systems with general service times," Queueing Systems: Theory and Applications, Springer, vol. 106(3), pages 333-372, April.
    • Handle: RePEc:spr:queues:v:106:y:2024:i:3:d:10.1007_s11134-024-09904-3
    DOI: 10.1007/s11134-024-09904-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-024-09904-3
    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-024-09904-3?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. Kristen Gardner & Samuel Zbarsky & Sherwin Doroudi & Mor Harchol-Balter & Esa Hyytiä & Alan Scheller-Wolf, 2016. "Queueing with redundant requests: exact analysis," Queueing Systems: Theory and Applications, Springer, vol. 83(3), pages 227-259, August.
    2. Youri Raaijmakers & Sem Borst & Onno Boxma, 2019. "Redundancy scheduling with scaled Bernoulli service requirements," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 67-82, October.
    3. Kristen Gardner & Mor Harchol-Balter & Alan Scheller-Wolf & Mark Velednitsky & Samuel Zbarsky, 2017. "Redundancy-d: The Power of d Choices for Redundancy," Operations Research, INFORMS, vol. 65(4), pages 1078-1094, August.
    4. Kristen Gardner & Rhonda Righter, 2020. "Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 3-51, October.
    5. Elene Anton & Urtzi Ayesta & Matthieu Jonckheere & Ina Maria Verloop, 2021. "On the Stability of Redundancy Models," Operations Research, INFORMS, vol. 69(5), pages 1540-1565, September.
    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. Kristen Gardner & Pascal Moyal, 2024. "Editorial introduction: special issue on product forms, stochastic matching, and redundancy," Queueing Systems: Theory and Applications, Springer, vol. 106(3), pages 193-198, April.
    2. Kristen Gardner & Pascal Moyal, 2024. "Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 199-203, September.
    3. Kristen Gardner & Rhonda Righter, 2022. "The cost of collaboration," Queueing Systems: Theory and Applications, Springer, vol. 100(1), pages 7-40, February.
    4. Mor Harchol-Balter, 2021. "Open problems in queueing theory inspired by datacenter computing," Queueing Systems: Theory and Applications, Springer, vol. 97(1), pages 3-37, February.
    5. Jan-Pieter Dorsman & Kristen Gardner, 2024. "New directions in pass-and-swap queues," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 205-256, September.
    6. Kristen Gardner & Rhonda Righter, 2020. "Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 3-51, October.
    7. Francisco Castro & Hamid Nazerzadeh & Chiwei Yan, 2020. "Matching queues with reneging: a product form solution," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 359-385, December.
    8. Céline Comte & Jan-Pieter Dorsman, 2021. "Pass-and-swap queues," Queueing Systems: Theory and Applications, Springer, vol. 98(3), pages 275-331, August.
    9. Jinsheng Chen & Jing Dong & Pengyi Shi, 2020. "A survey on skill-based routing with applications to service operations management," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 53-82, October.
    10. Kristen Gardner, 2022. "Correlation in redundancy systems," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 197-199, April.
    11. Youri Raaijmakers & Sem Borst & Onno Boxma, 2019. "Redundancy scheduling with scaled Bernoulli service requirements," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 67-82, October.
    12. Gideon Weiss, 2022. "Parallel multi-type many server conjecture," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 269-271, April.
    13. Gideon Weiss, 2020. "Directed FCFS infinite bipartite matching," Queueing Systems: Theory and Applications, Springer, vol. 96(3), pages 387-418, December.
    14. Bušić Ana & Cadas Arnaud & Doncel Josu & Fourneau Jean-Michel, 2024. "Performance paradox of dynamic matching models under greedy policies," Queueing Systems: Theory and Applications, Springer, vol. 107(3), pages 257-293, September.
    15. Lisa Aoki Hillas & René Caldentey & Varun Gupta, 2024. "Heavy traffic analysis of multi-class bipartite queueing systems under FCFS," Queueing Systems: Theory and Applications, Springer, vol. 106(3), pages 239-284, April.
    16. Jonatha Anselmi, 2022. "Replication vs speculation for load balancing," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 389-391, April.
    17. Cardinaels, Ellen & Borst, Sem & van Leeuwaarden, Johan S.H., 2024. "Heavy-traffic universality of redundancy systems with assignment constraints," Other publications TiSEM 1ab2791a-b085-466e-8ada-e, Tilburg University, School of Economics and Management.
    18. Youri Raaijmakers & Sem Borst & Onno Boxma, 2023. "Fork–join and redundancy systems with heavy-tailed job sizes," Queueing Systems: Theory and Applications, Springer, vol. 103(1), pages 131-159, February.
    19. Leela Nageswaran, 2023. "Implications of vaccine shopping during pandemic," Production and Operations Management, Production and Operations Management Society, vol. 32(4), pages 1133-1149, April.
    20. Neil Walton, 2022. "Queueing: a perennial theory," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 557-559, April.

    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:106:y:2024:i:3:d:10.1007_s11134-024-09904-3. 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.