PaperlayerView exact revision on arXiv

Source-linked AI summary

Better Late Than Never: Online Flow Time Scheduling with Online Estimates

Anupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter, Sorrachai Yingchareonthawornchai

arXiv:2609.07402v1cs.DS

TL;DR

SRPT is optimal for online flow-time scheduling but requires exact job sizes revealed at arrival, while earlier approaches relaxed those assumptions separately. This paper introduces a weaker signaling model and adapts multilevel feedback scheduling. It proves an O(1/ε^2)-competitive guarantee for the signaling model without requiring knowledge of ε.

  • Problem

    SRPT is optimal for single-machine online flow time, but assumes exact job sizes revealed at arrival, while prior approaches relaxed only one of these assumptions at a time.

    Source: §1 · p. 2

  • Method

    Balanced MLF adapts multilevel feedback with fresh and ongoing job classes and a balancing rule that keeps ongoing jobs to a constant fraction of active jobs.

    Source: §1.1 · p. 4

  • Results

    O(1/ε^2)-competitive for ε-signaling, without knowing ε.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Balanced MLF is asymptotically optimal across earlier models that separately relaxed exact-size knowledge or reveal-at-arrival assumptions.

    Source: §1 · p. 3

    The ε-signaling model reveals a signal at an adversarial time between ε and 1−ε of processing, plus completion.

    Source: §1 · p. 2

Abstract

from arXiv · show

In the classical online flow-time scheduling problem on a single machine, jobs arrive over time and must be processed to minimize the total time they spend in the system: for over fifty years, we have known that SRPT is an optimal online algorithm. But this algorithm requires exactness in two different ways: (a) job sizes must be known exactly, and (b) they must be revealed as soon as the job arrives. Recent work relaxed each of these assumptions separately: there are algorithms based on knowing approximate sizes (given when the job arrives), or based on knowing (exact) sizes at some point before the remaining size gets too small. Nonetheless, prior to this work, there was no known approach to relax both assumptions simultaneously. In this work, we consider a model that demands much less: When we process a job, at some point in time between when we complete an $\varepsilon$-fraction and a $(1-\varepsilon)$-fraction of its unknown processing requirement, we are informed that the job is ``somewhere in the middle''. Finally, when the job has received its desired amount of processing, we are informed of its completion. No other information is shared about the job. We give an $O(1/\varepsilon^2)$-competitive algorithm for this model. Slightly more generally, we assume that an algorithm receives a $\mu$-approximate estimate of each job's processing time at some time before we complete a $(1-\varepsilon)$-fraction of its processing. Our algorithm is $O(\mu/\varepsilon)$-competitive, and we show that this is asymptotically optimal. It is a surprisingly natural variant of the multilevel feedback algorithm (MLF) and it is parameter-oblivious: it does not need to know $\mu$ or $\varepsilon$ upfront. The core analytical contribution is to robustify the dual-fitting framework for this problem to handle jobs for which we have not yet received estimates.

1 Introduction

The introduction presents online estimates for flow-time scheduling amid uncertainty about job sizes and estimate timing, situates the model among work on adversarially arriving predictions, and defines the setting. It previews Balanced MLF with matching upper and lower bounds, outlines the paper’s structure, and notes analytical challenges involving changing classes and the lack of untouched jobs.

1 Introduction

  • O(1/ε^2)-competitive scheduling is possible when a signal arrives between the ε and (1−ε) processing fractions, without the algorithm knowing ε.The signal only indicates that the job is somewhere in the middle; exact size is revealed only upon completion. This removes the exact-timing requirement of the earlier O(1/ε)-competitive result [Gup+25].Source: §1 · p. 2
  • O(μ1μ2/ε) is both the competitive ratio guaranteed by Balanced MLF and an asymptotically matching lower bound in the online estimate model.The algorithm does not require μ1, μ2, or ε as inputs; the lower bound holds even when these parameters are known upfront.Source: §1 · pp. 2–3

