{"id":"1cbfded0-1ef5-49d3-b93c-debe6d870a99","arxiv_id":"2507.01225","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A pair-sampling constraint-programming scheduler (COSPiS) reduces peak CPU usage in a financial grid by up to 41.6% compared to manual scheduling while handling uncertainty in both job duration and CPU use.","lead":"This paper designs three scheduling algorithms that plan computing capacity and start times for data-center jobs whose runtime and CPU needs vary unpredictably. The best one, COSPiS, is reported to cut peak CPU usage by up to 41.6% versus manual scheduling while keeping jobs near their deadlines.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The headline results are in-sample: the evaluation appears to generate 'realized' duration/CPU values from the same histories used to build COSPiS samples, so 0% under-estimation is not validated under the distribution shifts the paper itself motivates.","rationale":"The single most load-bearing concern is the evaluation protocol: the paper never establishes that the 'observed' peak CPU usage and deadline violations come from out-of-sample realizations. The reader's weakest assumption points at the same issue, and I agree with it. I sharpened it to a concrete in-sample artifact by noting that the same historical distributions appear to be used both for building COSPiS pair samples and for generating the 50 evaluation runs. This matters more than hyperparameter tuning or missing code/data because it directly determines whether the headline 0% under-estimation and 41.6% peak reduction are trustworthy. It is also not an ad hominem or a consensus disagreement: it is a testable protocol question. The proposed chronological backtest settles it. Since the reader already returned CONDITIONAL and this concern supports that verdict, no adjustment is needed.","tokens_in":19488,"tokens_out":7291,"duration_ms":100314,"concrete_test":"Chronological backtest: for each of the 44 problems/day d, build each job's history D_j, R_j only from days strictly before d, fit COSPiS with K=25, alpha=0.4, and record p_est and the schedule. Then compare p_est with the actually recorded duration/CPU pairs of day d (the day being scheduled), and compute the true peak, under-estimation error, and deadline violations. If under-estimation remains 0% and peak reduction remains near 41.6%, the concern is resolved; if under-estimation rises materially, the headline is an in-sample artifact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.2 says only that 50 runs were performed 'to account for uncertainty'; it never states that schedules were executed against held-out days or that realizations were drawn out-of-sample. Figures 8-10 label results 'observed peak' without specifying the realization mechanism. COSPiS builds K samples from each job's history (Eq. 5), so if the same history is then used to generate test realizations, the capacity-under-estimation metric is measured in-sample: the solver is essentially being tested on the data it saw. This is load-bearing because the paper's motivating scenario (Section 1) is that market events shift durations and CPU usage, and Section 7 explicitly defers robustness testing to future work. If a real earnings-day spike or correlated surge occurs, the estimated peak p can be exceeded; Section 5.1 states that such under-estimation carries X-times cost and may make extra CPUs unavailable. The central claim of 41.6% peak reduction with 0% under-estimation is therefore not yet established for the conditions that motivated the method.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19705,"tokens_out":6795,"duration_ms":68821,"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":[{"comment":"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.","section":"Sections 5.1-5.3 and 7"},{"comment":"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.","section":"Section 5.3.1 and Figures 8-10"},{"comment":"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.","section":"Section 4.2, Eqs. (6)-(8), and Figure 10"}],"minor_comments":[{"comment":"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.","section":"Section 5.2"},{"comment":"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.","section":"Figure 8 and Section 5.3.2"},{"comment":"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.","section":"Section 4.2, Eq. (5), and Table 2"},{"comment":"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.","section":"Section 5.3.1, Figure 11"},{"comment":"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.","section":"Section 2, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript reports an industry case study with a proprietary manual-scheduling baseline. The in-sample nature of the evaluation and the use of the same metrics for tuning and reporting are the main concerns; both can be addressed with a clear out-of-sample protocol. If the authors cannot provide such a protocol, the editor may wish to require that the capacity-reliability claims be softened to in-sample estimates."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2507.01225. It's a genuine, well-scoped contribution: the pair-sampling SAA formulation for peak-resource scheduling with uncertainty in both duration and CPU usage is a real extension of existing work, and the paper is refreshingly honest about its limits. The deterministic formulations and the comparison against a modified SORU are clearly presented, and the four metrics (peak reduction, under/over-estimation, deadline violation) are sensible. The synthetic-data section is a nice sanity check.\n\nThe soft spots are real but not lethal. The biggest one is the evaluation protocol. The paper says 50 runs \"to account for uncertainty\" but never states whether jobs were actually executed on the grid or simulated from the historical data. If, as I suspect, the \"observed\" peaks come from sampling the same historical distributions used to build the COSPiS samples, then the 0% under-estimation result is in-sample. That matters because the paper's motivation is distribution shift—earnings days, correlated surges—and Section 7 explicitly defers robustness testing to future work. The headline 41.6% and 0% are therefore not validated for the conditions that motivated the method.\n\nSecond, the baseline is manual scheduling only. A simple list-scheduling or EDF baseline would make the comparison more meaningful, since \"better than manual\" is a low bar. Third, K and alpha are tuned on a four-problem subset and then reported on the full dataset; that's a mild selection bias, not a crime, but it inflates apparent performance somewhat. Fourth, no code or data, which is typical for an industry paper but limits external verification.\n\nNone of this sinks the paper. The formulations are explicit, the method is plausible, and the authors are upfront about what they didn't do—the Discussion is a model of candor. But I'd read the headline numbers as \"promising within-sample evidence\" rather than \"validated under uncertainty.\" For a fresh submission I'd want the evaluation protocol clarified, a holdout split or explicit acknowledgment of the in-sample nature, and at least one non-manual baseline. It deserves a serious referee; the core idea and the experimental write-up are worth engaging with.","headline":"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.","tokens_in":20229,"tokens_out":3444,"would_cite":true,"duration_ms":39074,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B35","90B36"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["capacity planning","job scheduling","scheduling under uncertainty","sample average approximation","constraint programming","cumulative constraint","peak CPU usage","grid computing"],"falsifier":"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.","tokens_in":1695,"feed_emoji":"🖥️","tokens_out":2985,"duration_ms":140679,"temperature":0.7,"pith_summary":"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.","feed_headline":"Pair sampling cuts estimated peak CPU use 41.6%","feed_subtitle":"A scheduler that pairs historical duration and CPU draws cuts peak usage while keeping deadline delays at seconds.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the proactive Sample Average Approximation idea that COSPiS extends from duration-only to paired duration-CPU sampling, and the baseline SORU Pk that COSPiS is compared against.","marker":"[28]"},{"why":"Provides the cumulative constraint propagator that enforces the per-time-point CPU bound in both constraint programming models.","marker":"[24]"},{"why":"The CP-SAT solver used to compute schedules for the Det, COSPiS, and SORU Pk models within the 15-minute limit.","marker":"[10]"},{"why":"The stochastic optimization modeling library behind the MILP formulation and a robust variant noted as too slow (around 10 jobs per hour) to include.","marker":"[6]"},{"why":"Establishes the NP-hardness of the underlying multiprocessor scheduling problem by reduction from bin packing, motivating the approximate approaches.","marker":"[19]"},{"why":"Defines the resource-constrained project scheduling formalism whose structure the COS problem extends to uncertain resource usage.","marker":"[20]"},{"why":"Represents the stochastic resource investment problem family that shares the minimize-resources objective but assumes deterministic resource usage, the gap this paper targets.","marker":"[29]"}],"fun_headline_variants":["Pair-sampling scheduler lowers peak CPU by 41.6%","Scheduler pairs historical draws to reduce peak CPU 41.6%","Pair sampling reduces estimated peak CPU 41.6% in tests","Capacity planning with pair sampling cuts peak CPU up to 41.6%","Handling both duration and CPU uncertainty cuts peak 41.6%"],"cache_read_input_tokens":22400,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Pair-sampling scheduler lowers peak CPU by 41.6%","Scheduler pairs historical draws to reduce peak CPU 41.6%","Pair sampling reduces estimated peak CPU 41.6% in tests","Capacity planning with pair sampling cuts peak CPU up to 41.6%","Handling both duration and CPU uncertainty cuts peak 41.6%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00113,"raw_usage":{"total_tokens":4703,"prompt_tokens":955,"completion_tokens":3748,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":3653}},"tokens_in":571,"tokens_out":3748,"duration_ms":29536,"temperature":1.0,"reasoning_tokens":3653,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:57:06.793203+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"In: Proceedings of the AAAI Conference on 35 Artificial Intelligence","cited_arxiv_id":null,"evidence_quote":"Supplies the proactive Sample Average Approximation idea that COSPiS extends from duration-only to paired duration-CPU sampling, and the baseline SORU Pk that COSPiS is compared against."},{"cited_title":"Constraints 16(3):250–282","cited_arxiv_id":null,"evidence_quote":"Provides the cumulative constraint propagator that enforces the per-time-point CPU bound in both constraint programming models."},{"cited_title":"https://github.com/google/or-tools","cited_arxiv_id":null,"evidence_quote":"The CP-SAT solver used to compute schedules for the Det, COSPiS, and SORU Pk models within the 15-minute limit."},{"cited_title":"Management Science 66(8):3329–3339","cited_arxiv_id":null,"evidence_quote":"The stochastic optimization modeling library behind the MILP formulation and a robust variant noted as too slow (around 10 jobs per hour) to include."},{"cited_title":"Discrete applied mathematics 6(2):173–191","cited_arxiv_id":null,"evidence_quote":"Establishes the NP-hardness of the underlying multiprocessor scheduling problem by reduction from bin packing, motivating the approximate approaches."},{"cited_title":"Springer","cited_arxiv_id":null,"evidence_quote":"Defines the resource-constrained project scheduling formalism whose structure the COS problem extends to uncertain resource usage."},{"cited_title":"IEEE Transactions on Evolutionary Computation 18(5):742–763","cited_arxiv_id":null,"evidence_quote":"Represents the stochastic resource investment problem family that shares the minimize-resources objective but assumes deterministic resource usage, the gap this paper targets."}],"review_version":1}