Pith. sign in

REVIEW 3 minor 35 references

Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model

T0 review · 0 major / 3 minor · reviewed 2026-06-25 · grok-4.3

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

Pith's one-line read Constant-competitive algorithms exist for scheduling with testing to minimize total weighted completion time on single and parallel machines.

desk verdict This paper gives the first constant-competitive algorithms for the weighted case of scheduling with testing, with ratios that match the prior unweighted bounds. read the letter →

arxiv 2606.25166 v1 pith:I5UYV7GV submitted 2026-06-23 cs.DS

Felix Buld , Andreas S. Schulz This is my paper · ORCID
classification cs.DS
keywords schedulingwithtestingcompetitiveanalysisweightedcompletiontimeonlinealgorithmssinglemachineparalleladversarialmodel
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

The paper develops the first constant-competitive online algorithms for the problem of scheduling with testing under job-dependent weights to minimize total weighted completion time. In this model each job has a weight reflecting its importance, an upper bound on processing time, and a testing time; an algorithm may either run the job up to the bound or test it first to learn its exact shorter processing time before scheduling it. For a single machine the authors give a deterministic algorithm with competitive ratio 2.3166 and a randomized variant with ratio 2.1523, matching the best known guarantees from the unweighted case. These single-machine procedures are then combined with list scheduling to obtain ratios 2.7763 and 2.5110 on identical parallel machines, which also improve the prior unweighted bounds.

What carries the argument

The central mechanism is a threshold-based decision rule (with randomization in one variant) that decides whether to test each job or run it to its upper bound, followed by list scheduling on the revealed processing times; the analysis bounds the weighted completion time against an optimal offline schedule by comparing the cost incurred on tested versus untested jobs.

What would settle it

An explicit job instance with weights, upper bounds, and testing times on which the algorithm's total weighted completion time exceeds 2.3166 times the optimal offline cost (or the stated randomized or parallel ratios) would falsify the claimed competitive ratios.

Watch

Extended reading notes

Core claim

The authors establish the first constant-competitive algorithms for weighted scheduling with testing in the adversarial model. For single-machine scheduling they present a deterministic algorithm with competitive ratio 2.3166 and a randomized variant with ratio 2.1523; these match the best-known upper bounds for the unweighted setting. Combining the same single-machine procedures with list scheduling yields competitive ratios of 2.7763 (deterministic) and 2.5110 (randomized) for identical parallel machines, improving even the unweighted case.

Load-bearing premise

Testing a job always reveals its exact processing time with no noise, and the algorithm must commit online to testing or running without knowledge of future jobs or the adversary's choices.

Editorial extensions

If this is right

  • The competitive ratios remain unchanged when job weights are introduced, matching the unweighted guarantees.
  • Parallel-machine bounds follow directly from applying the single-machine procedures inside a list-scheduling wrapper.
  • The same algorithmic framework improves the best-known ratios even when all weights are set to one.
  • The results hold in the fully adversarial online model where processing times are revealed only upon testing.

Reading between the lines

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

  • The testing decision thresholds could be tuned for other machine environments or objectives such as makespan.
  • If testing times themselves are uncertain, the current analysis would need adjustment but the overall competitive approach might still apply.
  • The matching of weighted and unweighted ratios suggests that the proof technique may extend to other linear cost functions on completion times.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The manuscript studies scheduling with testing on a single machine and identical parallel machines to minimize total weighted completion time in the adversarial model, where each job has a weight, an upper bound on processing time, and a testing time. An online algorithm may either run a job to its upper bound or test it to reveal its exact (lower) processing time. The paper claims the first constant-competitive algorithms for the weighted setting: a deterministic single-machine algorithm with ratio 2.3166, a randomized variant with ratio 2.1523 (matching the best unweighted bounds), and parallel-machine ratios of 2.7763 (deterministic) and 2.5110 (randomized) obtained by combining the single-machine algorithms with list scheduling, which also improves the prior unweighted parallel-machine bounds.

Significance. If the stated competitive ratios are established by the analysis, the work is significant because it is the first to obtain constant competitiveness for job-dependent weights (rather than unit weights) while matching the best-known unweighted ratios; the parallel-machine improvement via a standard list-scheduling reduction is a clean and useful extension. The adversarial model with exact revelation on testing is the standard one in the area, and the explicit numerical ratios allow direct comparison with prior work.

