Efficient scheduling in redundancy systems with general service times

Elene Anton (), Rhonda Righter and Ina Maria Verloop
Additional contact information
Elene Anton: Universite de Pau et des Pays de l’Adour, E2S UPPA, LIUPPA
Rhonda Righter: University of California
Ina Maria Verloop: CNRS-IRIT

Queueing Systems: Theory and Applications, 2024, vol. 106, issue 3, No 5, 333-372

Abstract: 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.

Keywords: Scheduling; Redundancy; Compatibilities; Performance (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11134-024-09904-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:queues:v:106:y:2024:i:3:d:10.1007_s11134-024-09904-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11134/

DOI: 10.1007/s11134-024-09904-3

Access Statistics for this article

Queueing Systems: Theory and Applications is currently edited by Sergey Foss

More articles in Queueing Systems: Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().