Non-Clairvoyant Scheduling with Progress Bars
Authors: Ziyad Benomar
Romain Cosson
Alexander Lindermayr
Jens Schlöter
Venue: NeurIPS 2025 spotlight ()
Keywords: online algorithms
competitive analysis
scheduling
algorithms with predictions
non-clairvoyance
Primary area: theory

Abstract: In non-clairvoyant scheduling, the goal is to minimize the
total job completion time without prior knowledge of individual
job processing times. This classical online optimization problem
has recently gained attention through the framework of
learning-augmented algorithms. We introduce a natural setting in
which the scheduler receives continuous feedback in the form of
progress bars—estimates of the fraction of each job completed over time.
We design new algorithms for both adversarial and stochastic progress bars
and prove strong competitive bounds. Our results in the adversarial case surprisingly
induce improved guarantees for learning-augmented scheduling with job size predictions.
We also introduce a general method for combining scheduling algorithms, yielding
further insights in scheduling with predictions. Finally, we propose a stochastic
model of progress bars as a more optimistic alternative to conventional worst-case
models, and present an asymptotically optimal scheduling algorithm in this setting.

Non-Clairvoyant Scheduling with Progress Bars
Ziyad Benomar
Romain Cosson
CREST, ENSAE, Ecole Polytechnique. Fairplay joint team, Palaiseau, France
Courant Institute of Mathematical Sciences New York University
rc6142@nyu. edu
ziyad. benomar@ensae... fr
Alexander Lindermayr
Jens Schlöter
Simons Institute for the Theory Computing
Centrum Wiskunde & Informatica (CWI)
UC Berkeley
Amsterdam, The Netherlands
alex. www.iieeraarrrbeeeeeel.........e
J www.sschloter@rr......
Abstract
In non-clairvoyant scheduling, the goal is minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization problem has recently gained attention through the framework of learning-augnnn augmented algorithms. We introduce a natural setting in which the scheduler receives continuous feedback in the form of progress bars estimates of the fraction of each job completed over time. We design new algorithms for both adversarial stochastic progress bars and prove strong competitive bounds. Our results in the adversarial case surprisingly induce improved guarantees for learning-augmentee scheduling with job size predictions. We also introduce a general method for combining scheduling algorithms, yielding further insights in scheduling with predictions. Finally, we propose a stochastic model progress bars a more optimistic alternative to conventional worst-case models, and present an asymptotically optimal scheduling algorithm this setting.
Introduction
We study the fundamental problem of scheduling single machine: there n jobs, each with processing time Pj. available at time 0, and the goal is to preemptively (i.e., can be interrupted and resumed later) schedule them minimize the sum of the completion times. the clairvoyant (or offline) setting, i.c., when all processing times are known to the scheduler, the optimal solution is schedule jobs increasing order of processing times. This rule is known Shortest Processing Time First, or as Smith's 's rule in reference to 1956 paper that first formalized it [Smi56]. In many practical applications, such as operating systems or high-pen performance computing, the scheduler does not know the jobs' processing times upfront. This restriction led to the model of non- non-clairvoyant (or online) scheduling, where the scheduler learns about the processing time of a job only when this job is completed. For this online problem, introduced in the early 90s (FST94, SWW91, MPT94], classical algorithm Round-Rood Robin, which simply allocates the same amount of computing power to all unfinished jobs. It approximates the optimal solution within factor (called competitive ratio) of 2, and is well-known that this value is optimal among non-clairvoyamt algorithms [MPT94].
The clairvoyant and non-clairvoyant models have stark contrast in their information model, which the amount of information (feedback) the online algorithm receives over time. In this paper, introduce and study a model of scheduling with progress bars that interpolates between these two settings. Non Non-claine cla-ciairvoyant scheduling has already been investigated through the lens of learning- angmented algorithms (aka algorithms with predictions) [LV21, MV20, LM25b]. Therein, algorithms
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

are equipped with additional, possibly erroneous information (predictions) to overcome limitations of the zero knowledge assumption and hence improve over classical lower bounds. The goal is to establish strong performance guarantees for perfect predictions (consistency) that degrade gracefully as the quality of the predictions worsens (smoothness), and which stay bounded for arbitrarily bad predictions (robustness). This line of research studied various prediction models for non-clairvoyant scheduling, such as (partial) predictions on the unknown processing times (input predictions) [PSK18, WZ20, ALT21, ALT22, IKQP23, BP23, BP24], predictions on the optimal scheduling order (action predictions) [DIL+ EKMM24, LM25a, LLMS23). A shortcoming of these models is that they give predictions priori, hence relying only on static information such as job identifiers or descriptions. This limits their applicability in natural situations where information might initially be scarce or extremely unreliable, but where its amount and reliability increases the scheduler interacts with the system.
Given these limitations, we ask the following question: Is there an information model that allows algorithms to refine their decisions over time? Our main motivation for this question is estimation techniques such as profiling [HRB15 18, WBB+ + 17, XGWC23J, which learn about jobs as they are being executed: while initially we have no good estimate of processing times, we can expect to give improved predictions after some processing. Inspired by this, we propose a formal model based on progress bars: while processing job, we receive an estimated indication of how much percentage of the job has been completed, revealed at different levels of granularity (e.g., frequency, time, or levels of updates). Clearly, we cannot expect that the progress bar is perfectly accurate, motivating the design of scheduling algorithms for adversarial and stochastic progress bars.
1.1 Our results
A progress bar for a job j E := (1........... is formally defined as a function 9 [0. - [0, 1], that non-decreasing and satisfies (0) and sp(1) the displayed progress when job j has actual progress of x, that is, it has been executed for fraction æ of its total processing time. The value (o can be interpreted as an estimate of x at any time during processing. In particular, we can model clairvoyant scheduling as having accurate progress bars Sj : x + x for all j (cf. Figure la), while the non-clairvoyant setting corresponds to uninformative progress bars 9j x + 1xx 1) (cf. Figure lb). We say that the progress bar y has granularity g E N if it is a step function taking g values besides 0 and 1.
For all x E [0, 1). (x) represents
From the scheduler's point of view, after allocating ej S. Py units of computing to job j. the displayed progress of job j. denoted by (eg))) = y (5/ps), provides an estimate of the actual progress of job j. equal to 2,y 5/pg.- It can also be interpreted as a prediction :y e,/ (e,),) on the job length, which usually refines as more computing is allocated to that job.
The problem of scheduling with progress bars has a flavor similar to decision with bandit feedback [LS20, BC12]. Indeed, the scheduler faces an explore-exploi tradeoff, where it is incentivized to prioritize jobs for which the progress bar seems to progress faster (exploit) but must also allocate some computation to other jobs refine estimates of their processing times (explore). Like in the bandits literature, the study of scheduling algorithms with progress bars lends itself to both an adversarial analysis and to a stochastic analysis. Specifically, we study three models of progress bars, which we describe in detail below.
1.1.1 Single signal progress bar
We first consider progress bars of granularity 1. In this case, the progress bar stays at O until a fraction 3, of job j has been processed, at which point it jumps to a displayed progress of a (where 3, may differ from due to inaccuracies). Finally, it jumps to 1 upon completion of the job. Formally,
b (z(z) 1 < < 1) 1(x
Accurate signal. We start by investigating the case where B5 = a for all jobs j. This is equivalent to each job emitting a signal exactly after it has been processed for an a fraction. This setting interpolates between the non-clairvoyant (a = 1) and clairvoyant (a 0) regimes. This setting has
'There is minor technical difference: while we learn in the clairvoyant setting about p5 at j's arrival, we need to process for > 0 fraction to deduce pj via the accurate progress bar (P) +

---

1
1
0.75
0.5
0.25
0
0
1
0
(1)
0 0 g
(a) Clairvoyant setting
(b) con-clairvoyant setting
(c) Untrusted progress bar with y
(d) Stochastic progress bar with =
Figure 1: Visualization of different progress bars. The horizontal axis represents the actual progress x a job and the vertical axis represents the displayed progress (zxx).
been studied before different context [YT17, GKL+25). We show in Theorem 2.1 that simple deterministic algorithm is (1 + a) comppttitvee This result appears concurrently also in [GKL+
Consistent, robust and smooth algorithm. Next, we assume that the signal emission time can be inaccurate, i.e., 3, # a. We demonstrate in Theorem 2.4 that for all p (0, 1), there is deterministic algorithm that is (1 + coonsistt,, (1 + -robust, and smooth. The parameter tunes a tradeoff between robustness and smoothness in this algorithm. We also demonstrate in Appendix E that the consistency and robustness bounds can be extended to the more general setting of having m parallel identical machines.
Improved ceesstency-robusteee tradeoff. In Section 2.3, we discuss how technique yields an algorithm for scheduling with job length predictions that improves over the best consisteney- robustness tradeoff in prior work, achieved by time sharing [PSK] 18]. Interestingly, our algorithm is the first to actually use the numerical values of the predicted job lengths for robustification, while time sharing is black box technique, which also applies to permutation predictions [LM25a].
1.1.2 Untrusted progress bar
We then consider the more general model where the progress bar has granularity g E: N, displaying intermediate progress levels (1) < ... al9). We denote for convenience ( = 0 and a (
3(0+1) 1. For each E [g]. the displayed progress increases from (h-1) to (h) when the actual
progress reaches k/a) (cf. Figure 1c for an example). Hence, we formally define for all x E [o, 1]
9+1
p2(x) = E -a (h-1))) 1(x 2 8/²)
General combining algorithm. To address this setting, we study a more general problem: how to combine multiple scheduling algorithms. [EKMM24] introduced randomized strategy to combine multiple permutation predictions, achieving performance close to that of the best prediction, up to regret term. In Theorem 3.1, we extend and improve their approach to combine arbitrary scheduling algorithms under mild assumptions, even if the algorithms rely on different types of predictions, none at all. In particular, this combining strategy a progress bar with granularity as a collection of g progress bars with granularity I cach, and combining different instantiations of the algorithm for the single-signal setting.
be applied in our setting by interpreting
Implications in learning-augmentedd scheduling. With our strategy, we can combine Round-Robin with any 1-consistent algorithm in any prediction model, giving a consistency of o(1) and robustness of 2 + o(1) for broad class of scheduling instances, where the maximum job processing time is small enough compared to the optimal objective value. For this class of instances, our result significantly improves upon previously known consistency tradeoffs for non-clairvoyant scheduling with predictions, and substantially narrows the gap between the prior ofate-of-the-art algorithms and the lower bound on the mansissency-robustten tradeoff established in [WZ20].

---

1.1.3 Stochastic progress bar
Finally, we study stochastic model of progress bars with granularity N. Specifically, the bar can display g + progress levels (M/s-1)ohhsgt) and jumps between these levels according to Poisson point process with rate g. Let 8
S 3/00 denote the first g points of this process,
0g min(1, for all h E [g]. and g(a+1) 1. An example is given in Figure 1d. Formally,
g+1
Σ h=1
1 1 (1)))
g ++
Our algorithm follows a repeated explore-then taplore-then-comii approach: it runs Hound-Robing until the progress bar of job reaches certain threshold of order (g2/33,, then commits that job until completion, and then it resumes the exploration phase with Round- Robin on the remaining jobs. We show in Theorem 4.2 that the competitive ratio of this algorithm is 1 + Ogg -1/3), and we prove in Theorem 4.3 a matching lower bound of 1 + (gg-1/5) on the competitive ratio of any algorithm.
1.2 Notation and organization
There are jobs j E [n] with processing times Pj such that ... S Pn. We consider scheduling with arbitrary preemptions, so a scheduler can process a job for an infinitesimal small amount of time. The optimal objective value is given by OPT = v (n i + 1)p; [Smi56]. The processing that job j has received until time f, also called the elapsed time of job j. is denoted by (t). The completion time Cj of job is the earliest time t that satisfies et(t) Pj. The total completion time of a scheduling algorithm is equal to ALG Σÿ-1 Cj. For two jobs j. E [m]] we denote by d(i,)) the delay that i incurs to j. i.e., d(i,j) = ex(Cg)) We have (see, e.g., [MPT94]):
-i=1(t
ALG = Σ Pj + ΣΣ d(i,j) + d(j.).
We present our models and theoretical results in Sections to 4, and then present our empirical results in Section All proofs are deferred to the appendix.
Scheduling with untrusted signal
We begin by studying a simplified scenario in which the progress bars have granularity 1. We assume that there exists some known a [0, and unknown 3, E [0, 1] for all j E [m]] such that (p (z) 1 (3, < < 1) + ((r = 1). This model is equivalent to assuming that each job emits
signal after being processed for an unknown fraction By of its total processing time.
2.1 Truthful signals
First, we assume that each job emits a signal exactly after being processed for fraction a of its total processing time, i.e., Bj a. The following theorem describes an optimal algorithm in this setting. Theorem 2.1. Consider the algorithm that runs Round-Robin over all jobs, and whenever job emits its signal, it is granted preferential execution, i.e. it is run alone until completion. This algorithm achieves a competitive ratio of 1 + a, which optimal even for randomized algorithms.
2.2 Untrusted signals
Then, we suppose the signal can be inaccurate: each job j emits its signal after being processed for a fraction 3, [0, 1] of its total processing time, instead of the announced We show how to adapt the previous algorithm to maintain robustness under such deviations. A natural baseline is to naively trust the predictions, running the previous algorithm for truthful signals described in Theorem 2.1.
Lemma 2.2. Blindly following the signals yields a total completion time of at most
+ 1J+a)PT++
Σ
(n i): a)p: +
Σ(p: -p:) 1(3pp) B.p.). i<j

---

