Pith. sign in

REVIEW 3 major objections 5 minor 31 references

Capacity Planning and Scheduling for Jobs with Uncertainty in Resource Usage and Duration

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Pair sampling over each job's historical duration and CPU-usage records, embedded in a constraint program, produces schedules with up to 41.6% lower estimated peak CPU usage than manual scheduling while keeping jobs within seconds of…

desk verdict A genuine SAA-based scheduling contribution with an honest write-up, but the headline peak-reduction numbers are in-sample and the evaluation protocol needs clarification. read the letter →

arxiv 2507.01225 v2 pith:FJFAH6FS submitted 2025-07-01 cs.DC cs.AI

Sunandita Patra , Mehtab Pathan , Mahmoud Mahfouz , Parisa Zehtabi , Wided Ouaja , Daniele Magazzeni , Manuela Veloso This is my paper · ORCID
classification cs.DCcs.AI MSC 90B3590B36
keywords capacityplanningjobschedulingunderuncertaintysampleaverageapproximationconstraintprogrammingcumulativepeakCPUusagegridcomputing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Organizations that run thousands of compute jobs on their own servers typically pay for capacity in proportion to the peak number of CPU cores in use at any moment. This paper argues that capacity planning and job scheduling should be solved together, because when each job starts determines how high that peak is. Its proposed scheduler, COSPiS (Capacity Optimization and Scheduling with Pair Sampling), samples pairs of historical duration and CPU-usage values for every job and uses constraint programming to choose start times that keep the worst-case peak low. The paper reports up to 41.6% lower estimated peak CPU usage than the manual schedules currently in production, with no capacity under-estimation on the 44 real problems tested and deadline delays of only a few seconds. If the claim holds, the same schedule would cut infrastructure cost and remove the risk that extra CPUs are unavailable when a job needs more than planned.

What carries the argument

The engine of the method is pair sampling inside a constraint program. Each job's history supplies $K = 25$ pairs $(d_{jk}, r_{jk})$ of duration and CPU usage; the constraint program then picks start times $s_j$ and a peak level $p$ so that for every sample $k$, the cumulative constraint — the requirement that at every time point the cores used by running jobs stay at or below $p_k$ — is satisfied. The tolerance parameter $\alpha = 0.4$ caps how many samples may be ignored for deadline and dependency constraints, converting rare historical outliers from plan-breakers into a tunable risk allowance. The same machinery run with a single deterministic estimate per job (median, mode, 75th percentile, or maximum) is what the paper contrasts against COSPiS: point estimates cannot represent the spread of outcomes, so they either under-provision or over-provision.

What would settle it

Take the same 44 problems, hide the execution records of volatile trading days, and check whether a COSPiS schedule built from the remaining history keeps its predicted peak above what actually happened on those hidden days; if the capacity under-estimation error rises above 0% or deadline delays grow from seconds to minutes, the reliability claim fails. A laboratory version would plan from one distribution and realize jobs from a shifted one (for example, durations and CPU usage inflated by 50%) and measure how often the realized peak breaks the planned capacity.

Watch

Extended reading notes

Core claim

The paper's central claim is that a scheduler can handle uncertainty in both a job's running time and its CPU-core demand at once, and that doing so beats methods that collapse either dimension to a single number. COSPiS draws $K = 25$ pairs of (duration, CPU usage) from each job's recorded history and builds a constraint program in which the start times $s_j$ and a peak variable $p$ must satisfy a cumulative constraint for every sample, so that at no time in any sample do the running jobs exceed the peak; a tolerance parameter $\alpha = 0.4$ allows a bounded fraction of samples to violate deadline and dependency constraints, which keeps rare historical spikes from inflating the plan. The objective is to minimize the largest peak over all samples, and the resulting schedule is what the organization would execute and buy capacity for. On 44 real capacity-planning problems of 7 to 348 jobs each, the paper reports up to 41.6% estimated peak reduction versus manual scheduling, a capacity under-estimation error of 0%, and deadline violations of only a few seconds, with the alternative estimators (median, mode, 75th percentile, max) either under-estimating capacity badly or over-reserving it.

Load-bearing premise

The claim rests on the assumption that each job's future duration and CPU usage are independent draws from the same historical records used to build the schedule, so on a day whose market conditions differ from everything in that history, the true peak could exceed the predicted capacity.

Editorial extensions

