# Non-clairvoyant Scheduling with Partial Predictions

Ziyad Benomar ENSAE, Ecole polytechnique Fairplay joint team
<EMAIL_ADDRESS>Vianney Perchet CREST, ENSAE, Criteo AI LAB Fairplay
joint team<EMAIL_ADDRESS>
###### Abstract

The non-clairvoyant scheduling problem has gained new interest within
learning-augmented algorithms, where the decision-maker is equipped with
predictions without any quality guarantees. In practical settings, access to
predictions may be reduced to specific instances, due to cost or data
limitations. Our investigation focuses on scenarios where predictions for only
$B$ job sizes out of $n$ are available to the algorithm. We first establish
near-optimal lower bounds and algorithms in the case of perfect predictions.
Subsequently, we present a learning-augmented algorithm satisfying the
robustness, consistency, and smoothness criteria, and revealing a novel
tradeoff between consistency and smoothness inherent in the scenario with a
restricted number of predictions.

##  1 Introduction

Optimal job scheduling is a longstanding and actively studied class of
optimization problems [49, 41, 26, 43, 18, 36, 50], with applications in
various domains spanning from supply chain management [29, 30] to operating
systems [33, 52, 55]. A particular setting is preemptive single-machine
scheduling [50, 16], where $n$ jobs $i\in[n]$ must be executed on the same
machine, with the possibility of interrupting a job and resuming it afterward,
and the objective is to minimize the sum of their completion times. An
algorithm is called clairvoyant if it has initial access to the job sizes,
otherwise, it is called non-clairvoyant [45]. The design of non-clairvoyant
algorithms is a classical problem in competitive analysis and online
algorithms [11]. In this paradigm, decisions must be made in an environment
where the parameters governing the outcome are unknown or might evolve over
time.

Due to the inherent difficulty of the problems in competitive analysis, the
performance of any online algorithm stays bounded away from that of the
optimal offline algorithm. However, the ascent of machine learning motivated
the incorporation of predictions in algorithm design, which started in works
such as [47, 35], then was formalized in [42] and [51]. Since then, learning-
augmented algorithms became a popular research topic and had multiple
applications [48]. The outcome of these algorithms depends both on the
parameters of the problem and the quality of the predictions. They are
required to have a performance that is near-optimal when the predictions are
accurate (consistency), near the worst-case performance without advice if the
predictions are arbitrarily erroneous (robustness), and that degrades smoothly
as the prediction error increases (smoothness).

In practice, predictions often incur costs and, at times, are infeasible due
to the lack of data. It is, therefore, crucial to understand the limitations
and the feasible improvements with a restrained number of predictions in
scenarios with multiple unknown variables. This question was first
investigated for the caching problem [32], and very recently for metrical task
systems [8], in settings where the algorithm is allowed to query a limited
number of predictions. It was also explored for the scheduling problem [15],
assuming that the decision-maker can query the true sizes of $B$ jobs out of
$n$. The authors present a
$\big{(}2-\tfrac{B(B-1)}{n(n-1)}\big{)}$-competitive algorithm, and they give
a lower bound on the competitive ratio of any algorithm only when $B=o(n)$.
The case of imperfect predictions, however, is not examined.

In non-clairvoyant scheduling, besides the querying model studied in the works
mentioned above, predictions of the sizes of certain jobs $i\in I$ may be
available, where $I\subset[n]$, perhaps derived from previous executions of
similar tasks. Assuming that $I$ is a subset of $[n]$ of size $B$, taken
uniformly at random, we examine the limitations and possible improvements of
non-clairvoyant algorithms.

###  1.1 Contributions

We initiate our analysis by addressing the scenario of perfect predictions. We
establish a lower bound on the $(n,B)$-competitive ratio of any algorithm (for
fixed $n\geq 2$ and $B\leq n$), which extends the lower bound of
$2-\frac{4}{n+3}$ in the non-clairvoyant case [45]. Considering that
$B=wn+o(n)$ for some $w\in[0,1]$, we derive from the prior bound that the
competitive ratio of any algorithm is at least $2-w-(\frac{4}{e}-1)w(1-w)$,
and we show an improved bound of $2-w-(3-2\sqrt{2})w(1-w)$. Demonstrating
these bounds is considerably more challenging than the case $B=0$, due to the
eventual dependency between the actions of the algorithm and the known job
sizes.

In the case of perfect predictions, we show that knowing only the relative
order of the $B$ job sizes, without knowledge of their values, enables a
$(2-\frac{B}{n})$-competitive algorithm, which improves substantially upon the
result of [15]. We propose a second algorithm leveraging the true sizes of the
$B$ jobs, yielding an $(n,B)$-competitive ratio of
$(2-\frac{B}{n}-\frac{2(1-B/n)}{n+1})$, which is strictly better than the
former, although both are asymptotically equivalent.

Subsequently, we adapt the latter algorithm to handle imperfect predictions.
While the difficulty in most works on learning-augmented algorithms lies in
ensuring robustness and consistency, smoothness in the case of scheduling with
limited predictions is also not immediate. Alongside the typical consistency-
robustness tradeoff, our algorithm also exhibits a consistency-smoothness
tradeoff. More precisely, governed by two hyperparameters
$\lambda,\rho\in[0,1]$, the $(n,B)$-competitive ratio of the algorithm is at
most $\min(\frac{2}{1-\lambda},\frac{C}{\lambda}+\frac{2S}{\lambda
n}\mathbb{E}[\eta])$. Here, $\mathbb{E}[\eta]$ denotes the total expected
prediction error, $\frac{2}{1-\lambda}$ is the algorithm’s robustness,
$\frac{C}{\lambda}=\frac{1}{\lambda}(2-\frac{B}{n}+\rho\frac{B}{n}(1-\frac{B-1}{n-1}))$
its consistency, and $\frac{2S}{\lambda n}=\frac{2}{\lambda
n}(\frac{1}{\rho}(1-\frac{B}{n})+\frac{B}{n})$ its smoothness factor,
characterizing the sensitivity of the bound to $\mathbb{E}[\eta]$. Notably,
alterations in the parameter $\rho$ yield opposing variations on the
consistency and the smoothness factor. Nonetheless, this tradeoff vanishes for
$B$ close to $0$ or $n$, and does not appear, for instance, in [51], [10] or
[40].

We illustrate our results for the case of perfect predictions in Figure 1,
comparing them with the competitive ratio proved in [15].

Figure 1: Lower bounds and competitive ratios for $B$ known job sizes.

###  1.2 Related work

Since their introduction in [51, 42], learning-augmented algorithms witnessed
an exponentially growing interest, as they offered a fresh perspective for
revisiting online algorithms, and provided new applications for machine
learning in algorithm design [48] and in the implementation of data structures
[35, 39]. Many fundamental problems in competitive analysis were studied in
this setting, such as ski rental [27, 5, 14, 23, 2, 44, 53], secretary [4,
24], matching [21, 19, 54, 34], caching and metrical task systems [42, 17, 3,
1, 20]. In particular, scheduling is one of the problems that were studied
most thoroughly. Different works cover various objective functions [51, 38,
7], prediction types [6, 46, 37], error metrics [31, 40], and other aspects
and applications [56, 13, 22]

The setting of learning-augmented algorithms with limited predictions was
initially explored by [32] for caching. The authors presented an algorithm
using parsimonious predictions, with a competitive ratio increasing with the
number of allowed queries. In another very recent paper [8], a similar setting
is studied for the more general problem of metrical task systems, where the
algorithm is allowed to query a reduced number of action predictions [3], each
giving the state of an optimal algorithm at the respective query step. An
additional related study by [25] focuses on the ski-rental and Bahncard
problems in a penalized adaptation of the setting with limited advice, where
the cost of the predictions is added to the algorithm’s objective function. In
the context of scheduling, [15] introduced the $B$-clairvoyant scheduling
problem, where an algorithm can query the exact sizes of $B$ jobs at any
moment during its execution. They show that the optimal strategy is to query
the sizes of $B$ jobs selected uniformly at random at the beginning of the
process. They establish that, if $B=o(n)$, then the competitive ratio of any
algorithm is at least $2$, then they provide a
$\big{(}2-\frac{B(B-1)}{n(n-1)}\big{)}$-competitive algorithm. The same paper
also addresses the secretary problem with restricted access to binary
predictions of known accuracy, and the ski-rental problem with access to an
oracle whose accuracy improves progressively over time.

The limit scenario $B=0$ corresponds to the non-clairvoyant scheduling
problem, studied in-depth in [45]. In particular, the paper demonstrates that
the competitive ratio of any non-clairvoyant algorithm is at least $2$, and
that it is achieved by the round-robin algorithm, executing all unfinished
jobs concurrently at equal rates. On the other hand, $B=n$ corresponds to the
setting presented in [51], where the authors introduce, for all
$\lambda\in(0,1)$, a preferential round-robin algorithm with robustness
$\frac{2}{1-\lambda}$ and consistency $\frac{1}{\lambda}$.

###  1.3 Problem and notations

The decision-maker is given $n$ jobs $i\in[n]$ with unknown sizes
$x_{1},\ldots,x_{n}$ to schedule on a single machine, and predictions
$(y_{i})_{i\in I}$ of $(x_{i})_{i\in I}$, with $I$ a uniformly random subset
of $[n]$ of size $B$. The objective is to leverage the predictions to minimize
the sum of the completion times. We assume that preemption is allowed, i.e. it
is possible to interrupt the execution of a job and resume it later, which is
equivalent, by neglecting the preemption cost, to assuming that the jobs can
be run in parallel at rates that sum to at most $1$.

To simplify the presentation, we consider that there are predictions
$y_{1},\ldots,y_{n}$ of $x_{1},\ldots,x_{n}$, but the decision-maker has only
access to $y_{\sigma(1)},\ldots,y_{\sigma(B)}$, where $\sigma$ is a uniformly
random permutation of $[n]$. We denote by $\eta_{i}=|x_{i}-y_{i}|$ the error
of the prediction $y_{i}$, and by
$\eta^{\sigma}=\sum_{i=1}^{B}\eta_{\sigma(i)}$ the total error of the
predictions accessed by the algorithm.

Consider an algorithm A and an instance $x=(x_{1},\ldots,x_{n})$ of job sizes,
we denote by $\textsf{A}(x)$ the sum of the completion times of the jobs when
executed by A. Furthermore, for all $i\neq j\in[n]$ and $t>0$, we denote by

  * •

$S_{i}^{\textsf{A}}(t)$ the processing time spent on job $i$ until time $t$,

  * •

$t_{i}^{\textsf{A}}=\inf\\{t\geq 0:S_{i}^{\textsf{A}}(t)=x_{i}\\}$ its
completion time,

  * •

$D^{\textsf{A}}_{ij}=S_{i}^{\textsf{A}}(t^{\textsf{A}}_{j})$ the total time
spent on job $i$ before job $j$ terminates,

  * •

and $P^{\textsf{A}}_{ij}=D^{\textsf{A}}_{ij}+D^{\textsf{A}}_{ji}$ the mutual
delay caused by $i,j$ to each other.

When there is no ambiguity, we omit writing the dependency to A. With these
notations, it holds that $t^{\textsf{A}}_{i}=x_{i}+\sum_{j\neq
i}D^{\textsf{A}}_{ji}$ for all $i$. Consequently, the objective function of A
can be expressed as

$\textsf{A}(x)=\sum_{i=1}^{n}x_{i}+\sum_{1\leq i<j\leq
n}P^{\textsf{A}}_{ij}\;.$ (1)

Observing that, for all $i\neq j\in[n]$, if $i$ terminates before $j$ then
$P^{\textsf{A}}_{ij}\geq x_{i}$, otherwise $P^{\textsf{A}}_{ij}\geq x_{j}$, we
deduce that $P^{\textsf{A}}_{ij}\geq\min(x_{i},x_{j})$. Equality is achieved
by the clairvoyant algorithm that runs the jobs until completion in non-
decreasing size order [45], which is the optimal offline algorithm, that we
denote OPT, satisfying

$\textsf{OPT}(x)=\sum_{i=1}^{n}x_{i}+\sum_{1\leq i<j\leq
n}\min(x_{i},x_{j})\;.$ (2)

When the predictions are perfect, for all $n\geq 2$ and $B\leq n$, we define
the $(n,B)$-competitive ratio of algorithm A as the worst-case ratio between
its objective, knowing the sizes of $B$ jobs taken uniformly at random, and
that of OPT, on instances of $n$ jobs

$\textsf{R}_{n,B}(\textsf{A})=\sup_{x\in(0,\infty)^{n}}\frac{\mathbb{E}[\textsf{A}(x)]}{\textsf{OPT}(x)}\;,$

where the expectation $\mathbb{E}[\textsf{A}(x)]$ is taken over the
permutation $\sigma$ and the actions of A if it a randomized algorithm. If the
number of predictions depends on the number of jobs, i.e. $B=(B_{n})_{n\geq
1}$ defines a sequence of integers, then the competitive ratio of A is defined
by

$\textsf{CR}_{B}(\textsf{A})=\sup_{n\geq
2}\textsf{R}_{n,B_{n}}(\textsf{A})\;.$

When the predictions are imperfect, the competitive ratio becomes also a
function of $\mathbb{E}[\eta^{\sigma}]$.

##  2 Lower bounds

In this section, we assume that the predictions are error-free, and we
establish lower bounds on the $(n,B)$-competitive ratio of any algorithm,
followed by a lower bound independent of $n$ when $B_{n}=wn+o(n)$ for some
$w\in[0,1]$. These lower bounds are obtained by constructing random job size
instances $x$ such that, for any deterministic algorithm A, the ratio
$\mathbb{E}_{\sigma,x}[\textsf{A}(x)]/\mathbb{E}_{x}[\textsf{OPT}(x)]$ is
above them. The result then extends to randomized algorithms and yields bounds
on their $(n,B)$-competitive ratio by using Lemma A.1, which is a consequence
of Yao’s principle [57]. In all this section, we consider i.i.d. job sizes.
Therefore, we can assume without loss of generality that the $B$ known job
sizes are $x_{1},\ldots,x_{B}$.

In the non-clairvoyant case $B=0$, taking i.i.d. exponentially distributed
sizes gives, with easy computation, that $\mathbb{E}[P^{\textsf{A}}_{ij}]=1$
(Remark A.3), which yields, using Equations (1) and (2), the lower bound
$2-\frac{4}{n+3}$ on the competitive ratio [45]. However, if $B>0$, the
algorithm can act according to the information it has on $(x_{i})_{i\in I}$,
and the dependence between its actions and these job sizes makes the analysis
more sophisticated.

We prove a generic lower bound using job sizes sampled from a distribution of
the form $\Pr(x_{1}\leq t)=1-\frac{\varphi(0)}{\varphi(t)}$. Stating the
theorem using the function $\varphi$ is more convenient than with the CDF. For
any positive numbers $T\geq x>0$ we denote

$G_{\varphi}(x,T)=\int_{0}^{T-x}\frac{dt}{\varphi(t)}+\frac{x}{\varphi(T-x)}\;,$
(3)

our generic lower bound is then stated as follows.

######  Theorem 2.1.

Let $\varphi:[0,\infty)\to[0,\infty)$ be a continuously differentiable and
increasing function satisfying $\varphi(0)>0$, $\varphi^{\prime}/\varphi$ is
non-increasing and $\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}<\infty$, and
let $\alpha_{\varphi}\geq 0$ satisfying

$\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx\geq\alpha_{\varphi}\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}\;.$

If $B=wn+o(n)$ for some $w\in[0,1]$, then it holds for any randomized
algorithm A that

$\textsf{CR}_{B}(\textsf{A})\geq
2-2(2-\alpha_{\varphi})w+(3-2\alpha_{\varphi})w^{2}\;.$

Moreover, if $\int_{0}^{\infty}\frac{dt}{\varphi(t)}<\infty$, then for all
$n\geq 2$ and $B\leq n$

$\textsf{R}_{n,B}(\textsf{A})\geq
C_{\varphi,n,B}-\frac{C_{\varphi,n,B}-1}{1+\frac{n-1}{2}\frac{\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}}{\int_{0}^{\infty}\frac{dt}{\varphi(t)}}}\;,$

where
$C_{\varphi,n,B}=(2-\tfrac{B}{n})-(3-2\alpha_{\varphi})\tfrac{B}{n}\big{(}1-\tfrac{B-1}{n-1}\big{)}$.

If $\int_{0}^{\infty}\frac{dt}{\varphi(t)}=\infty$, then the expectation of
the job sizes considered in the theorem is infinite. In this case, we consider
a truncated distribution with a maximum $a>0$. After completing the analysis,
we derive a lower bound that depends on $a$ and $w$, by considering
$B=wn+o(n)$ and $n\to\infty$, then, we conclude by taking the limit
$a\to\infty$.

For any value $\alpha_{\varphi}$ in Theorem 2.1, observe that
$C_{\varphi,n,0}=2$ and $C_{\varphi,n,n}=1$, which means that the lower bound
interpolates properly the non-clairvoyant and clairvoyant settings. The
remaining task is to choose an adequate function $\varphi$ satisfying the
conditions of the theorem with $\alpha_{\varphi}$ as large as possible. We
first consider exponentially distributed job sizes, often used to prove lower
bounds in scheduling problems. This corresponds to $\varphi(t)=e^{t}$.

######  Corollary 2.1.1.

For any algorithm A, it holds that

$\textsf{R}_{n,B}(\textsf{A})\geq C_{n,B}-\frac{4(C_{n,B}-1)}{n+3}\;,$

with
$C_{n,B}=2-\frac{B}{n}-(\tfrac{4}{e}-1)\frac{B}{n}\big{(}1-\frac{B-1}{n-1}\big{)}$.
In particular, if $B=wn+o(n)$ then

$\textsf{CR}_{B}(\textsf{A})\geq(2-w)-(\tfrac{4}{e}-1)w(1-w)\;.$

Corollary 2.1.1 gives, in particular, that $\textsf{R}_{n,0}(\textsf{A})\geq
2-\frac{4}{n+3}$, which corresponds exactly to the tight lower bound for the
non-clairvoyant scheduling problem [45]. However, the bound is not tight for
all values of $B\leq n$. To refine it, we consider distributions that would be
more difficult to process by the algorithm. One idea is to sample a different
parameter $\lambda_{i}\sim\mathcal{E}(1)$ independently for each $i\in[n]$,
then sample $x_{i}\sim\mathcal{E}(\lambda_{i})$. The distribution of $x_{i}$
in this case is given by

$\displaystyle\Pr(x_{i}\geq t)$ $\displaystyle=\int_{0}^{\infty}\Pr(x_{i}\geq
t\mid\lambda_{i}=\lambda)e^{-\lambda}d\lambda=\int_{0}^{\infty}e^{-(1+t)\lambda}d\lambda=\frac{1}{1+t}\;,$

which corresponds to $\varphi(t)=1+t$. More generally, we consider
$\varphi(t)=(1+t)^{r}$ for $r\in(\tfrac{1}{2},1]$. Such functions $\varphi$
correspond to distributions with a heavy tale and with infinite expectation
(i.e. $\int_{0}^{\infty}\frac{dt}{\varphi(t)}=\infty$). Using Theorem 2.1,
they only yield lower bounds on the competitive ratio but not on
$\textsf{R}_{n,B}$. Corollary 2.1.2 shows the bound obtained for
$r\to\frac{1}{2}$.