The theorem above shows that the algorithm is (1 + consissett which is the best possible consistency in this setting, and decomposes the additional cost into two components:
Signal timing error: The first sum captures discrepancies when signals are received. Interestingly, this term can be negative if signals arrive earlier than expected, potentially improving performance in the absence of scheduling inversions.
then be interpreted as the total inversion error, which is standard error term in learning- augmented scheduling [LM25a] and captures the increase of the objective due to scheduling jobs in non-optimal order.
Inversion error: The second
The inversion егror in the previous lemma can be upper bounded using the f--orrm of the signal timing errors Di=1 | al, resulting in the following bound.
Corollary 2.3. Blindly following the signals yields total completion time of at most (1 a)OPT (1+ ()) Σ |3, alp:
The advantage of this algorithm is that it is straightforward, as it does not even depend on a. However, it lacks robustness: its performance degrade arbitrarily given adversarial predictions. A standard approach of prior work on "concurrently" with Round-Robin (PSK18). Specifically, the consistent algorithm is run rate while hound-Robij is run at rate 1 - X, yielding a consistency of 1+a/> and robustness of 2/x. Nonetheless, our goal is achieve the perfect consistency 1 + while minimizing the robustness.
scheduling to address this issue is to run the algorithm
Robust algorithm. We propose the following refined strategy: when a job emits its signal at time t, it receives preferential execution for (1/a et);()) units of time, which is exactly the remaining processing time if the prediction were accurate. If the job finishes during this phase, Round-Robie is resumed. Otherwise, the job is excluded from Gound-Robiin until all other jobs have reached the same processing level or have been completed, alternated with preferential execution when some job emits its signal. In other words, our algorithm runs Shortest Elapsed Time First (SETF) for exploration phases. SETF always processes equally the jobs that have received the least amount of processing so far. This refined strategy corresponds Algorithm below, parametrized with p
While this strategy improves robustness, it suffers from critical weakness: britleness [EADL24, BP25]. That is, its performance degrades abruptly even for arbitrarily small errors in the signal emission times. We formalize this claim in Proposition A.3, and further illustrate it with experimental results in Figure 2a.
To mitigate this, we introduce Algorithm which satisfies all desired criteria, i.e., perfect consistency, robustness, and smoothness. This algorithm can be reinterpreted smooth algorithm from Lemma 2.2 (recovered for + 0) and the robust strategy described above (recovered for 1). Our main result Algorithm I is Theorem 2.4.
interpolation between the
Algorithm 1: (1 + cconsisttnt,,, (1 +1+ 1/ap) robust algorithm
1 J +- [n]
2 while J do
Run SETF on J.
if a job j emits its signal at time t then
Run job j alone for (1/ap - 1) et(t) units of time. if job completes then
J J
Theorem 2.4. Let p E (0, 1). Algorithm is (1 a) coonsisttn,,, (1 + 1/pa) and if E (0, 1),
2n
ALG s a)PT)
+ p(1 p)
Σ |8, 1aa-app:-
In Appendix E, we show that these ideas can also be applied in the more general scheduling environment of m parallel identical machines. This setting requires tackling additional hurdles, and give (1 + ccoosissttntt and (1 1/a)- -robutt algorithm preliminary proof-of-concept.
5

---

Interestingly, while most learning-ause augmeeted algorithms exhibit ronsissenee--rruusteesss tradeoff, our algorithm reveals a smoothness robustness tradeoff, governed by the parameter p. particular, for / 1, the algorithm achieves robustness + +//.. We also prove lower bound on the robustness of any (1 + -c-osissttttt algorithm for this problem. The construction is inspired from [W720].
mooothness-robustness
Theorem 2.5. a (0,1), then any (1 + a) consistent deterministic algorithm has robustness of least + ((v7/o).
2.3 Application to non-clairvoyant scheduling with predictions
Our results for untrusted progress bars can be leveraged to design a learning- augmented algorithm for non-clairvoyant scheduling with predictions on the processing times. Specifically, if the algorithm is provided with a prediction π, of Pj for each job j E [n]. we can frame it in the setting of progress follows: we fix a parameter
bars with granularity bar jumps to level a when is processed for ax, units of time. The scheduling is then performed using Algorithm 1 with parameter for some p E (0, 1). This yields consistency of 1 and robustness of + 1/pa. Moreover, defining 33 = a Pj. the error term appearing in Theorem 2.4 becomes proportional Σ, [T Pj--
[0, 1] and simulate that job's progress
Notably, this consistency-robusine tradeoff' improves upon the best- scheduling literature. In- known algorithms in the tradeoff achieves consistency !/a and robust- deed, the state-of-the-ee
ness 1-> for x (0, 1) [PSK18], whereas, with our approach, choosing 1-A --x and consistency 1+ '[[+X]
1-A leads to the same robustness
2
p([+X)
which can be made arbitrarily close to T as p + 1.
robustuns
Furthermore, existing algorithms typically rely only the permutation induced by the predictions on the processing times, whereas our algorithm makes explicit use of the predicted values πÿ. This provides the first separation between algorithms using value-based and permutation-basee predictions, two prediction types that were often treated indistinguishably in prior work [PSK18, 88, LM25a].
3 Scheduling with untrusted progress bar
We now consider the general setting where each job is equipped with a progress bar of granularity g E N, which can display progress levels 0 (1) <
(0)) 1, with jumps between these
levels occurring for actual progress levels S 860) S... S 88.00 S 1 for all j E [m]]
naive strategy in this setting is to select a single index h E [g] and apply Algorithm using only the 1tth jump in the progress bar for each job. This yields the guarantees from Theorem 2.4 with parameters (h) and (B)()) )-- The natural question we ask is whether it is possible achieve
performance close to that of choosing the best index in hindsight, among the indices available.
3.1 Combining scheduling algorithms
To address this question, we revisit a foundational problem in learning augmented algorithms: how to combine multiple algorithms to achieve a performance close to the best among them. We approach this problem for scheduling in a general framework, which extends beyond progress bars.
Suppose we are given g algorithms A (1) ..... A99), which may leverage different types of advice or predictions. For each E [g] and for all i + j E [m]. let (()) (1, j) denote the delay that job causes to job j under algorithm (A), We assume that each algorithm A (k) has computable delays, meaning that d( (i.j) can be determined when both jobs i and j have been completed (i.e., the computation may depend on Pt, Pj. the progress bar of both jobs, and possibly other information given during the computation). This assumption holds for most standard scheduling algorithms, whether or not they use advice, since analyzing the total completion time typically relies on studying mutual delays; (in,
e.g. Round-Rofhe blindly follows the prediction the single signal model since d(i,j) can be ex expressed as a function of p., B,, pz, By (see the proof of Lemma 2.2).
satisfies ((h) (i. min (Pi, P. Note that it also holds for the algorithm that

---

Algorithm 2: Combining multiple algorithms A ..... A99) A(9) with computable delays
1 Sample m pairs (Uk, )=+)==1 (2)
2 Run jobs E {ux, Ui oi until completion in any order.
3 For all E [g]: compute a(h) = Σn (d (mx, Us) + d us)).
Let h
arg min, al)). Schedule the remaining jobs using algorithm A (h)
Our combining strategy generalizes the method of [EKMM24), which considers the restricted setting of multiple permutation predictions. Their algorithm samples m pairs of jobs at random, runs them to completion, uses the empirical inversion error to select the best-performing permutation, and then schedules the remaining jobs following that permutation. We extend this idea to general scheduling algorithms with computable delays. After completing the sampled jobs, we compute the cumulative delays induced by each algorithm this sample. We then schedule the remaining jobs using the algorithm with the lowest empirical total delay. Crucially, our approach works for any algorithms with computable delays, and is not restricted to algorithms with predictions. We give formal description in Algorithm2 2.
Theorem 3.1. Let A 3. "A.,...,A))) be any deterministic scheduling algorithms having computable 8 satisfies
A(t)
delays. Then Algorithm with (log g/2/33
9 n 5/3 (l0g g) 1/3 max P.
B[ALG] S min A (h) +
4
iE(m]
This bound immediately generalizes to random instances, or to algorithms using random parameters, as we explain in Appendix B. If max; P, o(n (53O0), then the regret term in Theorem 3.1 becomes (OPT). This condition is satisfied as soon as constant fraction of jobs have size at least Q(n mmx;; pa) for some c < 1/3, as in that case OPT = 12(n2 2- max; p:) 5/3 max; pt).
3.2 Application to untrusted progress bars
We apply Theorem 3.1 to the setting of untrusted progress bars. For each h E [g], define A (h) as Algorithm 1 instantiated with = (A), ignoring all jumps except the 1h one. Additionally, we combine Round-Robin with the family of algorithms (A(*), ), to guarantee robustness. Thus, we can set p = 0 for all algorithms (A (h) )s. which yields the best smoothness bound (Lemma 2.2). Using Lemma 2.2, Theorem 3.1, and the fact that Kound-Robin is 2-competitive, gives the following result. Corollary 3.2. In the non-clairvoyant scheduling problem with progress bars, suppose each job i emits signals after fractions s(2)) <...s S ( of its total processing time, instead of the announced (1)) s... - Then there exists an algorithm with expected total completion time most
min 22OPT, min A A(h)) )
+0 11
3/3 (logg))))))
max Pi iE(n)
he[g]
where (h) < (1) EL (o(() -a p Eis (ps -op-piill p.) p.)-1(6(()) Pj < (00) p.).
3.3 Application to non-clairvoyant scheduling with predictions
In the context of learning-un -aggeettd scheduling, Theorem 3.1 can be used to combine Round-Rohh with any consistent algorithm that has computable delays. As an illustration, consider scheduling with a permutation prediction that predicting the optimal job order. The algorithm that blindly trusts this prediction has a total cost of at most OPT Eie, (p; - P.) ([a(j) < ai)) [LM25a]. and has computable delays: for all / j. the delay that job i incurs to job j is d(i.j) = p. ((a < ai)). Consequently, both algorithms can be combined using Algorithm yielding the following result.
Corollary 3.3. Given permutation prediction o, there exists an algorithm with expected total completion time at most
min (2 (PP,, OPT + (p) 1lo(-(((())))) < <())) On/5/3 maxp:)
iE(n)
7

---