If this is right

  • Peak reduction is a direct cost line: with billing proportional to peak cores, a 41.6% lower estimated peak means proportionally lower capacity spend on the on-prem grid.
  • Schedules produced from paired samples keep capacity under-estimation at zero, so partitions should stop needing to borrow idle CPUs from each other mid-day, removing the ripple of deadline breaches that borrowing causes.
  • Because COSPiS converges within the 15-minute solver budget on problems up to several hundred jobs, while the MILP variant times out beyond 50 jobs, the pair-sampling model is the one the authors put forward for daily production scheduling.
  • Deadline violations of only a few seconds across all approaches indicate the test problems carry comfortable deadline margins; with tighter deadlines, the same models would likely show wider separation in quality of service.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The tolerance parameter $\alpha$ is an explicit risk dial: a partition with hard regulatory deadlines could lower $\alpha$ and trade peak reduction for stronger guarantees, without changing the model.
  • Nothing ties the pair-sampling scheme to CPU cores; the same cumulative-constraint model applies to GPU, memory, or network bandwidth, since the peak objective treats any resource uniformly.
  • The historical-sample premise means the method may understate the true peak on days when a market event shifts the joint distribution of durations and CPU usage; a market-conditioned or distributionally robust variant is the natural stress test.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies capacity planning and job scheduling for on-premises grid computing, where each job has stochastic duration and CPU usage and must meet a deadline and dependency constraints. The objective is to minimize the predicted peak CPU usage while providing a capacity estimate. The authors propose three approximate approaches: a constraint-programming model with deterministic estimators (Det), a mixed-integer linear programming model with deterministic estimators (MILP), and COSPiS, a constraint-programming model using pair sampling under a Sample Average Approximation (SAA). The approaches are evaluated on 44 real problems from the authors' organization and on synthetic data, using metrics of peak reduction, capacity under-estimation error, capacity over-estimation error, and degree of deadline violation. The reported best result is a 41.6% estimated peak reduction for COSPiS compared with manual scheduling, with zero capacity under-estimation error and deadline violations of only a few seconds.

Significance. If the reported results hold, the work addresses a practically important gap: most scheduling literature handles duration uncertainty but not uncertainty in resource usage, and most methods minimize makespan rather than peak resource usage. The formulations are explicit, the dataset is real, and the authors include a comparison with an adapted SAA baseline. The central weakness is that the evaluation appears to be in-sample: realized peaks are generated from the same historical data used to construct the COSPiS samples, and the hyperparameters are tuned on a subset using the very metrics that are later reported on the full dataset. These issues do not invalidate the approach, but they do mean the headline capacity-reliability claims are not yet established for the distribution-shift and correlated-demand scenarios that motivate the paper. With out-of-sample or distribution-shift validation, the contribution could be significant for practitioners in stochastic resource-constrained scheduling.

major comments (3)
  1. [Sections 5.1-5.3 and 7] The evaluation computes the 'observed peak' and the capacity under-estimation error from simulated realizations, but the paper never states that the test realizations are drawn from held-out days or from distributions different from the historical data used to build the K pair samples in Eq. (5). Because Section 1 motivates the method by distribution shifts such as earnings-day spikes and Section 7 explicitly defers robustness testing to future work, the headline result of 41.6% peak reduction with 0% under-estimation error is not established for the very conditions that motivate the method. Please specify the realization mechanism in Section 5.2 and add an out-of-sample or distribution-shift experiment; otherwise the capacity-reliability claim is unsupported.
  2. [Section 5.3.1 and Figures 8-10] The hyperparameters K=25 and alpha=0.4 are selected by evaluating exactly the four reported metrics on a subset of four problems (Section 5.3.1), and the same metrics are then reported on the full 44-problem dataset in Figures 8-10. This in-sample selection can inflate the reported peak reduction and under-estimation accuracy. Please either tune on a separate validation subset and report test metrics, or show a sensitivity analysis demonstrating that the qualitative ranking is robust to the choice of K and alpha across the full dataset.
  3. [Section 4.2, Eqs. (6)-(8), and Figure 10] The model allows up to K alpha samples to violate deadline and dependency constraints, with alpha=0.4 in the experiments, yet the paper asserts that schedules still meet real-world deadlines with only a few seconds of violation. No probabilistic argument or out-of-sample test connects the alpha-tolerance to the realized deadline violation under the distribution shifts discussed in Section 1. Moreover, Eq. (6) applies the single violation variable v_k to all jobs in sample k, so ignoring one sample's deadline violation also relaxes the same constraint for every other job in that sample; the effect of this coupling on schedule quality is not discussed. Please provide either a concentration bound on violations or an experiment with realized durations drawn from the upper tail of the historical distributions.
