pith. machine review for the scientific record. sign in

arxiv: 2605.01522 · v1 · submitted 2026-05-02 · 💻 cs.PF · math.PR

Recognition: unknown

Priority Scheduling in the M/G/1 with Preemption Overhead

Edwin Peng, Shefali Ramakrishna, Ziv Scully

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:51 UTC · model grok-4.3

classification 💻 cs.PF math.PR
keywords M/G/1 queuepreemptive prioritypreemption overheadresponse time distributionLaplace transformqueueing theoryscheduling policy
0
0 comments X

The pith

Preemptive priority scheduling in the M/G/1 admits an exact response time distribution formula even when each pause or resume incurs stochastic overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a recursive formula for the Laplace transform of response time for every job class in an M/G/1 queue under class-based preemptive priority when stochastic overhead is incurred on each preemption. Prior queueing analyses omitted overheads despite their presence in virtually all practical preemptive systems, making stability regions and performance predictions unreliable. The derivation extracts all response time moments directly from the transform and introduces the job joint transform to keep the analysis tractable across many overhead models. This supplies the first closed-form distributional results for a preemptive policy that accounts for overhead.

Core claim

For class-based preemptive priority in the M/G/1 with stochastic overhead incurred independently on each pause or resume, a recursive formula yields the Laplace transform of response time for jobs of any given class; all moments follow by differentiation. The derivation relies on modeling the joint effect of job size and overheads via a new tool, the job joint transform, that remains closed under the priority discipline and extends to a wide variety of overhead distributions.

What carries the argument

The job joint transform, which tracks the combined effect of remaining job size and preemption overheads so that the transform recurses cleanly when a job is preempted or resumed under priority ordering.

If this is right

  • All moments of response time for each class become computable from the Laplace transform.
  • The stability region of the system can be obtained while fully accounting for overhead.
  • The same job joint transform technique applies to many other overhead models beyond the one analyzed.
  • Designers can now compare preemptive priority against non-preemptive alternatives using exact performance metrics that include overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The recursive structure may admit numerical inversion routines that let practitioners compute tail probabilities for specific overhead distributions.
  • The approach could extend to size-based preemptive policies such as SRPT once an analogous joint transform is defined for remaining work.
  • In real systems the formula supplies a benchmark for choosing preemption thresholds that balance overhead against responsiveness.

Load-bearing premise

The preemption overhead must be stochastic and incurred independently on each pause or resume with a distribution that lets the joint transform close under the priority discipline.

What would settle it

Simulate an M/G/1 system with a concrete overhead distribution, compute the empirical response time distribution for each class, and invert the recursive Laplace transform; disagreement between the two distributions falsifies the formula.

Figures

Figures reproduced from arXiv: 2605.01522 by Edwin Peng, Shefali Ramakrishna, Ziv Scully.