######  Corollary 2.1.2.

Let $w\in[0,1]$. If $B=wn+o(n)$, then it holds for any algorithm A that

$\textsf{CR}_{B}(\textsf{A})\geq(2-w)-(3-2\sqrt{2})w(1-w)\;.$

######  Remark 2.2.

If $x_{i}$ is sampled from the distribution induced by $\varphi(t)=(1+t)^{r}$,
then $x_{i}+1$ follows the Pareto distribution with scale 1 and shape $r$ [9],
which is commonly used to model the distribution of job sizes in the context
of the scheduling problem.

##  3 Known partial order

Before investigating the problem within the learning-augmented framework, we
introduce an algorithm exclusively for the scenario with perfect information.
Subsequently, in Section 4, we present a second algorithm, that we adapt to
handle possibly erroneous predictions.

The optimal algorithm OPT does not necessitate precise knowledge of job sizes.
Instead, it relies solely on their ordering. This observation suggests that it
might be possible to improve the competitive ratio of the non-clairvoyant case
by only knowing the relative order of a subset of the job sizes. Therefore,
rather than having access to the values $x_{\sigma(1)},\ldots,x_{\sigma(B)}$,
we assume that the decision-maker is only given a priority ordering $\pi$ of
them, i.e. a bijection $\pi:[B]\to\sigma([B])$ satisfying
$x_{\pi(1)}\leq\ldots\leq x_{\pi(B)}$.

1: Input: Ordering $\pi$ of $x_{\sigma(1)},\ldots,x_{\sigma(1)}$

2: Set $x_{\pi(0)}=0$

3: for $i=1$ to $B$ do

4: Run job $\pi(i)$ for $x_{\pi(i-1)}$ units of time

5: while job $\pi(i)$ is not finished do

6: Run round-robin on $\\{\sigma(j)\\}_{j>B}\cup\\{\pi(i)\\}$

7: end while

8: end for

9: Run round-robin on $\\{\sigma(j)\\}_{j=B+1}^{n}$ until completion

Algorithm 1 Catch-up and Resume Round-Robin (CRRR)

In Algorithm 1 (CRRR), for all $i\in[B]$, the execution of job $\pi(i)$ starts
only upon the termination of job $\pi(i-1)$. At this moment, all jobs
$\sigma(j)$ for $j>B$ are either completed or have undergone execution for
$x_{\pi(i-1)}$ units of time. CRRR then runs job $\pi(i)$ for a period of
length $x_{\pi(i-1)}$ to catch up with the progress of the jobs
$\\{\sigma(j)\\}_{j>B}$. Following this synchronization phase, it runs round-
robin on the set of jobs $\\{\sigma(j)\\}_{j>B}\cup\\{\pi(i)\\}$ until
$\pi(i)$ terminates. The same process iterates with $\pi(i+1)$ afterward. Once
all the jobs $\sigma(i)$ for $i\in[B]$ are completed, the algorithm runs round
robin on the unfinished jobs in $\\{\sigma(j)\\}_{j>B}$.

######  Theorem 3.1.

Algorithm CRRR satisfies

$2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{(n+1)(B+1)}\leq\textsf{R}_{n,B}(\textsf{CRRR})\leq
2-\frac{B}{n}\;.$

Moreover, if $B=\lfloor wn\rfloor$ for some $w\in[0,1]$, then
$\textsf{CR}(\textsf{CRRR})=2-w$.

Theorem 3.1 shows a substantially stronger result than the one presented in
[15], where the algorithm leveraging the values of the job sizes
$x_{\sigma(1)},\ldots,x_{\sigma(B)}$ is only
$\big{(}2-\frac{B(B-1)}{n(n-1)}\big{)}$-competitive.

##### Action predictions

The information provided to CRRR is the order in which the jobs
$\\{\sigma(i)\\}_{i\in[B]}$ would be executed by OPT. This corresponds to the
error-free scenario of action predictions [3, 40, 37, 8], where the decision-
maker receives predictions regarding the actions taken by the optimal offline
algorithm, rather than numeric predictions of unknown parameters. In the
context of the scheduling problem, utilizing the $\ell_{1}$ norm to measure
the error is not ideal for analyzing the action prediction setting [31].
Alternative error metrics, which account for the number of inversions in the
predicted permutation in comparison to the true one [40], would be more
suitable. Therefore, adapting CRRR to imperfect action predictions is left for
future research as it requires different considerations. For now, we shift our
focus to introducing another algorithm that utilizes not only the priority
order induced by the job sizes, but the size values themselves.

##  4 Predictions of the job sizes

We propose in this section a generic algorithm Switch, which we will adapt in
the cases of perfect and imperfect predictions. The algorithm takes as input
$n$ jobs with unknown sizes and breakpoints $\\{z_{\sigma(i)}\\}_{i\in[B]}$
that depend on the predictions $\\{y_{\sigma(i)}\\}_{i\in[B]}$, then it
alternates round-robin on the jobs $\\{\sigma(j)\\}_{j>B}$ and Shortest
Predicted Job First (SPJF), introduced in [51], on the jobs
$\\{\sigma(i)\\}_{i\in[B]}$, where the moment of switching from an algorithm
to another is determined by the breakpoints.

As in Section 3, we call ordering of $z_{\sigma(1)},\ldots,z_{\sigma(B)}$ any
bijective application $\pi:[B]\to\sigma([B])$ satisfying
$z_{\pi(1)}\leq\ldots\leq z_{\pi(B)}$. Note that, if the breakpoints are not
pairwise distinct, then the ordering is not unique. In that case, Switch
chooses an ordering $\pi$ uniformly at random. We assume furthermore that the
breakpoints induce the same order as the predictions, i.e.
$z_{\sigma(i)}<z_{\sigma(j)}\iff y_{\sigma(i)}<y_{\sigma(j)}$ for all
$i,j\in[B]$.

1: Input: Breakpoints $z^{\sigma}=(z_{\sigma(i)})_{i\in[B]}$

12: Choose an ordering $\pi$ of $(z_{\sigma(i)})_{i\in[B]}$ uniformly at
random;

3: for $i=1$ to $B$ do

4: while jobs $\\{\sigma(j)\\}_{j>B}$ are not all completed and
$\max\limits_{j>B}S_{\sigma(j)}(t)<z_{\pi(i)}$ do

5: Run round-robin on $\\{\sigma(j)\\}_{j=B+1}^{n}$

6: end while

7: Run job $\pi(i)$ until completion

8: end for

9: Run round-robin on $\\{\sigma(j)\\}_{j=B+1}^{n}$ until completion

Algorithm 2 Switch algorithm $\textsf{Switch}(z^{\sigma},x)$

Consider a run of Switch, and let $i\in[B]$. The condition
$\max\limits_{j>B}S_{\sigma(j)}(t)<z_{\pi(i)}$ in the while loop means that no
job $\sigma(j)$ for $j>B$ has been in execution for more than $z_{\pi(i)}$
units of time. Given that round-robin allocates equal importance to all jobs
$\\{\sigma(j)\\}_{j>B}$, upon exiting the while loop, each job $\sigma(j)$ is
either completed or has been in execution for precisely $z_{\pi(i)}$ units of
time. Following this step, job $\pi(i)$ is executed until completion, and the
same process recurs for $i+1$.

###  4.1 Perfect predictions

Assuming that the predictions are perfect, i.e. the decision-maker knows the
exact sizes of jobs ${\sigma(1)},\ldots,{\sigma(B)}$, it is possible to set
$z_{\sigma(i)}=x_{\sigma(i)}$ for all $i\in[B]$.

######  Theorem 4.1.

Algorithm Switch with breakpoints $z_{\sigma(i)}=x_{\sigma(i)}$ for all
$i\in[B]$ satisfies

$\textsf{R}_{n,B}(\textsf{Switch})=2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{n+1}\;.$

In particular, if $B=\lfloor wn\rfloor$ for some $w\in[0,1]$ then
$\textsf{CR}_{B}(\textsf{Switch})=2-w$.

Note that the $(n,B)$-competitive ratio above is strictly better than that of
CRRR, presented in Theorem 3.1. However, both algorithms have equivalent
performance when $n$ is large. In particular, their competitive ratios
coincide when $B=\lfloor wn\rfloor$.

A slight improvement on the $(n,B)$-competitive ratio can be obtained by
introducing randomness into Switch. Consider the Run To Completion algorithm
(RTC) defined in [45], executing all the jobs until completion in a uniformly
random order. Then we have the following result.

######  Proposition 4.2.

The algorithm that runs RTC with probability $\frac{2(n-B)}{n(n+3)-2B}$, and
runs Switch with breakpoints $z_{\sigma(i)}=x_{\sigma(i)}$ for all $i\in[B]$
with the remaining probability, has an $(n,B)$-competitive ratio of

$2-\frac{B}{n}-\frac{2(1-\frac{B}{n})(2-\frac{B}{n})}{n+3-\frac{2B}{n}}\;.$

For $B=0$, the ratio above becomes $2-\frac{4}{n+3}$, which is optimal in the
non-clairvoyant setting.

###  4.2 Imperfect predictions

We assume in this section that no quality guarantees are given on the
predictions $\\{y_{\sigma(i)}\\}_{i\in[B]}$. Recall that the total error
$\eta^{\sigma}=\sum_{i=1}^{B}|x_{\sigma(i)}-y_{\sigma(i)}|$ is a random
variable because $\sigma$ is a uniformly random permutation of $[n]$, hence
our results will depend on $\mathbb{E}[\eta^{\sigma}]$. Furthermore, by
appropriately normalizing the time unit, we can assume that the shortest job
size is at least $1$.

The goal is to design an algorithm that is consistent, robust, and with a
competitive ratio having a smooth dependency to $\mathbb{E}[\eta^{\sigma}]$.
We first study the consistency and smoothness of Switch with well-chosen
breakpoints, then we show that combining it with round-robin as in [51, 37]
gives robustness guarantees.

1: Input: predictions $(y_{\sigma(i)})_{i\in[B]}$, probability $F$

12: Sample $\xi\sim F$;

3: Run Switch with breakpoints $z_{\sigma(i)}=\xi y_{\sigma(i)}$

Algorithm 3 imperfect predictions $\textsf{Switch}(\xi y^{\sigma},x)$

Algorithm 3 simply runs Switch with random breakpoints $z_{\sigma(i)}=\xi
y_{\sigma(i)}$. The following lemma gives an upper bound depending on the
distribution $F$ of $\xi$.

######  Lemma 4.3.

Let $F$ be a probability distribution on $(0,\infty)$, and consider the
mappings $h_{F}:(0,\infty)^{2}\to\mathbb{R}$ and
$g_{F}:(0,\infty)\to\mathbb{R}$ defined by

$\displaystyle h_{F}(s,t)$ $\displaystyle=t\cdot{\textstyle\Pr_{\xi\sim
F}}(\xi<\tfrac{s}{t})$ $\displaystyle g_{F}(s)$
$\displaystyle=(1-s){\textstyle\Pr_{\xi\sim F}}(\xi<s)+\mathbb{E}_{\xi\sim
F}[\xi\mathbbm{1}_{\xi<s}]\;.$

Let $\beta_{F}=\sup_{s\in(0,1]}\frac{g_{F}(s)}{s}$ and $\gamma_{F}=\sup_{s\geq
1}(g_{F}(s)+s)$. If $\beta_{F},\gamma_{F}<\infty$ and $h_{F}$ is
$L_{F}$-Lipschitz w.r.t. the second variable $t$, then for any job sizes
$x_{1},\ldots,x_{n}$ and $B\leq n$, the expected sum of the completion times
achieved by Switch with breakpoints $z_{\sigma(i)}=\xi y_{\sigma(i)}$ is at
most

$\displaystyle\sum_{i=1}^{n}x_{i}+C^{1}_{n,B,F}\sum_{i<j}\min(x_{i},x_{j})+C^{2}_{n,B,F}\mathbb{E}[\eta^{\sigma}]\;,$

with
$C^{1}_{n,B,F}=2-\tfrac{B}{n}-\big{(}2-\beta_{F}-\gamma_{F}\big{)}\tfrac{B}{n}\big{(}1-\tfrac{B-1}{n-1}\big{)}$
and $C^{2}_{n,B,F}=(1+L_{F}+\mathbb{E}[\xi])(n-B)+B-1$.

A trivial choice of $\xi$ is the constant random variable equal to $1$ a.s.,
but this is not enough to guarantee smoothness, as it corresponds to the Dirac
distribution $F=\delta_{1}$, for which $h_{F}$ is not continuous w.r.t. to
$t$.

######  Lemma 4.4.

Let $\rho\in(0,1]$ and

$F:s\mapsto(1-e^{-(s-1)/\rho})\mathbbm{1}_{s>1}$

a shifted exponential distribution with parameter $1/\rho$, i.e. $\xi\sim
1+\mathcal{E}(1/\rho)$, then Switch with breakpoints $z_{\sigma(i)}=\xi
y_{\sigma(i)}$ for all $i\in[B]$ has an $(n,B)$-competitive ratio of at most

$\left(2-\tfrac{B}{n}+\rho\tfrac{B}{n}(1-\tfrac{B-1}{n-1})\right)+\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)\frac{2\mathbb{E}[\eta^{\sigma}]}{n}\;.$

The previous lemma highlights a tradeoff between the smoothness and the
consistency of the algorithm. Indeed, as $\rho$ decreases, the algorithm gains
in consistency, but the term
$\frac{2}{n}\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)$
multiplying $\mathbb{E}[\eta^{\sigma}]$ becomes larger. However, while setting
$\rho$ close to zero results in an arbitrarily high sensitivity to the error,
setting it close to $1$ gives a consistency of at most
$\big{(}2-\frac{B(B-1)}{n(n-1)}\big{)}$, which is still a decreasing function
of $B$, interpolating the values $2$ and $1$ in the clairvoyant and non-
clairvoyant cases. This implies that sacrificing a small amount of consistency
significantly improves smoothness.

For $B=n$, the lemma gives $\textsf{R}_{n,B}(\eta;\textsf{Switch})\leq
1+\frac{2\eta}{n}$, matching the bound proved on (SPJF) in [51]. On the other
hand, if $\eta=0$, setting $\rho=0$ results in
$\textsf{R}_{n,B}(0;\textsf{Switch})\leq 2-\frac{B}{n}$. Using tighter
inequalities in the proof, it is possible to retrieve the bound established in
Theorem 4.1 (See Inequality (39), Appendix C).

##### Preferential algorithm

Now we need to adapt the algorithm to guarantee robustness in the face of
arbitrarily erroneous predictions. We use the same approach as Lemma 3.1 of
[51], which consists of running concurrently a consistent algorithm and round-
robin at respective rates $\lambda$, $1-\lambda$ for some $\lambda\in[0,1]$.
However, their result only applies for deterministic algorithms A satisfying
for any instances $x=(x_{1},\ldots,x_{n})$ and
$x^{\prime}=(x^{\prime}_{1},\ldots,x^{\prime}_{n})$ that

$\big{(}\forall i\in[n]:x_{i}\leq
x^{\prime}_{i}\big{)}\implies\textsf{A}(x)\leq\textsf{A}(x^{\prime})\;.$

Such algorithms are called monotonic. Switch with breakpoints
$z_{\sigma(i)}=\xi y_{\sigma(i)}$ is not deterministic since its objective
function depends both on $\sigma$ and $\xi$. Nonetheless, we overcome this
difficulty by proving that, conditionally to $\sigma$ and $\xi$, its outcome
is deterministic and monotonic, then we establish the following theorem.

######  Theorem 4.5.

Let $\rho\in(0,1]$ and $F=1+\mathcal{E}(1/\rho)$. Then the preferential
algorithm $\textsf{ALG}_{\lambda}$ which runs Algorithm 3 at rate $\lambda$
and round-robin at rate $1-\lambda$ has an $(n,B)$-competitive ratio of at
most

$\min\left(\frac{2}{1-\lambda}\;,\;\frac{C_{\rho,n,B}}{\lambda}+\frac{2S_{\rho,n,B}}{\lambda
n}\cdot\mathbb{E}[\eta^{\sigma}]\right)\;,$

with

$\displaystyle
C_{\rho,n,B}=\big{(}2-\tfrac{B}{n}\big{)}+\rho\tfrac{B}{n}\big{(}1-\tfrac{B-1}{n-1}\big{)}\quad,\quad
S_{\rho,n,B}=\tfrac{4}{\rho}\big{(}1-\tfrac{B}{n}\big{)}+\tfrac{B}{n}\;.$

This upper bound generalizes that of [51]. It presents a consistency-
robustness tradeoff that can be tuned by adjusting the parameter $\lambda$,
and a consistency-smoothness tradeoff controlled by the parameter $\rho$,
which vanishes for $B$ close to $0$ or $n$, as the terms multiplying $\rho$
and $1/\rho$ respectively in $C_{\rho,n,B}$ and $S_{\rho,n,B}$ become zero.

##  5 Experiments

In this section, we validate our theoretical findings by testing the
algorithms we presented on various benchmark job sizes. In all the figures,
each point is averaged over $10^{4}$ independent trials.

##### Perfect information

We test the performance of Algorithms Switch and CRRR against the hard
instances used to prove the lower bounds of Section 2: we consider i.i.d. job
sizes sampled from the exponential distribution with parameter $1$, and job
sizes drawn from the distribution $\Phi(r,a)$ with parameters $r=0.51$ and
$a=10^{4}$, characterized by the tail probability

$\Pr(x^{a}_{i}\geq
t)=\frac{(1+t)^{-r}-(1+a)^{-r}}{1-(1+a)^{-r}}\mathbbm{1}_{t<a}\;,$

This distribution is a truncated version of the one defined by
$\Pr(x^{\infty}_{i}\geq t)=\frac{1}{(1+t)^{r}}$. The bound of Corollary 2.1.2
is obtained by using this distribution for $a>0$ and $r\in(\frac{1}{2},1)$,
and taking the limits $n\to\infty$, $a\to\infty$, and $r\to 1/2$.

Figure 2: Lower bounds and ratios of Switch, CRRR

Figure 2 exhibits the empirical ratios achieved by both algorithms with a
number $n\in\\{20,1000\\}$ of jobs. For $n=20$, Switch outperforms CRRR for
the two distributions, whereas their ratios are very close for $n=1000$. This
confirms that Switch and CRRR are asymptotically equivalent, as can be deduced
from Theorems 3.1 and 4.1. For the exponential distribution, as expected, both
algorithms have ratios above the non-asymptotic lower bound of Corollary
2.1.1. Meanwhile, considering the distribution $\Phi(0.51,10^{4})$, the
empirical ratios for $n=20$ are below the lower bound of Corollary 2.1.2,
because it is proved by taking $n\to\infty$. For $n=1000$, the ratios match
the lower bound.

##### Preferential algorithm

In the remaining discussion, we refer to Switch with breakpoints
$z_{\sigma(i)}=\xi y_{\sigma(i)}$ and $\xi\sim 1+\mathcal{E}(1/\rho)$, as
Switch with parameter $\rho$.

We generate a synthetic instance of $n=50$ job sizes, drawn independently from
the Pareto distribution with scale 1 and shape 1.1. The Pareto distribution,
known for its heavy tail, is particularly suitable for modeling job sizes [28,
12, 9], and it is a commonly used benchmark for learning-augmented scheduling
algorithms [51, 40]. Furthermore, we consider noisy predictions
$y_{i}=x_{i}+\varepsilon_{i}$ for all $i\in[50]$, where $\varepsilon_{i}$ is
sampled independently from a normal distribution with mean $0$ and standard
deviation $\tau$.

