CS Paper Radar

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

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

cs.DS ·submitted 2026-09-07 12:14 UTC · v1

Abstract

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 $μ$-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(μ/\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 $μ$ 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.

Comment
abstract shortened

Closest papers

Nearest neighbours by meaning across the whole index.

A QPTAS for Stochastic Scheduling of Bernoulli Jobs

cs.DS cs.CCmath.OC ·2026-10-08 ·Junho Hwang
benchmark similarity 0.62
Abstract · 23 pages, 1 figure

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $Ω(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.

0.25

Single-Machine Scheduling with Interval Predictions and Costly Preemption

cs.DS ·2026-09-14 ·Lachlan Bridges
theory similarity 0.61
Abstract · 8 pages

We study the single-machine total-completion-time problem $1||\sum C_j$ when processing times are unknown but each job comes with a reported interval. Jobs are initially processed in nondecreasing order of reported upper bound. If a job is still unfinished after receiving that much service, the reported upper bound has been violated and the policy switches to a resumable geometric fallback. Each interruption of an unfinished job incurs an additive penalty $κ$. For a residual set of $m$ jobs, known size ratio $D=s_1/s_0$, normalized interruption penalty $λ=κ/s_0$, and geometric depth $K$, we derive an explicit worst-case coefficient $Ψ_{m,D,λ}(K)$. When $λ>0$, a finite minimizing depth exists and can be chosen after the trigger from the observed number of unfinished jobs; the optimal depth decreases with the interruption penalty and increases with the residual set size. We also derive the exact worst-case coefficient $R_{n,D}$ for an arbitrary nonpreemptive list when all processing times lie in a known bounded range. These bounds give guarantees for valid intervals, a single interval failure, arbitrary reports, no-trigger outcomes, and random instances. In the single-failure regime, they also give a precise condition under which the proved fallback guarantee is smaller than the bounded-range continuation guarantee.

0.16

Sparse Predict and Demote: Optimal Scheduling with Minimal Size Advice

cs.PF cs.DScs.LG ·2026-11-06 ·Chengyi Liu, Thodoris Lykouris, Junxuan Shen, Adam Wierman
similarity 0.60
Abstract

Knowledge of job sizes is crucial for optimizing the mean response time in single-server scheduling. However, predictions of job sizes are typically inexact and may be costly to obtain. Thus, a long-standing research question is: what is the minimal information about job sizes required to obtain near-optimal mean response time? We introduce a novel policy, \emph{Sparse Predict and Demote (SPD)}, and prove that it achieves order-optimal mean response time in heavy traffic while requiring only one-bit job-size predictions for a vanishing fraction of arrivals. SPD achieves heavy-traffic order-optimality even in situations when predictions are (i) inexact up to any fixed multiplicative error bound, and (ii) costly, i.e., the server is used to compute predictions and is thus unavailable to serve jobs while processing prediction queries. Finally, we use numerical experiments to illustrate that SPD maintains near-optimal performance beyond the heavy-traffic regime.

0.20

Two-Machine Flow Shop with a Fixed Non-Availability Interval on the Second Machine

cs.DM ·2026-09-12 ·Hao Lu, Yuan Yuan, Xingwu Liu, Xin Han
theory similarity 0.60
Abstract

This paper investigates a two-machine permutation flow shop in which the second machine is unavailable during one fixed interval $[s,t]$. We consider the non-resumable setting: an operation interrupted by the interval must restart from the beginning after the machine becomes available. The objective is to minimize the makespan. We establish three results. First, we give a polynomial-time $10/7$-approximation algorithm. Second, we develop a pseudopolynomial-time exact dynamic program. Third, we prove that the problem does not admit a fully polynomial-time approximation scheme (FPTAS) unless $\mathrm{P}=\mathrm{NP}$, even when the non-availability interval has unit length. Together, these results characterize a distinctive complexity profile: exact optimization is possible in pseudopolynomial time, whereas the usual route from such an algorithm to an FPTAS is impossible unless $\mathrm{P}=\mathrm{NP}$. They also reveal an approximability separation from the corresponding non-resumable problem with the interval on the first machine.

0.19

Online Batching with Lookahead: Adversarial Limits and Stochastic Gains

cs.DS ·2026-10-12 ·Dimitris Christou, Jiayi Chen, Nihal Sharma, Aditya Akella, Shuchi Chawla +1 more
benchmarktheoryhot direction similarity 0.59
Abstract

Modern inference systems rely on batching to exploit parallel execution and amortize serial execution overheads, but batching creates a fundamental online scheduling tradeoff: serving requests immediately reduces request queuing delay, while waiting can form larger batches that better utilize parallel hardware and improve serving efficiency. We study this tradeoff in a single-server online batching model with bounded batch capacity, fixed batch processing time, and the objective of minimizing total flow time. Our focus is on the value of finite lookahead into future arrivals over a purely online setting for scheduling. We show that the benefits of lookahead depend on the arrival model. In the adversarial setting, finite perfect lookahead has inherent limitations: for any bounded lookahead window, every online algorithm remains separated from the offline optimum by a constant factor. Thus, worst-case arrival sequences can prevent perfect knowledge of future events from fully overcoming online uncertainty. In contrast, under Poisson arrivals in the stable regime, finite lookahead is much more powerful. Although the best distribution-aware online algorithm has a nonzero asymptotic gap from the offline optimum, lookahead closes this gap exponentially fast in the window length. We prove matching upper and lower bounds up to constants in the exponent. Together, these results give a tight characterization of when lookahead can close the online--offline gap, incorporating insights from the competitive analysis of online algorithms into queueing-theoretic steady-state bounds. We also study imperfect predictions, showing that the benefit of lookahead degrades gracefully with prediction error. Simulations on synthetic arrivals and experiments on real request traces support the theory: modest lookahead substantially reduces flow time and brings online batching close to the offline benchmark.

0.55

Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization

cs.DS ·2026-10-26 ·Weitian Tong, Yao Xu
similarity 0.59
Abstract · 34 pages, 8 figures

We study unweighted nonpreemptive throughput maximization: given jobs with processing times, release times, and deadlines, schedule a maximum-cardinality subset on identical machines. For every fixed $\varepsilon>0$, we give randomized algorithms with expected approximation ratios $17/13+\varepsilon$ in polynomial time and $21/17+\varepsilon$ in pseudopolynomial time. These improve the respective $4/3+\varepsilon$ and $5/4+\varepsilon$ guarantees of Armbruster, Grandoni, Tinguely, and Wiese [STOC'26]. Both results hold for an arbitrary number of identical machines. Our algorithms build on their configuration-LP and matching framework, which partitions time into blocks. For a job whose window meets multiple blocks, its boundary blocks are the first and last such blocks. Crossing boundary pairs, whose endpoints strictly interleave, permit additional assignments to sampled execution slots, while a noncrossing family can be coordinated using consistent joint distributions on at most three blocks. The exchange analysis accounts for fractional job assignments that must be erased before inserting an additional job. For the pseudopolynomial implementation, we project configurations onto selected job identities and use separate configuration distributions with common placement marginals. This retains efficient pricing while enforcing the correlations needed for coordination.

0.15

Non-Clairvoyant Scheduling is Hard Even for Trees

cs.DS ·2026-10-07 ·Kunal Agrawal, Owen Druzgal, Milind Prabhu, Jinhao Zhao
theory similarity 0.59
Abstract

We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vertices are unit-time subjobs and whose edges specify precedence constraints. We consider non-clairvoyant algorithms: the DAG is not known when a job arrives, and each subjob is revealed only when it becomes ready. Agrawal, Moseley, Newman, and Pruhs (SPAA 2024) showed that First-In-First-Out (FIFO) has competitive ratio $Ω(\log m)$ even when every job is an out-tree. They also proved that FIFO is $O(\log m)$-competitive in several natural settings and asked whether this guarantee extends to general instances. More broadly, they asked whether any non-clairvoyant algorithm can be $O(1)$-competitive. We answer both questions in the negative by proving a lower bound of $Ω(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule. In particular, every non-clairvoyant algorithm has competitive ratio $Ω(m)$ on some instance with $\mathrm{OPT} \ge m$. The lower bound holds even when every job is an out-forest. We complement these lower bounds with an asymptotically optimal non-clairvoyant algorithm. FIFO is $O(m)$-competitive, but can have competitive ratio $Ω(m)$ even when $\mathrm{OPT}=O(1)$. For instances with small $\mathrm{OPT}$, we design a Small-Frontier-First algorithm that is $O(\mathrm{OPT})$-competitive. Combining the two algorithms yields an $O(\min\{m,\mathrm{OPT}\})$-competitive non-clairvoyant algorithm.

0.34

Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm

cs.LG ·2026-10-05 ·Seoungbin Bae, Dabeen Lee
theory similarity 0.59
Abstract

We study contextual queueing bandits, where a learner schedules jobs while learning unknown service rates modeled by logistic functions of job-server features. Performance is measured by queue length regret, the expected excess queue length at round $t$ relative to an oracle that knows the service rates. Existing decaying-regret guarantees either have a suboptimal decay rate or require a known fixed horizon. They also assume context-wise slack and a strictly positive minimum eigenvalue of the feature covariance. In this paper, we propose WISE (Widest Interval Selection with Elimination), achieving rate-optimal $\widetilde{\mathcal O}(t^{-1/2})$ queue length regret at every sufficiently large time without knowing the horizon. We assume capacity slack, meaning that expected incoming workload under best-server service is below service capacity, and impose no covariance lower bound. Our analysis uses a workload potential measuring the expected service attempts needed by waiting jobs on their best servers. Its drift on nonempty rounds combines a negative term ensured by capacity slack with errors from suboptimal service choices. Then an elliptical potential count bounds how often WISE selects wide confidence intervals, thereby limiting the number of rounds with large service errors. We also sharpen the arrival-rate dependence of an existing lower bound and make its dependence on feature dimension and server count explicit. We prove another lower bound that quantifies the increase in regret as the normalized capacity slack decreases; to our knowledge, this is the first such lower bound for CQB. Simulations show small regret even when context-wise slack fails.

0.20