Constant-factor online scheduling of subadditive batches

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Tasks arrive at the event times of a rate-one Poisson process, with independent types uniform on $[0,1]$. A finite batch $B$ is processed by one server in a deterministic time $S(B)>0$. For disjoint nonempty batches $A,B$, assume \[0<S(A)<S(A\cup B)<S(A)+S(B).\] After a batch finishes, an online scheduler selects a subset of the tasks currently waiting to form the next batch, using only information available at that time. A task of type $a$ accumulates cost at rate $c(a)\ge0$ from its arrival until its batch finishes. Let $W$ be the long-run average total cost per unit time of a policy, and $W_*$ its infimum over online policies. Consider data with $0<W_*<\infty$, so the ratio below is defined; when $W_*=0$ the corresponding comparison is $W\le C W_*$.

Statement recorded in the supplied source.

Is there an explicit online scheduling algorithm, allowed to depend on $S$ and $c$, and an absolute constant $C<\infty$, such that $W/W_*<C$ for every pair $S,c$ with finite positive optimum? [S2]

Short English statement

Can one online batching rule achieve a universal constant factor of the best online waiting-cost performance?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 9700007 (AMR-096-0007). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 David J. Aldous, Bacon and eggs: task scheduling into batches, March 2009, Model bullet list and displayed Problem. https://www.stat.berkeley.edu/~aldous/Research/OP/bacon.html.