1.2 Related Work

  • The model includes Bec+04 and Gup+26 as special cases at ε = 1 with noisy estimates on arrival, and the µ1 = µ2 = 1 model with exact estimates before remaining processing drops below ε.It relaxes both size-knowledge assumptions; Balanced MLF is asymptotically optimal for these models simultaneously.Source: §1 · p. 3

1.1 Technical Overview

  • Balanced MLF combines MLF queues for exploring unknown jobs with estimate-based classes for known jobs, while balancing fresh and ongoing jobs so only a constant fraction are ongoing.Estimates fix a job’s class, whereas unknown jobs can be promoted as they receive processing; the balancing rule limits the number of ongoing jobs.Source: §1.1 · p. 4
  • Existing analyses face mutable job classes and no full jobs: jobs must receive processing before estimates arrive, so fresh jobs may already have substantial exploratory processing.This prevents directly comparing a fresh job’s remaining volume with its estimate, as prior analyses do for untouched jobs.Source: §1.1 · p. 4
  • The analysis dual-fits an effective LP using processing times between each job’s elapsed work and its true size, avoiding the need for a modified instance to preserve the algorithm’s schedule.Effective classes partition fresh jobs to support the dual-fitting properties; a pruning procedure removes selected jobs that obstruct those properties, including jobs that switch from ongoing back to fresh.Source: §1.1 · pp. 5–6

1.2 Related Work

  • Unlike [Lin+26], whose bounded operation count permits a factor-m loss for changing classes, this setting can require Ω(log pmax) chunks per job, making that approach lose at least log pmax.[Lin+26] give an O(m2)-competitive algorithm for total job flow; their number of operations bounds class changes, whereas this setting’s chunks cannot be bounded by ε and µ.Source: §1.2 · p. 7
  • The model frames online estimates as adversarially arriving predictions, a potentially applicable direction for online problems beyond scheduling.Predictions are usually available before the instance starts or attached to arriving requests; learning-augmented algorithms use potentially imprecise inputs to overcome worst-case lower bounds.Source: §1.2 · p. 7

1.3 Preliminaries and Notation

  • An estimate is revealed after the algorithm has processed qj units, where qj ≤ (1 − ε)pj, and the true processing time is learned at completion.The estimate satisfies pj/µ2 ≤ ˆpj ≤ µ1pj; at the signal time sj, at least εpj processing remains, and the job is known from then onward.Source: §1.3 · pp. 7–8

1.4 Paper Organization

  • The paper defines Balanced MLF, develops an effective instance and excess lemmas, proves the upper bound by dual fitting, and then establishes a matching lower bound.These topics are presented in Sections 2 through 6, respectively.Source: §1.4 · p. 8

2 Balanced MLF

Balanced MLF uses changing MLF classes and a balancing rule to schedule jobs with delayed estimates. Its properties constrain which jobs can compete and keep a constant fraction of active jobs fresh.

2 Balanced MLF

  • Before its estimate arrives, a job’s class tracks its elapsed processing; afterward, the estimate may raise that class, which never decreases.Jobs start in class 0 unless the estimate arrives at time 0.Source: §2 · p. 8
  • Balanced MLF processes the ongoing job with the smallest class and balances fresh and ongoing jobs, promoting a job when its class increases.A fresh job with the smallest class becomes ongoing when fresh jobs make up at least a quarter of active jobs and its class is below the smallest ongoing class.Source: §2 · p. 9

2.8 else

  • At time t, either every fresh job’s class is at least the smallest ongoing class, or fewer than a quarter of active jobs are fresh.This follows from the balancing phase’s condition for moving a fresh job into the ongoing set.Source: §2.8 · p. 9

2.1 Properties of Balanced MLF

  • At most one ongoing job occupies any given current class at a time.Source: §2.1 · p. 9
  • When processing a job of class k, if a smaller-class fresh job exists, no other active job can have class at most k.The paper identifies this as the special-rule property for the algorithm.Source: §2.1 · p. 10
  • The balancing rule keeps a constant fraction of active jobs fresh, allowing the later analysis to focus on fresh jobs.Source: §2.1 · p. 10

3 The Effective Instance

