The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines
Kao-Chuan Liang, Ya-Chun Liang · 2026
Read The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines by Kao-Chuan Liang, Ya-Chun Liang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02029.txt.
Introduction
Liang and Liang study online scheduling where every job needs a test first. Each job has a test of known length. A processing step of unknown length follows it. The size is revealed only when the test ends. Testing is obligatory, unlike in optional testing models.
Many identical machines run in parallel in this setting. The goal is to minimize the sum of completion times. The scheduler must split machine capacity wisely. Testing unrevealed jobs competes with processing known ones. Single-machine lower bounds suggest a square root of two benchmark. Those constructions do not transfer by simple replication. Jobs from different copies can interleave on machines. Test and processing steps need not stay together.
Catalog record
| CREATOR | Kao-Chuan Liang, Ya-Chun Liang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02029
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines Kao-Chuan Liang, Ya-Chun Liang Abstract We study online scheduling with obligatory testing on m 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 2 \sqrt{2} , established strictly for a single machine [ 5 ] . Our core conceptual contribution is demonstrating that completion-threshold quantities, denoted T X 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 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 1.4811 and a multi-type dyadic construction that asymptotically approaches 3 / 2 3/2 . Finally, we complement these theoretical limits with a deterministic 2 2 -competitive list-scheduling algorithm for arbitrary test times. Department of Computer Science, National Tsing Hua University, Hsinchu, [email protected] Department of Computer Science, National Tsing Hua University, Hsinchu, [email protected]://orcid.org/0000-0002-7359-4335 ccs Theory of computation Design and analysis of algorithms keywords Competitive ratio, Lower bounds, Online algorithms, Scheduling with testing, Sum of completion times, Multiple machines † † runningtitle: The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines † † runningauthor: Kao-Chuan Liang and Ya-Chun Liang † † copyright: Kao-Chuan Liang and Ya-Chun Liang † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The framework of scheduling with testing involves problems in which the processing time of a job is not known in advance, but can be revealed by performing a test. Most previous work considers the optional-test model, where the scheduler may decide whether to test a job first or to execute it directly using prior information. In contrast, Dogeas et al. [ 5 ] recently introduced the obligatory-test model, in which every job must be tested before its processing part can begin, and studied the single-machine case with the objective of minimizing the sum of completion times. In this paper, we extend the obligatory-test model to m identical parallel machines. Each job j consists of a test of known length t_{j} and a processing operation of unknown length p_{j} , where p_{j} is revealed only upon completion of the test. All jobs are available at time 0 , and the objective is to minimize \sum_{j}C_{j} , where C_{j} denotes the completion time of job j . We consider both standard test-time settings. In the uniform setting, all jobs have the same test time, and we assume without loss of generality that t_{j}=1 for all j . In the non-uniform setting, test times may vary across jobs. The obligatory-test model is structurally different from the optional one. In the optional model, the scheduler must decide whether information acquisition is worthwhile. In the obligatory model, this decision disappears, since every job must eventually be tested. The algorithm must instead decide how to divide machine time between two competing activities: testing jobs whose processing times are still unknown, and processing jobs whose test outcomes have already been revealed. If too much time is spent on testing, information is acquired quickly but a large processing backlog may accumulate. If too much time is spent on processing, the current backlog is reduced but future jobs are revealed more slowly. This tension already appears on a single machine, but it becomes more subtle on parallel machines, where multiple tests and multiple processing operations may proceed simultaneously. Thus, extending the model to multiple identical machines is not merely a routine generalization: it is the natural setting in which to ask whether parallelism can fundamentally mitigate this tradeoff between revealing jobs and processing revealed jobs. Our goal is to understand this tradeoff in the multiple-machine obligatory setting, with particular emphasis on lower bounds. Prior to our work, the only explicit deterministic lower bound for minimizing the sum of completion times in the obligatory-test model was the single-machine \sqrt{2} bound of Dogeas et al. [ 5 ] . Thus, even though the multiple-machine setting is structurally richer, its deterministic lower-bound landscape remained unexplored. This is largely because the adversarial techniques developed for a single machine do not readily generalize to parallel machines. To bridge this gap, our key observation is that the completion-threshold quantities, denoted T_{X} , serve as the fundamental analytical metric for obligatory testing on parallel machines. Because \mathrm{ALG}=\sum_{X=1}^{N}T_{X} , lower bounds on the times at which the first X jobs are completed systematically derive lower bounds on the total completion time. This viewpoint is especially effective in the obligatory model, where every completed job must first pass through a test before its processing time is revealed. As a result, slow progress in revealing jobs inherently forces delayed completion. This transforms the T_{X} perspective into a powerful mechanism for extending lower-bound reasoning from the single-machine setting to multiple machines. Utilizing this framework, we obtain substantially stronger deterministic lower bounds, including a three-type bound of 1.4811 and a multi-type dyadic construction that asymptotically approaches \frac{3}{2} . On the algorithmic side, we complement these theoretical limits with a simple, deterministic online algorithm achieving a competitive ratio of 2 for arbitrary test times. Crucially, our algorithmic upper bound applies to arbitrary test times in the full non-uniform model, while our lower-bound constructions establish strong impossibility results even in the restricted uniform setting. \begin{array}[]{c|c|cc|cc}\textbf{Testing Model}&\textbf{Machines}&\lx@intercol\hfil\textbf{Uniform Test Time}\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil\textbf{Non-Uniform Test Time}\hfil\lx@intercol\\ &&\mathrm{UB}&\mathrm{LB}&\mathrm{UB}&\mathrm{LB}\\ \hline\cr\textbf{Optional-test}&\textbf{Single}&2\,\mbox{\cite[cite]{[\@@bibref{}{DurrErlebachMegowMeissner2020}{}{}]}}&1.8546\,\mbox{\cite[cite]{[\@@bibref{}{DurrErlebachMegowMeissner2020}{}{}]}}&2.316513\,\mbox{\cite[cite]{[\@@bibref{}{LiuEtAl2023}{}{}]}}&1.8546\,\mbox{\cite[cite]{[\@@bibref{}{DurrErlebachMegowMeissner2020}{}{}]}}\\ &\textbf{Multiple}&2.9271\,\mbox{\cite[cite]{[\@@bibref{}{GongChenHayashi2024}{}{}]}}&\phi\,\mbox{(\lx@sectionsign\ref{sec:LB})}&3.2361\,\mbox{\cite[cite]{[\@@bibref{}{GongChenHayashi2024}{}{}]}}&\phi\,\mbox{(\lx@sectionsign\ref{sec:LB})}\\ \hline\cr\textbf{Obligatory-test}&\textbf{Single}&1.585\,\mbox{\cite[cite]{[\@@bibref{}{DogeasErlebachLiang2024}{}{}]}}&\sqrt{2}\,\mbox{\cite[cite]{[\@@bibref{}{DogeasErlebachLiang2024}{}{}]}}\longrightarrow\frac{3}{2}\,\mbox{(\lx@sectionsign\ref{sec:LB})}&1.861\,\mbox{\cite[cite]{[\@@bibref{}{DogeasErlebachLiang2024}{}{}]}}&\sqrt{2}\,\mbox{\cite[cite]{[\@@bibref{}{DogeasErlebachLiang2024}{}{}]}}\longrightarrow\frac{3}{2}\,\mbox{(\lx@sectionsign\ref{sec:LB})}\\ &\textbf{Multiple}&2\,\mbox{(\lx@sectionsign\ref{sec:alg})}&\frac{3}{2}\,\mbox{(\lx@sectionsign\ref{sec:LB})}&2\,\mbox{(\lx@sectionsign\ref{sec:alg})}&\frac{3}{2}\,\mbox{(\lx@sectionsign\ref{sec:LB})}\\ \end{array} Table 1: Summary of results Related Work. The framework of scheduling with testing can be studied under both stochastic and adversarial uncertainty. In the stochastic setting, testing reveals random job characteristics, and the objective is to minimize expected costs [ 13 ] . This probabilistic approach differs from our adversarial online setting, which originated with the optional-test model introduced by Dürr et al. [ 7 , 8 ] . In this model, jobs have known upper bounds, and the scheduler decides whether to test them to reveal actual processing times. For a single machine with uniform test times, Dürr et al. established tight bounds for makespan minimization and provided competitive algorithms and lower bounds for minimizing the sum of completion times. This was later extended to arbitrary test times by Albers and Eckl [ 1 ] , with subsequent algorithmic improvements by Liu et al. [ 14 ] via a refined amortized analysis. The broader paradigm of explorable uncertainty has also inspired related oracle-based variants [ 6 ] and applications in other online optimization domains, such as speed scaling [ 3 ] .