minor comments (5)
  1. [Section 5.2] State explicitly whether the 50 runs are repeated executions on real infrastructure or Monte Carlo simulations from historical distributions; the current wording ('to account for uncertainty') is ambiguous and affects interpretation of Figures 8-10.
  2. [Figure 8 and Section 5.3.2] MILP:P50 times out for problems with more than 50 jobs, so its box in the full-dataset plot is based only on smaller feasible instances; indicate the sample size or mark this limitation in the figure.
  3. [Section 4.2, Eq. (5), and Table 2] With historic record sizes as small as 1 (Table 2), the K=25 pair samples are necessarily drawn with replacement; state the sampling policy explicitly and whether duplicate samples are retained.
  4. [Section 5.3.1, Figure 11] The color scale for the hyperparameter heatmaps is not calibrated or described numerically; report the underlying metric values in the text or a table so the selection of (K, alpha) = (25, 0.4) is reproducible.
  5. [Section 2, Table 1] The related-work table uses checkmarks ambiguously: it does not distinguish between works that handle uncertainty in duration only versus resource usage only, and the columns 'Duration Uncertainty' and 'Resource Usage' are not defined in the caption. Consider replacing checkmarks with explicit labels.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: COSPiS's peak estimate is an optimization variable over sampled scenarios, and the reported metrics compare it to independently realized peaks; hyperparameter selection is a validation concern, not a circular reduction.

full rationale

The paper's derivation chain is self-contained. COSPiS defines the estimated peak p as the minimized maximum over K sampled duration/CPU pairs (Eq. 9 and objective min max{p_k}), and the evaluation metrics compare p to a separately realized peak p_real (Section 5.1). There is no equation in which p_real is forced to equal or bound p by construction; the only reported identity is the standard SAA constraint that each sample's cumulative usage is bounded by its p_k, which is the optimization model itself, not a prediction. No load-bearing self-citation appears: SORU [28] and RSOME [6] are external baselines/tools, not prior work by these authors, and no uniqueness claim is imported from the authors' own papers. The K and alpha hyperparameters are selected on a subset of four problems using the same four metrics later reported (Section 5.3.1), which is a mild in-sample selection concern, and Section 7 explicitly defers robustness to distribution shift to future work; however, neither makes the headline 41.6% peak reduction equivalent to an input or to a fitted constant. The 0% under-estimation error is a plausible consequence of p being a max over 25 samples, not a definitional identity. The paper therefore shows no significant circularity.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central method COSPiS introduces two tunable parameters (sample count K and tolerance alpha) that are fitted on a small subset of the data. The main domain assumptions are that historical data distributions are stationary and independent across jobs, and that peak CPU usage is the right cost proxy. No new physical or conceptual entities are introduced.

free parameters (2)
  • K (number of pair samples) = 25
    Number of (duration, CPU usage) pairs sampled per job in COSPiS; chosen via hyperparameter study on four problems (Section 5.3.1).
  • alpha (tolerance) = 0.4
    Maximum fraction of samples allowed to violate deadline constraints in COSPiS; chosen via hyperparameter study on four problems (Section 5.3.1).
assumptions (3)
  • domain assumption Historical job durations and CPU usage are representative of future executions, and each job's future (duration, CPU) pair is drawn independently from that history.
    COSPiS samples K pairs from historical data for each job (Section 4.2) and evaluation assumes these samples reflect future realizations; distribution shifts or cross-job correlation would invalidate the capacity estimates.
  • domain assumption The objective is correctly captured by minimizing the peak number of concurrently used CPU cores across the day, with non-preemptive jobs and a cumulative resource bound at every time point.
    Section 3.2 defines COS with peak resource usage p as the objective and Equation (4) uses the cumulative constraint; if the cost model or preemption assumptions differ, the optimization target is mis-specified.
  • ad hoc to paper Allowing a fraction (alpha) of SAA samples to violate deadline and dependency constraints still yields schedules that meet real-world deadlines with high probability.
    Equation (8) bounds the number of violated samples by K*alpha; the paper assumes this relaxation is benign based on empirical results, but no theoretical bound is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Capacity Planning and Scheduling for Jobs with Uncertainty in Resource Usage and Duration." pith.science (2026). https://pith.science/paper/FJFAH6FS