The analysis compares Balanced MLF and an optimal schedule through their numbers of active jobs at a fixed time. It constructs an effective instance and an LP relaxation to lower-bound the optimum’s active-job count.

3 The Effective Instance

  • Local competitiveness compares the algorithm’s and optimum’s active-job counts at each time; because each active job contributes one unit to flow time, it implies competitiveness.The analysis fixes a time t* and bounds |A(t*)| relative to |OPT(t*)|.Source: §3 · p. 10

3.1 Effective Processing Times and Effective Classes

  • Effective processing times and classes are used only to lower-bound |OPT(t*)|, not to claim that the algorithm runs identically on a reduced instance.The proof allows reductions to processing times and classes to obtain a more structured LP relaxation.Source: §3.1 · p. 10, §3.2 · p. 12
  • The effective processing times underestimate actual processing times, and the effective remaining times are nonnegative.The construction also tolerates inconsistencies between effective processing times and classes for a sufficiently small fraction of fresh jobs, at constant-factor cost to local competitiveness.Source: §3.1 · pp. 11–12

3.2 The LP Relaxation

  • The LP relaxation’s optimal value is at most |OPT(t*)|, providing a lower bound on the optimum’s active-job count.The relaxation uses effective processing times and the knapsack-cover relaxation.Source: §3.2 · pp. 12–13

4 The Excess Lemmas

This section develops dual-fitting sets from fresh jobs and uses pruning to establish strong and weak excess lemmas, including a lower bound for nonempty F(k) and a strong effective-excess bound for release-time sets.

4.1 Finding Consistent Fresh Jobs

  • Partitioning fresh jobs by effective class and pruning exceptions yields sets that retain at least half of the original fresh jobs.The procedure removes jobs that become fresh again at a class-transition interval; each removed job can be charged to a distinct class with a surviving job.Source: §4.1 · pp. 14–15

4.2 Strong and Weak Excess Lemmas

  • The candidate sets S(t) contain jobs released from time t through t*, and the section uses a nested sequence of these sets.The intervals are chosen around the last processing times of jobs in each class before t*, supporting the construction of sets with large effective excess.Source: §4.1 · p. 14, §4.2 · p. 15

4.2.1 The Strong Excess Lemma

  • When F̄(k) ≠ ∅, Lemma 4.6 states exe(S(t≥k+1)) ≥ P; the supplied statement truncates after P, so its full lower-bound term is unspecified.Jobs processed during [t≥k+1, t*] are released during that interval and belong to S(t≥k+1).Source: §4.2.1 · pp. 15, 18
  • Pruning F(k) into barred F(k) rules out the hypothesized job configuration, establishing the second property used in the strong excess lemma’s proof.The argument derives a contradiction with membership in the pruned set.Source: §4.2.1 · p. 19

4.2.2 The Weak Excess Lemma

  • If F(k) is nonempty, exe(S(t>k+1)) is at least the lemma’s p_j(t*) term minus 3·µ^2·Λ_k.The supplied statement gives this lower bound for the weak excess lemma.Source: §4.2.2 · p. 19
  • At most one job of current class at most k can be active at t>k; other jobs processed afterward are newly released, except for at most one possible exception.The proof also bounds the time spent processing the possible low-class job by µ^2·Λ_k.Source: §4.2.2 · pp. 19–20

5 Dual Fitting

The dual-fitting analysis builds a dual solution from crucial classes with positive effective excess, then bounds its objective and feasibility. Together these bounds yield an O(μ1μ2/ε)-competitive guarantee.

5 Dual Fitting

  • Heavy crucial classes have effective excess at least |F̄(k)|, while all light crucial classes except possibly the smallest have positive effective excess.These excess bounds support the dual construction.Source: §5 · p. 21

5.1 Definition of Dual Solution

  • The dual solution excludes the smallest light crucial class when one exists, because its excess is not guaranteed positive.The remaining crucial classes are used to define the dual variables.Source: §5.1 · p. 22

5.2 Objective Value

  • The dual assignment’s objective captures a constant fraction of the algorithm’s active-job count, up to an additive term.The objective-value bound is used in the final competitiveness proof.Source: §5.2 · p. 22