minor comments (3)
  1. [§3] §3 (single-machine deterministic algorithm): the description of how the weight-dependent ordering is maintained after testing should be expanded with a short pseudocode fragment or invariant statement, as the current prose leaves the tie-breaking rule for equal weights ambiguous.
  2. [§5] §5 (parallel-machine analysis): the application of list scheduling to the single-machine schedules is stated at a high level; a one-paragraph derivation showing that the 4/3 factor from list scheduling multiplies cleanly with the single-machine ratios (without additional cross terms) would improve readability.
  3. [Table 1] Table 1 (competitive-ratio summary): the table lists the new ratios but omits the previous best unweighted parallel-machine bounds being improved; adding those numbers would make the improvement claim immediately verifiable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the report, so we have nothing further to address point by point.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper presents competitive-ratio proofs for online scheduling algorithms against an optimal offline solution (OPT), which is an external benchmark independent of the algorithm's own outputs or fitted parameters. The claimed ratios (2.3166 deterministic, 2.1523 randomized) are derived via standard list-scheduling and randomization techniques that compare algorithm cost directly to OPT cost; no step reduces a prediction to a fitted input, renames a known result, or relies on a self-citation chain for the core bound. The extension from unweighted to weighted cases is presented as carrying through the same analysis structure without redefining quantities in terms of themselves. This is the normal, non-circular structure for competitive-analysis papers.

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

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The work relies on standard competitive-analysis assumptions (adversarial inputs, exact testing revelation) that are not enumerated here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model." pith.science (2026). https://pith.science/paper/I5UYV7GV

@misc{pith2026260625166,
  author       = {Pith},
  title        = {Pith review of: Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I5UYV7GV}},
  note         = {Machine review of arXiv:2606.25166}
}
read the original abstract

We study scheduling with testing on a single machine and on identical parallel machines to minimize the total \emph{weighted} completion time in the adversarial model. In this setting, each job is equipped with a weight, an upper bound on its processing time, and a testing time. An algorithm can either execute a job for an amount of time equal to the upper bound or test it first to reveal a potentially lower processing time used to schedule the job later. We establish the first constant-competitive algorithms for this problem with job-dependent weights that reflect each job's relative importance. For single-machine scheduling, we present a deterministic algorithm with a competitive ratio of 2.3166 and show that a randomized variant has a competitive ratio of 2.1523. These guarantees match the best-known upper bounds in the unweighted setting. Combining these algorithms with list scheduling yields competitive ratios of 2.7763 and 2.5110 for identical-parallel-machine scheduling, improving the previously best-known bounds even in the unweighted case.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 25 canonical work pages

  1. [1]

    Albers and A

    S. Albers and A. Eckl. Explorable uncertainty in scheduling with non-uniform testing times. In C. Kaklamanis and A. Levin, editors,WAOA 2020, volume 12806 ofLNCS, pages 127–142, Cham,

    2020

  2. [2]

    Springer.doi:10.1007/978-3-030-80879-2_9

    work page doi:10.1007/978-3-030-80879-2_9

  3. [3]

    Albers and A

    S. Albers and A. Eckl. Scheduling with testing on multiple identical parallel machines. In A. Lubiw, M. Salavatipour, and M. He, editors,WADS 2021, volume 12808 ofLNCS, pages 29–42, Cham,

    2021

  4. [4]

    Springer.doi:10.1007/978-3-030-83508-8_3

    work page doi:10.1007/978-3-030-83508-8_3

  5. [5]

    Amouzandeh, K

    A. Amouzandeh, K. Jansen, L. Pirotton, R. van Stee, and C. Wambsganz. Minimizing the weighted makespan with restarts on a single machine, 2025.doi:10.48550/arXiv.2510.09589

    work page Pith review doi:10.48550/arxiv.2510.09589 2025

  6. [6]

    Kononov, Giorgio Lucarelli, and Fanny Pascual

    E. Bampis, K. Dogeas, A. Kononov, G. Lucarelli, and F. Pascual. Speed scaling with explorable uncertainty. InProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architec- tures (SPAA 2021), pages 83–93, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3409964.3461812

    work page doi:10.1145/3409964.3461812 2021

  7. [7]

    Brucker.Scheduling Algorithms

    P. Brucker.Scheduling Algorithms. Springer, Berlin, Heidelberg, 5 edition, 2007.doi:10.1007/ 978-3-540-69516-5

    2007

  8. [8]

    Buld and A

    F. Buld and A. S. Schulz. Scheduling with testing: Competitive algorithms for minimizing the total weighted completion time in the adversarial model. In V. Chau, C. D¨ urr, M. Li, and P. Lu, editors,Frontiers of Algorithmics, volume 15828 ofLNCS, pages 64–77, Singapore, 2025. Springer. doi:10.1007/978-981-96-8312-3_5

    work page doi:10.1007/978-981-96-8312-3_5 2025