This result narrows the gap between known upper and lower bounds bounds on the consistency- robustness tradeoff for augmentedd
setting À = 1/vm implies that any (1 + scheduling. Specifically, in the lower bound of [WZ20], algorithm must have robustness at least 2 + (2/ va). In striking contrast, the best upper bound on this tradeoff from prior work is 2 ( x-X for À E (0, [PSK18], which we improved to 2 IIIx in Section 2.3. Our approach, for the first time, achieves consisteney + (1) and robustness 2 o(1) on instances satisfying max, P; ((PT))) providing first piece of evidence that near-perfect consistency and robustness could be simultancously achievable in Sarning-auggment scheduling.
Scheduling with stochastic progress bar
Model. The models studied in the previous sections may appear overly pessimistic, as real- world progress bars are not adversarial but instead provide noisy approximations of the true progress [WBB+17, HRB18, XGWC23J. To better capture this, we study a new model of stochastic progress bars that naturally fits applications in resource management and machine learning. For example, consider training neural network until it reaches a certain accuracy. The training can be seen as sequence of optimization steps (e.g., gradient descent updates) for which the number of iterations is not known precisely in advance. Yet, at any time, the fraction of the training that has been completed can be estimated from the current validation error, and from the appropriate scaling laws.
Specifically, we consider progress bars yp of granularity g E N, where we model the jumps of the progress bar by the first jumps of a Poisson process with rate g. meaning that the elapsed times between jumps are independent exponential random variables with parameter g. Poisson processes are a standard tool for modeling random event arrivals in queueing theory and related areas [Ben57, Wo182, GG96]. Formally, for j E [mi], denote by ((1) I ... S _ the first g points of Poisson point process with rate g Rt. Set (/()) min(1, B(m)) for all h [g] and afo+1) 1. We define a stochastic progress har as follows,
9+1 Σ
(2(x)
1(x 1 10
9
Remark 4.1 (Uniform progress bars). An alternative model is the one in which (
are drawn i.i.d. and uniformly from [0, 11, and then arranged in increasing order. This stochastic setting is sometimes called Binomial point process [Kal17]. because, for any x E [0, 1). the value ge(xx) is a Binomial random variable, specifically gep(z) ~ B(g.z). This contrasts with the Poisson point process model defined above, for which gyp(1) x)) is a Poisson random variable, specifically g<((x)) ~ P(rr). Both models are closely related via the well- Poisson approximation, which a classical technique in probabilistic analysis [MU17], and which essentially states that B(g, x)) and P(gx') are statistically indistinguishable for small values of x E [0, 1]. The Poisson formulation often allows for cleaner proofs, which is why we focus on this model in the theorem statements.
Connection to multi-armed bandits. Our setting is analogous to a multi-armed bandit problem with n arms [LS20], where arms can be pulled in continuous time instead of discrete rounds, and rewards are generated over time-specifically each jump of a progress bar from one level to the next is treated as a reward. Short jobs correspond to arms that emit rewards more frequently, aligning with our scheduling objective: complete shorter jobs quickly possible.
key feature of our problem, however, is that the number of jobs decreases over time, resembling the mortal bandits setting [CKRU08], In mortal bandits, algorithms typically rely on an aggressive exploration phase of the currently alive arms, followed by strong exploitation, contrasting with the more gradual apploration-exploiaatiio tradeoff seen in classical algorithms like E-greedy [SB98] or Upper Confidence Bound (UCB) methods [ACF02]. This intuition carries over to our setting in which the measure of performance is a competitive ratio: when two jobs have similar processing times, it is preferable to commit early to one of the two jobs rather than to waste time estimating which is the shortest of the two.
Repeated Cintore-ThenCCoomee algorithm. Following this intuition, we propose an algorithm that alternates between exploration and exploitation. It runs Round-Robin on all alive jobs until the
8

---

displayed progress of one of them reaches a threshold k/9+1 (for carefully chosen parameter k), at which point the algorithm fully commits to completing that job. It then resumes Bound-Robil on the remaining jobs and iterates this process. Thus, the algorithm alternates between phases of exploration (Round-Robin) and aggressive exploitation (committing to a job); see Algorithm can also seen as variant of Algorithm that ignores all except the k-th signals and where op -> 0.
Algorithm 3: Repeated Explore-Then-CCmmiii with threshold k
1 J <- [n]
2 while J + do
3
Round-robin step on J.
if 3 J (e,)(()) */o+1 then
Run job j until completion and set + J J\ {5}.
In the next theorem, we prove an upper bound on the competitive ratio of Algorithm 3.
Theorem 4.2. Let g 2 12. For l [(g/2)2/31 1. Algorithm 3 has a (expected) competitive ratio of at most 1 (12/ 1/3 3 for minimizing the total completion time with stochastic progress bar.
natural question is whether the convergence rate of O/31/3) optimal. We answer this question affirmatively, and establish the asymptotic optimality of our algorithm.
Theorem 4.3. The (expected) competitive ratio of any scheduling algorithm with a Poisson stochastic progress bar of gramularity g E N is at least 1 + 36 1/3.
The proof of this lower bound is similar to lower bound arguments for stochastic bandits, yet applied in the different context scheduling and of competitive analysis. We show that for two jobs with similar processing times, say Pl and p2 +++ 7 with T = g- 1/33 the processes e + (e) and (c) are statistically indistinguishable with non-negligible probability if means that the best thing an algorithm can do is running both jobs in parallel until a progress of т.
Morally, this
Finally, we also prove an upper bound on the competitive ratio with high probability in Appendix C.3.
Experiments
We now present empirical experiments that validate our theoretical results. In the experiments, consider instances with n = 500 jobs, where processing times are sampled independently from a Pareto distribution with parameter 1.1. Each point the figures represents an average over least 20 independent trials, with standard deviation indicated. In this section, we give short overview of our findings. An extensive description of our setup and results is given in Appendix D.
Erqpicct courettive azt0
10-15
Eayirical onupetitee endo
RR
Ale 3,2
3.0
m 10-5
Empicaal compatite
2,25
2.5
10-1
L35
Time slowing
3.5
Delayad prodictions
1.25
Cuntkning alaxciám
16P
10
10'
10
20
40
50
50
100
Grandarity
(a) Alg. for different values of p
(b) Robustification algorithms
(c) Stochastic Progress Bar
Figure 2
In Figures 2a and 2b, the predictions (TT)): are noisy estimates of the true job sizes Pt. with independent Gaussian noise: n, . NP:,, .r. Figure 2a shows behavior of Algorithm 1, with a 0.5, for various values of where signal emission times are computed as Br = max(0, min(1, T:/Ps)). As Theorem 2.4 suggests, setting / close to I improves robustness, but the algorithm's 's performance not smooth. On the other hand, smaller values improve smoothness the expense of robustness.

---

Figure 2b compares three robustification strategies: time sharing [PSK18], delayed predictions (Section 2.3), and the combining algorithm (Section 3.3). The first two use tuned hyperparameters to ensure the same robustness level. From the figure, delayed predictions appear to guarantee better robustness than time sharing, but the performance is highly sensitive to errors. In contrast, the combining algorithm requires no parameter tuning and achieves both strong robustness and consistency, while keeping good smoothness guarantees. The gap in performance between the combining algorithm and the other strategies becomes more significant for larger values of n.
Finally, in Figure 2c, we compare the performance of Algorithm (with k = 1 and k = ((g2/3)), Round-Robin (RR), and generic Explore-Thent Then-Commit (ETC) algorithm, which runs RR until all jobs reach displayed progress (g - and then schedules the jobs sequentially in decreasing order of their displayed progress. Our results show that the algorithm of Theorem 4.2 clearly outperforms the other algorithms over the full range of granularities. Moreover, the empirical competitive ratio approaches as grows, validating the bound of Theorem 4.2.
6 Conclusion and open directions
We initiated the study of progress bars in the context of non-clairvoyant scheduling. For both adversarial and stochastic progress bars, we developed algorithms and analyzed their performance guarantees. We believe that this framework is suited to other online problems and that it provides realistic perspective going beyond worst-case analysis.
Finally, we highlight two open directions. First, in the adversarial single-signal progress bar, there is gap of ((a (/3) between the upper bound and the lower bound in our analysis of the consistency- robustness tradeoff (cf. Theorem 2.4 and Theorem 2.5). Finding out the exact asymptotic tradeoff an interesting open problem. Second, in the stochastic progress har model, our results do not improve over the competitive ratio of 2 when the granularity of the progress bar is very small (specifically, for g S. 12). Particularly natural is the special setting where each job has a single uniformly distributed signal. We believe that even this minimal information sufficient to break the competitive ratio of 2, with experimental evidence suggesting that the competitive ratio could be below 5/3.
Acknowledgments and Disclosure of F Funding
We thank the anonymous reviewers for their helpful comments. RC carried out part of this work while Inria, Paris. AL was supported by the "Humans on Mars Initiative", funded by the Federal State of Bremen and the University of Bremen. JS was supported by the research project "Optimization for and with Machine Learning (OPTIMAL)", funded by the Dutch Research Couneil (NWO), grant number OCENN.GROOT.2019.015
References
[ACF02]
Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multi- armed bandit problem. Mach. Learn., (7(223))235-255) 2002.
[ALT21]
Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In STOC, pages 1070-1080. ACM, 2021.
[ALT22]
Yossi Azar, Stefano Leonardi, and Noam Touitou. Distortion-oblivious algorithms for minimizing flow time. SODA, pages 252-274. SIAM, 2022.
[BBEMI2] Olivier Beaumont, Nicolas Bonichon, Lionel Eyraud-Dubon and Loris Marchal. Min- imizing weighted mean completion time for malleable tasks scheduling. In IPDPS. pages 273-284, IEEE Computer Society, 2012.
[BC12]
Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and non- stochastic multi-armed bandit problems. Found. Trends Mach. Learn., 5-1):1-122 2012.
[Ben57]
VE Beneš. On queues with poisson arrivals. The Annals of Mathemaical Statistics, pages 670-677, 1957.
10

---

[BP23]
Ziyad Benomar and Vianney Perchet. Advice querying under budget constraint for online algorithms. In NeurIPS, 2023.
[BP24]
Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predic- tions. In JCML. OpenReview.net, 2024.
[BP25]
Ziyad Benomar and Vianney Perchet. On tradeoffs in learning- augmented algorithms. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
[CKRU08]
Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, and Eli Upfal. Mortal multi-armed bandits. In NIPS, pages 273-280, Curran Associates, Inc., 2008.
[CT06]
Thomas M. Cover and Joy A. Thomas. Elements of information theory (2. ed.). Wiley, 2006.
[2]L+222] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassil- vitskii. Algorithms with prediction portfolios. In NewrlPS, 2022.
[DIL+ Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassil- vitskii. Controlling tail risk in online ski-rental. In SODA, pages 0247-4266 SIAM, 2024.
[EADL24] Alex Elenter, Spyros Angelopoulos, Christoph Düm, and Yanni Lefki. Overcoming brittleness in pareto-optimal learning augmented algorithms. In NeurlPS, 2024.
[EKMM24] Marek Eliás, Haim Kaplan, Yishay Mansour, and Shay Moran. Baaming-augmentee algorithms with explicit predictors. In NeurIPS, 2024.
[FST94] Anja Feldmann, Jirí Sgall, and Shang-Hua Teng. Dynamic scheduling on parallel machines. Theor. Comput. Sci., 130(1):49-72 1994.
[GG96]
Robert G Gallager and Robert G Gallager. Poisson processes. Discrete stochastic processes, pages 31-55, 1996.
25) Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, and Sorrachai Yingchareonthaworchaai. A little clairvoyance is all you need. In FOCS. IEEE, 2025. To appear.
[HRB18] Muhammad Hafizhuddin Hilman, Maria Alejandra Rodriguez, and Rajkumar Buyya. Task runtime prediction in scientific workflows using an online incremental learning approach. In UCC, pages 93-102. IEEE Computer Society, 2018.
[IKQP23] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit, Non- clairvoyant scheduling with predictions. ACM Trans. Parallel Comput., 10(4):19:1- 19:26, 2023.
[Kal17]
Olav Kallenberg. Random Measures, Theory and Applications. Springer International Publishing, 2017.
[KT23]
Emin Karayel and Yong Kiam Tan, Concentration inequalities. Arch. Formal Proofs, 2023, 2023.
[LLMS23)
Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In ICML. volume 202 of Proceedings of Machine Learning Research, pages 18563-18583, PMLR, 2023.
[LM25a]
Alexander Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. ACM Trans. Parallel Comput., 2025.
[LM25b]
Alexander Lindermayr and Nicole Megow. Repository of papers on algorithms with predictions, 2025, http:/ htpp://aalee /alloitthhhsss witt-withh- predictions github. io/. Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[LS20]
[LV21]
Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. J. ACM, 68(4):24:1-244: 2021. Robert McNaughton. Scheduling with deadlines and loss functions. Management science, 6(1):1-12, 1959.
[McN59]
[Mer23]
Peter Mercer. Wallis's 's Product, pages 37-43. Springer Nature Switzerland, Cham, 2023.

---

[MPT94] Rajeev Motwani, Steven J. Phillips, and Eric Torng. Non-clairvoyant scheduling. Theor. Comput. Sci., 130(1):17-47, 1994.
[MU17]
Michael Mitzenmacher and Eli Upfal. Probability and compuling: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
[MV20]
Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
[PSK18)
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via MI predictions. In NewrIPS, pages 9684-9693, 2018.
[SB98]
Richard S. Sutton and Andrew G. Barto. Reinforcement learning introduction. Adaptive computation and machine learning. MIT Press, 1998.
[Smi56]
Wayne Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterty, 3(1-2):59-66, 1956.
[SWW91] David B. Shmoys, Joel Wein, and David P. Williamson. Scheduling parallel machines on-line. In On-Line Algorithms, volume DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 163-166. DIMACS/AMS, 1991.
[WBB 17] Denis Weerasiri, Moshe Chai Barukh, Boualem Benatallah, Quan Z. Sheng, and Rajiv Ranjan. taxonomy and survey of cloud resource orchestration techniques. ACM Comput. Surv., (002):26:1-26:444 2017.
[Wo182]
Ronald W. Wolff. Poisson arrivals see time averages. Oper: Res., 30(2):223-22) 231, 1982.
[W720]
Alexander Wei and Fred Zhang. Optimal rohustness-consistnnyy trade-offs for learning- augmented online algorithms. In NeurlPS, 2020.
[XGWC23] Yi Xie, Fengxian Gui, Wei-Jun Wang, and Chen Fu Chien. A two-stage multi-population genetic algorithm with heuristies for workflow scheduling heterogeneous distributed computing environments. IEEE Trans. Cloud Comput., 11()):144614460 2023.
[YT17) Sorrachai Yingchareonthaoonnhaai and Eric Torng. Delayed-clairvoyant scheduling. In MAPSP, pages 198-201, 2017.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract indicates the scope of the paper: Sarminn-auugeened scheduling, and describes the particular problem consider. A more formal description and discussion related work and scope are in the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
The paper presents different algorithms for scheduling with untrusted progress bars. The limitations of our algorithms are potential improvements are discussed in the paper.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions for all the theoretical results are clearly stated in the main body of the paper. All the proof' are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The paper gives all the information needed to reproduce the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The code is included in the supplementary material
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (attps://nips.. co/
oonooooo)oll)looolooollmmoommlll for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. cc/ wtc/public///e hwalliic/giies///eee /CsoeSuudmmmiicc iundbbiisse ieiinonoPiyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The experiments presented in the paper are simulations of scheduling algo- rithms with advice and do involve training or testing any machine learning models.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Standard deviations are reported in the figures
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
The experiments presented in the paper are simulations of scheduling algo- rithms with advice and do involve training testing any machine learning models. Reporting of computing resources is not necessary.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: : http///eerrrp..eeee httppppbii//tiiccccuideeeeeee
Answer: [Yes]
Justification:
Our paper respects the Code of Ethics of NeurlPS.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [No]
This paper presents foundational/theorrtiaal work in the field of learning augmented scheduling. We do not feel that any potential societal consequences of our work must be specifically highlighted.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
16

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: In general, learning- scheduling algorithms pose no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification; We do not use any prior assets. While we compare our algorithms benchmark algorithms from prior work (time-sharing), we re-implemented them for our experiments. The original papers introducing them are cited in the related work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
17

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are not used as any essential, original, or non-standard component in this research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https: pettps:/nneteee //nerrurpp.... wcc/oooeeeeccs//200000 for what should or should not be described.
19

---

A Proofs of Section 2
A.1 Proof of Theorem 2.1
In this section, we prove Theorem 2.1, which we restate below for convenience.
Theorem 2.1. Consider the algorithu that runs Round-Robin over all jobs, and whenever a job emits its signal, it is granted preferential execution, i.e. it is run alone until completion. This algorithu achieves a competitive ratio of + a, which is optimal even for randomized algorithms.
The upper bound of the theorem is corollary of Lemma 2.2, which show in the next section, noting that accurate signals imply a = 3, for all j E [n]. Hence, here we focus on proving the lower bound. The proof is adapted from [MPT94] and appears concurrently in [GKL++55].
Lemma A.1. For every E [0, 1I, every randomized algorithm that receives a single accurate signal at a has a competitive ratio of least + a: for minimizing the total completion time.
Proof. Using Yao's 's principle, we fix deterministic algorithm and consider a randomized instance with n jobs I...., n with processing times Pj drawn independently from the exponential distribution with scale 1. That is, every job has size of at least x with probability e e= and Elp,] 1.
Fix two arbitrary jobs and j. We compute their expected pairwise delay E[d(i,j) + d(j, a)] in the algorithm's 's schedule. To this end, consider for any fixed processing amount y the event & Evy) that neither nor has emitted its signal after the algorithm processed a total amount of y on both and together. Let y; denote the part of used for processing job i. Note that
P(E(v) = Plap: > yi] Plapy
vs) = e v/o
Therefore, the expected pairwise delay of and j while both have not yet emitted their signal is equal to Jo (PEE))) dy a. Furthermore, the expected pairwise delay of i and while at least one already emitted its signal is equal to
Eimin - (1) (1 a)p,Hl = (1- a) L P(p: P(p. ) x) IP(p > x) dx
1 2 a1)
Thus, E[d(i,j)++(G. 1 (1+a). Using (1), we conclude that ||[LG]| 2 n + 1i a).
We now study the optimal objective value OPT for this instance. In this scenario, an optimal schedule schedules job in non-decreasing order of their processing times. Thus, the expected pairwise delay of -1=1 3-1
and in the optimal schedule is equal to E[min(p;; H 2' Hence, E[OPT] n
We conclude that the competitive ratio is at least
n + Σラ Σ 1= 1 (1+a)
n Σラ= Σ
which approaches 1 + as goes to co, and thus, implies the statement.
A.2 Proof of Lemma 2.2
Recall that "blindly following the signals" refers to the algorithm of Theorem 2.1. That is, to the algorithm that runs round-robin over all jobs and, whenever job j emits signal, runs only this job until completion before returning to round-robin.
Lemma 2.2. Blindly following the signals yields a total completion time of most
(PP) Σ (n- () - a)p; +
Σ(rs p:) 1B3pp < <..p)) i<j
Proof. Let < j [n], pı S Pj. Recall that the algorithm processes both jobs with the same rate until one of them emits signal. Hence, the term min(B:p (8P5} describes the amount of processing each of the two jobs receive until one of the emits its signal.
20

---

If 3,p; < Byp then job i emits its signal first, when both jobs have been executed each for S.p, units of time, then executed until completion. Thus the mutual delay caused by the two jobs each other is
d(i.)) + a) = P: + 8.p. (1 a)p; + (3, a)ps
On the other hand, if B:p: > 8ypj. then we obtain similarly that
d(t,j) + d(j,t) 3,p3 + Pj
(1 a)p: -ap:) + (pj ps)
-
- (1 + a)p; + (8; -ap;; + (Pj pi)
where we used in the last inequality that B.p; 8.p-- In both cases, we can write that
d(i.j) + d(i,i) - (1 + a ); + (3 a)p; + (2j p.:pp > 9,p,).
and it follows that
ALG
Σ Pj
d(i,j) d(j.))
K
Σ
Pi
((1 + a)pp + +B: a)p: + (p) - p:) 3yp,))
Σ i=1
p: + (1+a) Σ (n - i)pp + Σ
- (3: a)p; + E(s (B:) < B.p)))
i=1
icj
$ (1+a)0PT
+
Σ (n (): - a)pp +
Σ - pp:)1 < B.p.)
1=1
{<
The inversion error in the previous lemma can upper bounded using the absolute signal timing errors, resulting in the following bound.
Corollary A.2. Blindly following the signals yields total completion time of at most
(1+ ②
(1 a)PT)
Σ
13:
-alp:
i=1
Proof. For all i < jf < Bip then
3,p, - -3:p;
Pj - Ps S Ps - Pj +
a
BiPj +
= Pj
pi
a
a
1
|8, a
3 -a alp;
a
follows that
Σ (p) (B)p( < Bpp)) - Σ
1
B3, alp, + 13, 13, alp.
10)
i<}
33 - app
a
1=1 j
n 1
13 a
1=1
21