Figure 3: Preferential Algorithm (PA) with different parameters

Figure 3 illustrates the empirical ratio of the Preferential Algorithm (PA)
across various parameter configurations, with varying error parameter $\tau$.

The left plot displays the ratios for different $\lambda$ and $\rho$ values,
with $B=25=n/2$. When $\lambda=0$, PA becomes round-robin. For $\lambda=1$ and
$\rho=0.5$, PA simply runs $\textsf{Switch}(\rho=0.5)$, which gives an
improved consistency ($\tau=0$), not equal to $1$ because $B<n$ and $\rho>0$,
and gives a ratio that deteriorates arbitrarily as $\tau$ increases. In
contrast, PA with $\lambda=0.5$ gives a weaker consistency but maintains
bounded ratios, even with arbitrarily erroneous predictions. The choice of
$\rho=0$ exhibits a slightly better consistency compared to $\rho=0.5$, in
line with theoretical expectations, but there is no significant difference
regarding sensitivity to errors. This should not be surprising since setting
$\rho>0$ ensures smoothness in the worst-case (see Figure 4), but it is not
necessarily needed for all instances.

The right plot examines the influence of $B$ on PA with parameters $\lambda=1$
and $\rho=0.5$, which corresponds to Switch with $\rho=0.5$. Larger $B$ values
improve consistency and also yield a smaller sensitivity to small errors.
However, for high $\tau$ values, having numerous predictions leads to faster
performance deterioration compared to having fewer predictions. This shows
that more predictions enhance consistency, while fewer predictions enhance
robustness.

##### Consistency-smoothness

To shed light on the tradeoff between consistency and smoothness raised in
Section 4.2, we consider i.i.d. job sizes $x_{1},\ldots,x_{100}$, each taking
the value 1 w.p. 1/2 and 2 w.p. 1/2, and we consider noisy predictions of the
form $y_{i}=x_{i}+\varepsilon_{i}$, where $\varepsilon_{i}$ follows a uniform
distribution over $[-\tau,\tau]$. Figure 4 illustrates the evolution, for
$\tau$ varying in $[0,0.15]$, of the empirical competitive ratio of Switch
with parameter $\rho\in\\{0,0.1,0.5\\}$ and $B\in\\{50,95\\}$,

For both values of $B$, the experiment reveals that larger values of $\rho$
give bigger ratios when $\tau=0$ (less consistency), but on the other hand
they yield less sensitivity to variations of the expected prediction error
(better smoothness), which confirms our theoretical findings. In particular,
for $\rho=0$, a significant discontinuity arises when $\tau$ becomes positive.
Figure 4 also shows that this tradeoff is less significant as $B$ approaches
$n=100$, with the consistency values for $\rho\in\\{0,0.1,0.5\\}$ drawing
closer.

Figure 4: Tradeoff between consistency and smoothness

##  6 Conclusion and future work

This paper explores the non-clairvoyant scheduling problem with a limited
number of predicted job sizes. We give near optimal lower and upper bounds in
the case of perfect predictions, and we introduce a learning-augmented
algorithm raising the common consistency-robustness tradeoff and an additional
consistency-smoothness tradeoff, the latter vanishing when $B$ approaches $0$
or $n$.

Our findings join previous works in demonstrating that online algorithms can
indeed achieve improved performance even when armed with a restricted set of
predictions, which is an assumption more aligned with practical scenarios.
Furthermore, it affirms the necessity of studying and understanding these
regimes, as they may unveil unique behaviors absent in the zero- or full-
information settings.

###  6.1 Open questions

##### Tight lower bounds

In the case of perfect predictions, there is a (small) gap between the lower
bounds of Section 2 and the competitive ratios of Switch and CRRR. An
interesting research avenue is to close this gap, either by designing better
algorithms or improving the lower bound. This could involve using Theorem 2.1
with more refined distributions.

##### Reduced number of action predictions

Algorithm Switch leverages the job sizes’ predictions, not only the order they
induce. Using the $\ell_{1}$ norm to measure the error is thus a suitable
choice. However, as discussed in Section 3, Algorithm CRRR only uses the
priority order in which OPT runs $(x_{\sigma(i)})_{i\in[B]}$. An interesting
question to explore is how to adapt it in the case of imperfect action
predictions, using appropriate error measures.

##### Smooth and $(2-\frac{B}{n})$-consistent algorithm

Lemma 4.4 and Figure 4 emphasize that, to achieve smoothness, Switch with
parameter $\rho$ must exhibit a consistency exceeding $2-\frac{B}{n}$. A
compelling question arises: Is it possible to devise a smooth algorithm with a
consistency of at most $2-\frac{B}{n}$?

## References

  * ABE+ [23] Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S Larsen, Adam Polak, and Bertrand Simon.  Paging with succinct predictions.  In International Conference on Machine Learning, pages 952–968. PMLR, 2023.
  * ACE+ [21] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon.  Learning-augmented dynamic power management with multiple states via new ski rental bounds.  Advances in Neural Information Processing Systems, 34:16714–16726, 2021.
  * ACE+ [23] Antonios Antoniadis, Christian Coester, Marek Eliáš, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  ACM Transactions on Algorithms, 19(2):1–34, 2023.
  * AGKK [20] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  Advances in Neural Information Processing Systems, 33:7933–7944, 2020.
  * AGP [20] Keerti Anand, Rong Ge, and Debmalya Panigrahi.  Customizing ml predictions for online algorithms.  In International Conference on Machine Learning, pages 303–313. PMLR, 2020.
  * AGS [21] Antonios Antoniadis, Peyman Jabbarzade Ganje, and Golnoosh Shahkarami.  A novel prediction setup for online speed-scaling.  arXiv preprint arXiv:2112.03082, 2021.
  * ALT [21] Yossi Azar, Stefano Leonardi, and Noam Touitou.  Flow time scheduling with uncertain processing time.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1070–1080, 2021.
  * Ano [24] Anonymous.  Algorithms for caching and MTS with reduced number of predictions.  In The Twelfth International Conference on Learning Representations, 2024.
  * Arn [14] Barry C Arnold.  Pareto distribution.  Wiley StatsRef: Statistics Reference Online, pages 1–10, 2014.
  * BDK+ [22] Evripidis Bampis, Konstantinos Dogeas, Alexander V Kononov, Giorgio Lucarelli, and Fanny Pascual.  Scheduling with untrusted predictions.  In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI, pages 4581–4587, 2022.
  * BEY [05] Allan Borodin and Ran El-Yaniv.  Online computation and competitive analysis.  cambridge university press, 2005.
  * BHB [01] Nikhil Bansal and Mor Harchol-Balter.  Analysis of srpt scheduling: Investigating unfairness.  In Proceedings of the 2001 ACM SIGMETRICS International conference on Measurement and modeling of computer systems, pages 279–290, 2001.
  * BMRS [20] Étienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson.  Learning augmented energy minimization via speed scaling.  Advances in Neural Information Processing Systems, 33:15350–15359, 2020.
  * BMS [20] Etienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  Advances in Neural Information Processing Systems, 33:20083–20094, 2020.
  * BP [23] Ziyad Benomar and Vianney Perchet.  Advice querying under budget constraint for online algorithms.  In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
  * BT [13] Kenneth R Baker and Dan Trietsch.  Principles of sequencing and scheduling.  John Wiley & Sons, 2013.
  * CPSZ [21] Jakub Chlkedowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz .Zolna.  Robust learning-augmented caching: An experimental study.  In International Conference on Machine Learning, pages 1920–1930. PMLR, 2021.
  * CS [90] TCE Cheng and CCS Sin.  A state-of-the-art review of parallel-machine scheduling research.  European Journal of Operational Research, 47(3):271–292, 1990.
  * CSVZ [22] Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang.  Faster fundamental graph algorithms via learned predictions.  In International Conference on Machine Learning, pages 3583–3602. PMLR, 2022.
  * CSW [23] Nicolas Christianson, Junxuan Shen, and Adam Wierman.  Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems.  In International Conference on Artificial Intelligence and Statistics, pages 9377–9399. PMLR, 2023.
  * DIL+ [21] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Faster matchings via learned duals.  Advances in neural information processing systems, 34:10393–10406, 2021.
  * DIL+ [22] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Algorithms with prediction portfolios.  Advances in neural information processing systems, 35:20273–20286, 2022.
  * DKT+ [21] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis.  Learning online algorithms with distributional advice.  In International Conference on Machine Learning, pages 2687–2696. PMLR, 2021.
  * DLPLV [21] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii.  Secretaries with advice.  In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 409–429, 2021.
  * DNS [23] Marina Drygala, Sai Ganesh Nagarajan, and Ola Svensson.  Online algorithms with costly predictions.  In International Conference on Artificial Intelligence and Statistics, pages 8078–8101. PMLR, 2023.
  * GLLK [79] Ronald Lewis Graham, Eugene Leighton Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan.  Optimization and approximation in deterministic sequencing and scheduling: a survey.  In Annals of discrete mathematics, volume 5, pages 287–326. Elsevier, 1979.
  * GP [19] Sreenivas Gollapudi and Debmalya Panigrahi.  Online algorithms for rent-or-buy with expert advice.  In International Conference on Machine Learning, pages 2319–2327. PMLR, 2019.
  * HBD [97] Mor Harchol-Balter and Allen B Downey.  Exploiting process lifetime distributions for dynamic load balancing.  ACM Transactions on Computer Systems (TOCS), 15(3):253–285, 1997.
  * HP [03] Nicholas G Hall and Chris N Potts.  Supply chain scheduling: Batching and delivery.  Operations Research, 51(4):566–584, 2003.
  * IDS+ [16] Dmitry Ivanov, Alexandre Dolgui, Boris Sokolov, Frank Werner, and Marina Ivanova.  A dynamic model and an algorithm for short-term supply chain scheduling in the smart factory industry 4.0.  International Journal of Production Research, 54(2):386–402, 2016.
  * IKMQP [21] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.  Non-clairvoyant scheduling with predictions.  In ACM Symposium on Parallelism in Algorithms and Architectures, 2021.
  * IKPP [22] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit.  Parsimonious learning-augmented caching.  In International Conference on Machine Learning, pages 9588–9601. PMLR, 2022.
  * JLT [85] E Douglas Jensen, C Douglass Locke, and Hideyuki Tokuda.  A time-driven scheduling model for real-time operating systems.  In Rtss, volume 85, pages 112–122, 1985.
  * JM [22] Billy Jin and Will Ma.  Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model.  Advances in Neural Information Processing Systems, 35:14555–14567, 2022.
  * KBC+ [18] Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis.  The case for learned index structures.  In Proceedings of the 2018 international conference on management of data, pages 489–504, 2018.
  * LLKS [93] Eugene L Lawler, Jan Karel Lenstra, Alexander HG Rinnooy Kan, and David B Shmoys.  Sequencing and scheduling: Algorithms and complexity.  Handbooks in operations research and management science, 4:445–522, 1993.
  * LLMS [23] Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter.  Minimalistic predictions to schedule jobs with online precedence constraints.  In International Conference on Machine Learning, pages 18563–18583. PMLR, 2023.
  * LLMV [20] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859–1877. SIAM, 2020.
  * LLW [22] Honghao Lin, Tian Luo, and David Woodruff.  Learning augmented binary search trees.  In International Conference on Machine Learning, pages 13431–13440. PMLR, 2022.
  * LM [22] Alexander Lindermayr and Nicole Megow.  Permutation predictions for non-clairvoyant scheduling.  In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, pages 357–368, 2022.
  * LRK [78] Jan Karel Lenstra and AHG Rinnooy Kan.  Complexity of scheduling under precedence constraints.  Operations Research, 26(1):22–35, 1978.
  * LV [18] Thodoris Lykouris and Sergei Vassilvtiskii.  Competitive caching with machine learned advice.  In International Conference on Machine Learning, pages 3296–3305. PMLR, 2018.
  * Mar [82] Charles Martel.  Preemptive scheduling with release times, deadlines, and due times.  Journal of the ACM (JACM), 29(3):812–829, 1982.
  * MLH+ [23] Jessica Maghakian, Russell Lee, Mohammad Hajiesmaili, Jian Li, Ramesh Sitaraman, and Zhenhua Liu.  Applied online algorithms with heterogeneous predictors.  In International Conference on Machine Learning, pages 23484–23497. PMLR, 2023.
  * MPT [94] Rajeev Motwani, Steven Phillips, and Eric Torng.  Nonclairvoyant scheduling.  Theoretical computer science, 130(1):17–47, 1994.
  * MRS+ [23] Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet.  On preemption and learning in stochastic scheduling.  In International Conference on Machine Learning, pages 24478–24516. PMLR, 2023.
  * MV [17] Andres Munoz and Sergei Vassilvitskii.  Revenue optimization with approximate bid predictions.  Advances in Neural Information Processing Systems, 30, 2017.
  * MV [22] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  Communications of the ACM, 65(7):33–35, 2022.
  * PI [77] Shrikant S Panwalkar and Wafik Iskander.  A survey of scheduling rules.  Operations research, 25(1):45–61, 1977.
  * Pin [12] Michael L Pinedo.  Scheduling, volume 29.  Springer, 2012.
  * PSK [18] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  Advances in Neural Information Processing Systems, 31, 2018.
  * RS [94] Krithi Ramamritham and John A Stankovic.  Scheduling algorithms and operating systems support for real-time systems.  Proceedings of the IEEE, 82(1):55–67, 1994.
  * SLLA [23] Yongho Shin, Changyeol Lee, Gukryeol Lee, and Hyung-Chan An.  Improved learning-augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis.  arXiv preprint arXiv:2302.06832, 2023.
  * SO [22] Shinsaku Sakaue and Taihei Oki.  Discrete-convex-analysis-based framework for warm-starting algorithms with predictions.  Advances in Neural Information Processing Systems, 35:20988–21000, 2022.
  * SWP [04] Christoph Steiger, Herbert Walder, and Marco Platzner.  Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks.  IEEE Transactions on computers, 53(11):1393–1407, 2004.
  * WZ [20] Alexander Wei and Fred Zhang.  Optimal robustness-consistency trade-offs for learning-augmented online algorithms.  Advances in Neural Information Processing Systems, 33:8042–8053, 2020.
  * Yao [77] Andrew Chi-Chin Yao.  Probabilistic computations: Toward a unified measure of complexity.  In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 222–227. IEEE Computer Society, 1977.

Proofs and auxiliary results

##  Appendix A Lower bounds

###  A.1 Preliminary result

######  Lemma A.1.

Let $F$ be a probability distribution on $(0,\infty)$ with finite expectation,
$x$ an array of $n$ i.i.d. random variables sampled from $F$, and
$\alpha_{n,B}\geq 0$ satisfying for any deterministic algorithm A with access
the sizes of $B$ jobs that

$\frac{\mathbb{E}_{\sigma,x}[\textsf{A}(x)]}{\mathbb{E}_{x}[\textsf{OPT}(x)]}\geq\alpha_{n,B}\;,$

then for any (deterministic or randomized) algorithm ALG, we have

$\textsf{R}_{n,B}(\textsf{ALG})\geq\alpha_{n,B}\;.$

###### Proof.

Let $F$ and $\alpha_{n,B}$ be as stated in the lemma. Using Yao’s minimax
principle [57] we deduce that for any randomized algorithm ALG

$\displaystyle\mathbb{E}_{\sigma,x}[\textsf{ALG}(x)]$
$\displaystyle\geq\inf_{\textsf{A}\text{
deterministic}}\mathbb{E}_{\sigma,x}[\textsf{A}(x)]$
$\displaystyle\geq\alpha_{n,B}\mathbb{E}_{x}[\textsf{OPT}(x)]\;,$

where the infimum is taken over all deterministic algorithms. The previous
inequality can be written as

$\mathbb{E}_{x}\big{[}\mathbb{E}_{\sigma}[\textsf{ALG}(x)]-\alpha_{n,B}\textsf{OPT}(x)\big{]}\geq
0\;,$

and this implies that, necessarily, there exists a value
$x^{*}=(x^{*}_{n},\ldots,x^{*}_{n})$ taken by $x$ verifying
$\mathbb{E}_{\sigma}[\textsf{ALG}(x^{*})]-\alpha_{n,B}\textsf{OPT}(x^{*})\geq
0$, hence

$\textsf{R}_{n,B}(\textsf{ALG})\geq\frac{\mathbb{E}_{\sigma}[\textsf{ALG}(x^{*})]}{\textsf{OPT}(x^{*})}\geq\alpha_{n,B}\;.$

∎

###  A.2 Proof of Theorem 2.1

Let A be a deterministic algorithm. Using Equation 1, it suffices to bound
$\mathbb{E}[P^{\textsf{A}}_{ij}]$ for all $i\neq j$ to deduce a bound on
$\mathbb{E}[\textsf{A}(x)]$, and since $P^{\textsf{A}}_{ij}$ is a non-negative
random variable, the focus can be narrowed down to bounding
$\Pr(P_{ij}^{\textsf{A}}>t)$ for all $t>0$. Following the proof scheme of
[45], we introduce the following definition.

######  Definition A.1.

Let A be a deterministic algorithm given an instance of $n$ jobs. For all
$i\neq j\in[n]$ and $t\geq 0$, we denote by $u_{i,j}^{\textsf{A}}(t)$ the time
spent on job $i$ when the total time spent on both jobs $i$ and $j$ is $t$,
assuming neither job $i$ nor $j$ is completed. More precisely,
$u_{i,j}^{\textsf{A}}(t)$ is defined by

$u_{i,j}^{\textsf{A}}(t)=S^{\textsf{A}}_{i}\big{(}\inf\\{t^{\prime}\geq
0:S^{\textsf{A}}_{i}(t^{\prime})+S^{\textsf{A}}_{j}(t^{\prime})=t\\}\big{)}\;.$

$u_{i,j}^{\textsf{A}}$ is therefore a rule defined solely by the algorithm.
For an instance $x=(x_{1},\ldots,x_{n})$ of job sizes, the real time spent on
$i$ when a total time of $t$ has been spent on both jobs $i,j$ is given by
$\min(u_{i,j}^{\textsf{A}}(t),x_{i})$.

For all $t\geq 0$, the following Lemma allows to express the event
$P^{\textsf{A}}_{ij}>t$ using $u_{ij}^{\textsf{A}}(t)$.

######  Lemma A.2.

Let $x_{1},\ldots,x_{n}$ be instance of $n$ job sizes, then for any algorithm
A, for any $i\neq j\in[n]$ and $t\geq 0$, the following equivalence holds

$\big{(}P^{\textsf{A}}_{ij}>t\big{)}\iff\big{(}x_{i}>u^{\textsf{A}}_{i,j}(t)\text{
and }x_{j}>t-u^{\textsf{A}}_{j,i}(t)\big{)}$

###### Proof.