5.3 Approximate Feasibility

  • Approximate feasibility is bounded by separating heavy- and light-class contributions, which are at most 8 and 7, respectively.The two bounds combine to establish approximate dual feasibility.Source: §5.3 · pp. 23–25

5.4 Proof of Theorem 1.2

  • |A(t*)| ≤ 1068ρ · |OPT(t*)|, establishing local O(ρ) competitiveness for Balanced MLF, where ρ = μ1μ2/ε.The proof concludes the theorem by combining the LP lower bound, weak duality, approximate feasibility, and the dual objective bound.Source: §5.4 · p. 25

6 Randomized Lower Bound

The section proves an Ω(μ/ε) lower bound for online estimates, matching the stated upper bound asymptotically even against randomized algorithms. A randomized hard instance creates a large local queue-size gap, which a bombardment sequence converts into a total-flow-time lower bound.

6 Randomized Lower Bound

  • The Bombardment Lemma turns a local queue-size gap into a total flow-time gap by appending unit jobs released over consecutive times.During the interval, the algorithm has at least δA(T, 1) active jobs, while the offline schedule has at most δ*(T) + 1.Source: §6 · pp. 25–26
  • Ω(μ/ε) is a lower bound for every randomized algorithm in the (ε, 1, μ)-online estimate model.The paper states this for minimizing total flow time on a single machine.Source: §6 · pp. 26, 29
  • Geometric sizes make unfinished jobs indistinguishable through fair-coin outcomes, while OPT knows sizes initially and uses Shortest Processing Time.For the algorithm, a Heads outcome reveals the final deterministic unit of work; the lower-bound intuition contrasts this uncertainty with OPT's advance knowledge.Source: §6 · pp. 26–28
  • The hard instance releases n jobs at time 0 with geometric processing times and caps estimates at min{Pj, 1/ε}.The instance conditions the geometric-size distribution on all job sizes being at most P; the passage verifies estimate feasibility.Source: §6 · p. 27
  • At time T, the expected local queue-size ratio is Ω(μ/ε), and bombardment converts it to the same-order total flow-time lower bound.The local ratio is expressed using δA(T, 1) and δ*(T) + 1.Source: §6 · p. 29

A Reducing ε-Signaling to Online Estimates

The appendix reduces ε-signaling to online estimates by treating elapsed processing when the signal arrives as the estimate. This estimate satisfies the online-estimate model's timing and distortion requirements, so the online-estimate guarantee implies the signaling guarantee.

A Reducing ε-Signaling to Online Estimates

B Bounding the Number of Preemptions of Balanced MLF

Balanced MLF's total preemptions are bounded in terms of the jobs' processing times, with separate charges for class increases and job releases. The bound is aggregate: an individual job may still be preempted up to n − 1 times.

B Bounding the Number of Preemptions of Balanced MLF

C Omitted Proofs

The omitted proofs establish scheduling invariants for Balanced MLF and bound the pruning procedure's removals. These results constrain ongoing classes, fresh-job balance, and the relationship between removed jobs and retained fresh jobs.

C Omitted Proofs

  • At every time, each class has at most one ongoing job.The proof uses the rule that a job is made ongoing only when its current class is smaller than those of ongoing jobs; a class change makes an ongoing job fresh.Source: C Omitted Proofs · p. 33
  • If a smaller-class fresh job exists while a job is processed, no third active job can have current class at most that of the processed job.This is Lemma 2.3's scheduling constraint.Source: C Omitted Proofs · p. 33
  • The fresh-job invariant is |Afresh(t)| ≥ 1/4 |A(t)| at every time t.Releases preserve the inequality; making a fresh job ongoing requires the balance condition, and completions or promotions do not break it.Source: §2.1 · p. 10, C Omitted Proofs · p. 34
  • The pruning argument pairs each removed job with at least two fresh jobs retained across effective classes.The proof counts ℓ distinct removal-triggering classes and obtains a retained fresh-job count of at least 2ℓ.Source: C Omitted Proofs · p. 34
Loading 2609.07402v1…