The Completion-Threshold Framework for Obligatory-Test Scheduling on Multiple Machines
2026-06-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a scheduling problem where jobs need to be tested before their true processing times are known, and the goal is to minimize total completion time on multiple identical machines. They identify a key measurement, called completion-threshold quantities (T_X), that helps understand the tradeoff between testing unknown jobs and processing known ones. Using this, they prove new stronger lower bounds on how well any deterministic scheduling algorithm can do with multiple machines, improving upon previous results for a single machine. They also provide a simple scheduling method that performs within twice the best possible total completion time.
online schedulingobligatory testingcompletion timedeterministic algorithmsmachine schedulingcompetitive ratiolower boundslist-schedulingmulti-machine schedulingprocessing time
Authors
Kao-Chuan Liang, Ya-Chun Liang
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.