---

We deduce from Lemma 2.2 that
ALG < (1+a)OPT+ (n (n-1) Σ
[3 0 0lp: i
3: 01 Pi
S +1+
( n
|8 Σ ==1
alp:
A.3 Proof of the brittleness of Algorithm 1 with
Proposition A.3. I 1, then for all 0, there an instance of job sizes (Py))e(n) and signal
emission fractions (3z)se(n) satisfying Σ}= |8,
al S e, for which Algorithm with p = satisfies
ALG
OPT 2
This means that an arbitrarily small error the signal emission times suffices to deviate from the consistency bound 1
Proof. Let E > 0, m 1, and 8 < Consider instance with 2m jobs, with sizes given by Pj = 1 for j I m and Pj = 1/a for j > m. For all j E [2m], let 33 a 8, so that the total deviation from the announced value is E, [8}
2md Se.
1, the initial phase is Round-Robin execution until each job has been processed for 8 units of time. At this point, the jobs with m emit their signals by definition of B3. To resolve simultaneous emissions, assume infinitesimal perturbations to ensure that signal times are distinct. These m jobs, each with size 1, then receive preferential execution one after the other, until reaching elapsed time of 3,/a 1 - 5/a. In particular, none of these jobs completed yet, their size
Running Algorithm 1 with parameter
At this stage, the second set of m jobs (j > m), each of size 1/a, have received less processing and are now scheduled using Round-Rofhe point they emit their signals and receive preferential execution, until they have elapsed time of 8/a²)) (1++1/)((-8/a)) Since no job has been completed by this time, the sum completion times incurred by the algorithm satisfies:
until they reach elapsed times of each, at which
3,ps/a = 1/a ó/22.. This happens at time m - -8/a)
ALG 2 2m m(1 + 1/a)(1 5/a) = 2m + 1/0)(1 5/(z).
On the other hand,
(m (m+j/a) mm² (2
1 1
OPT
+ o(m²)
2a
j=1
j=1
Therefore
ALG
4a
OPT 2 (1 (1-5/a).
o(1)
3a +
Note that, for a E [0, 1), we have 40.44 > 2. Hence, for sufficiently small and m sufficiently large, 3a+1
the lower bound above becomes larger than 2, which concludes the proof.
A.4 Proof of Theorem 2.4
Theorem 24. Let p E (0, 1]. Algorithm is a) consiistet, (1 + robust, and if p e (0, 1),
2n
n
ALG < a0OPPT p(1
|3, alp:
p)a²
i=1
22

---

Proof. As in other proofs, we assume that P1 S... S Pn. Let k will analyze the mutual delay between jobs i and j. depending on their job sizes and the times when their signals are emitted. To this end, we distinguish between multiple cases and, for each case prove robustness bound of the form j(i.j) + d(j, - (1 k)p; and an error-dependent bound of
pa and i < j E [n]. We
1 a - 1/k (13: alp; + 18, alp,).
+ S (1 app
Case 1 k3, S 1: Note that k3; < implies that i either does not finish during its preferential execution (k:3, < 1) or the preferential execution suffices to exactly finish (k:3, = 1). For this case, we can observe that proving d(i,,) + d(j,i) S (1 + k)p; immediately implies an error-dependent bound, just by using 33 S K
k
+(j,)) S k)pp (1 appp + (k: a)pt S (1 a)p;
(ax B.)., 1/k
(1 + a.pp + - 1
1/k (13: alp; + 18, alp;).
Hence, it suffices to show d(j,i) + d(t,j) $ (1 + k)pp We do so by distinguishing two sub-cases.
Case 1.1 Bypj 2 C2 If j emits its signal after i completes, then the SETF-part of the algorithm ensures that the delay is most d(j, i) d(i,)) S 2p, (1 k) Ps-
Case 1.2 Bip, < C;:: For j to emit its signal before completes, we must have 3,p; S Pi. The maximum delay of i caused by j d(j. i) max(k3,p, pt] I max kpt, Pil kp,, where the inequality follows from 3,P3 < p.. Note that the first term k3,P, in the maximum the maximum delay in case that j completes during its preferential execution, which is composed of delay of fJP' before j emits and a delay of (k 1)8Sp, during the preferential treatment. Since d(i, S ps holds trivially, we can conclude with d(j,i) d(i.j) I (1 k)p,
Case 2 k3, > 1 and Byp, > B.p.: In this case, i emits its signal before j due to 3,p; > 3,p-- Furthermore, completes during its preferential execution due to kB; > 1. Thus, the delay by j is only caused during the parallel exccution before i emits its signal. Hence i)j, < S.pp. Since d(i,j) p, holds trivially, we conclude d(j,t) i) + d(i,j) S (1 B:)p: I (1 k)p;. This immediately implies an error-dependent bound:
d(i.j) + d(j,t) < (1 + 3dp, I (1 + a)p: + 18+ alp:
s (1+ + 1: + 1
1/k (13, alp; + 13, - alp;).
Case 3 k:9 > 1 and Byp; S Appp this case, j emits before or at the same time (3,p, S 8.p))
and completes during its preferential execution h;;; > 1). We start with the general inequality
1 3,p, + 3ept S 13, alp; +
1 1 alpp
Pj P- P,
(2)
which will be useful below. Next, we distinguish between three sub-cases.
Case 3.1 kB, > 1: Job j is the first to emit its signal and is then executed until completion due to k: 2 1. Thus, d(i.j) = Syp, as only delays during the parallel execution before emits its signal. Furthermore, d(j, i) Pý as j finishes before during the preferential execution. Using 3,p; S 3.pp S Pt. we obtain
d(i,j) d(j.t) Byp; + + < (L k) < (1 k)p:
23

---

Furthermore, Bypy S P,p; and (2) give
d(i.j) + i() - 8,p, + Pj
(1 a)pi + - (p:) + (Dj - pi)
app:
1 18; alpi + 133 -alp
1
- a)+ + (B: - -a)p: +
<1+ + 1 _
1
|8 alp:
=
|8, alpp
a
1
< (1+ +
33 - alp; + - -18 Pp
1/k:
k ++1 1
S (1+ a)pp
(13, - alp: + 13, a pp))
a a- 1/k
where we used the second to last inequality that
1 1 k ak
a a+1sa+ s + -
which is equivalent to (ax - 2) [1+
Case 3.2 kB < 1 and k: > App;: Job j again emits its signal first and receives prefer- ential execution, but fails to terminate during the preferential execution as k33, < Since kB > S.p;. emits its signal before catching up with the elapsed time of j. and is then executed until completion. Thus j(i. p; and i) k3,,, We have
d(i,j) + d(j.)) = p3 + k3,p, S Pt + kBpp S (1 + k)p:
Additionally, it follows from kBj < 1 that
d(i,j) + d(j.)) 1) S p: + k:3pp
(1 a)p: k:3;pj opi
(1 + a)p: + (k:3pP PU) - (p: - (pp-)p;) + +pp - pp;)
(1 a)p; (1 10.-a. a)p; + (pj Pt)
S (1 + a)p: + 1-a 0
1/k (a 35)p; + (pj -p:),
where we used in the last inequality that k:B < 1 and p; S pj. Finally, (2) gives
1 0
1 |3, alp; + -18, - a pj
d(i,)) + d(j,)) & (1 + a)p, +
(a 3y)p; +
a- 1/k
a
(1 a)p; 1
2 -
- alp;
a 1/k 8 alps
++1
< (1+ + a a- 1/k (13: aap; + 18, alp,).
Case 3.3 kB, < 1 and k3,p; S Bipp In this case, the elapsed time of job reaches that of job j before job i emits its signal, both jobs are then processed equally until job emits its signal, then it receives preferential execution until completion. Hence d(i.j) ps and d(j = Bip,. It follows immediately that
d(i.j) + d(i = (1 + 3.)p S (1 k)pp
and = ((aa))(())-(aa)))((((1+(11-))0)- < (1tt)) a 1/k (1,3 - -alp, + |8, - alp,).
+ 1
From analyzing all the possible cases, we deduce that, for all values of p: S pj and Br, 3,. the mutual delay d(i,j) + d(j. i) is at most (1 + k)p, Using (1), follows that
ALG Σ ps+ Σ (((i)))+((
< Σ Ps + (1 + K)
Pr S R)OPT Σ K
1=1
24

---

which proves that the robustness ratio is at most 1 + 1/pa = 1/pa for some (0, 1].
We will now deduce the smoothness bound. To lighten the notation, denote by A, = | a p: for all é E [x]. In the case-analysis above, we have already shown the following error-dependent bound for all i < j:
&+1 (A +4,)
d(i.)) + ( a- 1/k
which yields after summation that
ALG
Σ Pr + (d(t,))+d(j.))
5-1
++1 Σ A +4,)
$ Σ
Pj + (1+ a) Σ
+
a-
1=1
ijj
j=1 1=1
k+1 < aPPT
n
Σ (n i) 1)ر,
a - 1/k
1=1
k+1
S {1+ 1/k: 1=1
A.
Finally, it holds for h 1/(pa) that
++1 1
1/(pa) +1 1 pa
a 1/k (1 (1-p)a p)a p(1 - p)a2 p(1 2
which concludes the proof.
Even for p = 1, we have no tight example for the robustness bound of Algorithm 1. The best example that we have shows that the robustness of this algorithm is in 1 1+00( (/a)a)) Thus, we leave as open question whether the robustness analysis of the algorithm can be improved.
A.5 Proof of Theorem 2.5
Theorem 2.5. Ifa (0,1), 1), then any + a)) consistent deterministic algorithm has robustness of at least + +(((//a))
Proof. Fix a deterministic a-clairvoyant algorithm. Consider an instance I composed of n jobs with unit processing times. Let t denote the first time when a job completes. We assume that 1 == é1 2 .... 2 En where Ej (t()) denotes the total progress of job j until time t. Thus, job completes at time t. We assume the algorithm does not idle, and have Σ C₁. Note that the best strategy for any algorithm at time is to finish the jobs in the order of their index as
1 61 < ... < ex- Since the algorithm is by assumption (1 compettiie,, must hold that
n(n + +1
nt
nn 1 1) e,) < ALG s (1 a (1 + a)
2
Since t = Σラ= ej. the above can only be true if
G - 1)e, S n(n + 2 1=1
(3)
2
Let >> 0 be sufficiently small. We consider another instance Ta with processing times p1 = 1 and P3 = e, + e for every job S & n. The jobs emits their signal until time as they have done in instance 4, Note that these signals may not emit after a- e-ffration of the jobs are done, which is
25

---

possible because we are in the robustness case. Thus, the algorithm processes I1 and I2 equivalently until time as it deterministic. We have for that
n ( OPT クラ-13 ej el el+ +
n (e1 (a+
ALG
Now, by considering this ratio function of e2, . subject to Σ 2== Ej = - and 2 en. note that is minimized if and only if C2 above is at least
On 4-1 n-1 for all jobs j. Thus, the
e1 2 (n 2) -1)
Since this ratio is minimized if is as large as possible, and the left-hand side of (3) is equal to n n'me,, this minimum (3) must be tight and we have that a(n 1) e1. Thus, the above is least
n n an ( + + e (n a(n + +) 1 fa(n 1)(n +
n(a(n +
Finally, choosing ((v1/0//))) implies that the robustness ratio of the algorithm is at least
n + an? an?
Ω
= -((n) ( ((V/)/))
which concludes the proof.
While our algorithm does not match this lower bound, it is possible improve the robustness by relaxing the consistency guarantee. This can be achieved by selecting parameter a' E |a, 1] and rumning Algorithm 1 with a' in place of a, using p a' a//a. Specifically, if a emits a signal at time f, the algorithm waits until the job has been processed for a' et(() before treating the signal a as emitted. This modification yields a degraded consistency of + , and improved robustness of 1 + 1/a'.
B Proofs of Section
Theorem 3.1. Let A()), ,.,,,.., (9) be any deterministic scheduling algorithms having computable delays. Then Algorithm 2 with 3 3/3 satisfies
9 5/3
B[ALG] < min A (h)
+ I
5/5 (/og/(logg)) 1/3 max P:
he(a)
iE(m)
Proof. Let PInax maX4e(m] Pt. Since E [0, Pmax] for all i E [n], the total delay caused by the first phase of the algorithm, where the jobs {uk, Uk hn are completed, is at most 2mn Pmax- Algorithm A (h) is then used schedule the remaining jobs, with a total objective value of at most A Al)) since having some jobs completed in the first phase can only improve the objective function. Therefore,
ALG A 2mn
Pmaxx
(4)
For all h [g] and i + j [n], denote by (i,) = (i. + (f. caused by jobs i.j to each other when scheduled with algorithm (h), For all h e [g]. recall that a(h) >e (dth)) (uR, vk) + (())((x) ux)) defined in Algorithm 2, and note that
i) the mutual delay
2m
E[a(h)] (E(M(() [11, n(n 1)
M (i.
j=li=1
26

---

Pmax Let Z(h) = a(h) - -[]a(h)] and h = arg min A())
It holds that
a
A (k)
Σ
M Mho (1,g)
Pi +
j=1
nnn 1) B[a(h)]
Pi
+
2m
1=1
n(n 1)
n(n 1) Z(h)
Pt +
a(h)
2m
2m
n(n
n(n - 1) a(hh))
r(nn 11 (h)
Pj
+
2m
2m
i=1
n(n - 1)
n2n - 1) 2(1²)
n(n - 1) ((h)
Σ 1=1
P: +
[[(()))]++
2m
2m
2m
n(n
1)
< A (A*)
(max ((h)) + max (-h))) hE
2m
hE[s
Combining this with Equation (4), and by definition of h², we obtain in expectation that
n(n 1)
B[ALG] S min A (h)
I3 [[ax [ + - + 2mn Pmax
2m
hEl
We have that ahh) is the sum of independent random variables (M (ug, Uk == all bounded 2p.ax]: ( (i.)) (i, + (1(h) (j, S p: + Pj < 2pmax- Thus, a(h) subgaussian random variable with variance factor ²² = Ex=1 (2Pmax 0)2 /4 mppmax [KT23]. Therefore, max, 7h) the maximum of
Let bound E[maxae [s] { and (
g subgaussian random variables all with variance factor mpnax (although not independent), hence, using the result of [KT23], we have
mmmax 7(h)] S Pmax v 2m logg
hE[g)
Similarly, we obtain the same upper bound on ( We deduce that
n² Pmax
log g
E[ALG]
min A (h) hG(a)
22m log g g 2mnn-Pmax
min (M)
n²
+ 2mn
2m
hE(a)
2m
Finally, for m = 2/ (log g) the above bound becomes
+ 9 - 5/3 (logg)))) 1/3
E[ALG] < min A (h)
Pmax
g] 4
which proves the theorem.
Remark B.I. If we are unable to compute (1) exuctly for all h after completing two jobs and
j. but can instead compute upper bound di (i, 2 ((h) j), then the upper bound stated in the theorem still applies by replacing A U0) with (1) for each h, where
(b)
Σp P
E
Σ i<3
(1.) 5 ( (1.0)
This guarantees that the combining algorithm achieves total completion time at most the minimum of these theoretical upper bounds, to the same regret term.
B.1 Random instances and randomized algorithms
The result of [EKMM24] holds with high probability. While we can also prove an upper bound w.h.p., our upper bound on the expectation is particularly useful allows an extension random job sizes and randomized algorithms, show below.
27

---

Generalization to random instances. 2/3 (logg) 1/3 in Algorithm gives
If the job sizes are random, then the same choice of m
9 + ( 5/3 (log.))
E[ALG] S min E|A 1
Elmax pil (E(n)
hE
Indeed, assuming that the job sizes are random, we obtain by Theorem 3.1, conditionally on the job sizes, that
(a
9 5/3 (log (log 9/8
E[ALG Pi.....PPl min A (M) hE[9l
max Ps ic|n]
hence, using that [/minne(s) A(h] - min [A)(") we find
9 4
E|AGG] < min E[A [h)
5/3 (log
E|maxp:] (E(n]
kEls
For example, if the job sizes are independently sampled from an exponential distribution with parameter 1, then
9 (n 5/3 log (log 1/3
E|ALG|
< min E[A (h)) hE[s]
+
4
min E[A (h) + (B[OPT)
Generalization randomized algorithms. The result can be easily generalized to algorithms using random parameters that can be sampled before starting the execution of the jobs (for e.g. choosing random permutation). Assuming that each algorithm A (A) uses random vector ((h) as parameter, that can be sampled before starting the algorithm, then the bound of Theorem 3.1 gives
E[ALG| g()) "(".,......)))
_.0)] S min A (E(M)) NE(9)
7 n 5/3 (logg)
1/3
max Ps
sE(n]
hence
[[ALG] s Elmin A (E()))
9
5/3 (logg)
1/3 max p: sc(m)
n
hE
4
9 5/3
min E[A E[A!
n1
(log
1/3 max Pi
kE
4
sE(n]
C Proofs of Section 4
C.1 Proof of Theorem 4.2
Theorem 4.2. Let g 12. For k= ((9/))2/3 Algorithm 3 has a (expected) competitive ratio of at most 1/3 for minimizing the total completion time with a stochastic progress bar.
Proof. For all j E [n], let T denote the total processing time allocated to job j by the point at which its progress bar reaches the threshold 9+1
&
Let i + j. If < Tj. then both jobs i.j are executed with similar rates until job i emits its signal, after which executed until completion. Therefore, d(i,j) pt and d(j,i) T.
Assume that P1 S ... S Pn. and let < E [n]. holds that
d(i.j) d(j,)) i) (p++))1(6 7,) (p. + +T)) <T)) p;1(7, T +,, < T.) (TL(T 17yl(7 <T)) p: min min(m,, (2) p.) <n),
28

---

Recalling that B[rs] = k/p; = &
g ps, and by independence of T3 and Ty, we obtain directly that
Elmin(Tr, ry)1 - pp) = pi, and it follows that
j) + d(j, 1) - +
+ (ps/ps-1o - 1)P(T) Ti)
<
+
+ (ps/pi-11 1)
b: - 1122
(1 x2) k-1
x2)x-1
dx
(5)
v /T(K: -1)
Py-m1 Pytpi
k
k- 1/2
(r ( 1) {" (1- x²) -²))-11
<
+
sup r21
dxy
dx
(6)
9
V -
h
k
1/2
1
$ 1
+
9
V 1))
h-2
k
2 +
Vk 1
where (5) follows from Lemma C.I taking m = k - 2 3. (6) is obtained immediately by taking Ps/Ps, (7) follows from Lemma C.2, and the last inequality holds because k 4.
Finally, by definition of k, we obtain that
E[d(i.)) + d(j. () < 1 + (g/2)2/3 +2 1
2 + 3 (g/2)1/3 g
12
1/3
=1+
(4g) S
1+
p. and it follows from (1) that
g
g
E[ALG] = Σ
Bld(i.j)
1=1
j=1
1=1
f
Pt
Pi
12
1/3 n
ΣΣ jl
Ps S OPT +
12 1/3
OPT.
g
i=1
Lemma C.1. If are independent random variables, following respectively Gamma distributions with parameters (m + 1, f1) and (m + 1, (2)). then
P( < <T) m 1/2
(1 (1-x2) x22) dr.
11-P2
Proof. For (1,2), the probability density function of Tq is
M m++ m!
I LE (0,
1
hence
000
m+1
P2 m+
IP(72 < <T))=
1 e Mtt
nhe e
124
dudl
00
m!
m!
m+1
P22 m+
t -
e tdudt
m!
m!
(HiH12)
m
2m+1 (mn+ dtdu
(m!)²
(m
f2m+1
dt du 11 + u2u
m
(m!)²
(M) + H22)2m+11
(M1l1)) )
4
(1o0
gamtle-'dt du.
(m!)²
J
(#1
2m=2
29

---

The inner integral corresponds to the Gamma function evaluated at 2m + 2, which equals (2m - 1)! as 2m 2 is integer, hence
P(22 < T1) (2m + 1)!
(21 m- L. (m!)a
2
(M) + M2u) 2m++2 du
Making the substitution hence
x
Jan taza
2,1
1, we have that do
201122 du and in +uza
x²
(m++wau)
(2m + 1)!
1/2
P( < T1)
(1 x x dx
(m!)²
4th
1 PItM2
Finally, using a well-known inequality on the central binomial coefficient [Mer23], we obtain that
(2m + 1)! (m!)²
2m
4t
(2m + 1)
S (2m + 1) VTm
and it follows that
m + 1/2 P(22 <TT
(1 - x²) m dr
mm
22
Lemma C.2. Ifm 3, then it holds that
(r 1) / x2-=
sup r11
dr
dx
5 m
Proof. With a variable change a
++ we obtain that
(r 1) [' (1 (1-x²) v
2u [[¹ (11-2 21- dx
sup r2
dx do)
sup ue(0.1)
2u Define for all E 10,1) 1) the function f(u) I-u St (1 (1²) th da. We will show the upper bound
separately for 1/2 and u < 1/2
Upper bound for large u. Let u > 1/2. Then, (uu can be simply upper bounded as follows
1 1- u2) [ dr 2u u²
2u
[(u)
With an immediate derivative analysis we have that u + 2u(1 u2)m mm is decreasing on /2m+1 1). In particular, it holds that V2m++I for u = 1/2, which gives
1/2 for m 3, hence + 2u(1 u²)m e maximal on [1/2, 1]
Yu 2
f(u) S 2u(1 u²) S (3/4)
(8)
m
Upper bound for small u. Consider now u S 1/2. It holds that
S. (1- - x2) do =n
/ ma² dr < -mm ma² dx
T. mz²
dx
2mn )u
00
2mxe
ma² dr
e ma?
2mu
hence
2u
mu²
1
m2²
f(u) <
sup
1
2mn
m
/
30

---

m 1-t
t b
attains its maximum on [0, 1/2 for bm
=
1
2
m.
hence
e e mm
2
2
m
xc
sup (0.
1
1 tm
2
2
m
1
m
and we deduce that
Vu $
f(u)
S
1
m
1
(9)
Combining (8) and (9), we conclude that supue((.1) f(u) 1 m-1
C.2 Proof of Theorem 4.3
We start by stating two classical results from information theory on the Kullback-Leibler (KL) divergence and total variation (TV) distance.
Proposition C.3 (see e.g. [CT06]). The KL divergence between two Poisson random variables is bounded as follows
DKL(P(A), P(W)) = Alog 2 - (A - :) (A (1-1)
where we used for the inequality Vx 2 -1: In(1 + x) S..
Proposition C.4 (Pinsker's inequality, see e.g. [CT06]).
(rr(P(A),P()) & (K((()))))))))
We now apply these results Poisson random variables with specific parameterization. Lemma C.5. Let T. Rt,, we have
DKL P gT
and by Pinsker's ' inequality, the TV distance between the two distributions is bounded by / 19r3..
Proof. Using the Proposition C.3 on the divergence between Poisson random variables,
+ S gT
DEL (P(g)), S gr
where we use Vo 2 0: 1#I 1-
Lemma C.6. Lett R. We consider two Poisson point processes X and Y, with fixed rates. We denote by ( E N the value of the process X at time and by X X(5 T) the value of the process on the interval [0, r), i.e., X(5 7) [0, N. Then, holds that
Drv 7), r)) Drv(((
Proof Sketch. Any coupling of X(< 7) and Y(S 7) induces coupling of ( and Y()). Thus, Dry (X (()) S Drv (X r), Y( T)). For the other inequality, consider a coupling (X, Y) of random variables such that X ~ X(r) and Y Y(r) and P(X * Y) Drv (Tv)(((),
well as U1, U2.... a list of uniform random variables in [0, r]. Then define
X(t) = #(i E (t) # (1...., 1}: U4 < t).
U, $ t), and
Note that if X = Y then, forall 7, = Y(). Also, it is standard observation that X
[0, + X(1) and E [0, - are two coupled Poisson point processes with the desired intensities. This shows the reverse inequality Drv(X(5 (
r)) Drv (X)(()))
D
31

---

Lemma C.7. Let T E (0,1). Consider an instance with two jobs {1. 2} with processing times [], We say that scheduling algorithm A has a preference job 1 if an elapsed time of is attained on job 1 before being attained on job 2. Let q be the probability that A has a preference for the longest job. Then, the competitive ratio of A is at least
9 3
2
1+
9
Proof. For the instance considered, we always have OPT for the longest job, then ALG 2 3 + 27 (consider the two options: either the algorithm goes and finishes the longest job first, or the algorithm finishes the shortest job first but was delayed by the longest job). Denoting by the probability that the algorithm has preference for the longest job, thus have B(ALG) 2 3 + (1 + g)r. Therefore, the competitive ratio is at least
the algorithm has a preference
ALG OPT
3 (1 +1+07 DT
2 1 2 7 (1 (1-3) (
1 37 (1-37) 2 + ST T
E
7
where we used Vo 2 -1 I+s 21-2 x and S 1.
Lemma C.8. Consider the instance with two jobs {1. of processing times (1,1+77 assigned at random (i.e., P((pI.22) = (1, +.1++7) = =1/2 and P((11.P2) = (1 + T,1)) (1)) = 1/2). For any scheduling algorithm A (deterministic the longest job is at least equal to 1/2 d, where d Drv (P(g), P ((1 +
randomized) the probability q that A has preference for
Proof. We consider X the Poisson process of the shortest job (rate 1) and X the Poisson process of the longest job (rate 1/(1 +T). We consider two pairs of Poisson point processes on [0, T]. with rates and T further denoted by (X x²) and (X X+) that are coupled in way such that under event A, with P(A) = 2d, we have X = X and XL = X Note that this coupling can be defined by considering two independent couplings of X and X and of X and X letting = (Pvgg( PPl(g)),P((g/(() P(gr/(1 (1++1) +))), and using the union bound.
We then introduce the random variable B E (S, L} saying if job is short (S) or long (L). Note that B is sampled independently at random from all the other random variables. We also introduce the notation S L and L S.
The variables X2). corresponding to the progress bars of jobs 1 and 2 until elapsed time of T. are obtained from (B, x x by letting xx) = (XB X xB"). ). Any scheduling algorithm A induces a (possibly random) function f such that f(X1. X2) E (S, L} which outputs $ if was preferred by algorithm A or L 2 was preferred by algorithm A. The probability that the longest job by algorithm A is preferred is equal to
q= XIx .x")= B=).
(10)
Conversely, the probability that the shortest job is preferred is equal to
1 1- ([ x²) B),
= -P(B.x ,B Bº),
(11)
where we used the fact that (B, XS, xxx) has the same law as (B", xS,, xx))
We now condition on the event A, of probability 1 22,, for which can use, X XB XB XB
and thus f x f(x 8B), which implies
B ((L(A)L(f(X*) x B²)) = E(1(())((({8'' x88= = B²))
(12)
We conclude by noting that the left- hand side is smaller than q by (10) and that the right-hand side is greater than 1- 1-g q 2d by (11) and a union bound. We get that,
9 S 1 2d
and thus,
9 2 1/2 d.
32

---

Theorem 4.3. The (expected) competitive ratio of any scheduling algorithm with a Poisson stochastic progress bar of gramularity g E I is at least 1 + 369 1/3
7/2 S 4' We consider the instance com- Proof. Let T = - which satisfies V 22202- 2
1/3
1
posed of two jobs {1, 2 of lengths permuted at random from {1,1+ 7). By Lemma C.8, the scheduling algorithm has preference for the longest job with probability q 2 2 d, where (Tv((((g),, P(gr/(1 (/0r/(1+T)))) +T)) satisfies d S V29T', 3, by Lemma C.5. Thus, by Lemma C.7, the competitive ratio is at least g
12T 2T+++ IT, where we used q Z 1 and
C.3 Bound with high probability
In this section, we study the tail risk of the competitive ratio of our Algorithm 2. While high- probability bounds for the competitive ratio relatively, this approach was also recently investigated by [DIL++24] for the ski rental problem. We start with two classical concentration lemmas on Poisson random variables and on Poisson processes.
Lemma C.9. Ler À R and e E [0, 1]. For X P(A), we have that
P(X 2 (1 +J)) {h((t), where hi(c) = e²
S <cx((-2/3).
(1 e)lte
iee S expl-=e/11
P(X S 1/(1 +) S h2(e)) where h2(e) (++))
Proof. These bounds are also known as multiplicative Chernoff bounds for Poisson variables, and well-documented, see e.g. [MU17, Th. 5.4].
Lemma C.10. Let 9 E N. p E R and E [0, Consider Poisson point process X(.) of rate i.e., stochastic process such that + X (1) is increasing and any time L X(1) ~ P(pp). Then, consider T = X- xg) = it E R (t) 2 g). We have,
1
(1++2 S 52ep((="0//)
P
(13)
1
where the probability is taken over the randomness in T. We shall also call ja the estimator of
Proof. First, we bound,
1 9
9
P
p <
=
1
TT
1 + EP
9
P
X
29 29)
1 1 E P
9
P
P
1+ 29
< h1 /e
< eep((=eg)
Then, we bound,
P P (1 e) 9
>> (1+ e)
P
1
= P x (1 )) < <9)
/1
= P(P((1 + ()g) <g),
< h2(e) < exp(-èg/7).
33

---

Theorem C.11. The Repeated Explore-then-Cone algorithm with threshold k S 9 has competitive ratio bounded by
k g
- 3c +
(14)
with probability at least 2n
for any E [0, 1].
Thus for a > 0, in the regime where
//alog
< 1, taking k = g2 leads to a competitive ratio in ga/s
1 +
Valogn g-18
with probability at least 0 +
Note that unlike in Theorem 4.2, the high-probabilltty competitive ratio scales with n, in contrast to the expected competitive ratio, which remains independent of n. This difference arises because the begh-probability guarantee requires concentration bounds that hold for each job j E [nx]. We thus expect that a granularity that increases (logarithmically) with g is needed to obtain high probability bounds in such regimes.
Proof. We consider jobs ordered by processing times p1 ....
S Pn- For j E [n]. we write 14y = 22 and denote by E [0. Pil the instant at which the k-th signal is observed for job j.
We shall focus on the the event E in which Vj E [n] : μj E
1 (1 + E) 1/
We note that by
union bound, and by applying Lemma C.10, we have that P(E < 2n exp( exp(-<kk/7).
We now bound the competitive ratio under event E. For all jobs j. we note that π T is a (1 e) estimate of Pj. We also decompose the completion time Cj as follows (1) the time spent finishing Pj (2) the time spent doing round robin on other arms, which equals Σizy min T;, T, (3) the time
spent finishing other jobs Dirrer, (p: T.). We can also equivalently decompose follows (2') the time spent on jobs finished before j. Eisr, <r, Ps and (3') the time spent on other jobs that will finish after j. Ex.LT Tj- We start by bounding the contribution of (3').
|n > T
1i + (T, 7 2
min
T2
j=
i=
j=1
(1 + c) k
2
pp
j=1 i=1
n j-1
$ 2(1 + c)
P
< 2(1 + <) OPT.
(15)
We then look at the contribution due to (2') under E, and we denote by a the permutation for which the values of Ta) ordered To(1) To(n).
Σ J=l HITKTT
Σ pi S (1+))
Σ m (1+E)
To(s)
A=1
< (1+
Pr
where the last inequality comes from Vj To() < (1+ under event E, since at least j elements Therefore, the combined
in {T; : E [n]] are smaller than (1 + <)p; (specifically " TT).
contribution of (1) and (2') is at most
Pr + Σ
Σ
51
(16)
1=1
j=1
34

---

We conclude by assembling (15) and (16) that, under event E, the competitive ratio is bounded by
(1 --=))²= + +) k
k
- 1 + 3e +
g
The last claim of the theorem statement follows from taking = va log assuming that this value is in [0,
D Experiments
We give more detailed overview of our experimental setup and results. Unless stated otherwise, we consider instances with n = 500 jobs, where processing times are sampled independently from Pareto distribution with shape parameter 1.1. This distribution is commonly used in literature to model job sizes scheduling problemmss [PSK18, LM25a, BP24].
Algorithm 1, robustness vs smoothness. In the first set of experiments, we compare the perfor- mance of Algorithm I with a fixed parameter a 0.5 and varying values of p. As established in Theorem 2.4. the parameter controls the tradeoff between robustness and smoothness. Predictions are generated as described in Section 5.
The two figures below illustrate the ratio of the algorithm's 's cost to that of OPT as a function of the parameter o, where o² denotes the variance of the generated predictions. Results are shown for E (10-15, 10-5, 10-3 10-1). The left figure displays this ratio for a E [0. 150). while the right figure presents the
metric logarithmic scale for E [5 10 10%).
As shown in Theorem 2.4, all values of p ensure the same level of consistency, namely 1+ = 3/2. However, larger values of p improve robustness at the expense of smoothness. This tradeoff is particularly evident when comparing P 10 15 with = 10-1 For instance, the left figure illustrates that with p 10-1, the performance ratio increases abruptly from the consistency bound of 1.5 to a higher value of 2 for moderate values a.. This effect becomes even more pronounced for larger values of p. specifically, for p the algorithm exhibits brittle behavior, as formally established in Proposition A.3. Larger values of ensure a better smoothness, hence a better overall performance when the prediction error small, but weaker robustness guarantees, attained when the prediction error is important. The robustness values can be compared more easily in the right figure.
2.75
3.5
Empirical competitive ratio
p 10
2.50
Empirical competitive
3.0
p 10
2.25
p 10
2.5
p
2.00
1.75
15
p
10
2.0
1.50
10
p 10
1.5
50
100
150
10a
10
10a
10a
Error parumeter
Error parameter
Figure 3: Algorithm with different values of p. Figure 4: Algorithm with different values of p. n 500, a E [0, 150)
n = 500, E [5 10-1,109]
evaluate and compare various robustification strategies, which are time sharing [PSK18], delayed predictions (Section 2.3), and the combining algorithm (Section 3.3). shown in Theorem 3.1, the performance of the combining algorithu incurs a regret term that diminishes as the sample size n grows. To highlight this behavior, compare the three robustification strategies for different values of Predictions are again generated according to Section 5, and the hyperparameters of the time-sharing and delayed-predicttonn strategies chosen to guarantee the same level of robustness
Robustification strategies. In the second set of experiments,
The figures below reveal that for different tested values of n, using delayed predictions yields better robustness the considered instances of job sizes. However, this strategy lacks smoothness
35

---

compared to time-sharing. for n = 50, the combining algorithm performs similarly to time-sharing However, as increases, the difference between the two approaches becomes more apparent. Notably, for n = 1000, the combining algorithm achieves nearly perfect consistency (ratio approaching 1) and robust performance on the tested instances. A key advantage of the combining algorithm is that it automatically balances consistency and robustness, without requiring manual tuning of hyperparameters to adjust this tradeoff.
50
= 500
1000
Capprical compeea co00
2.50
2.50
2.50
2.25
2,25
2.25
2,00
2.00
2.00
1.75
1:78
1.50
staring Delayed prodictions
Papprical
Time during
Enptrcal
Time sharing
Delaved predictions Combining algentt
Delay ed predetions
1:25
Combining alponthm
1.25
1.25
Comboning sigenthin
1.00
1.00
1.00
40
60
100
Faro parmittr
Fmoo parmmcttrr
Emur poramcier
Figure 5: Robustification strate- Figure 6: Robustification strate- Figure 7: Robustification strate- gies, for n2 1000
gies, for n = 50
gies, for n 500
Stochastic progress bar. For the stochastic experiments, which are given in Figure 2c, we average over 50 instances. For each instance, and for each considered value of g, we sample for each job independently progress bar signals, and then simulate the algorithms.
E Single Untrusted Signal on Multiple Machines
In this section, we provide preliminary results on the non-clairvoyant scheduling problem with a single untrusted signal on multiple identical machines. In this setting, we are given m identical machines. At any time f, each of the m machines can process most one job, and each job j can be processed on at most one machine. Using the possibility of preempting jobs arbitrarily often, the machines can simulate the parallel execution of multiple jobs with lower processing rate. More precisely, we can re- re-interpret the problem in the following way: At each time f, we assign rate R with 0 R I to each not yet completed job j. The assigned rates have to satisfy Eje(n) Rj m (for the sake of convenience, we assume that already completed jobs have rate of zero) to not exceed the processing capacities of the machines. Note that the assigned rates do not actually specify on which machine to schedule the jobs. This is without loss of generality as can McNaughton's wrap-around-rule [McN59] to transform these rates to an actual schedule that processes any job at any point in time on most one machine. In this formulation of the problem, the total processing that a job j receives until time (also called the elapsed time of j at t) is given by ey(t) = Jo RŞ dt'. The completion time Cj of a job j is still the earliest time l' with e, (1') 2 Pj. and the objective remains to assign rates to minimize Σド=ı Cj. As the result of this section, we prove the following theorem.
Theorem E.I. There is a (1 + -coocniistt and (1 + ) for non-clairvoyant scheduling with a single untrusted signal on parallel identical machines.
The theorem shows that the consistency and robustness of Theorem 2.4 for 1 translates to the setting of identical parallel machines. Questions concerning the smoothness and brittleness remain open for future work. To show the theorem, we first give an algorithm and afterwards separately prove consistency and robustness.
Algorithm J = f1...., n be a set of n jobs such that P1 <... S Pa. We consider the following algorithm, which can be seen as variant of Algorithm that replaces SETF with Round- Robin. The algorithm maintains two job sets E and S and a FIFO queue Q. At any time, the algorithm ensures that every unfinished job is either in E or in Q. The set S Q is the subset of the first (at most) m elements of the queue. In the beginning, we set E + J. At any time t. we assign the following rates:
(i) Schedule every job j in E at rate R2- = de == min (m - (S)/ af a job j E emits a signal at time I, set Pj +- ()()), remove j from E and enqueue it to Q in the next time step.
36

---

(ii Schedule every job in S at rate 1. If a job has been processed for p3 a)/a time steps while being in S, remove it from Q and add it to in the next timestep.
(ii) If a job is completed. remove from or
For fixed instance and the algorithm's schedule, we denote by E,, S, and Qt the sets E, S and Q at time I. Note that Q₁ U2 \ Er, where U, denotes the set of unfinished jobs at time 1.
In the same way as in Algorithm 1, the algorithm gives preferential execution to jobs once they emit their signal (cf. Step (ii)). The queue Q contains all jobs that currently receive preferential execution (S n Q)) or already emitted and still need preferential execution (Q 5). Since we schedule on m machines, at most m jobs can receive preferential execution at the same time. Hence, the S contains all jobs that currently receive preferential execution. The set E contains all jobs that have not yet emitted their signal and all jobs that emitted their signal but did not finish during their preferential execution. These jobs are processed in a Round Robin manner all machines that are currently not used for preferential execution (cf. Step (i)). contrast to the single machine setting, the preferential execution of jobs does not necessarily mean that no jobs in E are executed at the same time: If [S] < m, then m |S] machines are not used for the preferential execution of the jobs in and can be used for Round-Robe execution of the jobs in E' instead (cf. the rates in Step (i)).
E.1 Consistency
The goal of this section is to show the following lemma, which proves the consistency bound of Theorem E.I.
Lemma E.2. Iflll signals are emitted correctly, ALG S (1 + a) OPT.
To this end, fix an instance with job lengths PI..... Pr. and fix the algorithm's schedule assuming that all signals are emitted correctly, i.e., 83 for all j E [n].
Define for every job the (possibly empty) set ((() = (j E [n] E E Nx1 =j= k: m) le m, E + .... Note that in the optimal shortest processing time first (SPT) schedule, the set μ(E) contains the jobs that are executed after job l on the same machine as job Hence, the
optimality of SPT implies
OPT =
Σ
Pj
Pi REJ:JEN(()
Σ
(17)
JEJ
For every time and every job j E J, we define the following values:
8jt = 1[j U. (,,, i.e., 8yt indicates whether job j does receive preferential execution at time 1,
di j E U, S. A de E S j E u())), which indicates whether neither j nor job that is scheduled before the same machine j in SPT receives preferential execution at I and
A. = min Sel, m] min \ Syl. m 1Se1]. which is the number of machines that are used for preferential executions time l.
Let == maxje[n) C2 denote the time horizon of the algorithm's schedule. We write d, = S0 die dt and s, = f šyr dt. Using this notation, we start by giving a first bound on the algorithms objective value. To this end, we characterize the job completion times as follows.
Lemma E.3. For every job j. it holds that C₁ I d, + (1 (1-a)(p; + Eee Pe).
Proof. Let < T be the latest point in time before j enters the set S, i.e., before j receives preferential execution for the first time. Since we assume accurate signals, will complete during its preferential execution within (1 aa), time units. Thus, C₁ = t' + (1 -a)p,-
At any point in time < l', either d,. = 1 or some job l E St with j E (({)) is receiving preferential execution (using the definition of dje and that j E S, by choice of (!). The maximum amount of time during which jobs l with (x() receive preferential execution is a)) Σtersen()) Pe, again
37

---

using that in the case of accurate signals each such job receives preferential execution for (1 a)pp
time. Hence, t' I d + (1 - a) EeE:JEn(e) Pe and, therefore,
Cj =t + (1 a)p; - d + a)(p;
pe). (EJ:jEu((
Σ
This upper bound on the job completion times and the characterization of OPT in (17) immediately give
ALG = C
dj
+
a)
Σ
Pj
+
Pi (EJ.JEN(()
AE(n]
jE(m]
jEJ
S
Σ jEIn]
+ -1- a1-)
Hence, it remains to bound Eje(n) dj by 2a OPT to prove the consistency of (1 + a). To do so, continue with the following auxiliary lemma, which allows replace EjE(n] d, with Eje(n 8y So A, dt in the inequality above.
Lemma E.4. At any time t S T it holds that Σje(n) 8jt dj 2 A.-
Proof. To prove the statement, we first make the following two observations
1. Every job j E U, \ S. contributes a value of exactly one to the left side of the inequality only if there job E j. E p(f). Hence,
Σ JEIN]
Syt d i e U. \ B6 Se: p()))
2. The algorithm completes the jobs in order of their indices. To see this, fix two jobs with Pj < Pr. By definition of the algorithm, the two jobs are processed with the same rate until emits its signal and is removed from E and added to Q. Since j is added to Q before i, the job j will enter the set earlier than job i. Hence, the preferential execution of j starts earlier than the preferential execution of job and, using Pj < Pt. is also shorter. Since completes during its preferential execution, this implies Cj < C. For jobs j, with argue in the same way that they enter Q at the same time. By using the same tiebreaking rule in the queue Q and in the job index order, we can achieve that the algorithm finishes the jobs in order of their indices.
P: Pj.
assume that S; = (ki + 1..... 1e + |S|| - 1} and U, \ S, = {k + [St]..... n) for some E [m]. Therefore, for U, \ S, with k m j S min j - m E S.. Note that if & + m > n. there are no such jobs. Thus,
Since the jobs complete in order of their index by the second observation above,
every job
+ [S,] 1} holds that j μ(i m.) and
Ki E U, \ S, 38 E Sx E n(()}
min
+ |s, 1) min (n + 1, k m) +
= min[[U,] - 1, mm + |S,] - 11 min (0m((UU))) [U2) m]] +1
(min([U, \ m) +(S))) Um, S.l. (., + (. A,-
Using the first observation from the beginning of the proof,
conclude with
Σ 85 dzt > 10 E U. \ S. EE S.: m())) A.- JE(n]
38

---

As argued above, Lemmas E.3 and E.4 and (17) together imply,
S A dt + (1- a)-T)OPT.
ALG
jEIm
To conclude the proof of the consistency case [Lemma E.2), it remains to upper bound Eje(n] 83 Jo for A dt by 2a OPT, which do with the following lemma.
Lemma E.5. Let RR((RR)( Tye()) denote the total completion time of the Round Robin-produced schedule for the instance characterized by the processing limes {orp1,..., ..p)).......... Then,
. -R(((op)setm)) S 2- (PP((p))5)E)) = 2a OPT, and
. *RR((ap)(setm)) E)E(n) 83 - dt.
Proof. The first claim, RR((op))jejn) < 2 OPT((oP;))Emn) 2a OPT, follows because Round-Robin is 2-competitive [MPT94] and because scaling all processing times by the same factor does not change the structure of an optimal schedule, hence only scales the job completion times.
For the second claim, we consider the Bound-Robile schedule S, for the instance [apj)sefa and the schedule Sr, which is the schedule computed by the algorithm without the preferential execution. That is, we take the algorithms schedule for the instance (py Jeem and replace all preferential executions with idle time. The latter is equivalent to, any time changing the rates of jobs S from Ry to Rt O. Note that ST is a valid schedule for instance {opp J Je[mi since the accurate signals imply that ST processes every job for exactly op; time units. The objective value of schedule Sy for the instance {aps |Ejm] is exactly Σ}E(n] Cj(Sr) = EyE(m) 8j. as 8j is the point in time at which the algorithm completes the first a-fraccion of job j. Here, we use (S) denote the completion time of job j in schedule S for instance {ap; {apr)emm) On the other hand, the objective value of Sn for the instance (opy)sen) is exactly Eje(n C,(S,) = RR( (R((up;)eet)) Our strategy for proving the second claim of the lemma is to show that
Σ - CC((s)) - /-" dt,
(18)
jEIN]
JEIn
which then implies the second claim the lemma.
To show that (18) indeed holds, we consider the series of schedules S,, 0 O S T, for the instance {apy) se(n), where each S; is defined as follows:
ii) Define (S,) to be the set of unfinished jobs in schedule S, at time t'. For every time t' and every j E Up Up (St), define R. qr- Recall that ge is the rate that the jobs in Up \ Se receive time t' in the algorithms schedule for the instance (p, (pe]s and, thus, also the rate that the job j receives time 6' in schedule ST.
Note that this definition implics (S.) = Ue \ Qr for all t' < t, as Se operates on instance {ap, Jjjju] using the same rates the algorithm uses the full instance, which means that Up. \ Qe contains exactly all jobs that have not yet completed an a-fraction of their processing time.
(ii) For every time 1> and every job j E Ur it holds that R2 (S.) = min (r (S))) That is, the sub schedule for the sub interval (t. T] uses exactly the
rates.
Intuitively, for any 0 < < T, the schedule S; uses the same rates as Sy during [0.t] and uses Round-Robin during (1. Let T C [0, denote the set of points time with 0, T that additionally contains all times t in (0. at which the rates in any of the schedules Sy change. For all t T (0). let max(t' E T t' t). We conclude the proof by showing that
Σ C,,) - Σ C,(S,-) f: A di JE(m]
(19)
jE(n]
39

---

holds for all t E T O, which the implies (18) and, thus, the lemma.
To this end, consider arbitrary T {0} and the corresponding t_ In the following. ef (S) denote the elapsed time of at 6' in schedule S. By definition (see (i)) the schedules S, and S use the exact same rates during [0, [- Hence, all jobs have the same elapsed time at time t in both schedules, i.e., ej (S:) = ej (S,-) for all j E [nx]
Next, consider the interval (t f). By definition of T, both schedules do not change their respective processing rates during (t ,t). Using (i), this also means that both schedules process the jobs in U, S, during the entire interval. Thus, schedule S processes exactly the jobs j E Ue \\ S with rate
min(lu. \ S. l.m)
10,- \ 15t11
whereas S; processes exactly the jobs j E U-- \ S with rate
min(lU, S |S,
min [
A 10,
U/- S1-1
U/- [
S
Av Thus, e) = = - Jh= 13,13,-7
dt' for all j U-- 14-\S, SS-
Finally, after both schedules S, and St- execute round-robin with the only difference being that the elapsed time in Si- are already farther advanced than the elapsed times in S.. Since the difference in the elapsed times is the equivalent to the round-robin schedule in S,- after f ( de' This means that the completion times of jobs j E U, \ St- in schedule S, are the same in S.- but delayed by dt'. We can conclude with J U, 18,-1
for all jobs in U-- \ St-, the round-robin schedule in S, after t
Σ -
Σ C)(S-)+
Σ (c18-)) f(
Av 10/- S
dt'
19,
Σ C2(S)-) + Ar
jEIN
which implies (19) and, thus, the lemma.
E.2 Robustness
In this section, we prove the robustness bound of ALG S (1 + 1/a) OPT. To do so, we heavily rely on the following lower bound the optimal objective value, which is mixed bound of the standard volume lower bound and the fast single machine lower bound.
Lemma E.6 (Mixed lower bound; Lemma 9 in [BBEMI2]). For minimizing the total completion time of jobs with processing times p1 I ... I Pr. on m parallel identical machines, given partition (1) (2)
Pj Pj S Spj for every job j, it holds that
(2) S ОPT.
1=1
Before we prove the robustness bound, recall that T is the time horizon of the algorithm's schedule and define T" the earliest point in time with |Ur=| I m. Starting from TV. the number of alive jobs in the algorithm's ''s schedule is at most the number of machines, which implies that the algorithm processes all remaining jobs with the maximum rate of one until they complete.
Lemma E.7. For every a e (0, 1] holds that ALG < (1+1/a) -PP..
Proof. In order to later apply the lower bound on OPT of Lemma E.6, we first split the processing times P, of the jobs j E [n]:
40

---

Let = =h0 E Sy]] dl' denote the amount of processing that j receives at times / with j jED St. That pf is the amount of preferential execution that j receives.
I
Let =T 1 Ee] dt' denote the amount of processing that j receives after T" while being in E. Note that after T", the job will be executed with the full rate of one even if it is in E, as the number of alive jobs is at most the number of machines.
Finally, let p Pj ps. Pj denote the amount of processing that j receives with rate strictly less than one.
Next, recall that dr is the rate at which all jobs in E, executed at time t. Observe that &: (m (t]1/|Eal holds for all / S T" by definition algorithm and since [U,] m by choice of TV. Therefore,
1 F2
4t
S
(20)
Ext
for all < T'. This allows us to derive first upper bound on ALG:
T
[e dt ['
ALG
1Ue]
dt
IU, Ee|dt
J0
T
[eel dt + /-
dt
+
|Ua dt
Edl
1=T
T
T"
|
Σ pJ + (" U Fe
n
|
dt
dt +
J0
m
m
j=1
2
Σ R. K.F
Σ
dt +
SS: Eel
dt + Σ DI + 1 U0e Eil
JO
J0
3=1
2
T" |Sel ||e
F + / T
9t 1[k: E Ed] dt
dt + Σ
Pj
U0 Edldt
1
1=1
2 k=1
SS |E dt +
Σ
P5 +
1U
Eel
(21)
1=1
To further upper bound (21), we first focus upper bounding the sum of the two integrals in (21), which we rewrite as follows:
T
S
+
Uve dt
m
T
[Sel
Ed
T
JU, E, /' 1[s, = U, F. \ E,J dt.
dt
1[S, Ç U, F.)
m
Note that at any time when S, Ç U, \ E, it must hold |.,] To see this, recall that S, is defined contain the first up-to m elements Q: U. Fr (see the definition of the algorithm). Hence, S, does not contain all clements of Q., then it must contain elements. Thus, the above is equal to
41

---

T'
|S&] |E
dt + /
T
|1c m
dt + /
T
1ss, 3
U,)
Ed] 10, Ed
1[s, = U, \ Ed IU \ Ed dt
m
1
1
T
L[S: cU \ Ed - 10 \ Ed Edl-1S//d dt + S/² |Sal | dt
[Sa] B-
dt + m 0
11
1
|Sa] -5,111111 dt + m {"
1
( dt + '-" dt
JU, \ Edl |
1
|S|| |0 dt + / |f
m
0
R
16 + AjEeeea Σ
(22)
For job j. let tj be the time it enters set S. If there is another job j that is unfinished at time t then we can observe eg (tz) S et,t)): ): In case & has not yet entered S at ty. both jobs have been processed with the same rates during [0, t2), which implies et,t,) = (x,t) On the other hand, if l entered S earlier, then Ry 2 Ry for all t' <t, k either has the same rate as j (if E Up Se) or receives preferential execution and has larger rate as (if k: E Sy)). This implies e eg(1g) S en From eg(4)) S < (x(4),, we get ps: == e;(1y) S (x,())) S Pk- By definition of the algorithm, j receives preferential execution for 1-a Pj I 1-a - p& time units. Thus, j is part of set S for at most 1-a Pk time units. This implies
1-a l [ E S Ut
Pk.
a
Furthermore, since p So L St dt holds by definition of p we also get
h 1[ E S.As E Us] dt S p
Plugging these two inequalities into (22) yields
Sepl
EE
di
I0 \ Et
IbES I S IKE + Σ p)
m
Pk
f=1k=
j=1
k=
j=1
To conclude the proof, we can plug this inequality into (21):
2 n m
T"
S
EEl
ALG <
dt
+
+
U \
E.l dt
m
j=1
k=1
j=1
n
2
n
n
n
R
Pk
Pk
+
Pk
0
m
m
m
j=1
1=1
1=
j=1
j=1
j=1
1
1
OPT
(pk
+
Pk
Pk
a
m
1=1
j=1
a
< (1+ OPT.
OPT + OPT
Here, the second inequality uses Lemma E.6 with the partition pj
(1) = p3 and p. 0. The third
(2)
inequality we use Lemma E.6 once with the partition v + (2) = (r + 13 ) + Pf Py and once
with the partition p3 + p2( 2 p < pj-
42


Reviews:
[{"review_id": "dDYfp1b1ex", "reviewer": "Reviewer_wQQL", "summary": "This paper considers online scheduling problems where job sizes are unknown a priori but estimations about their remaining processing times are gradually revealed and refined. Online non-clairvoyant scheduling has been extensively studied in the literature. Recently, there has been a flurry of activities in online scheduling with predictions. Unlike these works, however, this paper studies the setup in which the scheduler starts with limited information although it is possible to get a better understanding via the means of progress bars. The paper considers three different progress bar models, for which efficient competitive algorithms are designed.", "questions": "- Can the framework of progress bars incorporate recent online machine learning schemes, such as multi-armed bandits, scheduling with testing, and queuing bandits?\n- Progress bars allow more flexibility in comparison with scheduling with predictions. Is it possible to compare them in a more formal way?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- This paper introduces a novel framework for online scheduling via the idea of progress bars. The framework is closely aligned with modern machine learning systems, where the decision-maker can obtain more refined information by analyzing more data sets. The paper proposes three models of progress bars, for which efficient algorithms have been devised. \n- The paper provides strong theoretical guarantees in terms of strong competitive ratios that depend on the parameters of progress bar models.\n- Numerical experiments demonstrate the computational performance of the algorithms.\n\nWeaknesses\n- As opposed to non-clairvoyant scheduling with predictions, the framework of this paper seems qualitatively different. However, formal comparisons are missing.", "was_revised": true, "final_justification": "I had questions regarding the connection to the existing work on scheduling with prediction and learning systems. The authors have addressed my questions. In accordance with this, I raise the score.", "rebuttal": "We thank the reviewers for their interest and careful reading. As observed by the reviewer, the paper introduces and studies three models of progress bars, specifically: \n1. Single-signal adversarial progress bar (Section 2) \n2. Multiple-signal adversarial progress bars (Section 3) \n3. Multiple-signal stochastic progress bars (Section 4) \n\nThe adversarial models (1) and (2) have strong connections to *learning-augmented algorithms* (question 2), whereas the stochastic model (3) is more closely aligned with the *online learning* literature (question 1). We provide some further details on these connections in response to the reviewer’s questions. \n\n**Comparing the setting to algorithms with predictions (Sections 2 and 3).** Sections 2 and 3 of the paper are initially motivated by the *algorithms with predictions* literature (see lines 28-46). This literature has, for now, investigated scheduling problems under two main types of predictions: \n- *permutation predictions* (e.g. [PSK18]), where the permutation is an estimate of the ordering of the jobs’ processing times, \n- *processing time predictions* (e.g. [LM25a]), where the predictions are an estimate of the processing times’ values. \n\nThese predictions are always provided to the scheduler along with the problem instance before the scheduling begins. Our progress bar models offer a strictly richer framework, where predictions typically refine over time and depend on the scheduler’s actions (see lines 63-66). We describe in the paper formal connections with classical models. The connection with processing time predictions is discussed in Section 2.3 (lines 196-208), where we rederive (and slightly improve) previous results. The connection with permutation predictions is discussed in Section 3.3 (lines 253-268), where we derive an algorithm improving upon previous results in a specific range of processing times. \n\n**Relation to bandits and bandits (Section 4).**  While there does not seem to be an immediate reduction between our setting and the bandit settings evoked by the reviewer, the problems appear to be closely connected. In particular, the scheduler relying on stochastic progress bars faces an explore-exploit tradeoff where it is incentivized to prioritize jobs for which the progress bar seems to progress faster (exploit) but must also allocate some computation to other jobs to refine estimates of their processing times (explore) (see lines 67-70 and 294-306). One crucial difference, however, is that we aim for a competitive ratio (i.e., multiplicative guarantee) rather than a regret (i.e., additive guarantee), in line with the literature on scheduling and online algorithms. Another (more superficial) difference is that our setting is in continuous time, whereas time in bandit problems is usually discrete. We note that the proof techniques in Section 4 draw inspiration from those in the bandits literature. Specifically, the lower bound (Theorem 4.3, proved in Section C.2) uses the fact that two progress bars are informationally indistinguishable (for a sufficiently long time) if their processing times (and thus, the rate of their reward) are sufficiently close. This argument is similar to those of [LS20, Chap. 15] or [BC 12, Sec 2.3] giving minimax lower bounds for stochastic bandits. The problems of scheduling with testing and queuing bandits will also be mentioned as related work."}, {"review_id": "OtKYNppaC5", "reviewer": "Reviewer_FqMT", "summary": "This paper introduces a novel model for non-clairvoyant scheduling enhanced with progress bars. The proposed framework interpolates between non-clairvoyant and clairvoyant settings by providing online feedback about job completion percentages, simulating real-world scenarios like system profiling or machine learning training. Three models of progress bars have been studied, including single signal progress bar, untrusted progress bar, stochastic progress bar. Besides, this paper combines worst-case competitive analysis with insights from learning-augmented algorithms and stochastic modeling. The authors design algorithms for each model and prove competitive ratio bounds. They also show how combining multiple scheduling strategies can improve performance and robustness.", "questions": "* Can the algorithms be applied to job scheduling scenarios with online, time-varying job arrivals?", "limitations": "This paper does not have any negative societal impact.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths.**\n1. This paper presents a novel and natural model (scheduling with progress bars) for incorporating dynamic feedback into scheduling, which seems reasonable in some real-world scenarios. This broadens the algorithmic design space for the learning-augmented job scheduling problem.\n2. The assumptions are well-justified and analyzed in both stochastic and adversarial settings.\n3. This paper achieves an improved tradeoff (over time-sharing) compared with the SOTA learning-augmented scheduling algorithms.\n4. The theoretical analysis is well-founded and clearly structured, which I appreciate.\n5. The algorithm *Repeated Explore-Then-Commit* is intuitive and well motivated.\n\n**Weaknesses.**\n1. The new algorithm design is motivated by real-world phenomena (e.g., profiling and ML training in which multi-round progressive information can be obtained), but not evaluated using real-world job traces.\n2. The empirical performance of the combining algorithm appears to be unstable and only shows clear advantages when $n$ is large. This limits its applicability, as it is uncommon for a large number of jobs to be queued on a single machine, particularly when such jobs, like those with progress bars, are typically ML training jobs discussed in this paper.", "was_revised": true, "final_justification": "I will keep my score as 4: borderline accept.", "rebuttal": "We thank the reviewer for their interest in our work and for reading and assessing our paper carefully. In the following, we comment on weaknesses and questions raised by the reviewer.\n\n**Weakness:** \nEmpirical performance is only advantageous for large $n$. We agree that our empirical experiments for the combining algorithm for $n=50$ (Figure 5) are not very stable (i.e., high variance). However, we emphasize that the average performance is still slightly better than previous methods, which are also unstable for a small number of jobs.\nFurthermore, we remark that for a very small number of jobs, the empirical and theoretical performance of a non-clairvoyant algorithm (without predictions) is already much better; e.g., the competitive ratio of Round-Robin is $4/3$ for $n=2$.\n\n**Question:**\nAlgorithms for online job arrival. All of our algorithms can also be adapted to handle online job arrival and to minimize the sum of completion times. This is because our algorithms are based on local time-independent decisions. In the analysis, one then typically needs to account for release dates by charging the sum of release dates against an additional OPT, which usually results in an increase of the competitive ratio by at most 1. This is a classical technique for both clairvoyant and non-clairvoyant algorithms, see e.g., Schulz & Skutella “The power of α-points in preemptive single machine scheduling”, 2002, or Lindermayr & Megow, “Permutation Predictions for Non-Clairvoyant Scheduling”, 2025. We see a potential for relevant future work for online job arrival when minimizing the total flow time (that is, completion time minus release time). We will comment on these facts in the camera-ready version."}, {"review_id": "iS1tzF33W4", "reviewer": "Reviewer_AbAQ", "summary": "The paper considers the single machine non-clairvoyant scheduling to minimize the total completion time with progress bars. All jobs are available at time 0 with an unknown job size. As a job is being processed, estimates of the job's progress are received by the scheduler as progress bars, allowing for informed decisions. The progress bars may be inaccurate, meaning that they may misreport the actual fractions of the processed job. Thus, this work falls within the field of algorithms with predictions, where the algorithm is expected to use predictions so that 1) the performance is near-optimal when the predictions are perfect (consistency) and 2) the performance is bounded under arbitrarily bad predictions (robustness). The distinction of this work is that the progress bars (i.e., the predictions) are received in the process of scheduling, contrasting the existing works where predictions are static and received upfront. The authors considered various settings of the progress bars and gave solutions for each: single signal progress bars, progress bars with multiple levels, and stochastic progress bars. For each setting, a consistent and robust algorithm is proposed. Experiments were conducted to validate the proposed algorithms.", "questions": "1. Regarding Line 204, the claimed contribution of improving upon the state-of-the-art seems a bit oversold. The parameter alpha must be chosen arbitrarily for the results to hold. Can you please justify this point?\n\n2. How are computable delays used in the proof of Theorem 3.1? Corollary 3.2 requires the algorithms to have computable delays, which were not shown. This may affect the correctness of the corollary. Can authors explain this point? The validity of the correctness may affect my evaluation. For example, if the result is not correctly proved, my evaluation may be lowered.\n\n3. Line 341. It is not clear that the delayed predictions have performance which is highly sensitive to errors. It seems that the performance deviation is small. Can you please explain this?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Scheduling with predictions continuously arrived at the scheduler is a novel setting. This setting is practical so algorithmic advances along this dimension are valuable.\n\n2. The problem of scheduling with progress bars was thoroughly studied under adverbial and stochastic settings. The results are rich.\n\n3. The paper makes meaningful connections to other fields, including the classic non-clairvoyant scheduling with predictions and multi-armed bandits.\n\n\nWeaknesses:\n\nThere are two major weaknesses and a few minor ones identified. The first major one is that some statements feel like over-selling the contributions, and the second is that elaboration and clarity are needed around the computable delays.\n\n\nOverselling contributions:\n\n1. Line 204: The contribution of improving upon state-of-the-art seems a bit oversold. The parameter alpha needs to be able to choose freely for the result to hold. It is not clear if the parameter alpha can be chosen freely. It is at least not explicitly stated so.\n\n2. Line 267 claims that a near-perfect consistency and robustness could be simultaneously achievable, but it is a bit oversold as it requires specific problem instances, e.g., max_i p_i = o(n^{-5/3} OPT).\n\n\nComputable delays:\n\n1. The need for computable delays is not explicitly in the proof of Theorem 3.1. What would happen to which part of the proof if the algorithms do not have computable delays?\n\n2. Corollary 3.2 requires algorithms (A^{(h)})_h to have computable delays to use Theorem 3.1. This was not shown, which may affect the correctness of the corollary. Are mutual delays of these algorithms functions in progress levels alpha and beta?\n\n\nMinor issues:\n\n1. Line 241: typo OPT = \\Omega not \\omega.\n\n2. Line 612: formula 2mn p_{max} is missing.\n\n3. Line 617: all with variance factor m p^2_{\\max}.\n\n\nDespite the issues identified, I have an overall positive feeling about the paper. The contributions are sufficient for NeurIPS, conditional on that the Corollary 3.2 is correctly proved, where I have a few questions in the Question section.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time, effort, and feedback on our submission. We address their questions and comments below.\n\n**Question 1.** In the context of scheduling with progress bars in Section 2, the parameter $\\alpha$ is indeed part of the problem definition and cannot be freely chosen. Nonetheless, our results can be applied to the setting of non-clairvoyant scheduling with predicted processing times $(\\pi_i)_i$, provided as inputs. Indeed, we can choose any $\\alpha \\in [0, 1]$ and \"simulate\" a progress bar that jumps at fraction $\\alpha$, i.e., when job $i$ has been processed for a time $\\alpha \\pi_i$, we consider that the progress bar jumped to level $\\alpha$, and we use our algorithm. This ensures the claimed consistency and robustness. More details are provided in Lines 196–203. We will revise the corresponding paragraph to emphasize that, in this setting, $\\alpha$ is a free parameter that can be chosen arbitrarily in the algorithm.\n\n**Question 2.** Regarding the role of computable delays: these are not used in the proof of Theorem 3.1, but they are essential for defining Algorithm 2. Specifically, after executing all jobs $(u_k, v_k)_{k=1}^m$ to completion, the algorithm must compute $d^{(h)}(u_k, v_k)$ for each $k$. The assumption of computable delays ensures this computation is possible. We will clarify this point in the paper.\n\nFor Corollary 3.2, we combine Round-robin with the algorithm that blindly follows the predictions. Round-robin has computable delays because for any jobs $i$ and $j$, we have $d(i,j) = \\min(p_i, p_j)$, which can be computed once both jobs have completed and their processing times are known. For the algorithm that blindly follows the predictions, we show in the proof of Lemma 2.2 that:\n- if $\\beta_i p_i < \\beta_j p_j$, then $d(i,j) = p_i$\n- otherwise, $d(i,j) = \\beta_j p_j$\n\nThus, $d(i,j)$ depends on $(\\beta_i p_i, \\beta_j p_j, p_i)$, all of which are known after both jobs are completed, since $\\beta_i p_i$ and $\\beta_j p_j$ are the times when the jobs emit their signals, and $p_i$ is observed at completion. We agree with the reviewer that this is an important explanation, and we will include it in the main body of the paper. \n\n**Question 3.** Figure 2 shows the empirical competitive ratio of the algorithms (on the y-axis) as a function of the prediction error parameter $\\sigma$ (on the x-axis). For delayed predictions, when $\\sigma = 0$, the competitive ratio is 1.5. However, even for very small $\\sigma > 0$, the ratio quickly degrades to 2, indicating a sharp decline in performance. This illustrates the algorithm’s sensitivity to even minor prediction errors. We agree that the phrase “the performance is highly sensitive to errors” may be ambiguous, and we will revise the text to explain this observation more clearly.\n\n**Minor issues.** We thank the reviewer for bringing the minor issues to our attention. We will correct them."}, {"review_id": "Vt1SYEnu01", "reviewer": "Reviewer_Ur9h", "summary": "This paper considered several settings under non-clairvoyant scheduling, namely single signal progress bar, untrusted and stochastic. In single signal progress bar, the paper introduced several algorithms and proved the consistency upper bound of these algorithm. The paper further discussed the robustness and smoothness of these algorithms, and proved that the proposed Algorithm 1 achieves a tradeoff between smoothness and robustness. The paper further proposed a lower bound of robustness.\n\nThe paper then generalized the results to untrusted setting and stochastic setting. In both setting, algorithms are introduced with corresponding consistency upper bound.", "questions": "My questions are listed below:\n\n1. What is the major technical difficulties to achieve the performance guarantees?\n\n2. For the problem described in Section 3, is there a lower bound for the total completion time?", "limitations": "Limitations are not explicitly discussed in this paper. See questions and weakness for potential limitation.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper proposed a new problem setting, offline scheduling with progress bar feedback, which is theoretically interesting and practically relevant.\n\n2. Under single-signal setup, the paper discussed several strategies achieving optimal consistency and tradeoffs between robustness and smoothness. These results are new to me.\n\n3. The paper also considered stochastic progress bar, where the signals are emitted according to Poisson process. This setting is also interesting and sounds practical relevant. Meanwhile, Algorithm 3, designed for this setting, with theoretical guarantee, is also new to me.\n\nWeakness:\n\n1. In the proof of Theorem 2.5, line 586, the claim \"the algorithm processes $I_1$ and $I_2$ equivalently until time t\" requires more clarification. Since $p_j$ are different in $I_1$ and $I_2$, the time of emitting signals might be different, which might results to a different execution routine.\n\n2. Algorithm 2 looks like a direct generalization of the results in [EKMM24]. \n\n3. The presentation of this paper is not clear enough. For example, the definition of robustness and brittleness are neither presented in the paper nor referred to previous works.", "was_revised": true, "final_justification": "All my concerns are addressed by the authors.", "rebuttal": "We thank the reviewer for their interest in our work and for reading and assessing our paper carefully. In the following, we comment on weaknesses and questions raised by the reviewer.\n\n**Clarity of the presentation:** It is true that the present version of the paper provides very succinct inline definitions of consistency, robustness, and smoothness (cf. Lines 34-37), as well as references to the literature that introduced these terms (cf. Line 32). The same holds for the term brittleness, which we only describe informally (cf. Lines 178-179) and with references to relevant related work (cf. Line 177).  For the sake of this paper, the statement of Proposition A.3 in the appendix can be understood as a definition of a brittle algorithm: A small perturbation in the signals leads to a competitive ratio that does not improve upon the lower bound for non-clairvoyant algorithms without access to untrusted signals.  We are happy to add formal definitions of all these terms in the final version of our paper.\n\n**Main technical challenges:** A key difference between all models considered in this paper and previous works on learning-augmented algorithms for non-clairvoyant scheduling is that algorithms in our models start without additional information on the instance. In contrast to these previous works, even perfect signals are not sufficient for designing an 1-competitive algorithm, because the algorithm will already make mistakes before it receives additional information. The overarching challenge across all our results is to design algorithms that do not make too many mistakes before more information is revealed. In the adversarial settings, we achieve this by carefully transitioning between different well-established algorithms for sum of completion time scheduling, and analyze our algorithms with a carefully parameterized case distinction. In the stochastic setting, we achieve this with an algorithm that uses ideas from multi-armed bandits (e.g., Explore-Then-Commit) and tailors them to the scheduling problem at hand (e.g., the Round-Robin phase and the repeated commit phases). The theoretical results for this algorithm require a non-trivial analysis that integrates scheduling aspects (e.g., the analysis of job delays) into a stochastic analysis.\n\n**Proof of Theorem 2.5:** Thank you for pointing this out, we will add a clarification in the final version. In the proof, we construct the two instances $I_1$ and $I_2$. For instance $I_1$, we assume that the signals are emitted correctly in order to enforce the inequality (3) for every deterministic $(1+\\alpha)$-consistent algorithm. Since our goal is to show a lower bound on the robustness for every deterministic $(1+\\alpha)$-consistent algorithm, we do not need to define $I_2$ with correctly emitted signals, and instead use adversarial signals that can be wrong. This allows us to just define the adversarial signals of instance $I_2$ that are emitted during $[0,t]$ to be exactly as in instance $I_1$. Hence, a deterministic algorithm is not able to distinguish $I_1$ and $I_2$ during $[0,t]$, and will process both instances in the same way. We will clarify that the equivalent behavior during $[0,t]$ on both instances is a consequence of the adversarial signals on instance $I_2$.\n\n**Lower bounds for scheduling with an untrusted progress bar (Section 3):** Lower bounds for the special case of a single untrusted signal (Section 2, Theorem 2.5) naturally translate to the more general setting of Section 3. Besides this, [EKMM24] gives a lower bound of $\\Omega(ng)$ on the regret term for combining $g$ algorithms (Theorem 32 in the arxiv version). In their lower bound, each algorithm is represented by a predicted job size vector and one of  these vectors matches the actual processing times. This lower bound instance should naturally translate to the untrusted progress bar setting, where we can just replace the $g$ different predicted sizes for a job with $g$ signals that are consistent with these predicted job sizes. Since this only reduces the amount of information the algorithm has access to, the lower bound should still hold. We will add a comment on this lower bound in the final version of the paper. Apart from this, we are not aware of any lower bounds."}]

Author rebuttal:

Meta-review: This paper proposes a new model for non-clairvoyant scheduling where the algorithm has access to progress bars that provide estimates of the fraction of each job that has been completed. Algorithms for different types of progress bars that achieve competitive ratio guarantees in terms of consistency and robustness are provided.
The proposed models with progress bars is novel, natural, and relevant. Different types of progress bars are explored. The proposed algorithms achieve strong and non-trivial theoretical guarantees.
Decision: Accept (spotlight)