Let A be an algorithm and $i\neq j\in[n]$. We denote by
$S_{ij}(t)=S_{i}(t)+S_{j}(t)$ the total processing time spent on both jobs $i$
and $j$ up to time $t$. Assuming that job $i$ finishes first, i.e. $t_{i}\leq
t_{j}$, no processing time is spent on job $i$ after $t_{i}$, hence
$S_{i}(t_{j})=S_{i}(t_{i})=x_{i}$, and
$P_{ij}=S_{i}(t_{j})+S_{j}(t_{i})=S_{ij}(t_{i})$. By symmetry, we deduce that
$P_{ij}=S_{ij}(\min(t_{i},t_{j}))$. Therefore, using that $S_{i}$ and $S_{j}$
are non-decreasing and continuous, it holds for all $t\geq 0$

$\displaystyle P_{ij}>t$ $\displaystyle\iff S_{ij}(\min(t_{i},t_{j}))>t$
$\displaystyle\iff\min(t_{i},t_{j})>\inf\\{t^{\prime}:S_{ij}(t^{\prime})\geq
t\\}$ $\displaystyle\iff x_{i}>S_{i}(\inf\\{t^{\prime}:S_{ij}(t^{\prime})\geq
t\\})\text{ and }x_{j}>S_{j}(\inf\\{t^{\prime}:S_{ij}(t^{\prime})\geq t\\})$
(4) $\displaystyle\iff x_{i}>u_{ij}(t)\text{ and }x_{j}>t-u_{ij}(t)\;.$ (5)

Equivalence (4) holds because $t_{i}=\inf\\{t^{\prime}\geq
0:S_{i}(t^{\prime})\geq x_{i}\\}$, thus for any $s\geq 0$ we have $t>s\iff
x_{i}>S_{i}(s)$. The same holds for $j$. For Equivalence (5), we simply used
Definition A.1 and the observation $u_{ij}(t)+u_{ji}(t)=t$. ∎

######  Remark A.3.

In the case of non-clairvoyant algorithms, the rule defining
$u^{\textsf{A}}_{ij}(\cdot)$ is dictated by the algorithm, independent of the
job sizes. Thus, if the job sizes are sampled independently from the
exponential distribution, Lemma A.2 gives for all $i\neq j$ that
$\Pr(P^{\textsf{A}}_{ij}>t)=\Pr(x_{i}>u^{\textsf{A}}_{i,j}(t))\Pr(x_{j}>t-u^{\textsf{A}}_{j,i}(t))=e^{-t}$,
and it follows immediately that $\mathbb{E}[P^{\textsf{A}}_{ij}]=1$ for any
deterministic algorithm. This argument, used in [45], is not applicable in our
context since the algorithm possesses access to certain job sizes, enabling
the formulation of a rule for $u^{\textsf{A}}_{i,j}$ that considers this
information. Therefore, more sophisticated techniques become necessary for our
analysis since the independence of the events $x_{i}>u^{\textsf{A}}_{i,j}(t)$
and $x_{j}>t-u^{\textsf{A}}_{j,i}(t)$ is lost.

######  Lemma A.4.

Let $a\in(0,\infty)$ and $\varphi:[0,\infty)\to[0,\infty)$ a continuously
differentiable and increasing function satisfying that $\varphi(0)>0$,
$t\mapsto\frac{\varphi^{\prime}(t)}{\varphi(t)}$ is non-increasing and
$\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}<\infty$. Let
$x_{1}^{a},\ldots,x_{n}^{a}$ i.i.d. random job sizes with distribution

$\Pr(x_{1}^{a}\leq
t)=1-\frac{\varphi(t)^{-1}-\varphi(a)^{-1}}{\varphi(0)^{-1}-\varphi(a)^{-1}}\mathbbm{1}_{t<a}\;,$

then for any algorithm A having access to the sizes of the first $B$ jobs
$x^{a}_{1},\ldots,x^{a}_{B}$, it holds that

$\displaystyle\mathbb{E}[P^{\textsf{A}}_{ij}]$
$\displaystyle\geq\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt-\underset{a\to\infty}{o(1)}$
$\displaystyle\forall i\neq j\leq B\;,$
$\displaystyle\mathbb{E}[P^{\textsf{A}}_{ij}]$ $\displaystyle\geq
2\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt-\underset{a\to\infty}{o(1)}$
$\displaystyle\forall i\neq j>B\;,$
$\displaystyle\mathbb{E}[P^{\textsf{A}}_{ij}]$
$\displaystyle\geq\varphi(0)^{2}\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}\frac{\varphi^{\prime}(x)}{\varphi(x)}dx-\underset{a\to\infty}{o(1)}\qquad$
$\displaystyle\forall i\leq B,j>B\;,$

where $G_{\varphi}(x,T)$ is defined in Equation (3), and the
$\underset{a\to\infty}{o(1)}$ term does not depend on the algorithm A.

Although Lemma A.4 is stated with $a\in(0,\infty)$, the results also hold for
random variables $x^{\infty}_{1},\ldots,x^{\infty}_{n}$ sampled from the limit
distribution $\Pr(x_{1}^{\infty}\leq t)=1-\frac{\varphi(0)}{\varphi(t)}$,
where the $o(1)$ term becomes zero.

Before proving the lemma, let us first observe that, since $\varphi$ is
increasing and $\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}<\infty$, then
necessarily $\lim_{x\to\infty}\varphi(x)=\infty$.

###### Proof.

Let us first observe that for all $t\geq 0$

$\Pr(\min(x^{\infty}_{1},x^{\infty}_{2})\geq t)=\Pr(x^{\infty}_{1}\geq
t)\Pr(x^{\infty}_{2}\geq t)=\frac{\varphi(0)^{2}}{\varphi(t)^{2}}\;,$

hence

$\mathbb{E}[\min(x^{\infty}_{1},x^{\infty}_{2})]=\int_{0}^{\infty}\Pr(\min(x^{\infty}_{1},x^{\infty}_{2})\geq
t)dt=\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt\;.$

In the following, we prove separately the three claims of the Lemma: in the
cases where both jobs sizes $x_{i},x_{j}$ are known, both are unknown, and
where only $x_{i}$ is known.

##### Both job sizes are known

For any $i\neq j\in[n]$, it holds that $P_{ij}\geq\min(x^{a}_{i},x^{a}_{j})$,
and this true in particular for $i\neq j\in[B]$. Furthermore, for any $t\geq
0$, since $\varphi(t)\geq\varphi(0)$, we have that the mapping
$a\mapsto\frac{\varphi(t)^{-1}-\varphi(a)^{-1}}{\varphi(0)^{-1}-\varphi(a)^{-1}}$
is non-increasing. It follows that

$\displaystyle\Pr(x_{1}^{a}\leq t)$ $\displaystyle\leq
1-\left(\lim_{a^{\prime}\to\infty}\frac{\varphi(t)^{-1}-\varphi(a^{\prime})^{-1}}{\varphi(0)^{-1}-\varphi(a^{\prime})^{-1}}\right)\mathbbm{1}_{t<a}$
$\displaystyle=1-\frac{\varphi(0)}{\varphi(t)}\mathbbm{1}_{t<a}\;,$ (6)

and therefore, for any $i\neq j\leq B$

$\displaystyle\mathbb{E}[P_{ij}]$
$\displaystyle\geq\mathbb{E}[\min(x_{1}^{a},x_{2}^{a})]$
$\displaystyle=\int_{0}^{\infty}\Pr(x_{1}^{a}\geq t)^{2}dt$
$\displaystyle\geq\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}\mathbbm{1}_{t<a}dt=\int_{0}^{a}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt$
$\displaystyle=\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt-\underset{a\to\infty}{o(1)}\;.$

##### Both job sizes are unknown

For $i\neq j>B$, the algorithm ignores the job sizes $x^{a}_{i}$ and
$x^{a}_{j}$ Therefore, $u_{i,j}$ is independent of $x^{a}_{i}$ and
$x^{a}_{j}$. Consequently, using Lemma A.2, the independence of $x_{i}^{a}$
and $x_{j}^{a}$, then Inequality (6), we obtain

$\displaystyle\Pr(P_{ij}>t)$ $\displaystyle=\Pr(x_{i}>u_{i,j}(t)\text{ and
}x_{j}>t-u_{i,j}(t))$
$\displaystyle=\Pr(x_{i}>u_{i,j}(t))\Pr(x_{j}>t-u_{i,j}(t))$
$\displaystyle\geq\left(\frac{\varphi(0)}{\varphi(u_{i,j}(t))}\mathbbm{1}_{u_{i,j}(t)<a}\right)\left(\frac{\varphi(0)}{\varphi(t-u_{i,j}(t))}\mathbbm{1}_{t-u_{i,j}(t)<a}\right)$
$\displaystyle=\frac{\varphi(0)^{2}\mathbbm{1}_{t-a<u_{i,j}(t)<a}}{\varphi(u_{i,j}(t)\varphi(t-u_{i,j}(t))}\;.$

Using that $\frac{\varphi^{\prime}}{\varphi}$ is non-increasing, we have for
any $t,u\geq 0$ that

$\displaystyle\frac{d}{du}\left(\varphi(u)\varphi(t-u)\right)$
$\displaystyle=\varphi^{\prime}(u)\varphi(t-u)-\varphi(u)\varphi^{\prime}(t-u)$
$\displaystyle=\varphi(u)\varphi(t-u)\left(\frac{\varphi^{\prime}(u)}{\varphi(u)}-\frac{\varphi^{\prime}(t-u)}{\varphi(t-u)}\right)$

The sign of $\frac{d}{du}\left(\varphi(u)\varphi(t-u)\right)$ is the same as
that of
$\frac{\varphi^{\prime}(u)}{\varphi(u)}-\frac{\varphi^{\prime}(t-u)}{\varphi(t-u)}$,
which is a non-increasing function. It is null for $u=t/2$, hence it is non-
positive for $u\leq t/2$ and non-negative for $u\geq t/2$. This implies that
$u\mapsto\varphi(u)\varphi(t-u)$ is minimal for $u=t/2$, i.e.
$\varphi(u)\varphi(t-u)\leq\varphi(\tfrac{t}{2})^{2}$ for all $t,u\geq 0$, in
particular

$\Pr(P_{ij}>t)\geq\frac{\varphi(0)^{2}}{\varphi(t/2)^{2}}\mathbbm{1}_{t-a<u_{i,j}(t)<a}\;,$

and it follows that

$\displaystyle\mathbb{E}[P_{ij}]$
$\displaystyle=\int_{0}^{\infty}\Pr(P_{ij}>t)dt\geq\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(\tfrac{t}{2})^{2}}\mathbbm{1}_{t-a<u_{i,j}(t)<a}dt\;.$

Observing that, for any $t\geq 0$, the mapping
$a\mapsto\varphi(0)^{2}/\varphi(\tfrac{t}{2})^{2}\mathbbm{1}_{t-a<u_{i,j}(t)<a}$
is non-decreasing, and its limit is
$\varphi(0)^{2}/\varphi(\tfrac{t}{2})^{2}$, the monotone convergence theorem
guarantees that

$\displaystyle\lim\limits_{a\to\infty}\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(\tfrac{t}{2})^{2}}\mathbbm{1}_{t-a<u_{i,j}(t)<a}dt$
$\displaystyle=\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(\tfrac{t}{2})^{2}}dt$
$\displaystyle=2\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt\;,$

therefore, for any $i\neq j>B$

$\mathbb{E}[P_{ij}]\geq
2\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt-\underset{a\to\infty}{o(1)}\;.$

##### Only the size of one job is known

For $i\leq B$ and $j>B$, the algorithm knows $x^{a}_{i}$, therefore
$u_{ij}(\cdot)$ can be a function of $x^{a}_{i}$. By Lemma A.2 then Inequality
(6), it holds for all $t\geq 0$ that

$\displaystyle\Pr(P_{ij}>t)$ $\displaystyle=\Pr(x^{a}_{i}>u_{i,j}(t)\text{ and
}x^{a}_{j}>t-u_{i,j}(t))$
$\displaystyle=\mathbb{E}[\mathbbm{1}_{x^{a}_{i}>u_{i,j}(t)}\mathbbm{1}_{x^{a}_{j}>t-u_{i,j}(t)}]$
$\displaystyle=\mathbb{E}\big{[}\mathbbm{1}_{x^{a}_{i}>u_{i,j}(t)}\mathbb{E}[\mathbbm{1}_{x^{a}_{j}>t-u_{i,j}(t)}\mid
x^{a}_{i},u_{i,j}(t)]\big{]}$
$\displaystyle=\mathbb{E}\big{[}\mathbbm{1}_{x^{a}_{i}>u_{i,j}(t)}\Pr\big{(}x^{a}_{j}>t-u_{i,j}(t)\mid
u_{i,j}(t)\big{)}\big{]}$
$\displaystyle\geq\mathbb{E}\left[\mathbbm{1}_{x^{a}_{i}>u_{i,j}(t)}\frac{\varphi(0)\mathbbm{1}_{t-u_{i,j}(t)<a}}{\varphi(t-u_{i,j}(t))}\right]$
$\displaystyle\geq\varphi(0)\mathbb{E}\left[\frac{\mathbbm{1}_{t-a<u_{i,j}(t)<x^{a}_{i}}}{\varphi(t-u_{i,j}(t))}\right]\;,$

and we obtain by integrating over $t$ and then using Tonelli’s theorem that

$\displaystyle\mathbb{E}[P_{ij}]$
$\displaystyle=\int_{0}^{\infty}\Pr(P_{ij}>t)dt$
$\displaystyle\geq\varphi(0)\mathbb{E}\left[\int_{0}^{\infty}\frac{\mathbbm{1}_{t-a<u_{i,j}(t)<x^{a}_{i}}}{\varphi(t-u_{i,j}(t))}dt\right]\;.$

Recall that $u_{i,j}(t)$ is defined as the time spent on job $i$ when a total
of $t$ units of time have been spent on both jobs $i$ and $j$, thus
$u_{ij}(0)=0$, $u_{ij}$ is non-decreasing and it is 1-Lipschitz. Let us denote
by $\mathcal{V}$ the set of functions on $[0,\infty)$ satisfying these
properties

$\mathcal{V}=\Big{\\{}v:[0,\infty)\to[0,\infty)\;:\;v(0)=0\text{ and
}\tfrac{v(t_{2})-v(t_{1})}{t_{2}-t_{1}}\in[0,1]\;\forall
t_{1}<t_{2}\Big{\\}}\;,$

and for all $x\geq 0$ and $T\in[0,\infty]$, we denote by $\mathcal{V}_{x,T}$
the subset of $\mathcal{V}$ defined as

$\mathcal{V}_{x,T}=\Big{\\{}v\in\mathcal{V}:\inf\\{t\geq 0:v(t)\geq
x\\}=T\Big{\\}}\;.$

For any $x\geq 0$ and $v\in\mathcal{V}$, let $T_{v}=\inf\\{t\geq 0:v(t)\geq
x\\}$, then $v\in\mathcal{V}_{x,T_{v}}$. Since $v$ is $1$-Lipschitz and
$v(0)=0$, it holds that $T_{v}\geq x$. If $v(t)<x$ for all $t\geq 0$ then
$T_{v}=\infty$. Therefore, we have for any $x\geq 0$

$\mathcal{V}=\bigcup_{T\in[x,\infty]}\mathcal{V}_{x,T}\;.$

Furthermore, given that $v$ is non-decreasing, $v(t)<x$ if and only if
$t<T_{v}$. Consequently, $\mathbb{E}[P_{ij}]$ satisfies

$\displaystyle\mathbb{E}[P_{ij}]$
$\displaystyle\geq\varphi(0)\mathbb{E}\left[\inf_{v\in\mathcal{V}}\int_{0}^{\infty}\frac{\mathbbm{1}_{t-a<v(t)<x^{a}_{i}}}{\varphi(t-v(t))}dt\right]$
$\displaystyle=\varphi(0)\mathbb{E}\left[\inf_{T\in[x^{a}_{i},\infty]}\inf_{v\in\mathcal{V}_{x^{a}_{i},T}}\int_{0}^{\infty}\frac{\mathbbm{1}_{t-a<v(t)<x^{a}_{i}}}{\varphi(t-v(t))}dt\right]$
$\displaystyle=\varphi(0)\mathbb{E}\left[\inf_{T\in[x^{a}_{i},\infty]}\inf_{v\in\mathcal{V}_{x^{a}_{i},T}}\int_{0}^{T}\frac{\mathbbm{1}_{t-a<v(t)}}{\varphi(t-v(t))}dt\right]\;.$
(7)

Let $x>0$ and $T\in[x,\infty]$, and define $v_{x,T}^{*}:t\geq
0\mapsto(t-T+x)\mathbbm{1}_{t>T-x}$, then for all $v\in\mathcal{V}_{x,T}$ we
have $v(t)\geq v_{x,T}^{*}(t)$ for all $t\in[0,T]$. Indeed, $v(t)\geq
0=v_{x,T}^{*}(t)$ for $t\in[0,T-x]$, and if $v(t)<v_{x,T}^{*}(t)$ for some
$t\in[T-x,T]$ then, because $v$ is $1$-Lipschitz, we have

$v(T)\leq v(T-x)+x<v_{x,T}^{*}(T-x)+x=x\;,$

which contradicts $v(T)\geq x$. Finally, as $\varphi$ and
$v\mapsto\mathbbm{1}_{t-a<v}$ are both non-decreasing, it holds for any
$v\in\mathcal{V}_{x,T}$ that

$\displaystyle\int_{0}^{T}\frac{\mathbbm{1}_{t-a<v(t)}}{\varphi(t-v(t))}dt$
$\displaystyle\geq\int_{0}^{T}\frac{\mathbbm{1}_{t-a<v_{x,T}^{*}(t)}}{\varphi(t-v_{x,T}^{*}(t))}dt$
$\displaystyle=\int_{0}^{T-x}\frac{\mathbbm{1}_{t-a<0}}{\varphi(t)}dt+\int_{T-x}^{T}\frac{\mathbbm{1}_{t-a<t-T+x}}{\varphi(T-x)}dt$
$\displaystyle=\int_{0}^{\min(a,T-x)}\frac{dt}{\varphi(t)}+\frac{x\mathbbm{1}_{T-x<a}}{\varphi(T-x)}$
$\displaystyle=\left\\{\begin{array}[]{ll}\int_{0}^{T-x}\frac{dt}{\varphi(t)}+\frac{x}{\varphi(T-x)}&\mbox{if
}T-x<a\\\ \int_{0}^{a}\frac{dt}{\varphi(t)}&\mbox{if }T-x\geq
a\end{array}\right.$ (10)
$\displaystyle=\left\\{\begin{array}[]{ll}G_{\varphi}(x,T)&\mbox{if }T-x<a\\\
\int_{0}^{a}\frac{dt}{\varphi(t)}&\mbox{if }T-x\geq a\end{array}\right.\;.$
(13)

Taking the infimum over $v\in\mathcal{V}_{x,T}$ then over $T\in[x,\infty]$ in
(13) gives for any $x\geq 0$ that

$\displaystyle\inf_{T\in[x,\infty]}\inf_{v\in\mathcal{V}_{x,T}}\int_{0}^{T}\frac{\mathbbm{1}_{t-a<v(t)}}{\varphi(t-v(t))}dt$
$\displaystyle\geq\min\left(\inf_{T\in[x,a+x)}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)$
$\displaystyle\geq\min\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)\;,$

and substituting into 7 leads to

$\displaystyle\mathbb{E}[P_{ij}]$
$\displaystyle\geq\varphi(0)\mathbb{E}\left[\min\left(\inf_{T\in[x^{a}_{1},\infty]}G_{\varphi}(x^{a}_{1},T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)\right]\;.$

Let us denote by $f_{a}$ and $f_{\infty}$ respectively the density functions
of $x_{1}^{a}$ and $x_{1}^{\infty}$. We have for any $x>0$ that

$f_{a}(x)=\frac{d}{dx}\Pr(x^{a}_{1}\leq
x)=\frac{\varphi^{\prime}(x)/\varphi(x)^{2}}{\varphi(0)^{-1}-\varphi(a)^{-1}}\mathbbm{1}_{x<a}\geq\frac{\varphi(0)\varphi^{\prime}(x)}{\varphi(x)^{2}}\mathbbm{1}_{x<a}=f_{\infty}(x)\mathbbm{1}_{x<a}\;,$
(14)

therefore

$\displaystyle\mathbb{E}[P_{ij}]$
$\displaystyle=\varphi(0)\int_{0}^{\infty}\min\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)f_{a}(x)dx$
$\displaystyle\geq\varphi(0)\int_{0}^{\infty}\min\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)f_{\infty}(x)\mathbbm{1}_{x<a}dx\;.$
(15)

