pith. sign in

arxiv: 1907.04824 · v1 · pith:PGJVLMCUnew · submitted 2019-07-10 · 💻 cs.PF · cs.DS

Scheduling With Inexact Job Sizes: The Merits of Shortest Processing Time First

Matteo Dell'Amico This is my paper

Pith reviewed 2026-05-24 23:16 UTC · model grok-4.3

classification 💻 cs.PF cs.DS
keywords schedulingjob size estimationSPTSRPTresponse timesimulationperformance evaluation
0
0 comments X

The pith

When job sizes are only estimates, the simple Shortest Processing Time policy matches the performance of complex alternatives.

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

The paper examines size-based scheduling when exact job lengths are unavailable and only coarse estimates exist. It focuses on Shortest Processing Time (SPT), a preemptive policy that always runs the job with the shortest estimated time and does not adjust estimates as work progresses. Simulations show that SPT achieves response times close to those of more elaborate algorithms built to tolerate estimation mistakes. This matters because size-based policies can cut average waiting times and improve fairness, yet exact sizes are rarely known in practice. The simplicity of SPT suggests it may allow future mathematical analysis even when inputs are inexact.

Core claim

SPT is a simplification of SRPT that skips remaining-size updates and simply schedules the job with the shortest estimated processing time. When job size estimates contain errors, SPT performs comparably to the best known algorithms designed for inexact sizes while being substantially simpler, as shown through extensive simulation across various error models and workloads.

What carries the argument

Shortest Processing Time (SPT): the scheduling rule that preemptively selects the job whose estimated total processing time is the smallest.

If this is right

  • SPT yields near-optimal mean sojourn time in simulated scenarios with inexact job sizes.
  • It is easier to implement and potentially analyze than error-aware alternatives.
  • Performance remains robust across different workload distributions and error patterns tested.

Where Pith is reading between the lines

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

  • Analytical results for SPT under error might become feasible due to its lack of state updates.
  • Practical systems could adopt SPT more readily than complex policies.
  • Similar simplifications might apply to other policies affected by estimation errors.

Load-bearing premise

The models used for job size distributions and estimation errors in the simulations represent those found in actual computing systems.

What would settle it

A trace from a production system or an additional simulation where SPT's mean response time exceeds that of the best error-handling algorithm by more than a small margin.

Figures

Figures reproduced from arXiv: 1907.04824 by Matteo Dell'Amico.

