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

Kao-Chuan Liang; Ya-Chun Liang

arxiv: 2606.02029 · v1 · pith:UVR5Q6AZnew · submitted 2026-06-01 · 💻 cs.DS

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

Kao-Chuan Liang , Ya-Chun Liang This is my paper

Pith reviewed 2026-06-28 12:30 UTC · model grok-4.3

classification 💻 cs.DS

keywords online schedulingobligatory testingcompletion timelower boundsmultiple machinescompetitive analysisdeterministic algorithms

0 comments

The pith

Bounding completion-threshold quantities T_X establishes the first strong deterministic lower bounds for obligatory-test scheduling on multiple machines.

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

The paper introduces completion-threshold quantities T_X to analyze online scheduling where every job must be tested on the same machines before its processing time is known, with the goal of minimizing total completion time. By showing that delayed testing forces delayed completions that can be bounded through these thresholds, it derives lower bounds that apply when multiple machines are available. A sympathetic reader would care because prior work only had a sqrt(2) bound for one machine, and these new bounds show how the information-processing tradeoff scales with more machines. The framework also yields a simple 2-competitive algorithm.

Core claim

Completion-threshold quantities T_X serve as the fundamental analytical metric because every completed job must pass through testing, so delayed revelation forces delayed completion. Bounding these T_X thresholds systematically derives strong lower bounds on the total completion time, including a three-type bound of 1.4811 and a multi-type dyadic construction approaching 3/2 asymptotically.

What carries the argument

The completion-threshold quantity T_X, which tracks the necessary completion points forced by testing delays and is used to bound the sum of completion times.

If this is right

The competitive ratio is at least 1.4811 in the worst case for certain three-type job instances on multiple machines.
For multi-type dyadic constructions, the lower bound approaches 3/2 as the number of types increases.
A deterministic list-scheduling algorithm achieves a competitive ratio of 2 for arbitrary test times.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The T_X framework could be applied to analyze other objectives such as minimizing makespan instead of sum of completion times.
The gap between the new lower bounds and the 2-competitive algorithm indicates potential for tighter analysis or improved online policies.
The asymptotic approach to 3/2 in the dyadic case suggests examining whether 3/2 is the true limit for this scheduling model.

Load-bearing premise

Testing and processing must compete directly for machine capacity, with any delay in processing time revelation necessarily delaying completion in a manner measurable by the T_X thresholds.

What would settle it

Finding a deterministic algorithm with competitive ratio below 1.4811 on the three-type instance, or showing that the dyadic construction fails to approach 3/2, would falsify the lower bounds derived from T_X.

read the original abstract

We study online scheduling with obligatory testing on $m$ identical machines with the objective of minimizing the sum of completion times. In this model, every job must undergo a test before its actual processing time is revealed. Consequently, the central algorithmic challenge is no longer whether to acquire information, but how to optimally balance machine capacity between revealing unknown jobs and processing currently known ones. While this tradeoff becomes structurally richer in the multiple-machine setting, the only prior explicit deterministic lower bound for this objective was $\sqrt{2}$, established strictly for a single machine in 2024 by Dogeas et al. [ESA 2024: 48:1-48:14]. Our core conceptual contribution is demonstrating that completion-threshold quantities, denoted $T_X$, serve as the fundamental analytical metric for this setting. Because every completed job must first pass through the testing phase, delayed revelation inherently forces delayed completion. By bounding these $T_X$ thresholds, we systematically derive strong lower bounds on the total completion time. Utilizing this framework, we establish the first substantial deterministic lower bounds for multiple machines, including a three-type bound of $1.4811$ and a multi-type dyadic construction that asymptotically approaches $3/2$. Finally, we complement these theoretical limits with a deterministic $2$-competitive list-scheduling algorithm for arbitrary test times.

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

The paper's core advance is a completion-threshold framework that produces the first explicit multi-machine lower bounds (1.4811 for three types, asymptotic 3/2) for obligatory testing scheduling, paired with a 2-competitive list algorithm.

read the letter

The main thing to know is that this work moves the single-machine sqrt(2) lower bound from Dogeas et al. into the multi-machine setting by defining T_X thresholds that track how testing delays force later completions. Bounding those thresholds yields the reported numbers and supports a simple deterministic algorithm.

What stands out is the explicit construction of the bounds. The three-type case at 1.4811 and the dyadic multi-type limit approaching 3/2 are concrete and appear to follow directly from analyzing when jobs must finish after their tests. The 2-competitive list scheduler is easy to state and works for arbitrary test times, which is a practical complement to the lower-bound side.

The framework itself is the clearest new device. It reframes the problem around shared machine capacity between testing and processing, then converts revelation delays into completion-time penalties without needing randomization. That step looks reproducible from the abstract description.