Observing for all $x>0$ that

$\inf_{T\in[x,\infty]}G_{\varphi}(x,T)\leq\lim_{T\to\infty}G_{\varphi}(x,T)=\int_{0}^{\infty}\frac{dt}{\varphi(t)}$
(16)

and that the mapping
$a\mapsto\min\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)f_{\infty}(x)\mathbbm{1}_{x<a}$
is non-decreasing, the monotone convergence theorem, the continuity of the
minimum, then Inequality 16 guarantee that

$\displaystyle\lim_{a\to\infty}\int_{0}^{\infty}\min$
$\displaystyle\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)f_{\infty}(x)\mathbbm{1}_{x<a}dx$
$\displaystyle=\int_{0}^{\infty}\lim_{a\to\infty}\left\\{\min\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)f_{\infty}(x)\mathbbm{1}_{x<a}\right\\}dx$
$\displaystyle=\int_{0}^{\infty}\min\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{\infty}\frac{dt}{\varphi(t)}\right)f_{\infty}(x)dx$
$\displaystyle=\int_{0}^{\infty}\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T)\right)f_{\infty}(x)dx$
$\displaystyle=\varphi(0)\int_{0}^{\infty}\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T)\right)\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx\;.$

Finally, the previous term is finite because

$\displaystyle\int_{0}^{\infty}\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T)\right)\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle\leq\int_{0}^{\infty}G_{\varphi}(x,2x)\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle=\int_{0}^{\infty}\left(\int_{0}^{x}\frac{dt}{\varphi(t)}+\frac{x}{\varphi(x)}\right)\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle\leq\int_{0}^{\infty}\left(2\int_{0}^{x}\frac{dt}{\varphi(t)}\right)\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle=2\int_{0}^{\infty}\left(\int_{t}^{\infty}\frac{\varphi^{\prime}(x)}{\varphi(t)^{2}}\right)\frac{dt}{\varphi(t)}$
$\displaystyle=2\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}<\infty\;.$

Therefore

$\displaystyle\int_{0}^{\infty}\min$
$\displaystyle\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T),\int_{0}^{a}\frac{dt}{\varphi(t)}\right)\frac{\varphi(0)}{\varphi(t)}\mathbbm{1}_{t<a}dt$
$\displaystyle=\varphi(0)\int_{0}^{\infty}\left(\inf_{T\in[x,\infty]}G_{\varphi}(x,T)\right)\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx-o(1)\;,$

and substituting into Inequality (15) gives the aimed result.

∎

####  A.2.1 Proof of the theorem

Using the previous lemmas, we can now prove the theorem.

###### Proof.

Let $x=(x_{1},\ldots,x_{n})$ be an array of i.i.d. random job sizes with
distribution $\Pr(x_{i}\leq t)=1-\frac{\varphi(0)}{\varphi(t)}$. Observe that

$\mathbb{E}[x_{1}]=\int_{0}^{\infty}\Pr(x_{1}\geq
t)dt=\varphi(0)\int_{0}^{\infty}\frac{dt}{\varphi(t)}\quad,\quad\mathbb{E}[\min(x_{1},x_{2})]=\int_{0}^{\infty}\Pr(x_{1}\geq
t)^{2}dt=\varphi(0)^{2}\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}\;.$

Lemma A.4 with $a=\infty$ gives for any algorithm A that
$\mathbb{E}[P_{ij}]\geq\mathbb{E}[\min(x_{1},x_{2})]$ for $i\neq j\leq B$,
$\mathbb{E}[P_{ij}]\geq 2\mathbb{E}[\min(x_{1},x_{2})]$ for $i\neq j>B$, and
$\mathbb{E}[P_{ij}]\geq\alpha_{\varphi}\mathbb{E}[\min(x_{1},x_{2})]$ for
$i\leq B,j>B$. Indeed, the probability density function of $x_{1}$ is
$t\mapsto\frac{\varphi(0)\varphi^{\prime}(t)}{\varphi(t)^{2}}$, and we have
for all $i\leq B$ and $j>B$ that

$\displaystyle\varphi(0)\mathbb{E}\big{[}\inf_{T\geq
x_{1}}G_{\varphi}(x_{1},T)\big{]}$
$\displaystyle=\varphi(0)^{2}\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle\geq\alpha_{\varphi}\varphi(0)^{2}\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}=\alpha_{\varphi}\mathbb{E}[\min(x_{1},x_{2})]\;.$

Assume that $\int_{0}^{\infty}\frac{dt}{\varphi(t)}<\infty$, i.e.
$\mathbb{E}[x_{1}]<\infty$, then by Equation (1) it holds that

$\displaystyle\mathbb{E}[\textsf{A}(x)]$ $\displaystyle\geq
n\mathbb{E}[x_{1}]+\sum_{1\leq i<j\leq
B}\mathbb{E}[\min(x_{1},x_{2})]+\sum_{B<i<j\leq
n}2\mathbb{E}[\min(x_{1},x_{2})]+\sum_{i=1}^{B}\sum_{j=B+1}^{n}\alpha_{\varphi}\mathbb{E}[\min(x_{1},x_{2})]$
$\displaystyle=n\mathbb{E}[x_{1}]+\left(\frac{B(B-1)}{2}+(n-B)(n-B-1)+\alpha_{\varphi}B(n-B)\right)\mathbb{E}[\min(x_{1},x_{2})]\;,$

the terms multiplying $\mathbb{E}[\min(x_{1},x_{2})]$ can be reordered as
follows

$\displaystyle\frac{B(B-1)}{2}$
$\displaystyle+(n-B)(n-B-1)+\alpha_{\varphi}B(n-B)$
$\displaystyle=\frac{B(B-1)}{2}+(n-B)(n-1+(\alpha_{\varphi}-1)B)$
$\displaystyle=\frac{B(B-1)}{2}+n(n-1)+(\alpha_{\varphi}-1)nB-
nB-B((\alpha_{\varphi}-1)B-1)$
$\displaystyle=\frac{B(B-1)}{2}+n(n-1)+(\alpha_{\varphi}-2)nB-(\alpha_{\varphi}-1)B(B-1)-(\alpha_{\varphi}-2)B$
$\displaystyle=n(n-1)-(2-\alpha_{\varphi})(n-1)B+(\tfrac{3}{2}-\alpha_{\varphi})B(B-1)$
(17)
$\displaystyle=\frac{n(n-1)}{2}\left(2-(4-2\alpha_{\varphi})\frac{B}{n}+(3-2\alpha_{\varphi})\frac{B(B-1)}{n(n-1)}\right)$
(18)
$\displaystyle=\frac{n(n-1)}{2}\left(2-\frac{B}{n}-(3-2\alpha_{\varphi})\frac{B}{n}\left(1-\frac{B(B-1)}{n(n-1)}\right)\right)\;,$
(19)

hence

$\displaystyle\mathbb{E}[\textsf{A}(x)]=n\mathbb{E}[x_{1}]+C_{n,B}\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]\;.$

On the other hand, by equation (2)

$\mathbb{E}[\textsf{OPT}(x)]=\mathbb{E}\left[\sum_{i=1}^{n}x_{i}+\sum_{i<j}\min(x_{i},x_{j})\right]=n\mathbb{E}[x_{1}]+\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]\;,$

therefore

$\displaystyle\frac{\mathbb{E}[\textsf{A}(x)]}{\mathbb{E}[\textsf{OPT}(x)]}$
$\displaystyle\geq\frac{n\mathbb{E}[x_{1}]+C_{n,B}\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]}{n\mathbb{E}[x_{1}]+\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]}$
$\displaystyle=C_{n,B}-\frac{C_{n,B}-1}{1+\frac{n-1}{2}\frac{\mathbb{E}[\min(x_{1},x_{2})]}{\mathbb{E}[x_{1}]}}\;,$

and using Lemma A.1, this yields

$\textsf{R}_{n,B}(\textsf{A})\geq
C_{n,B}-\frac{C_{n,B}-1}{1+\frac{n-1}{2}\frac{\mathbb{E}[\min(x_{1},x_{2})]}{\mathbb{E}[x_{1}]}}\;.$

If $B_{n}=wn+o(n)$ for some $w\in[0,1]$, then

$\displaystyle\textsf{CR}_{B}(\textsf{A})$
$\displaystyle\geq\liminf_{n\to\infty}\textsf{R}_{n,B_{n}}(\textsf{A})$
$\displaystyle\geq 2-2(2-\alpha_{\varphi})w+(3-2\alpha_{\varphi})w^{2}\;.$

Assume now that $\int_{0}^{\infty}\frac{dt}{\varphi(t)}=\infty$, thus
$\mathbb{E}[x_{1}]=\infty$. Let $a>0$, and
$x^{a}=(x_{1}^{a},\ldots,x_{n}^{a})$ be i.i.d. job sizes with distribution

$\Pr(x_{1}^{a}\leq
t)=1-\frac{\varphi(t)^{-1}-\varphi(a)^{-1}}{\varphi(0)^{-1}-\varphi(a)^{-1}}\mathbbm{1}_{t<a}\;.$

Therefore $x_{1}^{a}$ has a finite expectation $\mathbb{E}[x_{1}^{a}]\leq a$.
Denoting by $x_{1},x_{2}$ i.i.d. random variables with distribution
$\Pr(x_{1}\leq t)=1-\frac{\varphi(0)}{\varphi(t)}$, Lemma A.4 and Equation (1)
give for any algorithm A that

$\displaystyle\mathbb{E}[\textsf{A}(x^{a})]$ $\displaystyle\geq
n\mathbb{E}[x^{a}_{1}]+\sum_{1\leq i<j\leq
B}(\mathbb{E}[\min(x_{1},x_{2})]-\underset{a\to\infty}{o(1)})+\sum_{B<i<j\leq
n}(2\mathbb{E}[\min(x_{1},x_{2})]-\underset{a\to\infty}{o(1)})$
$\displaystyle\quad+\sum_{i=1}^{B}\sum_{j=B+1}^{n}(\alpha_{\varphi}\mathbb{E}[\min(x_{1},x_{2})]-\underset{a\to\infty}{o(1)})$
$\displaystyle=n\mathbb{E}[x^{a}_{1}]+C_{n,B}\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]-n^{2}\underset{a\to\infty}{o(1)}\;,$
(20)

where the last equation is obtained with the same computation as in the case
$\int_{0}^{\infty}\frac{dt}{\varphi(t)}<\infty$. Moreover, if $a\geq 1$ then

$\mathbb{E}[\min(x^{a}_{1},x^{a}_{2})]=\int_{0}^{\infty}\Pr(\min(x^{a}_{1},x^{a}_{2})\geq
t)dt=\int_{0}^{\infty}\left(\frac{\varphi(t)^{-1}-\varphi(a)^{-1}}{\varphi(0)^{-1}-\varphi(a)^{-1}}\right)^{2}\mathbbm{1}_{t<a}dt\;,$

and we have for any $t\geq 0$ that
$\left(\frac{\varphi(t)^{-1}-\varphi(a)^{-1}}{\varphi(0)^{-1}-\varphi(a)^{-1}}\right)^{2}\leq\frac{\varphi(t)^{-2}}{(\varphi(0)^{-1}-\varphi(1)^{-1})^{2}}$,
which is an integrable function. Furthermore, $\varphi$ is increasing and
$1/\varphi^{2}$ is integrable, hence
$\lim\limits_{a\to\infty}\varphi(a)=\infty$. Therefore, the dominated
convergence theorem gives that

$\displaystyle\lim_{a\to\infty}\mathbb{E}[\min(x^{a}_{1},x^{a}_{2})]$
$\displaystyle=\int_{0}^{\infty}\lim_{a\to\infty}\left\\{\left(\frac{\varphi(t)^{-1}-\varphi(a)^{-1}}{\varphi(0)^{-1}-\varphi(a)^{-1}}\right)^{2}\mathbbm{1}_{t<a}\right\\}dt$
$\displaystyle=\int_{0}^{\infty}\frac{\varphi(0)^{2}}{\varphi(t)^{2}}dt$
$\displaystyle=\mathbb{E}[\min(x_{1},x_{2})]\;.$

It follows that

$\displaystyle\textsf{OPT}(x^{a})$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{n}x_{i}^{a}+\sum_{i<j}\min(x_{i}^{a},x_{j}^{a})\right]$
$\displaystyle=n\mathbb{E}[x_{1}^{a}]+\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1}^{a},x_{2}^{a})]$
$\displaystyle=n\mathbb{E}[x_{1}^{a}]+\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]+n^{2}\underset{a\to\infty}{o(1)}\;.$

Combining this with Inequality (20), then using Lemma A.1, we obtain that

$\textsf{R}_{n,B}\geq\frac{n\mathbb{E}[x^{a}_{1}]+C_{n,B}\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]-n^{2}\underset{a\to\infty}{o(1)}}{n\mathbb{E}[x_{1}^{a}]+\frac{n(n-1)}{2}\mathbb{E}[\min(x_{1},x_{2})]+n^{2}\underset{a\to\infty}{o(1)}}\;,$

and if $B=wn+o(n)$ then

$\textsf{CR}_{B}(\textsf{A})\geq\liminf_{n\to\infty}\textsf{R}_{n,B}(\textsf{A})\geq\frac{\big{(}2-2(2-\alpha_{\varphi})w+(3-2\alpha_{\varphi})w^{2}\big{)}\mathbb{E}[\min(x_{1},x_{2})]-\underset{a\to\infty}{o(1)}}{\mathbb{E}[\min(x_{1},x_{2})]+\underset{a\to\infty}{o(1)}}\;$

and finally, taking the limit $a\to\infty$ yields

$\textsf{CR}_{B}(\textsf{A})\geq
2-2(2-\alpha_{\varphi})w+(3-2\alpha_{\varphi})w^{2}\;.$

∎

###  A.3 Proof of Corollary 2.1.1

###### Proof.

Let us consider i.i.d. exponentially distributed job sizes. This corresponds
to $\varphi(t)=e^{t}$ for all $t\geq 0$. It holds that $\varphi(0)=1>0$,
$\varphi$ is increasing, $\frac{\varphi^{\prime}}{\varphi}=1$ is non-
increasing, and

$\int_{0}^{\infty}\frac{dt}{\varphi(t)}=\int_{0}^{\infty}e^{-t}dt=1\;,\qquad\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}=\int_{0}^{\infty}e^{-2t}dt=\frac{1}{2}\;.$

Furthermore, it holds for all $x\geq 0$ and $T\geq x$ that

$\displaystyle G(x,T)$
$\displaystyle=\int_{0}^{T-x}\frac{dt}{\varphi(t)}+\frac{x}{\varphi(T-x)}$
$\displaystyle=\int_{0}^{T-x}e^{-t}dt+xe^{-(T-x)}$
$\displaystyle=1+(x-1)e^{-(T-x)}\;.$

Thus, for all $x\geq 0$

$\inf_{T\geq x}G(x,T)=\left\\{\begin{array}[]{ll}G(x,x)=x&\mbox{if }x<1\\\
\lim\limits_{T\to\infty}G(x,T)=1&\mbox{if }x\geq 1\end{array}\right.\;,$

and it follows that

$\displaystyle\varphi(0)^{2}\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle=\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}e^{-x}dx$
$\displaystyle=\int_{0}^{1}xe^{-x}dx+\int_{1}^{\infty}e^{-x}dx$
$\displaystyle=1-\tfrac{1}{e}$
$\displaystyle=2(1-\tfrac{1}{e})\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}\;.$

Finally, by Theorem 2.1, it holds for any algorithm A having access to the
sizes of $B$ jobs that

$\textsf{R}_{n,B}(\textsf{A})\geq
C_{n,B}-\frac{C_{n,B}-1}{1+\frac{n-1}{4}}=C_{n,B}-\frac{4(C_{n,B}-1)}{n+3}\;,$

with

$C_{n,B}=2-(4/e)\frac{B}{n}+(4/e-1)\frac{B(B-1)}{n(n-1)}\;.$

In particular, if $B=wn+o(n)$, then again by Theorem 2.1 we have

$\textsf{CR}(\textsf{A})\geq 2-\tfrac{4}{e}w+(\tfrac{4}{e}-1)w^{2}\;.$

∎

###  A.4 Proof of Corollary 2.1.2

###### Proof.

Let $r\in(\tfrac{1}{2},1)$, and consider $\varphi:t\mapsto(1+t)^{r}$. It holds
that $\varphi(0)=1>0$, $\varphi$ is increasing,
$\frac{\varphi^{\prime}}{\varphi}:t\mapsto\frac{r}{1+t}$ is non-increasing,
and
$\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}=\int_{0}^{\infty}\frac{dt}{(1+t)^{2r}}=\frac{1}{2r-1}<\infty$
because $r>\frac{1}{2}$. Moreover, it holds for all $x\geq 0$ and $T\geq x$
that

$\displaystyle G(x,T)$
$\displaystyle=\int_{0}^{T-x}\frac{dt}{\varphi(t)}+\frac{x}{\varphi(T-x)}$
$\displaystyle=\int_{0}^{T-x}\frac{dt}{(1+t)^{r}}+\frac{x}{(1+T-x)^{r}}$
$\displaystyle=-\frac{1}{1-r}+\frac{(1+T-x)^{1-r}}{1-r}+\frac{x}{(1+T-x)^{r}}\;,$

therefore, for all $x\geq 0$

$\displaystyle\inf_{T\geq x}G(x,T)$ $\displaystyle=-\frac{1}{1-r}+\inf_{T\geq
x}\left\\{\frac{(1+T-x)^{1-r}}{1-r}+\frac{x}{(1+T-x)^{r}}\right\\}$
$\displaystyle=-\frac{1}{1-r}+\inf_{y\in[0,1]}\left\\{\frac{y^{-(1-r)}}{1-r}+xy^{r}\right\\}\;,$

where the last inequality is obtained by considering $y=\frac{1}{1+T-x}$. It
holds that

$\displaystyle\frac{d}{dy}\left(\frac{y^{-(1-r)}}{1-r}+xy^{r}\right)$
$\displaystyle=-y^{-(2-r)}+rxy^{-(1-r)}$
$\displaystyle=rxy^{-(2-r)}\left(y-\frac{1}{rx}\right)\;,$