Show all 35 references
  1. [9]

    Damerius, P

    C. Damerius, P. Kling, M. Li, C. Xu, and R. Zhang. Scheduling with a limited testing budget: Tight results for the offline and oblivious settings. In I. L. Gørtz, M. Farach-Colton, S. J. Puglisi, and G. Herman, editors,31st Annual European Symposium on Algorithms (ESA 2023), v...

    2023

  2. [10]

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.doi:10.4230/LIPIcs.ESA.2023.38

    2023 doi

  3. [11]

    Dogeas, T

    K. Dogeas, T. Erlebach, and Y.-C. Liang. Scheduling with obligatory tests. In T. Chan, J. Fischer, J. Iacono, and G. Herman, editors,32nd Annual European Symposium on Algo- rithms (ESA 2024), volume 308 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48...

    2024 doi

  4. [12]

    Dufoss´ e, C

    F. Dufoss´ e, C. D¨ urr, N. Nadal, D. Trystram, and´O. C. V´ asquez. Scheduling with a processing time oracle.Applied Mathematical Modelling, 104:701–720, 2022.doi:10.1016/j.apm.2021.12.020

    2022 doi

  5. [13]

    D¨ urr, T

    C. D¨ urr, T. Erlebach, N. Megow, and J. Meißner. An adversarial model for scheduling with testing. Algorithmica, 82(12):3630–3675, 2020.doi:10.1007/s00453-020-00742-2

    2020 doi

  6. [14]

    W. L. Eastman, S. Even, and I. M. Isaacs. Bounds for the optimal scheduling ofnjobs onm processors.Management Science, 11(2):268–279, 1964.doi:10.1287/mnsc.11.2.268

    1964 doi

  7. [15]

    Gong, Z.-Z

    M. Gong, Z.-Z. Chen, G. Chen, G. Lin, and L. Wang. Randomized algorithms for fully online multiprocessor scheduling with testing.Annals of Operations Research, 358(1):71–101, 2026.doi: 10.1007/s10479-025-06804-4

    2026 doi

  8. [16]

    Gong, Z.-Z

    M. Gong, Z.-Z. Chen, and K. Hayashi. Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time.Algorithmica, 86(5):1400–1427, 2024.doi: 10.1007/s00453-023-01198-w

    2024 doi

  9. [17]

    M. Gong, J. Fan, G. Lin, B. Su, Z. Su, and X. Zhang. Multiprocessor scheduling with testing: improved online algorithms and numerical experiments.Journal of Scheduling, 28(5):513–527, 2025. doi:10.1007/s10951-025-00850-3

    2025 doi

  10. [18]

    M. Gong, R. Goebel, G. Lin, and E. Miyano. Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing.Journal of Combinatorial Optimization, 44(1):877–893, 2022. doi:10.1007/s10878-022-00865-y

    2022 doi

  11. [19]

    Kim and K.-Y

    J.-H. Kim and K.-Y. Chwa. Non-clairvoyant scheduling for weighted flow time.Information Pro- cessing Letters, 87(1):31–37, 2003.doi:10.1016/S0020-0190(03)00231-X. 15

    2003 doi

  12. [20]

    R. Levi, T. Magnanti, and Y. Shaposhnik. Scheduling with testing.Management Science, 65(2):776– 793, 2019.doi:10.1287/mnsc.2017.2973

    2019 doi

  13. [21]

    R. Levi, T. Magnanti, and Y. Shaposhnik. Scheduling with testing of heterogeneous jobs.Manage- ment Science, 70(5):2934–2953, 2024.doi:10.1287/mnsc.2023.4833

    2024 doi

  14. [22]

    Liang and Y.-C

    K.-C. Liang and Y.-C. Liang. The completion-threshold framework for obligatory-test scheduling on multiple machines, 2026.doi:10.48550/arXiv.2606.02029

    2026 doi arXiv

  15. [23]

    Lindermayr, G

    A. Lindermayr, G. Sch¨ afer, J. Schl¨ oter, and L. Stougie. Online flow time minimization with gradually revealed jobs, 2026.doi:10.48550/arXiv.2602.12716

    2026 doi

  16. [24]

    A. H.-H. Liu, F.-H. Liu, P. W. Wong, and X.-O. Zhang. The power of amortization on scheduling with explorable uncertainty. In J. Byrka and A. Wiese, editors,WAOA 2023, volume 14297 of LNCS, pages 90–103, Cham, 2023. Springer.doi:10.1007/978-3-031-49815-2_7

    2023 doi

  17. [25]

    A. H.-H. Liu, F.-H. Liu, P. W. Wong, and X.-O. Zhang. Amortization helps for scheduling with explorable uncertainty, even on parallel machines. InProceedings of the 16th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2024), pages 259–262, 2024

    2024

  18. [26]

    R. H. M¨ ohring, A. S. Schulz, and M. Uetz. Approximation in stochastic scheduling: The power of lp-based priority policies.Journal of the ACM, 46(6):924–942, 1999.doi:10.1145/331524.331530

    1999 doi

  19. [27]

    Motwani, S

    R. Motwani, S. Phillips, and E. Torng. Nonclairvoyant scheduling.Theoretical Computer Science, 130(1):17–47, 1994.doi:10.1016/0304-3975(94)90151-1

    1994 doi

  20. [28]

    M. L. Pinedo.Scheduling: Theory, Algorithms, and Systems. Springer, Cham, 6 edition, 2022. doi:10.1007/978-3-031-05921-6

    2022 doi

  21. [29]

    W. E. Smith. Various optimizers for single-stage production.Naval Research Logistics Quarterly, 3(1-2):59–66, 1956.doi:10.1002/nav.3800030106

    1956 doi

  22. [30]

    Z. Sun, N. T. Argon, and S. Ziya. Patient triage and prioritization under austere conditions. Management Science, 64(10):4471–4489, 2018.doi:10.1287/mnsc.2017.2855

    2018 doi

  23. [31]

    X. Zhang. Scheduling with explorable uncertainty for minimising the total weighted completion time. Master’s thesis, Utrecht University, 2023. A Unboundedness of Previous Approaches Considering Job- Dependent Weights For scheduling with testing to minimize the totalweightedcom...

    2023

  24. [32]

    Then applyDelay-All individually to each batch in order of non-increasing weights

    Intermediate strategyL-Delay-All: Group jobs in batches of same weight. Then applyDelay-All individually to each batch in order of non-increasing weights. They provide upper bounds on the competitive ratios of these algorithms, parameterized by input values such as the upper b...

  25. [33]

    , n, (long)t j = 1, uj =n 2, pj =n 2, wj = 1 +εforj=n+ 1

    AlgorithmsGreedyandL-Delay-All: Consider instances withn≥2smalljobs, onelargejob and ε >0 small: (short)t j = 1, uj =n 2, pj = 0, w j = 1 forj= 1, . . . , n, (long)t j = 1, uj =n 2, pj =n 2, wj = 1 +εforj=n+ 1. 16 Since the first algorithm focuses only on the weight, it proces...

  26. [34]

    , n, (heavy)t j = 1, uj = 2, pj = 0, wj =n 2 forj=n+ 1

    AlgorithmDelay-All: Consider instances withnlightjobs and oneheavyjob: (light)t j = 1, uj = 2, pj = 0, wj = 1 forj= 1, . . . , n, (heavy)t j = 1, uj = 2, pj = 0, wj =n 2 forj=n+ 1. Delay-Alltests all jobs first and then executes them. Especially the heavy job is not completed ...

  27. [35]

    Remark B.3.TheWeighted(α, β)-SORTalgorithm can be extended to identical parallel machines as theWeighted(α, β)-PCPalgorithm in Section 4

    To improve upon this, one would needβ < √ 2 since we have the term 1 +βin the maximum, henceα < √ 2 since we have the termα(1 + 1/β), but then 1 + 2/α>1 + √ 2. Remark B.3.TheWeighted(α, β)-SORTalgorithm can be extended to identical parallel machines as theWeighted(α, β)-PCPalg...

Pith tools

Reviewed June 25, 2026 · model on record in the stance chip above.