The softer parts are the gap between the 3/2 lower bound and the 2-competitive upper bound, and the fact that the strongest lower bounds are shown only for fixed numbers of job types rather than fully general instances. It is not yet clear whether the T_X analysis can be tightened further or whether the algorithm can be improved without losing determinism. The model premise that testing and processing directly compete for the same machines is stated up front, so any looseness would come from the bounding technique rather than hidden assumptions.

This is for scheduling theorists who already follow online algorithms with testing. A reader looking for multi-machine lower-bound methods will get usable ideas. The combination of new bounds plus an algorithm is enough to justify sending it to referees rather than desk rejection.

Referee Report

0 major / 3 minor

Summary. The manuscript introduces the completion-threshold framework for online scheduling with obligatory testing on m identical machines, minimizing the sum of completion times. Every job requires a test before its processing time is revealed, creating a tradeoff between testing and processing on shared machine capacity. The core device is the family of completion-threshold quantities T_X; bounding these thresholds converts delayed revelation into lower bounds on total completion time. Using the framework the authors derive a three-type lower bound of 1.4811 and a multi-type dyadic construction whose ratio approaches 3/2 asymptotically, improving on the prior single-machine √2 bound. They also supply a deterministic 2-competitive list-scheduling algorithm that works for arbitrary test times.

Significance. If the T_X bounds are shown to follow from the model without post-hoc parameter tuning, the paper supplies the first non-trivial deterministic lower bounds for the multi-machine obligatory-testing setting. The framework appears to be a reusable analytical tool that systematically links testing delays to completion-time penalties. The 2-competitive algorithm is a concrete algorithmic contribution that matches the model’s information constraints. These elements together advance the theory of online scheduling with mandatory information acquisition.

minor comments (3)

The abstract states that bounding T_X yields the 1.4811 and 3/2 figures; the main text should include an explicit derivation or optimization program (with the relevant section or equation) so that readers can verify that the numerical values are not the result of post-hoc fitting.
The multi-type dyadic construction is described only at high level; a short appendix or subsection giving the explicit job-type sequence and the resulting T_X recurrence would strengthen reproducibility.
The 2-competitive algorithm is stated to work for arbitrary test times; a brief argument or reference to the single-machine case (Dogeas et al.) explaining why the ratio remains 2 when m>1 would clarify the extension.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and recommendation of minor revision. No major comments were raised, so our response focuses on confirming the overall assessment and noting that we will address any minor points during revision.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines completion-threshold quantities T_X as an analytical device for converting the testing/processing tradeoff into lower bounds on sum of completion times. The abstract states that bounding T_X yields the reported deterministic lower bounds (1.4811 for three types, asymptotic 3/2) and that a separate 2-competitive algorithm is provided. No equations, self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations appear in the supplied text. The model premise (testing and processing share machine capacity) is adopted explicitly rather than derived from the bounds themselves. The derivation chain therefore remains self-contained against external benchmarks and does not reduce to its inputs by construction.

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 or derivable from the provided text.

pith-pipeline@v0.9.1-grok · 5767 in / 1180 out tokens · 24534 ms · 2026-06-28T12:30:36.074168+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model
cs.DS 2026-06 unverdicted novelty 7.0

Presents deterministic (2.3166) and randomized (2.1523) constant-competitive algorithms for weighted single-machine scheduling with testing, extended via list scheduling to parallel machines (2.7763/2.5110).

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 1 Pith paper

[1]

Explorable uncertainty in scheduling with non-uniform testing times

Susanne Albers and Alexander Eckl. Explorable uncertainty in scheduling with non-uniform testing times. In Approximation and Online Algorithms (WAOA 2020) , volume 12806 of Lecture Notes in Computer Science , pages 127--142. Springer, 2020. https://doi.org/10.1007/978-3-030-80879-2_9 doi:10.1007/978-3-030-80879-2_9

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

Scheduling with testing on multiple identical parallel machines

Susanne Albers and Alexander Eckl. Scheduling with testing on multiple identical parallel machines. In Algorithms and Data Structures: 17th International Symposium, (WADS 2021) , volume 12808 of Lecture Notes in Computer Science , pages 29--42. Springer, 2021. https://doi.org/10.1007/978-3-030-83508-8_3 doi:10.1007/978-3-030-83508-8_3

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

Kononov, Giorgio Lucarelli, and Fanny Pascual

Evripidis Bampis, Konstantinos Dogeas, Alexander V. Kononov, Giorgio Lucarelli, and Fanny Pascual. Speed scaling with explorable uncertainty. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2021) , pages 83--93. ACM, 2021. https://doi.org/10.1145/3409964.3461812 doi:10.1145/3409964.3461812

work page doi:10.1145/3409964.3461812 2021
[4]