The mapping $y\mapsto\frac{y^{-(1-r)}}{1-r}+xy^{r}$ is thus minimized on
$[0,\infty)$ for $y=\frac{1}{rx}$, and it is minimized on $[0,1]$ for
$y_{*}=\min(1,\frac{1}{rx})$. Therefore, it holds for $x\leq\frac{1}{r}$ that
$y_{*}=1$ and $\inf_{T\geq x}G(x,T)=-\frac{1}{1-r}+(\frac{1}{1-r}+x)=x$, and
for $x>\frac{1}{r}$ we have $y_{*}=\frac{1}{rx}$ and

$\displaystyle\inf_{T\geq x}G(x,T)$
$\displaystyle=-\frac{1}{1-r}+\frac{(rx)^{1-r}}{1-r}+(rx)^{-r}$
$\displaystyle=-\frac{1}{1-r}+\left(\frac{1}{1-r}+\frac{1}{r}\right)(rx)^{1-r}$
$\displaystyle=-\frac{1}{1-r}+\frac{(rx)^{1-r}}{r(1-r)}\;.$

We deduce that

$\displaystyle\varphi(0)^{2}\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle=\int_{0}^{1/r}\left(-\frac{1}{1-r}+x\right)\frac{r}{(1+x)^{r+1}}dx$
$\displaystyle\quad+\int_{1/r}^{\infty}\left(-\frac{1}{1-r}+\frac{(rx)^{1-r}}{r(1-r)}\right)\frac{r}{(1+x)^{r+1}}dx$
$\displaystyle=-\frac{1}{1-r}+\int_{0}^{1/r}\frac{rx}{(1+x)^{1+r}}dx+\frac{r^{1-r}}{1-r}\int_{1/r}^{\infty}\frac{x^{1-r}}{(1+x)^{r+1}}dx$
$\displaystyle\geq-\frac{1}{1-r}+\frac{r^{1-r}}{1-r}\int_{1/r}^{\infty}\frac{x^{1-r}}{(1+x)^{r+1}}dx\;.$
(21)

Let us denote $W_{r}=\int_{1/r}^{\infty}\frac{x^{1-r}}{(1+x)^{r+1}}dx$. It
holds that

$\displaystyle W_{r}=$
$\displaystyle\int_{1/r}^{\infty}\frac{x^{1-r}}{(1+x)^{r+1}}dx$
$\displaystyle=$
$\displaystyle\int_{1/r}^{\infty}\left(\frac{x}{1+x}\right)^{1-r}\frac{dx}{(1+x)^{2r}}$
$\displaystyle\geq$
$\displaystyle\int_{2}^{\infty}\sqrt{\frac{x}{1+x}}\cdot\frac{dx}{(1+x)^{2r}}$
$\displaystyle(r>\tfrac{1}{2})$ $\displaystyle\geq$
$\displaystyle\int_{0}^{1/3}\frac{\sqrt{1-s}}{s^{2-2r}}ds$
$\displaystyle(s\leftarrow\tfrac{1}{1+x})$ $\displaystyle=$
$\displaystyle\int_{0}^{1/3}\sqrt{1-s}\cdot\frac{d}{ds}\left(\frac{s^{2r-1}}{2r-1}\right)ds$
$\displaystyle=$
$\displaystyle\left[\frac{s^{2r-1}\sqrt{1-s}}{2r-1}\right]_{0}^{1/3}+\frac{1}{2(2r-1)}\int_{0}^{1/3}\frac{s^{2r-1}}{\sqrt{1-s}}ds$
$\displaystyle=$
$\displaystyle\frac{3^{-(2r-1)}\sqrt{2/3}}{2r-1}+\frac{1}{2(2r-1)}\int_{0}^{1/3}\frac{s^{2r-1}}{\sqrt{1-s}}ds\;.$

It holds for all $r\in(\tfrac{1}{2},1)$ that
$\frac{s^{2r-1}}{\sqrt{1-s}}\leq\frac{1}{\sqrt{1-s}}$, which is an integrable
function on $[0,\tfrac{1}{3}]$, hence the dominated convergence theorem
guarantees that

$\displaystyle\lim_{r\to\tfrac{1}{2}}\frac{1}{2}\int_{0}^{1/3}\frac{s^{2r-1}}{\sqrt{1-s}}ds$
$\displaystyle=\frac{1}{2}\int_{0}^{1/3}\lim_{r\to\tfrac{1}{2}}\frac{s^{2r-1}}{\sqrt{1-s}}ds$
$\displaystyle=\frac{1}{2}\int_{0}^{1/3}\frac{ds}{\sqrt{1-s}}$
$\displaystyle=\left[-\sqrt{1-s}\right]_{0}^{1/3}$
$\displaystyle=1-\sqrt{2/3}\;,$

we deduce that

$\displaystyle(2r-1)W_{r}$
$\displaystyle=3^{-(2r-1)}\sqrt{2/3}+\frac{1}{2}\int_{0}^{1/3}\frac{s^{2r-1}}{\sqrt{1-s}}ds$
$\displaystyle=\left(\sqrt{2/3}-\underset{r\to
1/2}{o(1)}\right)+\left(1-\sqrt{2/3}-\underset{r\to 1/2}{o(1)}\right)$
$\displaystyle=1+\underset{r\to 1/2}{o(1)}\;.$

Substituting into Inequality 21, and recalling that
$\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}=\frac{1}{2r-1}$, we deduce that
for $r$ close to $\frac{1}{2}$

$\displaystyle\varphi(0)^{2}\int_{0}^{\infty}\left\\{\inf_{T\geq
x}G_{\varphi}(x,T)\right\\}\frac{\varphi^{\prime}(x)}{\varphi(x)^{2}}dx$
$\displaystyle\geq-\frac{1}{1-r}+\frac{r^{1-r}}{1-r}W_{r}$
$\displaystyle=\left(-\frac{2r-1}{1-r}+\left(\frac{r^{1-r}}{1-r}\right)(2r-1)W_{r}\right)\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}$
$\displaystyle=\left(o(1)+(\sqrt{2}+o(1))(1-o(1))\right)\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}$
$\displaystyle=\left(\sqrt{2}+o(1)\right)\int_{0}^{\infty}\frac{dt}{\varphi(t)^{2}}\;.$

Consequently, by Theorem 2.1, if $B=wn+o(n)$, it holds for any algorithm A
that

$\textsf{CR}(\textsf{A})\geq 2-2\left(2-\sqrt{2}-\underset{r\to
1/2}{o(1)}\right)w+\left(3-2\sqrt{2}-\underset{r\to 1/2}{o(1)}\right)w^{2}\;,$

and taking the limit when $r\to\frac{1}{2}$ gives

$\textsf{CR}(\textsf{A})\geq 2-2(2-\sqrt{2})w+(3-2\sqrt{2})w^{2}\;.$

∎

##  Appendix B Known partial order

###  B.1 Preliminary results

######  Lemma B.1.

For any real numbers $x_{1},\ldots,x_{n}$, if $\sigma$ is a uniformly random
permutation of $[n]$ then

$\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]=\frac{2}{n(n-1)}\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})\;.$

###### Proof.

Since $\sigma$ is uniformly random, we have for any $i\neq j$ that
$\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]=\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma()})]$,
thus

$\displaystyle\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle=\frac{2}{n(n-1)}\mathbb{E}\Big{[}\sum_{1\leq i<j\leq
n}\min(x_{\sigma(i)},x_{\sigma(j)})\Big{]}$
$\displaystyle=\frac{2}{n(n-1)}\sum_{1\leq i<j\leq n}\min(x_{i},x_{j})\;.$

∎

######  Lemma B.2.

For any real numbers $x_{1},\ldots,x_{n}$, if $\sigma$ is a uniformly random
permutation of $[n]$ then

$\mathbb{E}[x_{\sigma(1)}\mathbbm{1}_{x_{\sigma(1)}<x_{\sigma(2)}}]\leq\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]=\frac{1}{n(n-1)}\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})\;,$

with equality if $x_{1},\ldots,x_{n}$ are pairwise distinct.

###### Proof.

$\sigma$ is a uniformly random permutation of $[n]$, therefore
$\mathbb{E}[x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(i)}<x_{\sigma(j)}}]=\mathbb{E}[x_{\sigma(1)}\mathbbm{1}_{x_{\sigma(1)}<x_{\sigma(2)}}]$
for all $i\neq j\in[n]$. It follows that

$\displaystyle\mathbb{E}[x_{\sigma(1)}\mathbbm{1}_{x_{\sigma(1)}<x_{\sigma(2)}}]$
$\displaystyle=\frac{1}{2}\left(\mathbb{E}[x_{\sigma(1)}\mathbbm{1}_{x_{\sigma(1)}<x_{\sigma(2)}}]+\mathbb{E}[x_{\sigma(2)}\mathbbm{1}_{x_{\sigma(2)}<x_{\sigma(1)}}]\right)$
$\displaystyle\leq\frac{1}{2}\mathbb{E}[x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(1)}<x_{\sigma(2)}}+x_{\sigma(2)}\mathbbm{1}_{x_{\sigma(2)}\leq
x_{\sigma(1)}}]$
$\displaystyle=\frac{1}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]\;,$

and using Lemma B.1 concludes the proof. To have equality, it must hold that
$\mathbbm{1}_{x_{\sigma(2)}<x_{\sigma(1)}}=\mathbbm{1}_{x_{\sigma(2)}\leq
x_{\sigma(1)}}$ for any permutation, and this is true if and only if the
values $x_{1},\ldots,x_{n}$ are pairwise distinct. ∎

###  B.2 Proof of Theorem 3.1

###### Proof.

For any $i\neq j\geq B+1$, as in round-robin,
$P_{\sigma(i)\sigma(j)}=2\min(x_{\sigma(i)},x_{\sigma(j)})$. For $i\neq j\leq
B$, since the jobs $\\{x_{\sigma(k)}\\}_{k=1}^{B}$ are run in non-decreasing
order one after the other, it holds that
$P_{\sigma(i)\sigma(j)}=\min(x_{\sigma(i)},x_{\sigma(j)})$. Finally, for
$i\leq B$ and $j\geq B+1$, the delay caused by $\sigma(j)$ to $\pi(i)$ is
always $D_{\sigma(j)\pi(i)}=\min(x_{\pi(i)},x_{\sigma(j)})$. On the other hand
if $x_{\sigma(j)}\leq x_{\pi(i-1)}$ then $x_{\sigma(j)}$ terminates before
phase $i$ begins, thus job $\pi(i)$ does not delay job $\sigma(j)$:
$D_{\pi(i)\sigma(j)}=0$. If $x_{\sigma(j)}>x_{\pi(i-1)}$, then after the first
step of phase $i$, the time spent on each of the jobs $\pi(i)$ and $\sigma(j)$
is $x_{\pi(i-1)}$. Both jobs are then executed with identical processing
powers until one of them is terminated, thus

$\displaystyle D_{\pi(i)\sigma(j)}$
$\displaystyle=\min(x_{\pi(i)},x_{\sigma(j)})\mathbbm{1}_{x_{\sigma(j)}>x_{\pi(i-1)}}$
$\displaystyle=x_{\pi(i)}\mathbbm{1}_{x_{\sigma(j)}>x_{\pi(i)}}+x_{\sigma(j)}\mathbbm{1}_{x_{\pi(i)}\geq
x_{\sigma(j)}>x_{\pi(i-1)}}\;.$

With the convention $x_{\pi(0)=0}$, taking the sum over $i$ gives

$\displaystyle\sum_{i=1}^{B}D_{\pi(i)\sigma(j)}$
$\displaystyle=\sum_{i=1}^{B}x_{\pi(i)}\mathbbm{1}_{x_{\sigma(j)}>x_{\pi(i)}}+x_{\sigma(j)}\sum_{i=1}^{B}\mathbbm{1}_{x_{\pi(i)}\geq
x_{\sigma(j)}>x_{\pi(i-1)}}$
$\displaystyle=\sum_{i=1}^{B}x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(j)}>x_{\sigma(i)}}+x_{\sigma(j)}\mathbbm{1}_{x_{\sigma(j)}\leq
x_{\pi(B)}}$
$\displaystyle\leq\sum_{i=1}^{B}x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(j)}>x_{\sigma(i)}}+x_{\sigma(j)}\;.$
(22)

Using Lemma B.2, and recalling that
$\\{\pi(i)\\}_{i=1}^{B}=\\{\sigma(i)\\}_{i=1}^{B}$, we have in expectation,

$\displaystyle\mathbb{E}\Big{[}\sum_{i=1}^{B}D_{\sigma(i)\sigma(j)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{B}D_{\pi(i)\sigma(j)}\Big{]}$
$\displaystyle\leq\frac{B}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\frac{1}{n}\sum_{k=1}^{n}x_{k}\;,$
(23)

and it follows that, for any $j\geq B+1$

$\displaystyle\mathbb{E}\Big{[}\sum_{i=1}^{B}P_{\sigma(i)\sigma(j)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{B}D_{\sigma(j)\sigma(i)}\Big{]}+\mathbb{E}\Big{[}\sum_{i=1}^{B}D_{\sigma(i)\sigma(j)}\Big{]}$
$\displaystyle\leq
B\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\frac{B}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\frac{1}{n}\sum_{k=1}^{n}x_{k}$
$\displaystyle=\frac{3B}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\frac{1}{n}\sum_{k=1}^{n}x_{k}\;,$

hence

$\sum_{j=B+1}^{n}\mathbb{E}\Big{[}\sum_{i=1}^{B}P_{\sigma(i)\sigma(j)}\Big{]}\leq\frac{3}{2}B(n-B)\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\left(1-\frac{B}{n}\right)\sum_{k=1}^{n}x_{k}\;.$

Finally, using Equation (1), the previous upper bounds on
$P_{\sigma(i)\sigma(j)}$ for all $i\neq j$, then Equation (19) with $3/2$
instead of $\alpha_{\pi}$ gives that the objective of CRRR on the instance
$x=\\{x_{1},\ldots,x_{n}\\}$ satisfies in expectation

$\displaystyle\mathbb{E}[\textsf{CRRR}(x)]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\mathbb{E}\Big{[}\sum_{1\leq i<j\leq
n}P_{\sigma(i)\sigma(j)}\Big{]}$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\sum_{1\leq i<j\leq
B}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]+\sum_{B<i<j\leq
n}2\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]$
$\displaystyle\quad+\sum_{j=B+1}^{n}\mathbb{E}\Big{[}\sum_{i=1}^{B}P_{\sigma(i)\sigma(j)}\Big{]}$
(24)
$\displaystyle\leq\left(2-\frac{B}{n}\right)\sum_{i=1}^{n}x_{i}+\left(\frac{B(B-1)}{2}+(n-B)(n-B-1)+\frac{3}{2}B(n-B)\right)\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle=\left(2-\frac{B}{n}\right)\sum_{i=1}^{n}x_{i}+\left(2-\frac{B}{n}\right)\frac{n(n-1)}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle=\left(2-\frac{B}{n}\right)\sum_{i=1}^{n}x_{i}+\left(2-\frac{B}{n}\right)\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})$ (25)
$\displaystyle=\left(2-\frac{B}{n}\right)\textsf{OPT}(x)\;,$ (26)

where we used B.1 for (25) then Equation (2) for (26). Therefore, the
$(n,B)$-competitive ratio of Algorithm 1 satisfies

$\textsf{R}_{n,B}(\textsf{CRRR})\leq 2-\frac{B}{n}\;.$ (27)

For proving the lower bound on $\textsf{R}_{n,B}$, let $\varepsilon>0$ and let
us consider job sizes $x^{\varepsilon}_{i}=1+i\varepsilon$ for all $i\in[n]$.
Observe that the only inequalities we used in the analysis are Inequalities
(22) ($x_{\sigma(j)}\mathbbm{1}_{x_{\sigma(j)}\leq x_{\pi(B)}}\leq
x_{\sigma(j)}$), and (23) given by Lemma B.2. The second one becomes equality
if the job sizes are pairwise distinct, which is satisfied by
$\\{x^{\varepsilon}_{i}\\}_{i=1}^{n}$. As for Inequality (22), since the job
sizes $x^{\varepsilon}$ are pairwise distinct and all larger than $1$, we can
give instead a lower bound on
$\mathbb{E}[x_{\sigma(j)}\mathbbm{1}_{x_{\sigma(j)}\leq x_{\pi(B)}}]$ for
$j>B$ as follows

$\displaystyle\mathbb{E}[x_{\sigma(j)}\mathbbm{1}_{x_{\sigma(j)}\leq
x_{\pi(B)}}]$
$\displaystyle=\mathbb{E}[x_{\sigma(j)}\mathbbm{1}_{\sigma(j)\leq\pi(B)}]$
$\displaystyle\geq\Pr(\sigma(j)<\pi(B))=\Pr(\sigma(n)<\max_{i\leq
B}\sigma(i))$
$\displaystyle=\sum_{k=B+1}^{n}\sum_{m=1}^{k-1}\Pr(\sigma(n)=m,\max_{i\leq
B}\sigma(i)=k)$
$\displaystyle=\sum_{k=B+1}^{n}\sum_{m=1}^{k-1}\sum_{\ell=1}^{B}\Pr(\sigma(n)=m,\sigma(\ell)=k,\forall
i\in[B]\setminus\\{\ell\\}:\sigma(i)\in[k-1]\setminus\\{m\\})$
$\displaystyle=\sum_{k=B+1}^{n}\sum_{m=1}^{k-1}\sum_{\ell=1}^{B}\frac{1}{n!}{k-2\choose
B-1}(B-1)!(n-B-1)!$
$\displaystyle=\sum_{k=B+1}^{n}\sum_{m=1}^{k-1}\frac{B!(n-B-1)!}{n!}{k-2\choose
B-1}$ $\displaystyle=\frac{B!(n-B-1)!}{n!}\sum_{k=B}^{n}(k-1){k-2\choose B-1}$
$\displaystyle=\frac{B\cdot B!(n-B-1)!}{n!}\sum_{k=B}^{n}{k\choose B}$
$\displaystyle=\frac{B\cdot B!(n-B-1)!}{n!}{n\choose B+1}$
$\displaystyle=\frac{B}{B+1}\;.$

Therefore, instead of (22), we have the lower bound