@misc{pith2026250701225,
  author       = {Pith},
  title        = {Pith review of: Capacity Planning and Scheduling for Jobs with Uncertainty in Resource Usage and Duration},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FJFAH6FS}},
  note         = {Machine review of arXiv:2507.01225}
}
read the original abstract

Organizations around the world schedule jobs (programs) regularly to perform various tasks dictated by their end users. With the major movement towards using a cloud computing infrastructure, our organization follows a hybrid approach with both cloud and on-prem servers. The objective of this work is to perform capacity planning, i.e., estimate resource requirements, and job scheduling for on-prem grid computing environments. A key contribution of our approach is handling uncertainty in both resource usage and duration of the jobs, a critical aspect in the finance industry where stochastic market conditions significantly influence job characteristics. For capacity planning and scheduling, we simultaneously balance two conflicting objectives: (a) minimize resource usage, and (b) provide high quality-of-service to the end users by completing jobs by their requested deadlines. We propose approximate approaches using deterministic estimators and pair sampling-based constraint programming. Our best approach (pair sampling-based) achieves much lower peak resource usage compared to manual scheduling without compromising on the quality-of-service.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp 1070–1080

    Azar Y, Leonardi S, Touitou N (2021) Flow time scheduling with uncertain pro- cessing time. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp 1070–1080

    work page 2021

  2. [2]

    IEEE Transactions on Automation Science and Engineering 33

    Bao Z, Chen L, Qiu K (2022) A robust optimization approach for the resource investment problem of an aircraft final assembly line. IEEE Transactions on Automation Science and Engineering 33

    work page 2022

  3. [3]

    PhD thesis

    Bidot J (2005) A general framework integrating techniques for scheduling under uncertainty. PhD thesis

    work page 2005

  4. [4]

    Journal of Scheduling 12(3):315–344

    Bidot J, Vidal T, Laborie P, et al (2009) A theoretic and practical framework for scheduling in a stochastic environment. Journal of Scheduling 12(3):315–344

    work page 2009

  5. [5]

    In: 2016 IEEE 9th International Conference on Cloud Computing (CLOUD), IEEE, pp 577–584

    Chen H, Zhu X, Qiu D, et al (2016) Uncertainty-aware real-time workflow schedul- ing in the cloud. In: 2016 IEEE 9th International Conference on Cloud Computing (CLOUD), IEEE, pp 577–584

    work page 2016

  6. [6]

    Management Science 66(8):3329–3339

    Chen Z, Sim M, Xiong P (2020) Robust stochastic optimization made easy with rsome. Management Science 66(8):3329–3339

    work page 2020

  7. [7]

    Journal of Scheduling 18(3):263– 273

    Creemers S (2015) Minimizing the expected makespan of a project with stochastic activity durations under resource constraints. Journal of Scheduling 18(3):263– 273

    work page 2015

  8. [8]

    Available at SSRN 2873356

    Creemers S (2016) The preemptive stochastic resource-constrained project scheduling problem: an efficient globally optimal solution procedure. Available at SSRN 2873356

    work page 2016