Felix Buld and Andreas S. Schulz. Scheduling with testing: Competitive algorithms for minimizing the total weighted completion time in the adversarial model. In Frontiers of Algorithmics (IJTCS-FAW 2025) , volume 15828 of Lecture Notes in Computer Science , pages 64--77. Springer, Singapore, 2025. https://doi.org/10.1007/978-981-96-8312-3_5 doi:10.1007/97...

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

Scheduling with obligatory tests

Konstantinos Dogeas, Thomas Erlebach, and Ya-Chun Liang. Scheduling with obligatory tests. In 32nd Annual European Symposium on Algorithms (ESA 2024) , volume 308 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 48:1--48:14. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.48 doi:10....

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

u rr, No \

Fanny Dufoss \'e , Christoph D \"u rr, No \"e l Nadal, Denis Trystram, and \'O scar C. V \'a squez. Scheduling with a processing time oracle. Applied Mathematical Modelling , 104:701--720, 2022. https://doi.org/10.1016/j.apm.2021.12.020 doi:10.1016/j.apm.2021.12.020

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

Scheduling with explorable uncertainty

Christoph D \"u rr, Thomas Erlebach, Nicole Megow, and Julie Mei ner. Scheduling with explorable uncertainty. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , pages 30:1--30:14, 2018. https://doi.org/10.4230/LIPIcs.ITCS.2018.30 doi:10.4230/LIPIcs.ITCS.2018.30

work page doi:10.4230/lipics.itcs.2018.30 2018
[8]

An adversarial model for scheduling with testing

Christoph D \"u rr, Thomas Erlebach, Nicole Megow, and Julie Mei ner. An adversarial model for scheduling with testing. Algorithmica , 82(12):3630--3675, 2020. https://doi.org/10.1007/s00453-020-00742-2 doi:10.1007/s00453-020-00742-2

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

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

Mingyang Gong, Zhi-Zhong Chen, and Kuniteru Hayashi. Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica , 86:1400--1427, 2024. https://doi.org/10.1007/s00453-023-01198-w doi:10.1007/s00453-023-01198-w

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

Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments

Mingyang Gong, Jing Fan, Guohui Lin, Bing Su, Zihan Su, and Xiang Zhang. Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments. Journal of Scheduling , 28(5):513--527, 2025. https://doi.org/10.1007/s10951-025-00850-3 doi:10.1007/s10951-025-00850-3

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

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Mingyang Gong, Randy Goebel, Guohui Lin, and Eiji Miyano. Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing. Journal of Combinatorial Optimization , 44(1):877--893, 2022. https://doi.org/10.1007/s10878-022-00865-y doi:10.1007/s10878-022-00865-y

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

Improved approximation algorithms for multiprocessor scheduling with testing

Mingyang Gong and Guohui Lin. Improved approximation algorithms for multiprocessor scheduling with testing. In Frontiers of Algorithmics / International Joint Conference on Theory and Applications of Models of Computation, IJTCS-FAW 2021 , volume 12874 of Lecture Notes in Computer Science , pages 65--77. Springer, 2022. https://doi.org/10.1007/978-3-030-9...

work page doi:10.1007/978-3-030-97099-4_5 2021
[13]

Magnanti, and Yaron Shaposhnik

Retsef Levi, Thomas L. Magnanti, and Yaron Shaposhnik. Scheduling with testing. Management Science , 65(2):776--793, 2019. https://doi.org/10.1287/mnsc.2017.2973 doi:10.1287/mnsc.2017.2973

work page doi:10.1287/mnsc.2017.2973 2019
[14]

Alison Hsiang-Hsuan Liu, Fu-Hong Liu, Prudence W. H. Wong, and Xiao-Ou Zhang. The power of amortization on scheduling with explorable uncertainty. In Approximation and Online Algorithms (WAOA 2023) , volume 14297 of Lecture Notes in Computer Science , pages 90--103. Springer, 2023. https://doi.org/10.1007/978-3-031-49815-2_7 doi:10.1007/978-3-031-49815-2_7

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

[1] [1]

Explorable uncertainty in scheduling with non-uniform testing times

Susanne Albers and Alexander Eckl. Explorable uncertainty in scheduling with non-uniform testing times. In Approximation and Online Algorithms (WAOA 2020) , volume 12806 of Lecture Notes in Computer Science , pages 127--142. Springer, 2020. https://doi.org/10.1007/978-3-030-80879-2_9 doi:10.1007/978-3-030-80879-2_9

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

[2] [2]

Scheduling with testing on multiple identical parallel machines

Susanne Albers and Alexander Eckl. Scheduling with testing on multiple identical parallel machines. In Algorithms and Data Structures: 17th International Symposium, (WADS 2021) , volume 12808 of Lecture Notes in Computer Science , pages 29--42. Springer, 2021. https://doi.org/10.1007/978-3-030-83508-8_3 doi:10.1007/978-3-030-83508-8_3

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

