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

Andreas S. Schulz; Felix Buld

arxiv: 2606.25166 · v1 · pith:I5UYV7GVnew · submitted 2026-06-23 · 💻 cs.DS

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

Felix Buld , Andreas S. Schulz This is my paper

Pith reviewed 2026-06-25 21:46 UTC · model grok-4.3

classification 💻 cs.DS

keywords scheduling with testingcompetitive analysisweighted completion timeonline algorithmssingle machine schedulingparallel machine schedulingadversarial model

0 comments

The pith

Constant-competitive algorithms exist for scheduling with testing to minimize total weighted completion time on single and parallel machines.

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

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.

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.

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.

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.

Where Pith is reading between the lines

These are 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.

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.

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.

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.

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.

Desk Editor's Note private letter to a colleague

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

The core result is a deterministic single-machine algorithm with competitive ratio 2.3166 and a randomized version at 2.1523 for minimizing total weighted completion time under the testing model. They then lift these via list scheduling to identical parallel machines, obtaining 2.7763 and 2.5110, which also improve the known unweighted bounds.

The extension to job-dependent weights is the main novelty. Prior work handled only the unweighted case, and carrying the same ratios through to the weighted setting is not automatic; the analysis must track how weights interact with the online testing decisions and the adversarial upper bounds. The abstract indicates they achieve this without degradation, which is the non-trivial part.

The model itself is standard: testing reveals exact processing time, the algorithm must decide online whether to test or run to the upper bound, and performance is measured against an optimal offline solution. No circularity appears in the stated claims, and the stress-test note finds no internal inconsistency in how the weighting is handled.

The main limitation visible from the abstract is that the proofs are not shown here, so one cannot yet inspect the charging arguments or potential function used to bound the weighted sum. If those steps contain gaps when weights vary, the ratios would not hold. That said, the paper does not appear to rely on any unusual assumptions beyond the usual adversarial model.

This is for researchers working on online and approximation algorithms for scheduling with partial information. A reader already following the unweighted testing results would find the weighted extension and the parallel-machine improvements directly useful. It deserves a serious referee because it addresses a clear open question in the subfield and supplies concrete, stated ratios rather than asymptotic claims.

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)

[§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.
[§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.
[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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 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.

pith-pipeline@v0.9.1-grok · 5710 in / 1126 out tokens · 23794 ms · 2026-06-25T21:46:55.960734+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

35 extracted references · 25 canonical work pages · 1 internal anchor

[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]

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

work page doi:10.1007/978-3-030-80879-2_9
[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]

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

work page doi:10.1007/978-3-030-83508-8_3
[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 doi:10.48550/arxiv.2510.09589 2025
[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]

Brucker.Scheduling Algorithms

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

2007
[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
[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), volume 274 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 38:...

2023
[10]

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

work page doi:10.4230/lipics.esa.2023.38 2023
[11]

Scheduling with obligatory tests

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:14, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informati...

work page doi:10.4230/lipics.esa.2024.48 2024
[12]

u rr, No \

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

work page doi:10.1016/j.apm.2021.12.020 2022
[13]

An adversarial model for scheduling with testing

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

work page doi:10.1007/s00453-020-00742-2 2020
[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

work page doi:10.1287/mnsc.11.2.268 1964
[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

work page doi:10.1007/s10479-025-06804-4 2026
[16]

Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time

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

work page doi:10.1007/s00453-023-01198-w 2024
[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

work page doi:10.1007/s10951-025-00850-3 2025
[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

work page doi:10.1007/s10878-022-00865-y 2022
[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

work page doi:10.1016/s0020-0190(03)00231-x 2003
[20]

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

work page doi:10.1287/mnsc.2017.2973 2019
[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

work page doi:10.1287/mnsc.2023.4833 2024
[22]

The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines

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

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2606.02029 2026
[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

work page doi:10.48550/arxiv.2602.12716 2026
[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

work page doi:10.1007/978-3-031-49815-2_7 2023
[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
[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

work page doi:10.1145/331524.331530 1999
[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

work page doi:10.1016/0304-3975(94)90151-1 1994
[28]

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

work page doi:10.1007/978-3-031-05921-6 2022
[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

work page doi:10.1002/nav.3800030106 1956
[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

work page doi:10.1287/mnsc.2017.2855 2018
[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 totalweightedcompletion time in the adversarial model, some algorithms were proposed by [28]. Th...

2023
[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 bounduor the maximal weightw max. It also contains lower bounds of 2.4 for the se...
[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 processes the long job immediately after testing, causing a large delay for all short ...
[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 immediately after testing. The optimal offline algorithm tests and executes each...
[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(α, β)-PCPalgorithm in Section 4. Using the pairwise contribution bound from Theorem B.2 and ...

[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 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

[9] [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), volume 274 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 38:...

2023

[10] [10]

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

work page doi:10.4230/lipics.esa.2023.38 2023

[11] [11]

Scheduling with obligatory tests

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:14, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informati...

work page doi:10.4230/lipics.esa.2024.48 2024

[12] [12]

u rr, No \

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

work page doi:10.1016/j.apm.2021.12.020 2022

[13] [13]

An adversarial model for scheduling with testing

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

work page doi:10.1007/s00453-020-00742-2 2020

[14] [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

work page doi:10.1287/mnsc.11.2.268 1964

[15] [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

work page doi:10.1007/s10479-025-06804-4 2026

[16] [16]

Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time

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

work page doi:10.1007/s00453-023-01198-w 2024

[17] [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

work page doi:10.1007/s10951-025-00850-3 2025

[18] [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

work page doi:10.1007/s10878-022-00865-y 2022

[19] [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

work page doi:10.1016/s0020-0190(03)00231-x 2003

[20] [20]

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

work page doi:10.1287/mnsc.2017.2973 2019

[21] [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

work page doi:10.1287/mnsc.2023.4833 2024

[22] [22]

The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines

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

work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2606.02029 2026

[23] [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

work page doi:10.48550/arxiv.2602.12716 2026

[24] [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

work page doi:10.1007/978-3-031-49815-2_7 2023

[25] [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

[26] [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

work page doi:10.1145/331524.331530 1999

[27] [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

work page doi:10.1016/0304-3975(94)90151-1 1994

[28] [28]

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

work page doi:10.1007/978-3-031-05921-6 2022

[29] [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

work page doi:10.1002/nav.3800030106 1956

[30] [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

work page doi:10.1287/mnsc.2017.2855 2018

[31] [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 totalweightedcompletion time in the adversarial model, some algorithms were proposed by [28]. Th...

2023

[32] [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 bounduor the maximal weightw max. It also contains lower bounds of 2.4 for the se...

[33] [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 processes the long job immediately after testing, causing a large delay for all short ...

[34] [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 immediately after testing. The optimal offline algorithm tests and executes each...

[35] [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(α, β)-PCPalgorithm in Section 4. Using the pairwise contribution bound from Theorem B.2 and ...