Source-linked AI summary
Scheduling with Predictions and the Price of Misprediction
Michael Mitzenmacher
TL;DR
When service times are unknown but predicted, the paper derives queue-performance formulae for scheduling strategies using predicted times and introduces the price of misprediction. Simulations show close agreement between the formulae and measured performance, with benefits from prediction persisting at high loads.
Problem
Traditional scheduling analyses assume service times are known, while this paper addresses queueing systems where only predicted service times are available.
Source: §I · p. 1Method
The paper derives expected time-in-system formulae for predicted-time scheduling strategies using a joint density of actual and predicted service times, and defines the price of misprediction.
Source: §I · p. 1Results
SPJF and SPRPT formulae differ from their simulation results by less than 1%, and simulations report substantial gains over FIFO under high loads.
Source: §V · p. 9Takeaways & Limitations
The framework can estimate the price of misprediction or potential benefits of better prediction for single-queue scheduling systems.
Source: §VI · p. 10
Abstract
from arXiv · showhide
In many traditional job scheduling settings, it is assumed that one knows the time it will take for a job to complete service. In such cases, strategies such as shortest job first can be used to improve performance in terms of measures such as the average time a job waits in the system. We consider the setting where the service time is not known, but is predicted by for example a machine learning algorithm. Our main result is the derivation, under natural assumptions, of formulae for the performance of several strategies for queueing systems that use predictions for service times in order to schedule jobs. As part of our analysis, we suggest the framework of the "price of misprediction," which offers a measure of the cost of using predicted information.
I. INTRODUCTION
The paper extends queueing analysis to scheduling with predicted service times, deriving performance formulae and introducing the price of misprediction. It situates this framework among work on prediction-informed algorithms and scheduling with imperfect information.
I. INTRODUCTION
- The paper aims to bridge machine learning and traditional algorithm analysis, extending queueing models to settings with predictions and potentially other algorithmic problems.It frames the work as a general framework rather than a specific predictor.Source: §I · p. 1
- The framework models actual and predicted service times jointly and uses their density to derive queue-performance equations, without requiring the scheduler to know that distribution.The system observes only predicted service time when a job arrives.Source: §I · p. 1
- For predicted-time analogues SPJF and SPRPT, the paper derives expected time-in-system formulae and reports simulations suggesting weak predictions can perform well.SJF and SRPT minimize average time in the system under standard queueing assumptions.Source: §I · p. 1
- The price of misprediction measures the cost of replacing accurate service times with predictions for these scheduling strategies.The paper does not develop prediction methods; it analyzes performance for prediction systems matching its assumptions.Source: §I · p. 1
II. RELATED WORK
- Prior prediction-informed scheduling work studied fixed job collections and competitive ratios, while this paper analyzes predicted service times in queueing systems.Other related work addresses imperfect load information, threshold-based multiple queues, or adversarial noise in approximate service observations.Source: §II · p. 2
- The policies also fit the SOAP framework, but the paper derives its results from the original SJF and SRPT analyses.The authors describe that derivation as more instructive and straightforward.Source: §II · p. 2
A. A Simple Example
A two-type job example compares optimal ordering, random ordering, and shortest-predicted-job-first under classification errors. It uses the ratio of imperfect- to perfect-information performance to express the price of misprediction.
A. A Simple Example
- With short and long jobs, shortest job first minimizes average waiting time when true job types are known.Waiting time is time in the system before service begins.Source: A. A Simple Example · p. 2
- For jobs with no type information, random ordering yields an expected waiting time computed by averaging each job’s expected wait.The analysis generally uses asymptotic expressions and calculates each job’s wait from the other short and long jobs.Source: A. A Simple Example · pp. 2–3
- Under shortest-predicted-job-first, short jobs are mislabeled long with probability p and long jobs short with probability q.The analysis conditions expected waiting time on whether each job is classified correctly or incorrectly.Source: A. A Simple Example · p. 3
- The predicted-ordering waiting-time expression differs additively from the optimal asymptotic expression by (p+q)(ℓ−s).The ratio depends specifically on the total error p+q.Source: A. A Simple Example · p. 3
- The price of misprediction is the ratio of a measure under predicted information to that measure under accurate information for the same algorithm.For this example, the measure is expected waiting time and the asymptotic ratio is denoted R.Source: A. A Simple Example · p. 3
B. General Predictions
The section develops waiting-time and misprediction-cost calculations for jobs with actual and predicted service times. Its exponential example yields a price of misprediction of 4/3, and the framework can help assess prediction value using the joint distribution of actual and predicted times.
B. General Predictions
- The price of misprediction can be computed numerically from g(x, y), the joint density of actual and predicted service times.The expected-waiting calculations compare the probability that another job has a smaller actual service time with the probability it has a smaller predicted time and the corresponding conditional actual service time.Source: B. General Predictions · p. 4
- A predictor whose exponential prediction mean equals the actual service time gives a 4/3 price of misprediction; sequential scheduling without information is twice as costly as full information.The example is not intended to match a real-world case; the authors say a predictor need only order most jobs correctly for this intuition to apply.Source: B. General Predictions · p. 4
- Empirical approximations of g can support estimates of misprediction cost and trade-offs between reduced waiting time and the cost of prediction methods.The authors note that g need not be known exactly if a good empirical approximation is available.Source: B. General Predictions · p. 4
- When predicted-time ordering also orders jobs by expected service time, that ordering is optimal for minimizing expected waiting time.The framework assumes a continuous, well-behaved density with necessary derivatives; the authors say it can be modified for point masses or other discontinuities.Source: B. General Predictions · p. 4
IV. SINGLE QUEUE MODELS
This section derives performance formulae for prediction-based variants of SJF and SRPT in single-queue systems, expressing their performance through the price of misprediction.
IV. SINGLE QUEUE MODELS
- The section derives performance formulae for prediction-based variants of shortest job first and shortest remaining processing time in single-queue systems.It begins by reviewing standard queue analysis, including jobs with priorities, before extending the methods to predictions.Source: §IV · p. 5
- The analysis expresses the strategies' performance as the price of misprediction.Source: §IV · p. 5
- The derivation reviews standard queue-analysis methods for priority systems before extending them to the prediction setting.Source: §IV · p. 5
A. Priority-based Systems
For Poisson arrivals with multiple job types, the section models predicted types using a misclassification matrix and derives an expected-waiting-time price of misprediction for priority scheduling.
A. Priority-based Systems
- For k job types with Poisson arrivals, the section orders priority classes by fixed service times or, more generally, by expected service times.Each type has an arrival rate; the general case allows a service-time distribution for each type.Source: A. Priority-based Systems · p. 5
- A matrix M models classification errors, with m_ij giving the probability that a true type i job is predicted as type j.Predicted-type arrival rates and service-time distributions are then used to analyze priority scheduling by predicted type.Source: A. Priority-based Systems · pp. 5–6
- The section derives an expression for the price of misprediction in expected waiting time when jobs are prioritized by predicted type.The analysis applies the standard priority-system formula to predicted types and sums over the possible types.Source: A. Priority-based Systems · p. 6
B. Shortest Job First
The section extends shortest-job-first analysis to shortest predicted job first (SPJF), deriving a waiting-time price of misprediction and describing related variants and evaluation scope.
B. Shortest Job First
- SPJF is expressed as a limiting case of priority analysis, paralleling how SJF arises from priorities based on service time.Source: B. Shortest Job First · p. 6
- The standard SJF waiting-time analysis supplies the baseline that the section generalizes to SPJF.For standard SJF, the cited setup considers the waiting time for a job with service time x in equilibrium.Source: B. Shortest Job First · p. 6
- Integrating waiting-time expressions over service time or predicted service time gives the price of misprediction for SPJF.The predicted-time formulation uses the joint density g(x, y) and assumes independently determined job service-time characteristics.Source: B. Shortest Job First · pp. 6–7
- For the exponential service-time and prediction example, the price expression has no simple closed form but can be evaluated numerically for a given λ.Source: B. Shortest Job First · p. 7
- The analysis can also extend to preemptive shortest predicted job first and to predicted distributions summarized by expected processing time.The preemptive variant allows preemption by a job with a shorter original predicted time; the latter approach is called shortest predicted expected processing time.Source: B. Shortest Job First · p. 7
C. Shortest Remaining Processing Time
The section extends SRPT analysis to predicted remaining processing times, deriving expressions for waiting, residence, and total time in the system. Its busy-period analysis accounts for jobs whose predicted remaining times fall below a threshold.
C. Shortest Remaining Processing Time
- SPRPT residence time accounts for preemptions as predicted remaining processing time falls toward zero, even when actual service remains.Once predicted remaining time reaches zero, the job cannot be preempted.Source: C. Shortest Remaining Processing Time · pp. 7–8
- Jobs already in service can also contribute when their predicted remaining times later cross below the threshold.The analysis includes jobs whose initial predicted time exceeds the threshold, while accounting for cases where they finish before reaching it.Source: C. Shortest Remaining Processing Time · p. 8
- The waiting-time derivation uses a busy period restricted to jobs with predicted remaining processing times below the focal job’s threshold.Its first two moments are computed through an equivalent FCFS busy period with specified initiating and additional job distributions.Source: C. Shortest Remaining Processing Time · p. 8
- The expected time in the system is obtained by averaging each job’s expected waiting plus residence time over its predicted service time.The corresponding equations can be used with standard SRPT equations to compute the price of misprediction.Source: C. Shortest Remaining Processing Time · p. 9
V. SIMULATION RESULTS
Simulations support the accuracy of the derived equations and show that predicted-time scheduling retains benefits under high load. Across the examined cases, performance degrades gracefully as prediction accuracy decreases.
V. SIMULATION RESULTS
- The simulations average results across 1,000 trials, each run for 1,000,000 time units, with the first 100,000 discarded to reduce startup bias.The reported setting uses Poisson arrivals, exponential service times with mean 1, and predicted times exponential with mean x conditional on actual time x.Source: §V · p. 9
- For SPRPT, equation results differ from simulations by less than 1%, despite aligning less closely than the SPJF equations.The authors attribute this to equation complexity and greater variability in time in the system.Source: §V · p. 9, Table II · p. 10
- Less than 1% difference separates SPJF equation results from simulations, while predicted-time performance remains close to full-information performance.Under high loads, gains over FIFO remain substantial; FIFO’s expected time in the system is 1/(1 − λ).Source: §V · p. 9, Table I · p. 10
- The reported simulations show performance degrades gracefully as α increases; each job with service time x receives a predicted time drawn uniformly over [(1 − α)x, (1 + α)x].When α = 0, predicted service time equals true service time.Source: §V · p. 10
VI. CONCLUSION
The paper generalizes single-queue scheduling analyses to predicted service times modeled by a joint distribution. It uses the resulting formulas to assess misprediction costs and identifies multiple-queue analysis as future work.
VI. CONCLUSION
- Exact performance formulas for single-queue scheduling are derived under probabilistic assumptions, including a joint distribution for actual and predicted service times.The formulas can be used to determine the price of misprediction or potential benefits of better prediction.Source: §VI · pp. 10–11
- Analysis of multiple-queue systems is left for future work, including strategies such as power of two choices and SITA.The authors note that workload division can make performance more variable and that additional techniques may be needed.Source: §VI · pp. 10–11
- At λ = 0.95, simulations show graceful performance degradation as prediction noise α increases for exponential and Weibull distributions.The predictions are uniform over [(1 − α)x, (1 + α)x], with α = 0 representing full information.Source: Figure 1 · p. 11
- The authors suggest extending prediction-based analysis to a broader range of scheduling and traditional algorithmic problems.Source: §VI · p. 11
APPENDIX I PROOF OF 4/3 PRICE OF MISPREDICTION FOR THE FINITE CASE
The finite-case appendix derives a 4/3 price of misprediction. A separate appendix develops a preemptive predicted-job analysis using steady-state waiting and residence times.
APPENDIX I PROOF OF 4/3 PRICE OF MISPREDICTION FOR THE FINITE CASE
- The finite-case calculation gives expected waiting time 1/3 with predictions and a 4/3 price of misprediction.The full-information expected waiting time is 1/4; the analysis reduces the expectation to a pair of jobs.Source: Appendix I · p. 13
APPENDIX II DERIVATION FOR PSPJF
- The PSPJF analysis treats residence time as a busy period involving jobs with predicted service times at most the focal job’s prediction.Its expected waiting time likewise includes only jobs with predicted service times at most that value.Source: APPENDIX II DERIVATION FOR PSPJF · pp. 13–14
- The appendix obtains expected time in the system by integrating expected waiting plus residence time over the predicted-service-time distribution.Source: APPENDIX II DERIVATION FOR PSPJF · pp. 13–14