Show all 31 references
  1. [9]

    Or Spectrum 42(4):901–933

    Gerhards P (2020) The multi-mode resource investment problem: a benchmark library and a computational study of lower and upper bounds. Or Spectrum 42(4):901–933

    2020

  2. [10]

    https://github.com/google/or-tools

    Google (2022) Google optimization tools. https://github.com/google/or-tools

    2022

  3. [11]

    In: Pro- ceedings of the International Conference on Automated Planning and Scheduling, pp 119–123

    Gopalakrishnan S, Borrajo D (2022) Assignment and prioritization of tasks with uncertain durations for satisfying makespans in decentralized execution. In: Pro- ceedings of the International Conference on Automated Planning and Scheduling, pp 119–123

    2022

  4. [12]

    Journal of project management 3(2):55–88

    Habibi F, Barzinpour F, Sadjadi S (2018) Resource-constrained project scheduling problem: review of past and recent developments. Journal of project management 3(2):55–88

    2018

  5. [13]

    European Journal of operational research 297(1):1–14

    Hartmann S, Briskorn D (2022) An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of operational research 297(1):1–14

    2022

  6. [14]

    Journal of the Operational Research Society 56(4):406–413

    Hsu CC, Kim DS (2005) A new heuristic for the multi-mode resource investment problem. Journal of the Operational Research Society 56(4):406–413

    2005

  7. [15]

    The Journal of Supercomputing 79(7):7484–7512

    Li Z, Yu H, Fan G (2023) Cost-effective approaches for deadline-constrained workflow scheduling in clouds. The Journal of Supercomputing 79(7):7484–7512

    2023

  8. [16]

    IEEE Transactions on Cloud Computing 34 9(03):1180–1194

    Liu J, Ren J, Dai W, et al (2021) Online multi-workflow scheduling under uncer- tain task execution time in iaas clouds. IEEE Transactions on Cloud Computing 34 9(03):1180–1194

    2021

  9. [17]

    International journal of machine learning and cybernetics 7(4):613–621

    Ma W, Che Y, Huang H, et al (2016) Resource-constrained project scheduling problem with uncertain durations and renewable resources. International journal of machine learning and cybernetics 7(4):613–621

    2016

  10. [18]

    In: Pro- ceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, pp 66–75

    Malewicz G (2005) Parallel scheduling of complex dags under uncertainty. In: Pro- ceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, pp 66–75

    2005

  11. [19]

    Discrete applied mathematics 6(2):173–191

    Morihara I, Ibaraki T, Hasegawa T (1983) Bin packing and multiproces- sor scheduling problems with side constraint on job types. Discrete applied mathematics 6(2):173–191

    1983

  12. [20]

    Springer

    Neumann K, Schwindt C, Zimmermann J (2002) Project scheduling with time windows and scarce resources: temporal and resource-constrained project scheduling with regular and nonregular objective functions, vol 508. Springer

    2002

  13. [21]

    In: 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE, pp 453–460

    Oddi A, Rasconi R, Cesta A (2015) A multi-objective large neighborhood search methodology for scheduling problems with energy costs. In: 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE, pp 453–460

    2015

  14. [22]

    ARPN Journal of Engineering and Applied Sciences 8(1):26–32

    Radhamani A, Baburaj E (2013) Performance efficient heterogeneous multi core scheduling strategy based on genetic algorithm. ARPN Journal of Engineering and Applied Sciences 8(1):26–32

    2013

  15. [23]

    Journal of Scheduling 21(3):349–365

    Rostami S, Creemers S, Leus R (2018) New strategies for stochastic resource- constrained project scheduling. Journal of Scheduling 21(3):349–365

    2018

  16. [24]

    Constraints 16(3):250–282

    Schutt A, Feydy T, Stuckey PJ, et al (2011) Explaining the cumulative propaga- tor. Constraints 16(3):250–282

    2011

  17. [25]

    European Journal of Operational Research 181(1):86–101

    Shadrokh S, Kianfar F (2007) A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty. European Journal of Operational Research 181(1):86–101

    2007

  18. [26]

    Journal of Artificial Intelligence Research 64:385–427

    Song W, Kang D, Zhang J, et al (2019) A sampling approach for proactive project scheduling under generalized time-dependent workability uncertainty. Journal of Artificial Intelligence Research 64:385–427

    2019

  19. [27]

    Journal of Scheduling 21(2):251–267

    Tran TT, Padmanabhan M, Zhang PY, et al (2018) Multi-stage resource-aware scheduling for data centers with heterogeneous servers. Journal of Scheduling 21(2):251–267

    2018

  20. [28]

    In: Proceedings of the AAAI Conference on 35 Artificial Intelligence

    Varakantham P, Fu N, Lau HC (2016) A proactive sampling approach to project scheduling under uncertainty. In: Proceedings of the AAAI Conference on 35 Artificial Intelligence

    2016

  21. [29]

    IEEE Transactions on Evolutionary Computation 18(5):742–763

    Xiong J, Liu J, Chen Y, et al (2013) A knowledge-based evolutionary multiob- jective approach for stochastic extended resource investment project scheduling problems. IEEE Transactions on Evolutionary Computation 18(5):742–763

    2013

  22. [30]

    Journal of Systems and Software 184:111123

    Yin L, Zhou J, Sun J (2022) A stochastic algorithm for scheduling bag-of-tasks applications on hybrid clouds under task duration variations. Journal of Systems and Software 184:111123

    2022

  23. [31]

    Zhou Y, Miao J, Yan B, et al (2021) Stochastic resource-constrained project scheduling problem with time varying weather conditions and an improved esti- mation of distribution algorithm. Computers & Industrial Engineering 157:107322 36 Table of Symbols Symbol Description COS ...

    2021

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.