Figure 3.1
Figure 3.1. Figure 3.1: (Left) The service history of a class 2 job represented via a busy period tree. Shaded regions mark periods of overhead. Arrows mark exactly when arrivals occurred during the root job’s effective service time. (Right) The corresponding realization of the job joint distribution J2 = (𝑅2,𝐴® 2) Algorithm 3.1. Generation of a busy period tree Generate root of the busy period tree: ⊲ Assign the root class 𝑘 ∈… view at source ↗
Figure 3.2
Figure 3.2. Figure 3.2: (Left) A full busy period tree. Nodes are labeled with their class. Classes 1, 2, and 3 are purple, green, and orange respectively. Overhead is shaded darker. Pause and resumes are labeled with “P” and “R” respectively. Arrows are drawn from jobs to the jobs that arrived during their service. (Right) Highlighting the class < 3 busy period tree with a blue background and black outline. Jobs of class 3 and… view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: A class 3 job and the arrivals during its service. The shaded orange region marked A is a class 3 overhead chain made up of two links, and the other shaded orange region marked B is another class 3 overhead chain made up of only one link. (Section 2) to derive the exact form of the job joint transform for our system. By deriving the job joint transform for our system and the load of the system, we will h… view at source ↗
Figure 5
Figure 5. Figure 5: illustrates how a timeline of arrivals and service corresponds to the segment tree. [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: Two representations of the arrival sequence and service order of jobs in a busy period. Job F is of class 1 (periwinkle); jobs C, D, and E are of class 2 (orange); and jobs A and B are of class 3 (green). Each block is a segment of a job. Original work is colored a lighter shade and overhead work is colored a darker shade. (Left) Timeline of the service order of segments in the system. Time goes from lef… view at source ↗
Figure 5.2
Figure 5.2. Figure 5.2: (Left) Class 2 relevant subtrees of a segment tree highlighted by blue backgrounds. Segments are labeled with their class. Red dotted arrows indicate arrival or continuation edge into class > 2 segment. (Right) Separation of the class 2 relevant subtrees. The set of segments in each subtree is served contiguously, and notably, any class ≤ 2 job arrives and departs entirely during its relevant subtree. Ob… view at source ↗
Figure 5.3
Figure 5.3. Figure 5.3: (Left) A single class 2 relevant subtree. Segments are labeled with their class. Red dotted arrows denote arrival edges into class 2 jobs. (Right) Partition of the segments into class 2 superjobs and a class 2 supersetup. Shaded areas denote boundaries between different class 2 superjobs or supersetups. The pink shaded area denotes a supersetup, whereas each blue shaded area denotes a separate superjob. … view at source ↗
Figure 5.4
Figure 5.4. Figure 5.4: Pictured above are the various states of the system to which an early class 2 job (green, with dotted border) could arrive. From left to right, an early class 2 job could (a) arrive during the busy period started by a lower-class job that arrived to an idle system, (b) arrive during the busy period started by the pause overhead triggered by an earlier class ≤ 2 job that arrived during the service of a cl… view at source ↗
read the original abstract

Virtually all practical settings where preemptive scheduling is employed are susceptible to preemption overhead, and accounting for these overheads is necessary to make informed scheduling design decisions. However, preemption overhead is almost never accounted for in queueing-theoretic analyses of preemptive scheduling policies. This is true even for simple preemptive policies in simple queueing models: even the stability region, let alone the response time distribution, is difficult to analyze under overhead. In this work, we give the first response time distribution analysis of an M/G/1 under a preemptive scheduling policy with preemption overhead. Specifically, we consider class-based preemptive priority, where a stochastic overhead is incurred when pausing or resuming a job. We derive a recursive formula for the Laplace transform of response time for jobs of any given class, from which all response time moments can be extracted. Beyond the specific policy and model we analyze, our broader aim is to provide a first step towards a general framework for analyzing queues with preemption overhead. To that end, we perform much of our analysis in a way that applies to a wide variety of overhead models by introducing a new theoretical tool called the job joint transform.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The paper analyzes the M/G/1 queue under class-based preemptive priority scheduling with stochastic preemption overhead incurred on each pause or resume. It introduces the job joint transform as a new tool and derives a recursive formula for the Laplace transform of response time for each class, from which moments can be extracted. The broader goal is a framework for queues with preemption overhead.

Significance. If the recursive derivation is correct, the result is significant: it supplies the first exact response-time analysis for a standard preemptive policy once overhead is included, fills a practical gap in queueing theory, and supplies a reusable transform tool. The ability to extract all moments and the explicit handling of overhead distinguish it from prior work that assumes zero-cost preemption.

major comments (1)
  1. [§4] §4 (recursive Laplace-transform derivation) and the definition of the job joint transform: the recursion is stated to hold for a general stochastic overhead model, yet the closure property under the priority discipline is only guaranteed when the overhead distribution satisfies the specific transform-manipulation conditions identified in the skeptic note. The manuscript should add an explicit lemma or corollary stating the precise conditions on the overhead distribution (e.g., independence, support, or moment requirements) that make the joint transform close recursively; without this, the central claim applies only to a narrower class of overheads than advertised.
minor comments (3)
  1. [Abstract] The abstract claims that 'all response time moments can be extracted' from the Laplace transform; a short paragraph or appendix showing the differentiation steps for the first two moments would make this concrete and aid readers.
  2. [Introduction] Stability region is mentioned as difficult to analyze under overhead, yet no explicit stability condition (in terms of load and overhead moments) is given for the multi-class case; adding this would strengthen the practical utility.
  3. [§3] Notation for the joint transform (e.g., the arguments corresponding to remaining work and overhead) should be summarized in a table or displayed equation early in the paper to reduce reader effort when following the recursion.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying an opportunity to strengthen the presentation of the job joint transform and its recursive application. We address the major comment below and have revised the manuscript to incorporate an explicit statement of the required conditions.

read point-by-point responses

  1. Referee: §4 (recursive Laplace-transform derivation) and the definition of the job joint transform: the recursion is stated to hold for a general stochastic overhead model, yet the closure property under the priority discipline is only guaranteed when the overhead distribution satisfies the specific transform-manipulation conditions identified in the skeptic note. The manuscript should add an explicit lemma or corollary stating the precise conditions on the overhead distribution (e.g., independence, support, or moment requirements) that make the joint transform close recursively; without this, the central claim applies only to a narrower class of overheads than advertised.

    Authors: We agree that an explicit statement of the closure conditions improves clarity. The job joint transform is constructed precisely so that it remains closed under the preemptive priority recursion whenever the overhead random variables are independent of service times and of one another and possess a Laplace-Stieltjes transform that is analytic in a neighborhood of the origin. These are the minimal conditions needed for the algebraic manipulations in the recursion to be valid. We have added Lemma 4.1 in Section 4, which states these requirements formally and proves that they suffice for recursive closure. The lemma is referenced in the abstract, introduction, and the statement of the main theorem. We have also added a short remark clarifying that the result therefore applies to any overhead distribution satisfying these standard analytic conditions (e.g., exponential, deterministic, or phase-type overheads), which covers the models of practical interest while making the scope precise. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation introduces independent joint transform tool

full rationale

The paper derives a recursive Laplace-transform formula for response time by introducing a new 'job joint transform' tool that enables closure under the priority discipline for a class of overhead models. This is a first-principles application of standard transform methods to an extended model; the recursion is obtained from the tool rather than by renaming or fitting inputs. No self-citations are load-bearing in the provided derivation chain, and the result is not equivalent to the inputs by construction. The closure property is an explicit modeling assumption, not a hidden tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

Central claim rests on standard M/G/1 assumptions plus a new modeling construct for overhead. No free parameters are mentioned. The job joint transform is an invented entity whose independent evidence is not provided in the abstract.

axioms (2)
  • domain assumption Jobs arrive according to a Poisson process and have i.i.d. general service times (M/G/1 model)
    Core modeling assumption stated in the title and abstract.
  • domain assumption Preemption overhead is stochastic, incurred on each pause or resume, and independent of job state
    Required for the overhead model analyzed and for the joint transform to be well-defined.
invented entities (1)
  • job joint transform no independent evidence
    purpose: Theoretical tool that captures combined effects of service and preemption overhead to enable analysis across overhead models
    New construct introduced to generalize the analysis beyond the specific priority policy.

pith-pipeline@v0.9.0 · 5509 in / 1534 out tokens · 43764 ms · 2026-05-10T15:51:25.424700+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

50 extracted references · 38 canonical work pages

  1. [1]

    Søren Asmussen and Peter W. Glynn. 2017. On Preemptive-Repeat LIFO Queues.Queueing Systems87, 1 (Oct. 2017), 1–22. doi:10.1007/s11134-017-9532-3

    work page doi:10.1007/s11134-017-9532-3 2017

  2. [2]

    Athreya and Peter E

    Krishna B. Athreya and Peter E. Ney. 1972.Branching Processes. Springer, Berlin, Germany. doi:10.1007/978-3-642-65371-1

    work page doi:10.1007/978-3-642-65371-1 1972

  3. [3]

    Avi-Itzhak

    B. Avi-Itzhak. 1963. Preemptive Repeat Priority Queues as a Special Case of the Multipurpose Server Problem—II.Operations Research11, 4 (Aug. 1963), 610–619. doi:10.1287/opre.11.4. 610

    work page doi:10.1287/opre.11.4 1963

  4. [4]

    Nikhil Bansal, Bart Kamphorst, and Bert Zwart. 2018. Achievable Performance of Blind Policies in Heavy Traffic.Mathematics of Operations Research43, 3 (Aug. 2018), 949–964. doi:10.1287/moor.2017.0890

    work page doi:10.1287/moor.2017.0890 2018

  5. [5]

    Jacob Bergquist and Karl Sigman. 2022. Stationary Workload and Service Times for Some Nonwork-Conserving M/G/1 Preemptive LIFO Queues.Stochastic Models38, 4 (Oct. 2022), 515–544. doi:10.1080/15326349.2022.2074458

    work page doi:10.1080/15326349.2022.2074458 2022

  6. [6]

    Dimitris Bertsimas and José Niño-Mora. 1999. Optimization of Multiclass Queueing Networks with Changeover Times via the Achievable Region Approach: Part II, the Multi-Station Case. Mathematics of Operations Research24, 2 (May 1999), 331–361. doi:10.1287/moor.24.2.331

    work page doi:10.1287/moor.24.2.331 1999

  7. [7]

    Marko A. A. Boon, Rob D. van der Mei, and Erik M. M. Winands. 2011. Applications of Polling Systems.Surveys in Operations Research and Management Science16, 2 (July 2011), 67–82. doi:10.1016/j.sorms.2011.01.001 26 Priority Scheduling in the M/G/1 with Preemption Overhead Shefali Ramakrishna, Edwin Peng, and Ziv Scully

    work page doi:10.1016/j.sorms.2011.01.001 2011

  8. [8]

    Borst and Onno J

    Sem C. Borst and Onno J. Boxma. 1997. Polling Models with and without Switchover Times. Operations Research45, 4 (Aug. 1997), 536–543. doi:10.1287/opre.45.4.536

    work page doi:10.1287/opre.45.4.536 1997

  9. [9]

    Borst and Onno J

    Sem C. Borst and Onno J. Boxma. 2018. Polling: Past, Present, and Perspective.TOP26, 3 (Oct. 2018), 335–369. doi:10.1007/s11750-018-0484-5

    work page doi:10.1007/s11750-018-0484-5 2018

  10. [10]

    Boxma and Wim P

    Onno J. Boxma and Wim P. Groenendijk. 1987. Pseudo-Conservation Laws in Cyclic-Service Systems.Journal of Applied Probability24, 4 (1987), 949–964. doi:10.2307/3214218

    work page doi:10.2307/3214218 1987

  11. [11]

    Boxma and Bert Zwart

    Onno J. Boxma and Bert Zwart. 2007. Tails in Scheduling.ACM SIGMETRICS Performance Evaluation Review34, 4 (March 2007), 13–20. doi:10.1145/1243401.1243406

    work page doi:10.1145/1243401.1243406 2007

  12. [12]

    Jianyu Cao and Weixin Xie. 2017. Stability of a Two-Queue Cyclic Polling System with BMAPs under Gated Service and State-Dependent Time-Limited Service Disciplines.Queueing Systems 85, 1 (Feb. 2017), 117–147. doi:10.1007/s11134-016-9504-z

    work page doi:10.1007/s11134-016-9504-z 2017

  13. [13]

    Wei Chang. 1965. Preemptive Priority Queues.Operations Research13, 5 (Oct. 1965), 820–827. doi:10.1287/opre.13.5.820

    work page doi:10.1287/opre.13.5.820 1965

  14. [14]

    Stanford

    Steve Drekic and David A. Stanford. 2001. Reducing Delay in Preemptive Repeat Priority Queues.Operations Research49, 1 (Feb. 2001), 145–156. doi:10.1287/opre.49.1.145.11186

    work page doi:10.1287/opre.49.1.145.11186 2001

  15. [15]

    Ernst, Søren Asmussen, and John J

    Philip A. Ernst, Søren Asmussen, and John J. Hasenbein. 2018. Stability and Busy Periods in a Multiclass Queue with State-Dependent Arrival Rates.Queueing Systems90, 3-4 (Dec. 2018), 207–224. doi:10.1007/s11134-018-9587-9

    work page doi:10.1007/s11134-018-9587-9 2018

  16. [16]

    Val Andrei Fajardo and Steve Drekic. 2017. Waiting Time Distributions in the Preemptive Accumulating Priority Queue.Methodology and Computing in Applied Probability19, 1 (March 2017), 255–284. doi:10.1007/s11009-015-9476-1

    work page doi:10.1007/s11009-015-9476-1 2017

  17. [17]

    S. W. Fuhrmann and Robert B. Cooper. 1985. Stochastic Decompositions in the 𝑀/𝐺/ 1Queue with Generalized Vacations.Operations Research33, 5 (Oct. 1985), 1117–1129. doi: 10.1287/ opre.33.5.1117

    1985

  18. [18]

    Donald P. Gaver. 1962. A Waiting Line with Interrupted Service, Including Priorities.Journal of the Royal Statistical Society. Series B (Methodological)24, 1 (1962), 73–90. doi: 10.1111/j. 2517-6161.1962.tb00438.x

    work page doi:10.1111/j 1962

  19. [19]

    Carmelita Goerg. 1986. Evaluation of the Optimal SRPT Strategy with Overhead.IEEE Transactions on Communications34, 4 (April 1986), 338–344. doi: 10.1109/TCOM.1986.1096548

    work page doi:10.1109/tcom.1986.1096548 1986

  20. [20]

    2013.Performance Modeling and Design of Computer Systems: Queueing Theory in Action

    Mor Harchol-Balter. 2013.Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press, Cambridge, UK. doi: 10.1017/ CBO9781139226424

    2013

  21. [21]

    1963.The Theory of Branching Processes

    Theodore Edward Harris. 1963.The Theory of Branching Processes. Springer, Berlin, Germany. https://www.rand.org/pubs/reports/R381.html

    1963

  22. [22]

    Bart Kamphorst and Bert Zwart. 2020. Heavy-Traffic Analysis of Sojourn Time under the Foreground–Background Scheduling Policy.Stochastic Systems10, 1 (March 2020), 1–28. doi:10.1287/stsy.2019.0036 27 Priority Scheduling in the M/G/1 with Preemption Overhead Shefali Ramakrishna, Edwin Peng, and Ziv Scully

    work page doi:10.1287/stsy.2019.0036 2020

  23. [23]

    1976.Queueing Systems, Volume 2: Computer Applications

    Leonard Kleinrock. 1976.Queueing Systems, Volume 2: Computer Applications. Wiley, New York, NY

    1976

  24. [24]

    Chuanpeng Li, Chen Ding, and Kai Shen. 2007. Quantifying the Cost of Context Switch. In Proceedings of the 2007 Workshop on Experimental Computer Science (ExpCS 2007). ACM, San Diego, CA, 4. doi:10.1145/1281700.1281702

    work page doi:10.1145/1281700.1281702 2007

  25. [25]

    Minghong Lin, Adam Wierman, and Bert Zwart. 2011. Heavy-Traffic Analysis of Mean Response Time under Shortest Remaining Processing Time.Performance Evaluation68, 10 (Oct. 2011), 955–966. doi:10.1016/j.peva.2011.06.001

    work page doi:10.1016/j.peva.2011.06.001 2011

  26. [26]

    John D. C. Little. 2011. Little’s Law as Viewed on Its 50th Anniversary.Operations Research 59, 3 (June 2011), 536–549. doi:10.1287/opre.1110.0940

    work page doi:10.1287/opre.1110.0940 2011

  27. [27]

    Jayakrishnan Nair, Adam Wierman, and Bert Zwart. 2010. Tail-Robust Scheduling via Limited Processor Sharing.Performance Evaluation67, 11 (Nov. 2010), 978–995. doi: 10.1016/j.peva. 2010.08.012

    work page doi:10.1016/j.peva 2010

  28. [28]

    Marcel F. Neuts. 1977. The 𝑀/𝐺/ 1Queue with Several Types of Customers and Change-over Times.Advances in Applied Probability9, 3 (Sept. 1977), 604–644. doi:10.2307/1426117

    work page doi:10.2307/1426117 1977

  29. [29]

    Rudesindo Núñez-Queija. 2002. Queues with Equally Heavy Sojourn Time and Service Requirement Distributions.Annals of Operations Research113, 1/4 (July 2002), 101–117. doi:10.1023/A:1020905810996

    work page doi:10.1023/a:1020905810996 2002

  30. [30]

    Natalia Osipova, Urtzi Ayesta, and Konstantin Avrachenkov. 2009. Optimal Policy for Multi- Class Scheduling in a Single Server Queue. In21st International Teletraffic Congress (ITC 21). IEEE, Paris, France, 1–8

    2009

  31. [31]

    Edwin Peng. 2022. Exact Response Time Analysis of Preemptive Priority Scheduling with Switching Overhead.ACM SIGMETRICS Performance Evaluation Review49, 2 (Jan. 2022), 72–74. doi:10.1145/3512798.3512824

    work page doi:10.1145/3512798.3512824 2022

  32. [32]

    Shefali Ramakrishna and Ziv Scully. 2024. Transform Analysis of Preemption Overhead in the M/G/1.ACM SIGMETRICS Performance Evaluation Review52, 2 (Sept. 2024), 18–20. doi:10.1145/3695411.3695419

    work page doi:10.1145/3695411.3695419 2024

  33. [33]

    Runnenburg

    Johannes Th. Runnenburg. 1965. On the Use of the Method of Collective Marks in Queueing Theory. InProceedings of the Symposium on Congestion Theory, Walter L. Smith and William E. Wilkinson (Eds.). University of North Carolina Press, Chapel Hill, 399–438

    1965

  34. [34]

    Runnenburg

    Johannes Th. Runnenburg. 1979. Van Dantzig’s Collective Marks Revisited. InProceedings Bicentennial Congress Wiskundig Genootschap; Part II (Mathematical Centre Tracts, 101), P. C. Baayen, D. van Dulst, and J. Oosterhoff (Eds.). Centrum Voor Wiskunde en Informatica, Amsterdam, The Netherlands, 309–329

    1979

  35. [35]

    Linus Schrage. 1969. A Mixed-Priority Queue with Applications to the Analysis of Real-Time Systems.Operations Research17, 4 (Aug. 1969), 728–742. doi:10.1287/opre.17.4.728 28 Priority Scheduling in the M/G/1 with Preemption Overhead Shefali Ramakrishna, Edwin Peng, and Ziv Scully

    work page doi:10.1287/opre.17.4.728 1969

  36. [36]

    Linus E. Schrage. 1967. The Queue 𝑀/𝐺/ 1with Feedback to Lower Priority Queues.Manage- ment Science13, 7 (March 1967), 466–474. doi:10.1287/mnsc.13.7.466

    work page doi:10.1287/mnsc.13.7.466 1967

  37. [37]

    Schrage and Louis W

    Linus E. Schrage and Louis W. Miller. 1966. The Queue 𝑀/𝐺/ 1with the Shortest Remaining Processing Time Discipline.Operations Research14, 4 (Aug. 1966), 670–684. doi: 10.1287/ opre.14.4.670

    1966

  38. [38]

    2022.A New Toolbox for Scheduling Theory

    Ziv Scully. 2022.A New Toolbox for Scheduling Theory. Ph. D. Dissertation. Carnegie Mellon University, Pittsburgh, PA.https://ziv.codes/pdf/scully-thesis.pdf

    2022

  39. [39]

    Ziv Scully and Mor Harchol-Balter. 2018. SOAP Bubbles: Robust Scheduling under Adversarial Noise. In56th Annual Allerton Conference on Communication, Control, and Computing. IEEE, Monticello, IL, 144–154. doi:10.1109/ALLERTON.2018.8635963

    work page doi:10.1109/allerton.2018.8635963 2018

  40. [40]

    Ziv Scully, Mor Harchol-Balter, and Alan Scheller-Wolf. 2018. SOAP: One Clean Analysis of All Age-Based Scheduling Policies.Proceedings of the ACM on Measurement and Analysis of Computing Systems2, 1, Article 16 (March 2018), 30 pages. doi:10.1145/3179419

    work page doi:10.1145/3179419 2018

  41. [41]

    Boxma, Jan-Pieter Dorsman, and Adam Wierman

    Ziv Scully, Lucas van Kreveld, Onno J. Boxma, Jan-Pieter Dorsman, and Adam Wierman

  42. [42]

    Proceedings of the ACM on Measurement and Analysis of Computing Systems4, 2, Article 30 (June 2020), 33 pages

    Characterizing Policies with Optimal Response Time Tails under Heavy-Tailed Job Sizes. Proceedings of the ACM on Measurement and Analysis of Computing Systems4, 2, Article 30 (June 2020), 33 pages. doi:10.1145/3392148

    work page doi:10.1145/3392148 2020

  43. [43]

    Stanford, Peter Taylor, and Ilze Ziedins

    David A. Stanford, Peter Taylor, and Ilze Ziedins. 2014. Waiting Time Distributions in the Accumulating Priority Queue.Queueing Systems77, 3 (July 2014), 297–330. doi: 10.1007/ s11134-013-9382-6

    2014

  44. [44]

    Lajos Takács. 1963. Delay Distributions for One Line with Poisson Input, General Holding Times, and Various Orders of Service.Bell System Technical Journal42, 2 (March 1963), 487–503. doi:10.1002/j.1538-7305.1963.tb00509.x

    work page doi:10.1002/j.1538-7305.1963.tb00509.x 1963

  45. [45]

    Van Oyen, Dimitrios G

    Mark P. Van Oyen, Dimitrios G. Pandelis, and Demosthenis Teneketzis. 1992. Optimality of Index Policies for Stochastic Scheduling with Switching Penalties.Journal of Applied Probability29, 4 (Dec. 1992), 957–966. doi:10.2307/3214727

    work page doi:10.2307/3214727 1992

  46. [46]

    2019.Queueing Systems with Non-Standard Service Poli- cies and Server Vacations

    Rocco van Vreumingen. 2019.Queueing Systems with Non-Standard Service Poli- cies and Server Vacations. MSc. University of Amsterdam, Amsterdam, The Nether- lands. http://www.mt-support.nl/VanVreumingen/Rocco/wp-content/uploads/2020/01/ Master-thesis-Queueing-systems-with-non-standard-service-policies-and-server-vacations. pdf

    2019

  47. [47]

    Chang-Heng Wang, Siva Theja Maguluri, and Tara Javidi. 2021. Heavy Traffic Queue Length Scaling in Switches with Reconfiguration Delay.Queueing Systems98, 1 (June 2021), 49–93. doi:10.1007/s11134-021-09695-x

    work page doi:10.1007/s11134-021-09695-x 2021

  48. [48]

    Adam Wierman, Mor Harchol-Balter, and Takayuki Osogami. 2005. Nearly Insensitive Bounds on SMART Scheduling.ACM SIGMETRICS Performance Evaluation Review33, 1 (June 2005), 205–216. doi:10.1145/1071690.1064236 29 Priority Scheduling in the M/G/1 with Preemption Overhead Shefali Ramakrishna, Edwin Peng, and Ziv Scully

    work page doi:10.1145/1071690.1064236 2005

  49. [49]

    Adam Wierman and Misja Nuyens. 2008. Scheduling despite Inexact Job-Size Information. ACM SIGMETRICS Performance Evaluation Review36, 1 (June 2008), 25–36. doi: 10.1145/ 1384529.1375461

    work page arXiv 2008

  50. [50]

    marked” Poisson arrivals (occurring at rate𝜃) occur during𝑉. In this context, we refer to𝑉as being “unmarked

    Adam Wierman and Bert Zwart. 2012. Is Tail-Optimal Scheduling Possible?Operations Research60, 5 (Oct. 2012), 1249–1257. doi:10.1287/opre.1120.1086 30 Priority Scheduling in the M/G/1 with Preemption Overhead Shefali Ramakrishna, Edwin Peng, and Ziv Scully. A Notation Table Notation Description Defined in 𝑛number of classes § 2 <𝑘,≤𝑘,>𝑘,≥𝑘shorthand for set...

    work page doi:10.1287/opre.1120.1086 2012