Figure 1
Figure 1. Figure 1: Mean sojourn time (MST) of various algorithms against PS: at the dotted line, MST is equivalent to PS. A low shape value corresponds to high job [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Impact on mean sojourn time of the Weibull distribution’s shape [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 5
Figure 5. Figure 5: Per-job slowdown: full CDF (top) and zoom on the 10% more critical [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: Impact of error on heavy-tailed workloads, sorted by growing skew. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 7
Figure 7. Figure 7: Evaluation on real workloads from Facebook. [PITH_FULL_IMAGE:figures/full_fig_p006_7.png] view at source ↗
read the original abstract

It is well known that size-based scheduling policies, which take into account job size (i.e., the time it takes to run them), can perform very desirably in terms of both response time and fairness. Unfortunately, the requirement of knowing a priori the exact job size is a major obstacle which is frequently insurmountable in practice. Often, it is possible to get a coarse estimation of job size, but unfortunately analytical results with inexact job sizes are challenging to obtain, and simulation-based studies show that several size-based algorithm are severely impacted by job estimation errors. For example, Shortest Remaining Processing Time (SRPT), which yields optimal mean sojourn time when job sizes are known exactly, can drastically underperform when it is fed inexact job sizes. Some algorithms have been proposed to better handle size estimation errors, but they are somewhat complex and this makes their analysis challenging. We consider Shortest Processing Time (SPT), a simplification of SRPT that skips the update of "remaining" job size and results in a preemptive algorithm that simply schedules the job with the shortest estimated processing time. When job size is inexact, SPT performs comparably to the best known algorithms in the presence of errors, while being definitely simpler. In this work, SPT is evaluated through simulation, showing near-optimal performance in many cases, with the hope that its simplicity can open the way to analytical evaluation even when inexact inputs are considered.

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

2 major / 1 minor

Summary. The manuscript claims that Shortest Processing Time (SPT), a preemptive policy that schedules the job with the shortest estimated size without updating remaining times, achieves performance comparable to more complex algorithms designed for inexact job sizes, while being simpler; this is supported by simulation results showing near-optimal mean sojourn time in many cases, with the hope that simplicity will enable future analytical results despite the challenges of inexact inputs.

Significance. If the simulation outcomes hold under representative conditions, the result would be significant for practical systems: it identifies a simple, low-complexity policy that retains much of the benefit of size-based scheduling even with estimation errors, potentially improving response time and fairness without requiring the implementation overhead of more elaborate error-robust schedulers.

major comments (2)
  1. [Abstract] Abstract: the central claim that SPT 'performs comparably to the best known algorithms in the presence of errors' and yields 'near-optimal performance in many cases' rests entirely on simulation; however, the abstract (and thus the load-bearing evidence) provides no description of the error model used to generate inexact sizes, the workload distributions or traces, the number of runs, or any statistical significance tests, making it impossible to evaluate whether the chosen models are representative.
  2. [Abstract] Abstract: the statement that 'simulation-based studies show that several size-based algorithm are severely impacted by job estimation errors' is used to motivate the work, but no quantitative comparison metrics, specific competing algorithms, or performance deltas are supplied to ground the subsequent claim of SPT comparability.
minor comments (1)
  1. [Abstract] The abstract contains a subject-verb agreement error ('several size-based algorithm are' should read 'algorithms are').

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address the two major comments on the abstract below, agreeing that additional context on the simulation setup would improve clarity. We propose targeted revisions to the abstract while preserving its conciseness.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that SPT 'performs comparably to the best known algorithms in the presence of errors' and yields 'near-optimal performance in many cases' rests entirely on simulation; however, the abstract (and thus the load-bearing evidence) provides no description of the error model used to generate inexact sizes, the workload distributions or traces, the number of runs, or any statistical significance tests, making it impossible to evaluate whether the chosen models are representative.

    Authors: We agree that the abstract would benefit from a brief mention of key simulation parameters to support the claims. The full experimental methodology, including the multiplicative log-normal error model, synthetic and trace-based workloads, multiple runs, and averaging of results, is detailed in Sections 4 and 5. We will revise the abstract to concisely reference the error model, workload types, and simulation repetitions, enabling better assessment of representativeness without substantially increasing length. revision: yes

  2. Referee: [Abstract] Abstract: the statement that 'simulation-based studies show that several size-based algorithm are severely impacted by job estimation errors' is used to motivate the work, but no quantitative comparison metrics, specific competing algorithms, or performance deltas are supplied to ground the subsequent claim of SPT comparability.

    Authors: The motivational statement references prior literature on the sensitivity of policies such as SRPT to estimation errors. To better ground the claim, we will revise the abstract to include a short example of performance impact (e.g., SRPT's degradation under inexact sizes) drawn from established results or our simulations. This will provide quantitative grounding while remaining within abstract constraints. revision: yes

Circularity Check

0 steps flagged

No circularity: simulation study with no derivations or self-referential structure

full rationale

The paper is a simulation-based comparison of scheduling policies under inexact job sizes. The abstract and description explicitly state that analytical results are challenging and evaluation proceeds via simulation. No equations, parameter fits, uniqueness theorems, ansatzes, or self-citations are invoked as load-bearing steps in any derivation chain. The central claim (SPT performs comparably) is presented as an empirical outcome under the chosen error models and workloads, with no reduction of predictions to inputs by construction. This matches the default expectation of no significant circularity for non-derivational work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The work is a simulation study; the abstract introduces no free parameters, mathematical axioms, or new postulated entities.

pith-pipeline@v0.9.0 · 5786 in / 974 out tokens · 20602 ms · 2026-05-24T23:16:08.764488+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

36 extracted references · 36 canonical work pages · 1 internal anchor

  1. [1]

    The queue M/G/1 with the shortest remaining processing time discipline,

    L. E. Schrage and L. W. Miller, “The queue M/G/1 with the shortest remaining processing time discipline,” Operations Research, vol. 14, no. 4, pp. 670–684, 1966

    work page 1966

  2. [2]

    Fairness and efficiency in web server protocols,

    E. J. Friedman and S. G. Henderson, “Fairness and efficiency in web server protocols,” in SIGMETRICS PER, vol. 31. ACM, 2003, pp. 229–237

    work page 2003

  3. [3]

    PSBS: Practical size-based scheduling,

    M. Dell’Amico, D. Carra, and P. Michiardi, “PSBS: Practical size-based scheduling,” IEEE Transactions on Computers, vol. 65, no. 7, pp. 2199–2212, 2016

    work page 2016

  4. [4]

    Size-based schedul- ing policies with inaccurate scheduling information,

    D. Lu, H. Sheng, and P. Dinda, “Size-based schedul- ing policies with inaccurate scheduling information,” in MASCOTS. IEEE, 2004, pp. 31–38

    work page 2004

  5. [5]

    Scheduling jobs with estimation errors for multi-server systems,

    R. Mailach and D. G. Down, “Scheduling jobs with estimation errors for multi-server systems,” in Teletraffic Congress (ITC 29), 2017 29th International , vol. 1. IEEE, 2017, pp. 10–18

    work page 2017

  6. [6]

    A Simulator for Data-Intensive Job Scheduling

    M. Dell’Amico, “A simulator for data-intensive job scheduling,” arXiv, Tech. Rep. arXiv:1306.6023, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  7. [7]

    Analysis of LAS scheduling for job size distributions with high variance,

    I. A. Rai, G. Urvoy-Keller, and E. W. Biersack, “Analysis of LAS scheduling for job size distributions with high variance,” in SIGMETRICS PER, vol. 31, no. 1. ACM, 2003, pp. 218–228

    work page 2003

  8. [8]

    Kleinrock, Queueing systems, Volume II: Computer Applications

    L. Kleinrock, Queueing systems, Volume II: Computer Applications. Wiley Interscience, 1976

    work page 1976

  9. [9]

    Scheduling flows with unknown sizes: Approximate analysis,

    L. Guo and I. Matta, “Scheduling flows with unknown sizes: Approximate analysis,” in SIGMETRICS PER , vol. 30. ACM, 2002, pp. 276–277

    work page 2002

  10. [10]

    Revisiting size-based scheduling with estimated job sizes,

    M. Dell’Amico, D. Carra, M. Pastorelli, and P. Michiardi, “Revisiting size-based scheduling with estimated job sizes,” in MASCOTS. IEEE, 2014

    work page 2014

  11. [11]

    Scheduling despite inexact job-size information,

    A. Wierman and M. Nuyens, “Scheduling despite inexact job-size information,” in SIGMETRICS PER , vol. 36. ACM, 2008, pp. 25–36

    work page 2008

  12. [12]

    New Schedul- ing Policy For Estimation Of Stationary Performance Characteristics In Single Server Queues With Inaccurate Job Size Information

    L. Meykhanadzhyan and R. Razumchik, “New Schedul- ing Policy For Estimation Of Stationary Performance Characteristics In Single Server Queues With Inaccurate Job Size Information.” ECMS, vol. 2016, pp. 710–716, 2016

    work page 2016

  13. [13]

    Estimating mean sojourn time in the processor sharing M / G / 1 queue with inaccurate job size information,

    I. Horv ´ath, R. Razumchik, and M. Telek, “Estimating mean sojourn time in the processor sharing M / G / 1 queue with inaccurate job size information,” Tech. Rep., 2017. [Online]. Available: http://webspn.hit.bme. hu/∼telek/cikkek/razu17b.pdf

    work page 2017

  14. [14]

    Bounding Moments of Sojourn Time in M/G/1 FCFS Queue with Inaccurate Job Size Infor- mation and Additive Error: Some Observations from Numerical Experiments,

    T. A. Milovanova, L. A. Meykhanadzhyan, and R. V . Razumchik, “Bounding Moments of Sojourn Time in M/G/1 FCFS Queue with Inaccurate Job Size Infor- mation and Additive Error: Some Observations from Numerical Experiments,” 2018

    work page 2018

  15. [15]

    FLEX: A slot allo- cation scheduling optimizer for MapReduce workloads,

    J. Wolf, D. Rajan, K. Hildrum, R. Khandekar, V . Kumar, S. Parekh, K.-L. Wu, and A. Balmin, “FLEX: A slot allo- cation scheduling optimizer for MapReduce workloads,” Middleware, pp. 1–20, 2010

    work page 2010

  16. [16]

    HFSP: size-based scheduling for Hadoop,

    M. Pastorelli, A. Barbuzzi, D. Carra, M. Dell’Amico, and P. Michiardi, “HFSP: size-based scheduling for Hadoop,” in BIGDATA. IEEE, 2013, pp. 51–59

    work page 2013

  17. [17]

    Web servers under overload: How scheduling can help,

    B. Schroeder and M. Harchol-Balter, “Web servers under overload: How scheduling can help,” ACM TOIT, vol. 6, no. 1, pp. 20–52, 2006

    work page 2006

  18. [18]

    Query size estimation by adaptive sampling,

    R. J. Lipton and J. F. Naughton, “Query size estimation by adaptive sampling,” Journal of Computer and System Sciences, vol. 51, pp. 18–25, 1995

    work page 1995

  19. [19]

    ARIA: automatic resource inference and allocation for MapRe- duce environments,

    A. Verma, L. Cherkasova, and R. H. Campbell, “ARIA: automatic resource inference and allocation for MapRe- duce environments,” in ICAC, 2011, pp. 235–244

    work page 2011

  20. [20]

    Re-optimizing data-parallel computing,

    S. Agarwal, S. Kandula, N. Bruno, M.-C. Wu, I. Stoica, and J. Zhou, “Re-optimizing data-parallel computing,” in NSDI. USENIX, 2012, pp. 21–21

    work page 2012

  21. [21]

    Same queries, different data: Can we predict runtime performance?

    A. D. Popescu, V . Ercegovac, A. Balmin, M. Branco, and A. Ailamaki, “Same queries, different data: Can we predict runtime performance?” in ICDEW. IEEE, 2012, pp. 275–280

    work page 2012

  22. [22]

    Optimus: an efficient dynamic resource scheduler for deep learning clusters,

    Y . Peng, Y . Bao, Y . Chen, C. Wu, and C. Guo, “Optimus: an efficient dynamic resource scheduler for deep learning clusters,” in EuroSys, 2018

    work page 2018

  23. [23]

    Can “very noisy

    S. Emadi, R. Ibrahim, and S. Kesavan, “Can “very noisy” information go a long way? an exploratory analysis of personalized scheduling in service systems,” Working paper, Tech. Rep., 2019

    work page 2019

  24. [24]

    Kleinrock, Queueing systems

    L. Kleinrock, Queueing systems. Volume I: Theory. Wi- ley Interscience, 1975

    work page 1975

  25. [25]

    E. G. Coffman and P. J. Denning, Operating systems theory. Prentice-Hall, 1973

    work page 1973

  26. [26]

    Processor-sharing queues: Some progress in analysis,

    S. F. Yashkov, “Processor-sharing queues: Some progress in analysis,” Queueing systems , vol. 2, no. 1, pp. 1–17, 1987

    work page 1987

  27. [27]

    Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful Departures,

    R. Righter and J. G. Shanthikumar, “Scheduling Multiclass Single Server Queueing Systems to Stochastically Maximize the Number of Successful Departures,” Probability in the Engineering and Informational Sciences , vol. 3, no. 3, pp. 323–333, Jul. 1989. [Online]. Available: https://www.cambridge.org/core/journals/probability- in-the-engineering-and-informa...

    work page 1989

  28. [28]

    Adaptive and scalable comparison scheduling,

    P. R. Jelenkovic, X. Kang, and J. Tan, “Adaptive and scalable comparison scheduling,” in ACM SIGMETRICS Performance Evaluation Review, vol. 35, no. 1. ACM, 2007, pp. 215–226

    work page 2007

  29. [29]

    Classifying scheduling policies with respect to unfairness in an M/GI/1,

    A. Wierman and M. Harchol-Balter, “Classifying scheduling policies with respect to unfairness in an M/GI/1,” in ACM SIGMETRICS Performance Evaluation Review, vol. 31. ACM, 2003, pp. 238–249

    work page 2003

  30. [30]

    Computer schedul- ing methods and their countermeasures,

    E. G. Coffman Jr and L. Kleinrock, “Computer schedul- ing methods and their countermeasures,” in Proceedings of the April 30–May 2, 1968, spring joint computer conference. ACM, 1968, pp. 11–21

    work page 1968

  31. [31]

    D. R. Cox and W. Smith, Queues. CRC Press, 1991, vol. 2

    work page 1991

  32. [32]

    Fairness and scheduling in single server queues,

    A. Wierman, “Fairness and scheduling in single server queues,” Surveys in Operations Research and Manage- ment Science, vol. 16, no. 1, pp. 39–48, 2011

    work page 2011

  33. [33]

    Fairness and classifications,

    ——, “Fairness and classifications,” ACM SIGMETRICS Performance Evaluation Review, vol. 34, no. 4, pp. 4–12, 2007

    work page 2007

  34. [34]

    Interactive analytical processing in big data systems: A cross-industry study of MapReduce workloads,

    Y . Chen, S. Alspaugh, and R. Katz, “Interactive analytical processing in big data systems: A cross-industry study of MapReduce workloads,” PVLDB, vol. 5, no. 12, pp. 1802–1813, 2012

    work page 2012

  35. [35]

    The case for srpt scheduling in web servers,

    M. Harchol-Balter, M. Crovella, and S. Park, “The case for srpt scheduling in web servers,” Technical Re- port MIT-LCS-TR-767, MIT Lab for Computer Science, Tech. Rep., 1998

    work page 1998

  36. [36]

    Analysis of SRPT scheduling: Investigating unfairness,

    N. Bansal and M. Harchol-Balter, “Analysis of SRPT scheduling: Investigating unfairness,” SIGMETRICS Per- form. Eval. Rev., vol. 29, pp. 279–290, Jun. 2001

    work page 2001