$\displaystyle\mathbb{E}\Big{[}\sum_{i=1}^{B}D_{\sigma(i)\sigma(j)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{B}D_{\pi(i)\sigma(j)}\Big{]}$
$\displaystyle=\frac{B}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\mathbb{E}[x_{\sigma(j)}\mathbbm{1}_{x_{\sigma(j)}\leq
x_{\pi(B)}}]$ (28) $\displaystyle\geq\frac{B}{2}+\frac{B}{B+1}\;,$ (29)

and thus, since we proved earlier that
$D_{\sigma(i)\sigma(j)}=\min(x^{\varepsilon}_{\sigma(i),x^{\varepsilon}_{\sigma(j)}}$
for all $i\leq B$ and $j>B$, it holds that

$\mathbb{E}\Big{[}\sum_{i=1}^{B}P_{\sigma(i)\sigma(j)}\Big{]}\geq\sum_{i=1}^{B}\mathbb{E}[\min(x_{\sigma(i),x_{\sigma(j)}}]+\frac{B}{2}+\frac{B}{B+1}\geq\frac{3B}{2}+\frac{B}{B+1}$

and using that $x^{\varepsilon}_{i}\geq 1$ for all $i\in[n]$, we obtain by
substituting the previous inequalities into (24) that

$\displaystyle\mathbb{E}[\textsf{CRRR}(x^{\varepsilon})]$ $\displaystyle\geq
n+\frac{B(B-1)}{2}+(n-B)(n-B-1)+(n-B)\left(\frac{B}{2}+\frac{B}{B+1}\right)$
$\displaystyle=\left(n+(n-B)\frac{B}{B+1}\right)+\left(\frac{B(B-1)}{2}+(n-B)(n-B-1)+\frac{3B}{2}(n-B)\right)$
$\displaystyle=\left(2n-B-\frac{n-B}{B+1}\right)+\left(n(n-1)-\frac{(n-1)B}{2}\right)$
$\displaystyle=(n+1)\left(n-\frac{B}{2}\right)-\frac{n-B}{B+1}\;.$

On the other hand, Equation (2), along with $x^{\varepsilon}_{i}\leq
1+n\varepsilon$ for all $i\in[n]$, gives

$\textsf{OPT}(x^{\varepsilon})\leq\sum_{i=1}^{n}(n-i+1)(1+n\varepsilon)=\frac{n(n+1)}{2}(1+n\varepsilon)\;,$

and it follows that

$\displaystyle\textsf{R}_{n,B}(\textsf{CRRR})$
$\displaystyle\geq\frac{\mathbb{E}[\textsf{CRRR}(x^{\varepsilon})]}{\textsf{OPT}(x^{\varepsilon})}$
$\displaystyle\geq\frac{(n+1)\left(n-\frac{B}{2}\right)-\frac{n-B}{B+1}}{\frac{n(n+1)}{2}(1+n\varepsilon)}$
$\displaystyle=\frac{1}{1+n\varepsilon}\left(2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{(n+1)(B+1)}\right)\;.$

Taking the limit $\varepsilon\to 0$ and using Inequality (27), we obtain that

$2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{(n+1)(B+1)}\leq\textsf{R}_{n,B}(\textsf{CRRR})\leq
2-\frac{B}{n}\;.$

Finally, if $B_{n}=\lfloor wn\rfloor$ for some $w\in[0,1]$ then $B_{n}\geq
wn$, hence $\textsf{CR}_{B}(\textsf{CRRR})=\sup_{n\geq
2}R_{n,B_{n}}(\textsf{CRRR})\leq 2-w$, and this bound is reached by the lower
bound on $R_{n,B_{n}}$ for $n\to\infty$, which gives that
$\textsf{CR}_{B}(\textsf{CRRR})=2-w$. ∎

##  Appendix C Predictions of the job sizes

###  C.1 Proof of Theorem 4.1

We first compute the mutual delays of the jobs in Switch with any breakpoints.

######  Lemma C.1.

For any job sizes $x=(x_{1},\ldots,x_{n})$, and for any permutation $\sigma$
of $[n]$ and breakpoints $z^{\sigma}=(z_{\sigma(1)},\ldots,z_{\sigma(B)})$,
the Switch algorithm $\textsf{Switch}(z^{\sigma},x)$ satisfies for all $i\neq
j\in[n]$ that

$\displaystyle P_{\sigma(i)\sigma(j)}$
$\displaystyle=x_{\sigma(i)}\mathbbm{1}_{z_{\sigma(i)}<z_{\sigma(j)}}+x_{\sigma(j)}\mathbbm{1}_{z_{\sigma(i)}>z_{\sigma(j)}}+(\theta_{ij}x_{\sigma(i)}+(1-\theta_{ij})x_{\sigma(j)})\mathbbm{1}_{z_{\sigma(i)}=z_{\sigma(j)}}\qquad$
$\displaystyle\text{if }i,j\leq B\;,$ $\displaystyle P_{\sigma(i)\sigma(j)}$
$\displaystyle=2\min(x_{\sigma(i)},x_{\sigma(j)})$ $\displaystyle\text{if
}i,j>B\;,$ $\displaystyle P_{\sigma(i)\sigma(j)}$
$\displaystyle=x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(j)}>z_{\sigma(i)}}+\min(z_{\sigma(i)},x_{\sigma(i)})$
$\displaystyle\text{if }i\leq B,j>B\;.$

where $\theta_{ij}$ is a Bernoulli random variable with parameter $1/2$
independent of $\sigma$ for all $i\neq j\in[B]$.

###### Proof.

Let us first define the random variables $\theta_{ij}$. For all $i\neq
j\in[B]$, if $z_{\sigma(i)}\neq z_{\sigma(j)}$ then let $\theta_{ij}$ be an
independent Bernoulli random variable with parameter $1/2$, and if
$z_{\sigma(i)}=z_{\sigma(j)}$ then let $\theta_{ij}$ be the indicator that
$z_{\sigma(i)}$ comes before $z_{\sigma(j)}$ with the ordering $\pi$. Since
$\pi$ is an ordering of the breakpoints chosen uniformly at random, then
$\theta_{ij}$ is a Bernoulli random variable with parameter $1/2$
independently of $\sigma$.

For $i\neq j\in[B]$, if $z_{\sigma(i)}<z_{\sigma(j)}$ then job $\sigma(i)$ is
executed until completion before job $\sigma(j)$ starts being executed, thus
$D_{\sigma(i)\sigma(j)}=x_{\sigma(i)}$ and $D_{\sigma(j)\sigma(i)}=0$ and
$P_{\sigma(i)\sigma(j)}=x_{\sigma(i)}$. By symmetry, if
$z_{\sigma(i)}>z_{\sigma(j)}$ then $P_{\sigma(i)\sigma(j)}=x_{\sigma(j)}$. In
the case where $z_{\sigma(i)}=z_{\sigma(j)}$, since $\pi$ is chosen uniformly
at random among all the permutations of $[B]$ satisfying
$z_{\pi(1)}\leq\ldots\leq z_{\pi(B)}$, each of the jobs $\sigma(i),\sigma(j)$
is run until completion before the other one starts with equal probability
$1/2$, hence
$P_{\sigma(i)\sigma(j)}=\theta_{ij}x_{\sigma(i)}+(1-\theta_{ij})x_{\sigma(j)}$.
It follows that

$P_{\sigma(i)\sigma(j)}=x_{\sigma(i)}\mathbbm{1}_{z_{\sigma(i)}<z_{\sigma(j)}}+x_{\sigma(j)}\mathbbm{1}_{z_{\sigma(i)}>z_{\sigma(j)}}+(\theta_{ij}x_{\sigma(i)}+(1-\theta_{ij})x_{\sigma(j)})\mathbbm{1}_{z_{\sigma(i)}=z_{\sigma(j)}}\;.$

For $i\neq j>B$, jobs $\sigma(i),\sigma(j)$ are processed symmetrically and
the delays they cause to each other are the same as in round-robin. Therefore
$D_{\sigma(i)\sigma(j)}=D_{\sigma(j)\sigma(i)}=\min(x_{\sigma(i)},x_{\sigma(j)})$,
and it holds that

$P_{\sigma(i)\sigma(j)}=2\min(x_{\sigma(i)},x_{\sigma(j)})\;.$

For $i\leq B$ and $j>B$, at the time when job $\sigma(i)$ starts being
executed, it holds by definition of Algorithm 2 that either job $\sigma(j)$ is
completed or $S_{\sigma(j)}=z_{\sigma(i)}$, hence the delay caused by job
$\sigma(j)$ to job $\sigma(i)$ is
$D_{\sigma(j)\sigma(i)}=\min(z_{\sigma(i)},x_{\sigma(j)})$. On the other hand,
job $\sigma(i)$ delays job $\sigma(j)$ if and only if
$x_{\sigma(j)}>z_{\sigma(i)}$, and in this case job $\sigma(i)$ runs until
completion before job $\sigma(j)$ is completed, hence
$D_{\sigma(i)\sigma(j)}=x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(j)}>z_{\sigma(i)}}$,
and it follows that

$P_{\sigma(i)\sigma(j)}=x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(j)}>z_{\sigma(i)}}+\min(z_{\sigma(i)},x_{\sigma(i)})$

∎

####  C.1.1 Proof of the theorem

Using the previous lemma, we now prove Theorem 4.1

###### Proof.

Using Lemma C.1, it holds for all $i\neq j\in[n]$ that
$P_{\sigma(i)\sigma(j)}=\min(x_{\sigma(i)},x_{\sigma(j)})$ if $i,j\leq B$,
$P_{\sigma(i)\sigma(j)}=2\min(x_{\sigma(i)},x_{\sigma(j)})$ if $i,j>B$, and if
$i\leq B$ and $j>B$ then

$P_{\sigma(i)\sigma(j)}=\min(x_{\sigma(i)},x_{\sigma(j)})+x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(i)}<x_{\sigma(j)}}\;.$

Taking the expectation over $\sigma$ then using Lemma B.2 gives

$\displaystyle\mathbb{E}[x_{\sigma(i)}\mathbbm{1}_{x_{\sigma(i)}<x_{\sigma(j)}}]$
$\displaystyle=\mathbb{E}[x_{\sigma(1)}\mathbbm{1}_{x_{\sigma(1)}<x_{\sigma(2)}}]$
$\displaystyle\leq\frac{1}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]\;,$
(30)

hence for any $i\leq B$ and $j>B$

$\mathbb{E}[P_{\sigma(i)\sigma(j)}]\leq\frac{3}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]\;.$

It follows from Equation (1) that for any instance of $n$ job sizes
$x=(x_{1},\ldots,x_{n})$, the switch algorithm 2 with breakpoints
$(z_{\sigma(i)})_{i=1}^{B}=(x_{\sigma(i)})_{i=1}^{B}$ satisfies

$\displaystyle\mathbb{E}[\textsf{Switch}(x^{\sigma},x)]$
$\displaystyle\leq\sum_{i=1}^{n}x_{i}+\sum_{1\leq i<j\leq
B}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]+\sum_{B<i<j\leq
n}2\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]$
$\displaystyle\quad+\sum_{i=1}^{B}\sum_{j=B+1}^{n}\frac{3}{2}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\left(\frac{B(B-1)}{2}+(n-B)(n-B-1)+\frac{3}{2}B(n-B)\right)\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\left(2-\frac{B}{n}\right)\frac{n(n-1)}{2}\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\left(2-\frac{B}{n}\right)\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})\;,$ (31)

where we used Lemma B.1 for the last equation. We can assume without loss of
generality that $x_{1}\leq\ldots\leq x_{n}$, which yields $\sum_{1\leq i<j\leq
n}\min(x_{i},x_{j})=\sum_{i=1}^{n}(n-i)x_{i}$. Finally, Equation (2) gives

$\displaystyle\frac{\mathbb{E}[\textsf{Switch}(x^{\sigma},x)]}{\textsf{OPT}(x)}$
$\displaystyle\leq\frac{\sum_{i=1}^{n}x_{i}+\left(2-\frac{B}{n}\right)\sum_{i=1}^{n}(n-i)x_{i}}{\sum_{i=1}^{n}x_{i}+\sum_{i=1}^{n}(n-i)x_{i}}$
$\displaystyle=2-\frac{B}{n}-\frac{(1-\frac{B}{n})\sum_{i=1}^{n}x_{i}}{\sum_{i=1}^{n}(n-i+1)x_{i}}$
$\displaystyle=2-\frac{B}{n}-\frac{(1-\frac{B}{n})}{\sum_{i=1}^{n}(n-i+1)q_{i}}\;,$
(32)

where $q_{i}=(\sum_{j=1}^{n}x_{j})^{-1}x_{i}$ for all $i\in[n]$. The variables
$(q_{i})_{i=1}^{n}$ satisfy $\sum_{i=1}^{n}q_{i}=1$, and we can assume without
loss of generality that $q_{1}\leq\ldots\leq q_{n}$ (i.e. $x_{1}\leq\ldots\leq
x_{n}$). Expression (32) is maximized under these constraints for
$q_{1}=\ldots=q_{n}=\frac{1}{n}$. It follows for all job sizes
$x_{1},\ldots,x_{n}$ that

$\displaystyle\frac{\mathbb{E}[\textsf{Switch}(x^{\sigma},x)]}{\textsf{OPT}(x)}\leq
2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{n+1}\;,$

hence $\textsf{R}_{n,B}(\textsf{Switch})\leq
2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{n+1}$. Let us now prove that this is
exactly the competitive ratio of ALG. Observe that the only inequality we used
while analyzing $\textsf{Switch}(x^{\sigma},x)$ is Inequality (30), which
becomes an equality if the job sizes are pairwise distinct. Let us, therefore,
consider job sizes $x^{(\varepsilon)}_{i}=1+i\varepsilon\in[1,1+n\varepsilon]$
for some $\varepsilon>0$. All the inequalities becoming inequalities, it holds
in particular that

$\displaystyle\textsf{R}_{n,B}(\textsf{Switch})\geq\frac{\mathbb{E}[\textsf{Switch}(x^{\sigma},x^{(\varepsilon)})]}{\textsf{OPT}(x^{(\varepsilon)})}$
$\displaystyle=2-\frac{B}{n}-\frac{(1-\frac{B}{n})\sum_{i=1}^{n}x^{(\varepsilon)}_{i}}{\sum_{i=1}^{n}(n-i+1)x^{(\varepsilon)}_{i}}$
$\displaystyle\geq
2-\frac{B}{n}-\frac{(1-\frac{B}{n})\sum_{i=1}^{n}(1+n\varepsilon)}{\sum_{i=1}^{n}(n-i+1)}$
$\displaystyle=2-\frac{B}{n}-(1+n\varepsilon)\frac{2(1-\frac{B}{n})}{n+1}\;,$

and taking $\varepsilon\to 0$ yields that

$\textsf{R}_{n,B}(\textsf{Switch})=2-\frac{B}{n}-\frac{2(1-\frac{B}{n})}{n+1}\;.$

Let $w\in[0,1]$. If $B=\lfloor wn\rfloor$, then $B/n\geq w$ and it holds for
all $n\geq 2$ that $\textsf{R}_{n,B}(\textsf{Switch})\leq 2-w$, and this bound
is reached for $n\to\infty$, thus $\textsf{CR}_{B}(\textsf{Switch})=2-w$. ∎

###  C.2 Proof of Proposition 4.2

###### Proof.

It is shown in [45] that for any instance $x=(x_{1},\ldots,x_{n})$, the
expected sum of completion times resulting from a run of RTC is
$\mathbb{E}[\textsf{RTC}(x)]=\frac{n+1}{2}\sum_{i=1}^{n}x_{i}$. Using Equation
31, we deduce that the algorithm ALG that runs RTC with probability
$\frac{2(n-B)}{n(n+3)-2B}$ and runs Switch with breakpoints
$z^{\sigma}=x^{\sigma}$ with the remaining probability satisfies

$\displaystyle\mathbb{E}[\textsf{ALG}(x)]$
$\displaystyle=\frac{2(n-B)}{n(n+3)-2B}\textsf{RTC}(x)+\left(1-\frac{2(n-B)}{n(n+3)-2B}\right)\mathbb{E}[\textsf{Switch}(x^{\sigma},x)]$
$\displaystyle=\frac{2(n-B)}{n(n+3)-2B}\cdot\frac{n+1}{2}\sum_{i=1}^{n}x_{i}+\left(1-\frac{2(n-B)}{n(n+3)-2B}\right)\left(\sum_{i=1}^{n}x_{i}+\left(2-\frac{B}{n}\right)\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})\right)$
$\displaystyle=\left(\frac{(n-1)(n-B)}{n(n+3)-2B}+1\right)\sum_{i=1}^{n}x_{i}+\left(1-\frac{2(n-B)}{n(n+3)-2B}\right)\left(2-\frac{B}{n}\right)\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})$
$\displaystyle=\left(2-\frac{B}{n}-\frac{2(1-\frac{B}{n})(2-\frac{B}{n})}{n+3-\frac{2B}{n}}\right)\left(\sum_{i=1}^{n}x_{i}+\sum_{1\leq
i<j\leq n}\min(x_{i},x_{j})\right)$
$\displaystyle=\left(2-\frac{B}{n}-\frac{2(1-\frac{B}{n})(2-\frac{B}{n})}{n+3-\frac{2B}{n}}\right)\textsf{OPT}(x)\;.$

∎

###  C.3 Proof of Lemma 4.3

###### Proof.

Let $x_{1},\ldots,x_{n}$ Let $\xi$ be a random variable with distribution $F$.
Let $i\neq j\leq B$, by symmetry, we can assume that $x_{\sigma(i)}\leq
x_{\sigma(j)}$. Lemma C.1 gives that

$\displaystyle P_{\sigma(i)\sigma(j)}$
$\displaystyle=x_{\sigma(i)}\mathbbm{1}_{y_{\sigma(i)}<y_{\sigma(j)}}+x_{\sigma(j)}\mathbbm{1}_{y_{\sigma(i)}>y_{\sigma(j)}}+\tfrac{x_{\sigma(i)}+x_{\sigma(j)}}{2}\mathbbm{1}_{y_{\sigma(i)}=y_{\sigma(j)}}$
$\displaystyle\leq
x_{\sigma(i)}\mathbbm{1}_{y_{\sigma(i)}<y_{\sigma(j)}}+x_{\sigma(j)}\mathbbm{1}_{y_{\sigma(i)}\geq
y_{\sigma(j)}}$
$\displaystyle=x_{\sigma(i)}+(x_{\sigma(j)}-x_{\sigma(i)})\mathbbm{1}_{y_{\sigma(i)}\geq
y_{\sigma(j)}}$ $\displaystyle\leq
x_{\sigma(i)}+(x_{\sigma(j)}-y_{\sigma(j)}+y_{\sigma(i)}-x_{\sigma(i)})\mathbbm{1}_{y_{\sigma(i)}\geq
y_{\sigma(j)}}$ $\displaystyle\leq
x_{\sigma(i)}+(\eta_{\sigma(i)}+\eta_{\sigma(j)})$
$\displaystyle=\min(x_{\sigma(i)},x_{\sigma(j)})+(\eta_{\sigma(i)}+\eta_{\sigma(j)})\;,$

and we obtain in expectation that for all $i\neq j\leq B$

$\mathbb{E}[P_{\sigma(i)\sigma(j)}]\leq\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]+\frac{2}{B}\mathbb{E}[\eta^{\sigma}]\;.$
(33)

For $i\neq j>B$, Lemma C.1 gives

$\mathbb{E}[P_{\sigma(i)\sigma(j)}]=2\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]\;.$
(34)

For $i\leq B$ and $j>B$, we have again by Lemma C.1 that

$\mathbb{E}[P_{\sigma(i)\sigma(j)}]=\mathbb{E}[\min(\xi
y_{\sigma(i)},x_{\sigma(j)})]+\mathbb{E}[x_{\sigma(i)}\mathbbm{1}_{\xi
y_{\sigma(i)}<x_{\sigma(j)}}]\;.$

Conditional on the permutation $\sigma$, i.e. taking the expectation only over
$\xi$, the first term can be bounded as follows