[3] [3]

Kononov, Giorgio Lucarelli, and Fanny Pascual

Evripidis Bampis, Konstantinos Dogeas, Alexander V. Kononov, Giorgio Lucarelli, and Fanny Pascual. Speed scaling with explorable uncertainty. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2021) , pages 83--93. ACM, 2021. https://doi.org/10.1145/3409964.3461812 doi:10.1145/3409964.3461812

work page doi:10.1145/3409964.3461812 2021

[4] [4]

Felix Buld and Andreas S. Schulz. Scheduling with testing: Competitive algorithms for minimizing the total weighted completion time in the adversarial model. In Frontiers of Algorithmics (IJTCS-FAW 2025) , volume 15828 of Lecture Notes in Computer Science , pages 64--77. Springer, Singapore, 2025. https://doi.org/10.1007/978-981-96-8312-3_5 doi:10.1007/97...

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

[5] [5]

Scheduling with obligatory tests

Konstantinos Dogeas, Thomas Erlebach, and Ya-Chun Liang. Scheduling with obligatory tests. In 32nd Annual European Symposium on Algorithms (ESA 2024) , volume 308 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 48:1--48:14. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.48 doi:10....

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

[6] [6]

u rr, No \

Fanny Dufoss \'e , Christoph D \"u rr, No \"e l Nadal, Denis Trystram, and \'O scar C. V \'a squez. Scheduling with a processing time oracle. Applied Mathematical Modelling , 104:701--720, 2022. https://doi.org/10.1016/j.apm.2021.12.020 doi:10.1016/j.apm.2021.12.020

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

[7] [7]

Scheduling with explorable uncertainty

Christoph D \"u rr, Thomas Erlebach, Nicole Megow, and Julie Mei ner. Scheduling with explorable uncertainty. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , pages 30:1--30:14, 2018. https://doi.org/10.4230/LIPIcs.ITCS.2018.30 doi:10.4230/LIPIcs.ITCS.2018.30

work page doi:10.4230/lipics.itcs.2018.30 2018

[8] [8]

An adversarial model for scheduling with testing

Christoph D \"u rr, Thomas Erlebach, Nicole Megow, and Julie Mei ner. An adversarial model for scheduling with testing. Algorithmica , 82(12):3630--3675, 2020. https://doi.org/10.1007/s00453-020-00742-2 doi:10.1007/s00453-020-00742-2

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

[9] [9]

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

Mingyang Gong, Zhi-Zhong Chen, and Kuniteru Hayashi. Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica , 86:1400--1427, 2024. https://doi.org/10.1007/s00453-023-01198-w doi:10.1007/s00453-023-01198-w

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

[10] [10]

Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments

Mingyang Gong, Jing Fan, Guohui Lin, Bing Su, Zihan Su, and Xiang Zhang. Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments. Journal of Scheduling , 28(5):513--527, 2025. https://doi.org/10.1007/s10951-025-00850-3 doi:10.1007/s10951-025-00850-3

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

[11] [11]

Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

Mingyang Gong, Randy Goebel, Guohui Lin, and Eiji Miyano. Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing. Journal of Combinatorial Optimization , 44(1):877--893, 2022. https://doi.org/10.1007/s10878-022-00865-y doi:10.1007/s10878-022-00865-y

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

[12] [12]

Improved approximation algorithms for multiprocessor scheduling with testing

Mingyang Gong and Guohui Lin. Improved approximation algorithms for multiprocessor scheduling with testing. In Frontiers of Algorithmics / International Joint Conference on Theory and Applications of Models of Computation, IJTCS-FAW 2021 , volume 12874 of Lecture Notes in Computer Science , pages 65--77. Springer, 2022. https://doi.org/10.1007/978-3-030-9...

work page doi:10.1007/978-3-030-97099-4_5 2021

[13] [13]

Magnanti, and Yaron Shaposhnik

Retsef Levi, Thomas L. Magnanti, and Yaron Shaposhnik. Scheduling with testing. Management Science , 65(2):776--793, 2019. https://doi.org/10.1287/mnsc.2017.2973 doi:10.1287/mnsc.2017.2973

work page doi:10.1287/mnsc.2017.2973 2019

[14] [14]

Alison Hsiang-Hsuan Liu, Fu-Hong Liu, Prudence W. H. Wong, and Xiao-Ou Zhang. The power of amortization on scheduling with explorable uncertainty. In Approximation and Online Algorithms (WAOA 2023) , volume 14297 of Lecture Notes in Computer Science , pages 90--103. Springer, 2023. https://doi.org/10.1007/978-3-031-49815-2_7 doi:10.1007/978-3-031-49815-2_7

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