$\displaystyle\mathbb{E}[\min(\xi y_{\sigma(i)},x_{\sigma(j)})\mid\sigma]$
$\displaystyle\leq\mathbb{E}[\min(\xi
x_{\sigma(i)},x_{\sigma(j)})+\xi\eta_{\sigma(i)}\mid\sigma]$
$\displaystyle=\mathbb{E}[x_{\sigma(j)}\mathbbm{1}_{\xi x_{\sigma(i)}\geq
x_{\sigma(j)}}+\xi x_{\sigma(i)}\mathbbm{1}_{\xi
x_{\sigma(i)}<x_{\sigma(j)}}\mid\sigma]+\mathbb{E}[\xi]\eta_{\sigma(i)}$
$\displaystyle=x_{\sigma(j)}\Pr(\xi\geq\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\mid\sigma)+x_{\sigma(i)}\mathbb{E}\Big{[}\xi\mathbbm{1}_{\xi<\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}}\mid\sigma\Big{]}+\mathbb{E}[\xi]\eta_{\sigma(i)}\;,$
(35)

and for the second term, the expectation conditional on $\sigma$ satisfies

$\displaystyle\mathbb{E}[x_{\sigma(i)}\mathbbm{1}_{\xi
y_{\sigma(i)}<x_{\sigma(j)}}\mid\sigma]$
$\displaystyle\leq\mathbb{E}[y_{\sigma(i)}\mathbbm{1}_{\xi
y_{\sigma(i)}<x_{\sigma(j)}}+\eta_{\sigma(i)}\mid\sigma]$
$\displaystyle=y_{\sigma(i)}\Pr(\xi<\tfrac{x_{\sigma(j)}}{y_{\sigma(i)}}\mid\sigma)+\eta_{\sigma(i)}$
$\displaystyle=h_{F}(x_{\sigma(j)},y_{\sigma(i)})+\eta_{\sigma(i)}$
$\displaystyle\leq
h_{F}(x_{\sigma(j)},x_{\sigma(i)})+L_{F}|x_{\sigma(i)}-y_{\sigma(i)}|+\eta_{\sigma(i)}$
(36)
$\displaystyle=x_{\sigma(i)}\Pr(\xi<\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\mid\sigma)+(1+L_{F})\eta_{\sigma(i)}\;,$
(37)

where we used for (36) that $h_{F}$ is $L$-Lipschitz with respect to the
second variable. Combining (35) and (37) yields

$\displaystyle\mathbb{E}[P_{\sigma(i)\sigma(j)}\mid\sigma]$ $\displaystyle\leq
x_{\sigma(j)}+(x_{\sigma(i)}-x_{\sigma(j)})\Pr(\xi<\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\mid\sigma)+x_{\sigma(i)}\mathbb{E}\Big{[}\xi\mathbbm{1}_{\xi<\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}}\mid\sigma\Big{]}+(1+L_{F}+\mathbb{E}[\xi])\eta_{\sigma(i)}$
$\displaystyle=x_{\sigma(j)}+x_{\sigma(i)}\left(\big{(}1-\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}\Pr(\xi<\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\mid\sigma)+\mathbb{E}\Big{[}\xi\mathbbm{1}_{\xi<\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}}\mid\sigma\Big{]}\right)+(1+L_{F}+\mathbb{E}[\xi])\eta_{\sigma(i)}$
$\displaystyle=x_{\sigma(j)}+x_{\sigma(i)}g_{F}\big{(}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}+(1+L_{F}+\mathbb{E}[\xi])\eta_{\sigma(i)}\;.$
(38)

We can assume without of generality that $x_{1}\leq\ldots\leq x_{n}$. It holds
by definition of the constants $\beta_{F}$ and $\gamma_{F}$ that
$g_{F}\big{(}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}\leq\beta_{F}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}$
if $\sigma(j)<\sigma(i)$, and
$g_{F}\big{(}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}\leq\gamma_{F}-\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}$
if $\sigma(j)>\sigma(i)$, which gives

$\displaystyle\mathbb{E}\left[x_{\sigma(j)}+x_{\sigma(i)}g_{F}\big{(}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}\right]$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[x_{\sigma(j)}+x_{\sigma(i)}g_{F}\big{(}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}\mid\sigma(j)<\sigma(i)\right]$
$\displaystyle\qquad+\frac{1}{2}\mathbb{E}\left[x_{\sigma(j)}+x_{\sigma(i)}g_{F}\big{(}\tfrac{x_{\sigma(j)}}{x_{\sigma(i)}}\big{)}\mid\sigma(j)>\sigma(i)\right]$
$\displaystyle\leq\frac{1+\beta_{F}}{2}\mathbb{E}[x_{\sigma(j)}\mid\sigma(j)<\sigma(i)]+\frac{\gamma_{F}}{2}\mathbb{E}[x_{\sigma}(i)\mid\sigma(j)>\sigma(i)]$
$\displaystyle=\frac{1+\beta_{F}}{2}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})\mid\sigma(j)<\sigma(i)]+\frac{\gamma_{F}}{2}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})\mid\sigma(j)>\sigma(i)]$
$\displaystyle=\frac{1+\beta_{F}+\gamma_{F}}{2}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]\;,$

thus we obtain by taking the expectation over $\sigma$ in (38) that

$\mathbb{E}[P_{\sigma(i)\sigma(j)}]\leq\Big{(}\tfrac{1+\beta_{F}+\gamma_{F}}{2}\Big{)}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]+\Big{(}\tfrac{1+L_{F}+\mathbb{E}[\xi]}{B}\Big{)}\mathbb{E}[\eta^{\sigma}]\;.$

Using Equation 1, the inequality above, Inequalities (33), (34), then Equation
19 with $\frac{1+\beta_{F}+\gamma_{F}}{2}$ instead of $\alpha_{\pi}$, we
deduce that Algorithm 3 satisfies for any job sizes $x_{1},\ldots,x_{n}$ that

$\displaystyle\mathbb{E}[\textsf{Switch}(\xi y^{\sigma},x)]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\sum_{1\leq i<j\leq
n}\mathbb{E}[P_{\sigma(i)\sigma(j)}]$
$\displaystyle\leq\sum_{i=1}^{n}x_{i}+\sum_{1\leq i<j\leq
B}\left(\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]+\frac{2}{B}\mathbb{E}[\eta^{\sigma}]\right)+\sum_{B<i<j\leq
n}2\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]$
$\displaystyle\qquad+\sum_{i=1}^{B}\sum_{j=B+1}^{n}\left(\Big{(}\tfrac{1+\beta_{F}+\gamma_{F}}{2}\Big{)}\mathbb{E}[\min(x_{\sigma(i)},x_{\sigma(j)})]+\Big{(}\tfrac{1+L_{F}+\mathbb{E}[\xi]}{B}\Big{)}\mathbb{E}[\eta^{\sigma}]\right)$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\left(\frac{B(B-1)}{2}+(n-B)(n-B-1)+\Big{(}\tfrac{1+\beta_{F}+\gamma_{F}}{2}\Big{)}B(n-B)\right)\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle\qquad+\big{(}B-1+(1+L_{F}+\mathbb{E}[\xi])(n-B)\big{)}\mathbb{E}[\eta^{\sigma}]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\left(n(n-1)+\Big{(}1-\tfrac{\beta_{F}+\gamma_{F}}{2}\Big{)}B(B-1)-\Big{(}\tfrac{3}{2}-\tfrac{\beta_{F}+\gamma_{F}}{2}\Big{)}B(n-1)\right)\mathbb{E}[\min(x_{\sigma(1)},x_{\sigma(2)})]$
$\displaystyle\qquad+\left(B-1+(1+L_{F}+\mathbb{E}[\xi])(n-B)\right)\mathbb{E}[\eta^{\sigma}]$
$\displaystyle=\sum_{i=1}^{n}x_{i}+\left(2-\Big{(}3-\beta_{F}-\gamma_{F}\Big{)}\frac{B}{n}+\Big{(}2-\beta_{F}-\gamma_{F}\Big{)}\frac{B(B-1)}{n(n-1)}\right)\sum_{i<j}\min(x_{i},x_{j})$
$\displaystyle\qquad+\big{(}B-1+(1+L_{F}+\mathbb{E}[\xi])(n-B)\big{)}\mathbb{E}[\eta^{\sigma}]\;,$

where we used Lemma B.1 for the last equality. ∎

###  C.4 Proof of Lemma 4.4

###### Proof.

Let $\xi\sim 1+\mathcal{E}(1/\rho)$. The mapping $h_{F}$ defined in Lemma 4.3
becomes for all $s,t>0$

$h_{F}(s,t)=tF(\tfrac{s}{t})=t\left(1-e^{-\frac{1}{\rho}(\frac{s}{t}-1)}\right)\mathbbm{1}_{t<s}\;.$

For all $s>0$, it holds for all $t<s$ that

$\frac{\partial h_{F}(s,t)}{\partial
t}=1-e^{\frac{1}{\rho}(\frac{s}{t}-1)}-t\times\frac{s}{\rho
t^{2}}e^{-\frac{1}{\rho}(\frac{s}{t}-1)}=1-\left(\frac{s}{\rho
t}+1\right)e^{-\frac{1}{\rho}(\frac{s}{t}-1)}\;,$

but the mapping $u\mapsto(\tfrac{u}{\rho}+1)e^{-\frac{u-1}{\rho}}$ is
decreasing on $[1,\infty]$. Indeed

$\displaystyle\frac{\partial}{\partial
u}\left((\tfrac{u}{\rho}+1)e^{-\frac{u-1}{\rho}}\right)$
$\displaystyle=\tfrac{1}{\rho}e^{-\frac{u-1}{\rho}}-\tfrac{1}{\rho}(\tfrac{u}{\rho}+1)e^{-\frac{u-1}{\rho}}=-\tfrac{u}{\rho^{2}}e^{-\frac{u-1}{\rho}}<0\;,$

and since $\frac{s}{t}>1$ we deduce that

$-\frac{1}{\rho}=1-\lim_{u\to
1}(\tfrac{u}{\rho}+1)e^{-\frac{u-1}{\rho}}\leq\frac{\partial
h_{F}(s,t)}{\partial t}\leq
1-\lim_{u\to\infty}(\tfrac{u}{\rho}+1)e^{-\frac{u-1}{\rho}}=1\;,$

thus $|\frac{\partial h_{F}(s,t)}{\partial
t}|\leq\max(1,\tfrac{1}{\rho})=\tfrac{1}{\rho}$ for all $t<s$. Otherwise, if
$t\geq s$ then $h_{F}(s,t)=0$ and $h_{F}(s,\cdot)$ is continuous in $t=s$,
therefore $t\mapsto h_{F}(s,t)$ is $\tfrac{1}{\rho}$-Lipschitz.

On the other hand, given that $\xi>1$ a.s., it holds for $s\leq 1$ that
$\mathbb{E}[\xi\mathbbm{1}_{\xi<s}]=0$, and for $s>1$ that

$\displaystyle\mathbb{E}[\xi\mathbbm{1}_{\xi<s}]$
$\displaystyle=\Pr(\xi<s)+\mathbb{E}[(\xi-1)\mathbbm{1}_{\xi-1<s-1}]$
$\displaystyle=F(s)+\int_{0}^{\infty}t\mathbbm{1}_{t<s-1}\frac{e^{-t/\rho}}{\rho}dt$
$\displaystyle=F(s)+\int_{0}^{s-1}\frac{te^{-t/\rho}}{\rho}dt$
$\displaystyle=F(s)+\left[-(t+\rho)e^{-t/\rho}\right]_{0}^{s-1}$
$\displaystyle=\left(1-e^{-(s-1)/\rho}\right)+\left(-(s-1+\rho)e^{-t/\rho}+\rho\right)$
$\displaystyle=1+\rho+(s+\rho)e^{-(s-1)/\rho}\;.$

If follows for all $s>0$ that

$\displaystyle g_{F}(s)$
$\displaystyle=(1-s)\left(1-e^{-(s-1)/\rho}\right)\mathbbm{1}_{s>1}+\left(1+\rho+(s+\rho)e^{-(s-1)/\rho}\right)\mathbbm{1}_{s>1}$
$\displaystyle=\left((2+\rho)-s-(1+\rho)e^{-(s-1)/\rho}\right)\mathbbm{1}_{s>1}\;,$

hence $\beta_{F}=\sup_{0<s\leq 1}\frac{g_{F}(s)}{s}=0$ and

$\gamma_{F}=\sup_{s\geq 1}(g_{F}(s)+s)=\sup_{s\geq
1}\left((2+\rho)-(1+\rho)e^{-(s-1)/\rho}\right)=2+\rho\;.$

Finally, with $L_{F}=\frac{1}{\rho}$, $\beta_{F}=0$ and $\gamma_{F}=2+\rho$,
and observing that $\mathbb{E}[\xi]=1+\rho$, the constants $C^{1}_{n,B,F}$ and
$C^{1}_{n,B,F}$ defined in Lemma 4.3 satisfy

$\displaystyle C^{1}_{n,B,F}$
$\displaystyle=2-(1-\rho)\frac{B}{n}-\rho\frac{B(B-1)}{n(n-1)}=2-\frac{B}{n}+\rho\frac{B}{n}\left(1-\frac{B-1}{n-1}\right)\;,$
$\displaystyle C^{2}_{n,B,F}$
$\displaystyle\leq(2+\rho+\tfrac{1}{\rho})(n-B)+B\leq\frac{4}{\rho}(n-B)+B\;,$

and the objective function of Algorithm 3 with any job sizes
$x=\\{x_{1},\ldots,x_{n}\\}$ can be upper-bounded as follows

$\displaystyle\mathbb{E}[\textsf{Switch}(\xi y^{\sigma},x)]$
$\displaystyle\leq\sum_{i=1}^{n}x_{i}+C^{1}_{n,B,F}\sum_{i<j}\min(x_{i},x_{j})+\left(\frac{4}{\rho}(n-B)+B\right)\mathbb{E}[\eta^{\sigma}]\;,$

and by Equation (2) we obtain

$\displaystyle\frac{\mathbb{E}[\textsf{Switch}(\xi
y^{\sigma},x)]}{\textsf{OPT}(x)}$
$\displaystyle\leq\frac{\sum_{i=1}^{n}x_{i}+C^{1}_{n,B,F}\sum_{i<j}\min(x_{i},x_{j})}{\sum_{i=1}^{n}x_{i}+\sum_{i<j}\min(x_{i},x_{j})}+\left(\frac{4}{\rho}(n-B)+B\right)\frac{\mathbb{E}[\eta^{\sigma}]}{\textsf{OPT}(x)}$
$\displaystyle=C^{1}_{n,B,F}-\frac{(C^{1}_{n,B,F}-1)\sum_{i=1}^{n}x_{i}}{\sum_{i=1}^{n}x_{i}+\sum_{i<j}\min(x_{i},x_{j})}+\left(\frac{4}{\rho}(n-B)+B\right)\frac{\mathbb{E}[\eta^{\sigma}]}{\textsf{OPT}(x)}\;.$

As we showed in the proof of Theorem 4.1, we have
$\frac{\sum_{i=1}^{n}x_{i}}{\sum_{i=1}^{n}x_{i}+\sum_{i<j}\min(x_{i},x_{j})}\geq\frac{2}{n+1}$,
and the minimum is reached when all the job sizes are equal. Moreover, using
the assumption that all the job sizes are at least equal to 1, we have that
$\textsf{OPT}(x)\geq\frac{n(n+1)}{2}$. Consequently

$\displaystyle\frac{\mathbb{E}[\textsf{Switch}(\xi
y^{\sigma},x)]}{\textsf{OPT}(x)}$ $\displaystyle\leq
C^{1}_{n,B,F}-\frac{2(C^{1}_{n,B,F}-1)}{n+1}+\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)\frac{2\mathbb{E}[\eta^{\sigma}]}{n+1}\;,$

which yields after taking the supremum over instances $x$ of $n$ jobs having
sizes at least $1$ that

$\displaystyle\textsf{R}_{n,B}(\eta;\textsf{Switch})$ $\displaystyle\leq
C^{1}_{n,B,F}-\frac{2(C^{1}_{n,B,F}-1)}{n+1}+\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)\frac{2\mathbb{E}[\eta^{\sigma}]}{n+1}$
(39) $\displaystyle\leq
C^{1}_{n,B,F}+\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)\frac{2\mathbb{E}[\eta^{\sigma}]}{n}$
$\displaystyle=\left(2-\tfrac{B}{n}+\rho\tfrac{B}{n}(1-\tfrac{B-1}{n-1})\right)+\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)\frac{2\mathbb{E}[\eta^{\sigma}]}{n}\;.$

∎

###  C.5 Proof of Theorem 4.5

###### Proof.

Let $\rho\in(0,1]$, and $x=(x_{1},\ldots,x_{n})$ be an instance of job sizes
all at least equal to $1$. Before starting to run, the algorithm has access to
predictions $y_{\sigma(1)},\ldots,y_{\sigma(B)}$ of
$x_{\sigma(1)},\ldots,x_{\sigma(B)}$, it samples $\xi\sim
1+\mathcal{E}(1/\rho)$ and sets the breakpoints $z_{\sigma(i)}=\xi
y_{\sigma(i)}$ for all $i\in[B]$. With $\sigma$ and the breakpoints fixed, the
preferential algorithm runs Algorithm 2 at rate $\lambda$ and round-robin at
rate $1-\lambda$. Lemma C.1 and Equation 1 guarantee that, with a fixed
permutation $\sigma$ and fixed breakpoints, Algorithm 2 is monotonic, as all
the mutual delays $P_{\sigma(i)\sigma(j)}$ are non-decreasing functions of
$x_{\sigma(i)}$ and $x_{\sigma(j)}$. Following the proof of Lemma 3.1 in [51],
when running the preferential algorithm, the completion times of Algorithm 2
increase by a factor of $1/\lambda$, while the completion times of round-robin
increase by a factor $1/(1-\lambda)$, and since both algorithms are monotonic,
the fact that some jobs are run simultaneously by both of them can only
improve the objective function. Denoting $\textsf{Switch}(\xi y^{\sigma},x)$
the objective function of Algorithm 2 with instance $x=(x_{i})_{i=1}^{n}$ and
breakpoints $\xi y^{\sigma}=(\xi y_{\sigma(i)})_{i=1}^{B}$, and
$\textsf{RR}(x)$ the objective function of round-robin with $x$, it follows
that

$\textsf{ALG}_{\lambda}(x)\leq\min\left(\frac{\textsf{Switch}(\xi
y^{\sigma},x)}{\lambda},\frac{\textsf{RR}(x)}{1-\lambda}\right)\;.$

Given that $\textsf{RR}(x)$ is deterministic and $2$-competitive, and using
Lemma 4.4, we obtain by taking the expectation that

$\displaystyle\mathbb{E}[\textsf{ALG}_{\lambda}(x)]$
$\displaystyle\leq\mathbb{E}\left[\min\left(\frac{\textsf{RR}(x)}{1-\lambda},\frac{\textsf{Switch}(\xi
y^{\sigma},x)}{\lambda}\right)\right]$
$\displaystyle\leq\min\left(\frac{\textsf{RR}(x)}{1-\lambda},\frac{\mathbb{E}[\textsf{Switch}(\xi
y^{\sigma},x)]}{\lambda}\right)$
$\displaystyle\leq\min\left(\frac{2}{1-\lambda},\frac{\left(2-\tfrac{B}{n}+\rho\tfrac{B}{n}(1-\tfrac{B-1}{n-1})\right)+\left(\tfrac{4}{\rho}(1-\tfrac{B}{n})+\tfrac{B}{n}\right)\frac{2\mathbb{E}[\eta^{\sigma}]}{n}}{\lambda}\right)\textsf{OPT}(x),$

which concludes the proof. ∎