MLshort=ML,long=machine learning,short-indefinite=an SoCshort=SoC,long=system-
on-chip,long-plural-form=systems-on-chip,short-indefinite=an

# Speed-Oblivious Online Scheduling:
Knowing (Precise) Speeds is not Necessary

Alexander Lindermayr University of Bremen, Faculty of Mathematics and Computer
Science, Germany<EMAIL_ADDRESS>Nicole Megow 11footnotemark:
1 Martin Rapp Faculty for Informatics, Karlsruhe Institute of Technology,
Germany<EMAIL_ADDRESS>
###### Abstract

We consider online scheduling on unrelated (heterogeneous) machines in a
_speed-oblivious_ setting, where an algorithm is unaware of the exact job-
dependent processing speeds. We show strong impossibility results for
clairvoyant and non-clairvoyant algorithms and overcome them in models
inspired by practical settings: (i) we provide competitive _learning-
augmented_ algorithms, assuming that (possibly erroneous) predictions on the
speeds are given, and (ii) we provide competitive algorithms for the _speed-
ordered_ model, where a single global order of machines according to their
unknown job-dependent speeds is known. We prove strong theoretical guarantees
and evaluate our findings on a representative heterogeneous multi-core
processor. These seem to be the first empirical results for scheduling
algorithms with predictions that are evaluated in a non-synthetic hardware
environment.

##  1 Introduction

Heterogeneous processors are getting more and more common in various domains.
For several years now, efficiency and performance gains in smartphone chips
have depended crucially on the combination of high-performance and low-
performance (but energy-efficient) cores [ARM13]. Heterogeneity has recently
been introduced also to the desktop market with Intel Alder Lake (Q1’2022)
[RYR+22] and AMD Zen 5 (announced for 2023). Further, jobs differ in their
instruction mix and memory access patterns, and hence may not benefit
uniformly from the high-performance cores, which typically feature larger
caches, out-of-order execution, and a higher CPU frequency. Figure 1 shows
job-dependent speed varieties in common benchmark suites (_PARSEC-3.0_ ,
_SPLASH-3_ , _Polybench_) running on _big_ and _LITTLE_ cores of a Kirin 970
smartphone SoC with Arm big.LITTLE architecture.

Figure 1:  The execution time and speedup of the _big_ over _LITTLE_ cores on
an Arm big.LITTLE heterogeneous processor varies strongly between jobs and
different input data. Variations of the speedup w.r.t. input data are large
for some jobs (e.g., _water-nsquared_) but small for others (e.g., _fmm_).

These advances show the demand for schedulers that respect job-dependent
heterogeneity. Formally, the _(processing) speed_ $s_{ij}$ of job $j$ on
machine $i$ is the amount of processing that $j$ receives when running on $i$
for one time unit. Despite the relevance of values $s_{ij}$ for high-
performance scheduling, there is a big discrepancy between how theory and
practice handle them: while scheduling theory most commonly assumes that
speeds are known to an algorithm, this is typically not the case in practice.
Hence, algorithms that perform well in theory are often not applicable in
practice.

In this work, we propose new models and algorithms to bridge this gap. In
particular, we introduce _speed-oblivious_ algorithms, which do not rely on
knowing (precise) speeds. Thereby we focus on (non-)clairvoyant scheduling
subject to minimizing the total (weighted) completion time.

Formally, an instance of this scheduling problem is composed of a set $J$ of
$n$ jobs, a set $I$ of $m$ machines, and a time-discretization. The
characteristics of a job $j\in J$ are its processing requirement $p_{j}$, its
weight $w_{j}$, and for every machine $i\in I$ its individual processing speed
$s_{ij}>0$. A job $j$ arrives online at its release date $r_{j}$, i.e., an
algorithm is unaware of its existence before that time. A schedule assigns for
every unfinished job $j\in J$ and for every machine $i\in I$ at any time
$t\geq r_{j}$ a _(machine) rate_ $y_{ijt}\in[0,1]$, which induces the progress
$q_{jt}=\sum_{i}s_{ij}y_{ijt}$ of $j$ at time $t$. The completion time $C_{j}$
of a job $j$ in a fixed schedule is the first point in time $t$ that satisfies
$\sum_{t^{\prime}=r_{j}}^{t}q_{jt^{\prime}}\geq p_{j}$. A schedule is feasible
if there exists a progress-preserving actual schedule, where at any
infinitesimal time a job is being processed on at most one machine. This
applies if the rates satisfy $\sum_{i\in I}y_{ijt}\leq 1$ for all $j\in J$ and
$\sum_{j\in J}y_{ijt}\leq 1$ for all $i\in I$ at any time $t$ [IKM18]. The
task is to compute a feasible schedule that minimizes $\sum_{j\in
J}w_{j}C_{j}$.

An algorithm is called non-migratory, if it assigns for each job $j$ positive
rates only on a single machine $i_{j}$, and migratory otherwise. Further, it
is called _non-preemptive_ if for all jobs $j$, machines $i$, and times $t$, a
rate $y_{ijt}>0$ implies $y_{ijt^{\prime}}=1$ for all times $t^{\prime}$ with
$t\leq t^{\prime}\leq C_{j}$. We say that the machines are _related_ if
$s_{i}=s_{ij}$ for all jobs $j$ and machines $i$, i.e., speeds are not job-
dependent.

#### Models and state-of-the-art in theory

Scheduling jobs (offline) on machines with job-dependent heterogeneity (called
_unrelated_ machine scheduling) to minimize the total weighted completion time
is a prominent NP-hard problem; several approximation algorithms are known,
e.g., [HSSW97, SS02b, Li20, BSS21, IL23]. Well-studied online models include
_online_ job arrival [PST04], i.e., a job is unknown to an algorithm until its
release date $r_{j}$, and _non-clairvoyance_ [MPT94], i.e., an algorithm has
no knowledge about the total processing requirement $p_{j}$ of a job (as
opposed to _clairvoyant_ schedulers). In particular, online algorithms cannot
revert previous decisions. The performance of an online algorithm is typically
evaluated by its _competitive ratio_ [BE98], i.e., the worst-case ratio
between the algorithm’s objective value and the optimal objective value (given
full information upfront) for every instance. We say that an algorithm is
$\rho$-competitive if its competitive ratio is at most $\rho$. Known online
results include [HSSW97, CGKM09, AGK12, IKMP14, IKM18, GMUX20, Jäg21, BKL21,
LM22].

To the best of our knowledge, unrelated machine scheduling has been studied
only in a _speed-aware_ setting, where an algorithm knows the speeds $s_{ij}$
for available jobs. It is not difficult to see that there are prohibitive
lower bounds for speed-oblivious scheduling on (un-)related machines: consider
an instance with a single unit-sized job $j$ which makes substantial progress
only on one machine. This means that in the worst-case, the first $m-1$
machines tried by the algorithm have speed $\epsilon$ and $j$ makes no
substantial progress. Thus, the algorithm spends at least $m$ time units to
complete it. Knowing this fast machine upfront allows an optimal solution to
complete the job immediately. This implies a competitive ratio of at least
$\Omega(m)$ for $m$ machines:

######  Observation 1.1.

Any speed-oblivious algorithm has a competitive ratio of at least $\Omega(m)$
for minimizing the total (weighted) completion time on $m$ related machines,
even if the algorithm is clairvoyant.

#### Models and state-of-the-art in practice

Practical scheduling algorithms commonly operate in open systems [FR98], where
jobs arrive online, are non-clairvoyant, and, in contrast to the assumption in
theory, their exact processing speeds on every core are _unknown_ upfront.
Therefore, state-of-the-practice schedulers usually ignore heterogeneity
between jobs, e.g., Linux Energy-Aware Scheduling [The19]. State-of-the-art
schedulers rely on prior knowledge about jobs [KPSH15], which is not always
available, or rely on predictions of job characteristics to leverage this
information gap. Such predictions could be based on prior executions of
repeating jobs or on machine-learning-based techniques [GBA+18, RPMH21]. They
are often quite precise, but can be highly inaccurate due to varying and
unpredictable input data as shown in Figure 1. To the best of our knowledge,
all these approaches are evaluated only empirically. In particular, there are
no theoretical guarantees on the performance in worst-case scenarios or with
respect to a prediction’s quality.

###  1.1 Our Results

We initiate the theoretical study of speed-oblivious algorithms. Since strong
lower bounds rule out good worst-case guarantees for speed-oblivious unrelated
machine scheduling without further assumptions, we propose two (new) models
which are motivated by data-driven machine-learned models and modern
heterogeneous hardware architectures:

  * •

Speed predictions give algorithms access to values $\bm{\hat{}}{s}_{ij}$ for
every machine $i$ at the release date of every job $j$. We measure the
accuracy of such a prediction by the _distortion error_ $\mu$, where
$\mu=\mu_{1}\cdot\mu_{2}$ and

$\mu_{1}=\max_{i\in I,j\in
J}\left\\{\frac{\bm{\hat{}}{s}_{ij}}{s_{ij}}\right\\}\text{ and
}\mu_{2}=\max_{i\in I,j\in
J}\left\\{\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\right\\}.$

  * •

Speed-ordered machines assume an order on $I$ such that for all
$i,i^{\prime}\in I$ and jobs $j\in J$ holds $s_{ij}\geq s_{i^{\prime}j}$ if
and only if $i\leq i^{\prime}$. Algorithms are aware of this order.

Finally, we compare algorithms for these models with heuristics in experiments
on an actual modern heterogeneous chip. These are the first empirical results
which show the benefit of learning-augmented algorithms and validate
theoretical findings on _real_ hardware. In particular, we initiate the
investigation in practical applicability of theoretical scheduling algorithms
for actual realistic hardware environments.

We now give a more detailed overview of our results.

#### Learning-augmented algorithms for speed predictions

We provide the first learning-augmented algorithms with job-dependent speed
predictions and prove error-dependent performance guarantees w.r.t. the
distortion error $\mu$. This gives formal evidence on why algorithms perform
well in practice, even if the assumed speeds slightly diverge from the true
speeds. We further show that a competitive ratio linear in $\mu$ is best
possible, even for migratory algorithms and related machines. We emphasize
that the algorithms do not have access to $\mu$ upfront for the given
instance.

######  Theorem 1.2.

For minimizing the total weighted completion time on unrelated machines, there
exist speed-oblivious online algorithms with speed predictions that are

  1. (i)

clairvoyant and $8\mu$-competitive,

  2. (ii)

clairvoyant, non-preemptive and $7.216\mu^{2}$-competitive,

  3. (iii)

non-clairvoyant and $108\mu$-competitive.

For $(i)$, we design a novel and efficient clairvoyant algorithm, which might
be of independent interest. It always schedules the subset of jobs that
maximizes the total (predicted) density in a feasible job-to-machine
assignment, where the density of a job $j$ on machine $i$ is equal to
$\frac{w_{j}s_{ij}}{p_{j}}$. We show that it is $8$-competitive in the speed-
aware setting. Interestingly, this algorithm reduces to Smith’s rule on a
single machine [S+56] and preemptive variants [SS02a, MS04].

On the technical side, we prove upper bounds on the competitive ratios using
the _dual-fitting_ technique [JMM+03, AGK12]. There, we lower bound the
optimal solution by the dual of a linear programming (LP) relaxation, and then
show that a specific feasible dual assignment has an objective value which is
close to the algorithm’s objective value. The main difficulty is therefore to
come up with good dual assignment. For $(i)$, we present a new dual setup,
which we believe could be helpful for future dual-fitting approaches. The
algorithms and proofs for $(ii)$ and $(iii)$ are are inspired by previous work
(Greedy WSPT [GMUX20], Proportional Fairness [IKM18]). However, for $(iii)$ we
achieve better constants via optimized duals, even for the speed-aware case.
In all proofs, we use scalable properties of duals to convert bad decisions
due to imprecise predictions into scaled bounds on the competitive ratio.

#### Novel algorithms for speed-ordered machines

The strong lower bound of $\Omega(m)$ on the competitive ratio for speed-
oblivious algorithms for $m$ machines crucially relies on accelerating the
machine that an algorithm tries last. This argument becomes infeasible in the
speed-ordered setting, because the machines are distinguishable upfront.
Designing an algorithm is yet still challenging, as precise factors between
speeds remain unknown. On the negative side, we show that any constant-
competitive algorithm must migrate jobs. This is even true for clairvoyant
algorithms and related machines. On the positive side, we present two
algorithms:

######  Theorem 1.3.

There is a clairvoyant speed-oblivious online algorithm for minimizing the
total weighted completion time on speed-ordered related machines with a
competitive ratio of at most $8$.

We show that this algorithm is not competitive on unrelated machines. Somewhat
surprisingly, our non-clairvoyant algorithm achieves non-trivial competitive
ratios for both related and unrelated machines, as the following theorem
states.

######  Theorem 1.4.

There is a non-clairvoyant speed-oblivious online algorithm for minimizing the
total completion time

  1. (i)

on speed-ordered related machines with a competitive ratio of at most $216$,
and

  2. (ii)

on speed-ordered unrelated machines with a competitive ratio of
$\Theta(\log(\min\\{n,m\\}))$.

A crucial observation for deriving these algorithms is that in the speed-
ordered setting certain speed-aware algorithms use strategies which can be
formulated _even without_ precise speed values. An additional challenge is the
few-job regime, i.e., there are less jobs than machines, where we have to
ensure that the algorithms prefer the fast machines.

###  1.2 Further Related Work

Uncertainty about machine speeds or, generally, the machine environment, have
hardly been studied in scheduling theory. Some works consider scheduling with
unknown non-availability periods, i.e., periods with speed $0$ [AS01, DJST09],
permanent break-downs of a subset of machines [SZ20], or more generally
arbitrarily changing machine speed for a single machine [ELM+12], but not on
heterogenous machines. In scheduling with testing, unknown processing
requirements of a job (and thus its machine-dependent speed) can be explored
by making queries, e.g., [DEMM20, AE20, ABK+18], but also here heterogenous
processors are not considered.

Mitigating pessimistic lower bounds of classic worst-case analysis via
untrusted predictions [MV22, LM23] has been successfully applied to various
scheduling problems [PSK18, LLMV20, ALT21, ALT22, IKQP21, LX21, LM22, AGS22,
DIL+22]. While all these results concentrate on the uncertainty of online
arrival and non-clairvoyance, Balkanski et al. [BOSW22] consider a robust
scheduling problem where machine speeds are only predicted and jobs have to be
grouped to be scheduled together before knowing the true machine speeds; such
problems without predictions were introduced in [EHM+21, SZ20]. In contrast,
in our model an algorithm will never learn about a job’s true speed(s) before
its completion and, further, the speeds might be job-dependent.

##  2 Algorithms with Speed Predictions

In this section, we investigate the model with speed predictions. We first
rule out any sublinear error-dependency.

######  Theorem 2.1.

Any speed-oblivious algorithm with speed predictions has a competitive ratio
of at least $\Omega(\min\\{\mu,m\\})$ for minimizing the total (weighted)
completion time, even if the algorithm is clairvoyant and machines are
related.

###### Proof.

Let $\mu_{1},\mu_{2}\geq 1$ and $\mu=\mu_{1}\cdot\mu_{2}$. Consider an
instance $J=\\{j\\}$ with $p_{j}=2\mu$ and $m\geq 2\mu$ machines such that
$\bm{\hat{}}{s}_{i}=\mu_{1}$ for all $1\leq i\leq m$. The algorithm cannot
distinguish the machines. For the first $2\mu-1$ machines $i$ on which the
algorithm processes $j$, the adversary fixes $s_{i}=1$. Thus, at time
$2\mu-1$, the remaining processing requirement of $j$ is at least
$2\mu-(2\mu-1)=1$ and there exists a machine $i^{\prime}$ on which $j$ has not
been processed yet. Thus, the adversary can set $s_{i^{\prime}}=\mu$ and
complete $j$ on $i^{\prime}$ within two time units, implying a competitive
ratio of at least $\Omega(\min\\{\mu,m\\})$. ∎

Observe that this construction already works for two machines when migration
is forbidden.

###  2.1 A Clairvoyant Algorithm

We firstly present a novel migratory algorithm for the clairvoyant setting
with known processing requirements for both the speed-aware setting as well as
speed predictions. Sequencing jobs by Smith’s rule by non-increasing density
$\frac{w_{j}}{p_{j}}$ (aka Weighted-Shortest-Processing-Time, WSPT) is optimal
on a single machine [S+56]. In the online setting with release dates, this
policy is $2$-competitive when applied preemptively on the available
unfinished jobs [SS02a]. It can be extended to identical parallel machines
[MS04], by processing at any time the (at most) $m$ jobs with highest
densities. However, this approach is infeasible on unrelated machines, because
jobs can have different densities on every machine.

Inspired by the power of densities, we compute a subset of at most $m$ jobs
that instead maximizes the total density, that is, the sum of the densities of
the job-to-machine assignment. This can be done efficiently by computing at
any time $t$ a matching $M_{t}$ between alive jobs $j\in J(t)=\\{j\in J\mid
r_{j}\leq t\leq C_{j}\\}$ and machines $i\in I$ with edge weights
$\bm{\hat{}}{\delta}_{ij}=\frac{w_{j}\bm{\hat{}}{s}_{ij}}{p_{j}}$ using, e.g.,
the Hungarian algorithm [Kuh55]. In the analysis, we crucially exploit the
local optimality of any two matched job-machine pairs via exchange arguments.

Algorithm 1 Maximum Density

0: time $t$, speed (predictions) $\\{\bm{\hat{}}{s}_{ij}\\}$

1: Construct a complete bipartite graph $G_{t}=I\cup J(t)$ where an edge
$(i,j)\in I\times J(t)$ has a weight equal to
$\bm{\hat{}}{\delta}_{ij}=\frac{w_{j}\bm{\hat{}}{s}_{ij}}{p_{j}}$.

2: Compute a maximum-weight matching $M_{t}$ for $G_{t}$.

3: Schedule jobs to machines according to $M_{t}$ at time $t$.

######  Theorem 2.2.

Algorithm 1 has a competitive ratio of at most $8\mu$ for minimizing the total
weighted completion time on unrelated machines with speed predictions.

This theorem implies immediately the following corollary for the speed-aware
setting ($\mu=1$).

######  Corollary 2.3.

Algorithm 1 has a competitive ratio of at most $8$ for minimizing the total
weighted completion time on unrelated machines in the speed-aware setting.

The remaining section is devoted to proof of Theorem 2.2, which uses a dual-
fitting argumentation. To this end, we state the standard migratory linear
programming relaxation for our objective function [SS02b]. In fact, we state a
variant where the machines of an optimal solution run at a lower speed of
$\frac{1}{\alpha}$ for $\alpha\geq 1$ [IKM18].

min $\displaystyle\sum_{i\in I}\sum_{j\in J}\sum_{t\geq 0}w_{j}\cdot
t\cdot\frac{x_{ijt}s_{ij}}{p_{j}}$ ($\text{LP}_{\alpha}$) s.t.
$\displaystyle\sum_{i\in I}\sum_{t\geq 0}\frac{x_{ijt}s_{ij}}{p_{j}}\geq 1$
$\displaystyle\forall j\in J$ $\displaystyle\sum_{j\in J}\alpha\cdot
x_{ijt}\leq 1$ $\displaystyle\forall i\in I,t\geq 0$ $\displaystyle\sum_{i\in
I}\alpha\cdot x_{ijt}\leq 1$ $\displaystyle\forall j\in J,t\geq r_{j}$
$\displaystyle x_{ijt}\geq 0$ $\displaystyle\forall i\in I,j\in J,t\geq r_{j}$
$\displaystyle x_{ijt}=0$ $\displaystyle\forall i\in I,j\in J,t<r_{j}$

Let ${\textsc{Opt}}_{\alpha}$ denote the optimal objective value in this
restricted setting. The dual of ($\text{LP}_{\alpha}$) can be written as
follows. (From now on we omit obvious set constraints in the notation for an
improved readability.)

max $\displaystyle\sum_{j}a_{j}-\sum_{i,t}b_{it}-\sum_{j,t\geq r_{j}}c_{jt}$
($\text{DLP}_{\alpha}$) s.t. $\displaystyle\frac{a_{j}s_{ij}}{p_{j}}-\alpha
b_{it}-\alpha c_{jt}\leq w_{j}\frac{s_{ij}t}{p_{j}}\qquad$
$\displaystyle\forall i,j,t\geq r_{j}$ $\displaystyle
a_{j},b_{it},c_{jt^{\prime}}\geq 0\qquad$ $\displaystyle\forall i,j,t\;\forall
t^{\prime}\geq r_{j}$

Fix an instance and the algorithm’s schedule. Let $\kappa\geq 1$ be a
constant. We define for every machine $i$ and any time $t$

$\beta_{it}=\begin{cases}\bm{\hat{}}{\delta}_{ij}&\text{ if }i\text{ is
matched to }j\in J(t)\text{ in }M_{t}\\\ 0&\text{ otherwise,}\end{cases}$

and for every job $j$ and any time $t$

$\gamma_{jt}=\begin{cases}\bm{\hat{}}{\delta}_{ij}&\text{ if }j\text{ is
matched to }i\in I\text{ in }M_{t}\\\ 0&\text{ otherwise.}\end{cases}$

Consider the following values:

  * •

$\bm{\bar{}}{a}_{j}=w_{j}C_{j}$ for every job $j$,

  * •

$\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\beta_{it^{\prime}}$ for every machine $i$ and time $t$, and

  * •

$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\gamma_{jt^{\prime}}$ for every job $j$ and time $t\geq r_{j}$.

We show in Lemma 2.5 that these values define a feasible solution for the dual
problem ($\text{DLP}_{\alpha}$), and that the corresponding dual objective
value is at least a certain fraction of the algorithm’s solution value (Lemma
2.4). Weak LP duality then implies Theorem 2.2. Let
${\textsc{Alg}}=\sum_{j}w_{j}C_{j}$.

######  Lemma 2.4.

$(1-\frac{2\mu_{1}}{\kappa}){\textsc{Alg}}\leq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}$

In the following, let $U_{t}$ be the set of unfinished jobs at time $t$, i.e.,
all jobs $j$ with $t\leq C_{j}$, and let $W_{t}=\sum_{j\in U_{t}}w_{j}$.

###### Proof.

Fix a time $t$ and a job $j$. If $j\in U_{t}$, let
$i^{j}_{1},\ldots,i^{j}_{z(j)}$ be the sequence of individual machine
assignments of $j$ between time $t$ and $C_{j}$. Let
$\bm{\hat{}}{\delta}(i,j):=\bm{\hat{}}{\delta}_{ij}$. Note that

$\sum_{\ell=1}^{z(j)}\bm{\hat{}}{\delta}(i^{j}_{\ell},j)=\sum_{\ell=1}^{z(j)}\bm{\hat{}}{s}_{i^{j}_{\ell},j}\frac{w_{j}}{p_{j}}\leq\mu_{1}\sum_{\ell=1}^{z(j)}s_{i^{j}_{\ell},j}\frac{w_{j}}{p_{j}}\leq\mu_{1}w_{j}.$

Therefore, $\sum_{i}\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{j\in
U_{t}}\sum_{\ell=1}^{z(j)}\bm{\hat{}}{\delta}(i^{j}_{\ell},j)\leq\frac{\mu_{1}}{\kappa}W_{t}$.
Similarly,
$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{\ell=1}^{z(j)}\bm{\hat{}}{\delta}(i^{j}_{\ell},j)\leq\frac{\mu_{1}}{\kappa}w_{j}$.
If $j\in J\setminus U_{t}$, then, $\bm{\bar{}}{c}_{jt}=0$. Hence, $\sum_{j\in
J}\bm{\bar{}}{c}_{jt}\leq\frac{\mu_{1}}{\kappa}W_{t}$. Finally, we conclude
$\sum_{i,t}\bm{\bar{}}{b}_{it}\leq\frac{\mu_{1}}{\kappa}{\textsc{Alg}}$ and
$\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\leq\frac{\mu_{1}}{\kappa}{\textsc{Alg}}$. ∎

######  Lemma 2.5.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{it}=\bm{\bar{}}{b}_{it}$ and
$c_{jt}=\bm{\bar{}}{c}_{jt}$ is feasible for ($\text{DLP}_{\alpha}$) if
$\alpha=\mu_{2}\kappa$.

###### Proof.

First note that the dual assignment is non-negative. Let $i\in I,j\in J$ and
$t\geq r_{j}$. The definition of $\bm{\bar{}}{a}_{j}$ yields
$\bm{\bar{}}{a}_{j}\frac{s_{ij}}{p_{j}}-w_{j}t\frac{s_{ij}}{p_{j}}\leq\sum_{t^{\prime}=t}^{C_{j}}\frac{w_{j}s_{ij}}{p_{j}}.$
By using the fact that
$\frac{w_{j}s_{ij}}{p_{j}}\leq\mu_{2}\frac{w_{j}\bm{\hat{}}{s}_{ij}}{p_{j}}$,
the definitions of $\bm{\bar{}}{b}_{it}$ and $\bm{\bar{}}{c}_{jt}$, and the
value of $\alpha$, it remains to validate for every $t\leq t^{\prime}\leq
C_{j}$ that
$\frac{w_{j}\bm{\hat{}}{s}_{ij}}{p_{j}}=\bm{\hat{}}{\delta}_{ij}\leq\beta_{it^{\prime}}+\gamma_{jt^{\prime}}$.
We distinguish five cases:

  1. (i)

If $(i,j)\in M_{t^{\prime}}$, then
$\bm{\hat{}}{\delta}_{ij}=\beta_{it^{\prime}}=\gamma_{jt^{\prime}}$.

  2. (ii)

If $(i,j^{\prime})\in M_{t^{\prime}}$ and $(i^{\prime},j)\in M_{t^{\prime}}$
s.t. $i^{\prime}\neq i$ (and thus $j^{\prime}\neq j$), we know by the
optimality of $M_{t^{\prime}}$ that

$\displaystyle\bm{\hat{}}{\delta}_{ij}\leq\bm{\hat{}}{\delta}_{ij}+\bm{\hat{}}{\delta}_{i^{\prime}j^{\prime}}\leq\bm{\hat{}}{\delta}_{i^{\prime}j}+\bm{\hat{}}{\delta}_{ij^{\prime}}=\gamma_{jt^{\prime}}+\beta_{it^{\prime}}.$

  3. (iii)

If $(i^{\prime},j)\in M_{t^{\prime}}$ and $i$ is not matched in
$M_{t^{\prime}}$, we conclude
$\bm{\hat{}}{\delta}_{ij}\leq\bm{\hat{}}{\delta}_{i^{\prime}j}=\gamma_{jt^{\prime}}.$

  4. (iv)

If $(i,j^{\prime})\in M_{t^{\prime}}$ and $j$ is not matched in
$M_{t^{\prime}}$, we conclude
$\bm{\hat{}}{\delta}_{ij}\leq\bm{\hat{}}{\delta}_{ij^{\prime}}=\beta_{it^{\prime}}.$

  5. (v)

The case where $\bm{\hat{}}{s}_{ij}>0,w_{j}>0$, but both $i$ and $j$ are
unmatched in $M_{t^{\prime}}$ contradicts the optimality of $M_{t^{\prime}}$,
as $t^{\prime}\leq C_{j}$. Else holds $\bm{\hat{}}{\delta}_{ij}=0$, and we
conclude since the right side of the inequality is non-negative. ∎

###### Proof of Theorem 2.2.

Weak LP duality implies that the optimal objective value of
($\text{DLP}_{\alpha}$) is greater or equal to the optimal objective value of
($\text{LP}_{\alpha}$). Being the objective value of a relaxation, the latter
is a lower bound on ${\textsc{Opt}}_{\alpha}$, which in turn is at most
$\alpha{\textsc{Opt}}$ by scaling completion times, where Opt denotes the
optimal objective value of the original problem. This implies via Lemma 2.4
and Lemma 2.5

$\displaystyle\mu_{2}\kappa\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\mu_{2}\kappa}\geq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\geq\left(1-\frac{2\mu_{1}}{\kappa}\right)\cdot{\textsc{Alg}}.$

Choosing $\kappa=4\mu_{1}$, we conclude ${\textsc{Alg}}\leq
8\mu\cdot{\textsc{Opt}}$. ∎

###  2.2 A Clairvoyant Non-Preemptive Algorithm

Algorithm 2 Greedy WSPT

0: speed predictions $\\{\bm{\hat{}}{s}_{ij}\\}$

function UponJobArrival(job $j$)

Assign job $j$ to machine $g(j)=\operatorname*{arg\,min}_{i\in
I}\bm{\hat{}}{Q}_{ij}$.

end function

function UponMachineIdle(machine $i$, time $t$)

Start processing the job $j$ with largest $\bm{\hat{}}{\delta}_{ij}$ among all
alive jobs assigned to $i$ which satisfy $\bm{\hat{}}{r}_{ij}\leq t$.

end function

In many applications, job migration or preemption are not possible. In this
section, we show that the non-preemptive Greedy WSPT algorithm by [GMUX20]
achieves an error-dependent competitive ratio when using predicted speeds to
make decisions (Algorithm 2). The intuition of this algorithm is to greedily
assign arriving jobs to machines, where they are then scheduled in WSPT order,
i.e., on machine $i$ by non-decreasing $\frac{w_{j}s_{ij}}{p_{j}}$. The greedy
job-to-machine assignment intuitively minimizes the increase of the objective
value that scheduling the job on a machine incurs in the current state.
Additionally, the execution of job $j$ is delayed depending on its processing
time $\frac{p_{j}}{s_{ij}}$ on the assigned machine $i$. This is necessary due
to simple lower bounds in the non-preemptive setting [LSS03].

To make this precise, for every $j\in J$, let $M_{i}(j)$ be the set of jobs,
excluding job $j$, which are assigned to machine $i$ at time $r_{j}$, but have
not been started yet. As this definition is ambiguous if there are two jobs
$j$ and $j^{\prime}$ with $r_{j}=r_{j^{\prime}}$ being assigned to $i$, we
assume that we assign them in the order of their index. For all machines $i$,
jobs $j$ and a constant $\theta>0$, which we will set $\theta=\frac{2}{3}$, we
define
$\bm{\hat{}}{r}_{ij}=\max\\{r_{j},\theta\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}\\}$
and $\bm{\hat{}}{Q}_{ij}$ as

$w_{j}\Bigg{(}\bm{\hat{}}{r}_{ij}+\frac{\bm{\hat{}}{r}_{ij}}{\theta}+\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}+\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}\geq\bm{\hat{}}{\delta}_{ij}\end{subarray}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\Bigg{)}+\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}\end{subarray}}w_{j^{\prime}}.$

We prove in Section A.1 the following theorem.

######  Theorem 2.6.

Algorithm 2 has a competitive ratio of at most
$\frac{368}{51}\mu^{2}<7.216\mu^{2}$ for minimizing the total weighted
completion time on unrelated machines with speed predictions.

###  2.3 A Non-Clairvoyant Algorithm

In the non-clairvoyant setting, any constant-competitive algorithm for
minimizing the total completion time on unrelated machines has to migrate and
preempt jobs [MPT94, GIK+12]. Since such algorithms cannot compute densities,
a common strategy is to run all jobs simultaneously at a rate proportional to
their weight [MPT94, KC03]. On unrelated machines with job-dependent speeds,
the Proportional Fairness Algorithm (PF) develops this idea further by
respecting job-dependent speeds [IKM18]. It is known that PF has a competitive
ratio of at most $128$ for minimizing the total weighted completion time
[IKM18]. In the following, we show that PF has a linear error-dependency in
$\mu$ when computing rates via predicted speeds. As a byproduct, we slightly
improve the upper bound on the speed-aware competitive ratio of PF via
optimized duals to $108$.

Algorithm 3 Proportional Fairness

0: time $t$, speed predictions $\\{\bm{\hat{}}{s}_{ij}\\}$

Use solution $\\{y_{ijt}\\}_{i,j}$ of ($\text{CP}_{t}$) as rates at time $t$.

######  Theorem 2.7.

Algorithm 3 has a competitive ratio of at most $108\mu$ for minimizing the
total weighted completion time on unrelated machines with predicted speeds.

At every time $t$, Algorithm 3 schedules jobs $J(t)$ with rates computed via
the following convex program ($\text{CP}_{t}$) with variables
$\bm{\hat{}}{y}_{ijt}$ for every machine $i$ and job $j\in J(t)$.

max $\displaystyle\sum_{j\in J(t)}w_{j}\log\left(\sum_{i\in
I}\bm{\hat{}}{s}_{ij}\bm{\hat{}}{y}_{ijt}\right)$ ($\text{CP}_{t}$) s.t.
$\displaystyle\sum_{j\in J(t)}\bm{\hat{}}{y}_{ijt}\leq 1$
$\displaystyle\forall i\in I$ $\displaystyle\sum_{i\in
I}\bm{\hat{}}{y}_{ijt}\leq 1$ $\displaystyle\forall j\in J(t)$
$\displaystyle\bm{\hat{}}{y}_{ijt}\geq 0$ $\displaystyle\forall i\in I,j\in
J(t)$

We now give an overview over the proof of Theorem 2.7 and defer further
details to Section A.2.

Fix an instance and PF’s schedule. Let $\kappa\geq 1$ and $0<\lambda<1$ be
constants which we fix later. In the following, we assume by scaling that all
weights are integers. For every time $t$, let $Z^{t}$ be the sorted
(ascending) list of length $W_{t}$ composed of $w_{j}$ copies of
$\frac{q_{jt}}{p_{j}}$ for every $j\in U_{t}$. We define $\zeta_{t}$ as the
value at the index $\lfloor\lambda W_{t}\rfloor$ in $Z^{t}$. Let
$\\{\eta_{it}\\}_{i,t}$ and $\\{\theta_{jt}\\}_{j\in J(t),t}$ be the KKT
multipliers of the first two constraint sets of the optimal solution
$\\{y_{ijt}\\}_{i,j}$. Let $\mathds{1}[\varphi]$ be the indicator variable of
the formula $\varphi$, and consider the following duals:

  * •

$\bm{\bar{}}{a}_{j}=\sum_{t^{\prime}=0}^{C_{j}}w_{j}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
for every job $j$,

  * •

$\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\zeta_{t^{\prime}}\eta_{it^{\prime}}$ for every machine $i$ and time $t$,
and

  * •

$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{t^{\prime}=t}^{C_{j}}\zeta_{t^{\prime}}\theta_{jt^{\prime}}$
for every job $j$ and time $t\geq r_{j}$.

We show that this assignment has an objective value which lower bounds a
fraction of PF’s objective value, and that it is feasible for
($\text{DLP}_{\alpha}$) for some values of $\alpha$.

######  Lemma 2.8.

$(\lambda-\frac{4}{(1-\lambda)\kappa}){\textsc{Alg}}\leq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}$

######  Lemma 2.9.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{it}=\bm{\bar{}}{b}_{it}$ and
$c_{jt}=\bm{\bar{}}{c}_{jt}$ is feasible for ($\text{DLP}_{\alpha}$) if
$\alpha=\kappa\mu$.

###### Proof of Theorem 2.7.

Weak duality, 2.8 and 2.9 imply

$\displaystyle\kappa\mu\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\kappa\mu}\geq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\geq\left(\lambda-\frac{4}{(1-\lambda)\kappa}\right)\cdot{\textsc{Alg}}.$

Setting $\kappa=36$ and $\lambda=\frac{2}{3}$ implies ${\textsc{Alg}}\leq
108\mu\cdot{\textsc{Opt}}$. ∎

##  3 Algorithms for Speed-Ordered Machines

This section contains our results on speed-ordered machines. In the first
subsection, we present a clairvoyant algorithm, and in the second subsection a
non-clairvoyant algorithm. But first, we observe that in this model migration
is necessary for speed-oblivious algorithms.

######  Theorem 3.1.

Any non-migratory speed-oblivious algorithm has a competitive ratio of at
least $\Omega(m)$ for minimizing the total completion time on $m$ speed-
ordered machines, even if it is clairvoyant and the machines are related.

###### Proof.

Consider the execution of some algorithm on an instance of $n$ jobs with unit-
weights and with processing requirements equal to $n^{2}m$ and $s_{1}=n^{2}m$.
If at some point in time, the algorithm starts a job on machines $2,\ldots,m$,
the adversary sets $s_{2}=\ldots=s_{m}=1$ to enforce an objective value of at
least $\Omega(n^{2}m)$, while scheduling all jobs on the first machine gives
an objective value of at most $\mathcal{O}(n^{2})$. If this does not happen,
the algorithm must have scheduled all jobs on the first machine. But then the
adversary sets $s_{2}=\ldots=s_{m}=n^{2}m$ and achieves an objective value of
$\mathcal{O}(\frac{n^{2}}{m})$ by distributing the jobs evenly to all
machines, while the algorithm has an objective value of $\Omega(n^{2})$. ∎

###  3.1 A Clairvoyant Algorithm

Algorithm 4 Maximum Density for speed-ordered machines

0: time $t$, speed-ordered machines $s_{1}\geq\ldots\geq s_{m}$

1: $\sigma_{t}\leftarrow$ order of $J(t)$ with non-increasing
$\frac{w_{j}}{p_{j}}$.

2: $M_{t}=\\{(k,\sigma_{t}(k))\\}_{k\in[\ell]}$ where $\ell=\min\\{m,\lvert
J(t)\rvert\\}$

3: Schedule jobs to machines according to $M_{t}$ at time $t$.

Our clairvoyant algorithm for speed-ordered related machines is motivated by
the following observation. If the machines are related and speed-ordered,
Algorithm 1, given correct speed predictions, will assign jobs by non-
increasing order of $\frac{w_{j}}{p_{j}}$ to machines in speed order, because
this clearly maximizes the total scheduled density, i.e., sum of assigned
$\frac{w_{j}s_{i}}{p_{j}}$. Algorithm 4 can therefore emulate this schedule of
maximum density _without_ having to compute a maximum matching, and thus does
not require (predicted) speeds. These observations also suggest that the
analysis must be similar. Indeed, we can use a similar dual-fitting as for
Theorem 2.2 to prove the following theorem. We mainly present new ideas for
proving the dual feasibility. Note that this observation does not hold for
unrelated machines.

######  Theorem 3.2.

Algorithm 4 has a competitive ratio of at most $8$ for minimizing the total
weighted completion time on speed-ordered related machines.

We use a dual-fitting analysis based on ($\text{DLP}_{\alpha}$) to prove this
theorem. Fix an instance and the algorithm’s schedule, and observe that the
algorithm ensures at every time $t$ that $M_{t}$ is a matching between alive
jobs and machines. Recall that for related machines, $s_{i}=s_{ij}$ for every
job $j$ and every machine $i$. Let $\kappa\geq 1$ be a constant. We define for
every machine $i$ and any time $t$

$\beta_{it}=\begin{cases}\frac{w_{j}s_{i}}{p_{j}}&\text{ if }i\text{ is
matched to }j\in J(t)\text{ in }M_{t}\\\ 0&\text{ otherwise,}\end{cases}$

and for every job $j$ and any time $t$

$\gamma_{jt}=\begin{cases}\frac{w_{j}s_{i}}{p_{j}}&\text{ if }j\text{ is
matched to }i\in I\text{ in }M_{t}\\\ 0&\text{ otherwise.}\end{cases}$

Using these values, we have the following dual assignment:

  * •

$\bm{\bar{}}{a}_{j}=w_{j}C_{j}$ for every job $j$,

  * •

$\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\beta_{it^{\prime}}$ for every machine $i$ and time $t$, and

  * •

$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\gamma_{jt^{\prime}}$ for every job $j$ and time $t\geq r_{j}$.

We first observe that the dual objective of this assignment is close to
algorithm’s objective. The proof works analogous to the proof of Lemma 2.4.

######  Lemma 3.3.

$(1-\frac{2}{\kappa}){\textsc{Alg}}\leq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}$

######  Lemma 3.4.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{it}=\bm{\bar{}}{b}_{it}$ and
$c_{jt}=\bm{\bar{}}{c}_{jt}$ is feasible for ($\text{DLP}_{\alpha}$) if
$\alpha=\kappa$ and $s_{i}=s_{ij}$ for every job $j$ and every machine $i$.

###### Proof.

Since the dual assignment is clearly non-negative, we now show that it
satisfies the dual constraint. Let $i\in I,j\in J$ and $t\geq r_{j}$. We first
observe that

$\displaystyle\bm{\bar{}}{a}_{j}\frac{s_{i}}{p_{j}}-w_{j}t\frac{s_{i}}{p_{j}}\leq\sum_{t^{\prime}=t}^{C_{j}}\frac{w_{j}s_{i}}{p_{j}}.$

Using $\alpha=\kappa$, it remains to validate for every $t\leq t^{\prime}\leq
C_{j}$ that
$\frac{w_{j}s_{i}}{p_{j}}\leq\beta_{it^{\prime}}+\gamma_{jt^{\prime}}$. We
distinguish five cases:

  1. (i)

If $(i,j)\in M_{t^{\prime}}$, then
$\frac{w_{j}s_{i}}{p_{j}}=\beta_{it^{\prime}}=\gamma_{jt^{\prime}}$.

  2. (ii)

If $(i,j^{\prime})\in M_{t^{\prime}}$ and $(i^{\prime},j)\in M_{t^{\prime}}$
s.t. $i\neq i^{\prime}$, we have two cases. If $i<i^{\prime}$, it must be that
$\sigma_{t^{\prime}}(j^{\prime})<\sigma_{t^{\prime}}(j)$ and, thus,
$\frac{w_{j^{\prime}}}{p_{j^{\prime}}}\geq\frac{w_{j}}{p_{j}}$. But then,
$\frac{w_{j}s_{i}}{p_{j}}\leq\frac{w_{j^{\prime}}s_{i}}{p_{j^{\prime}}}$.
Otherwise, that is, $i>i^{\prime}$, we know by the speed order that $s_{i}\leq
s_{i^{\prime}}$, and, thus,
$\frac{w_{j}s_{i}}{p_{j}}\leq\frac{w_{j}s_{i^{\prime}}}{p_{j}}$. Put together,

$\frac{w_{j}s_{i}}{p_{j}}\leq\frac{w_{j^{\prime}}s_{i}}{p_{j^{\prime}}}+\frac{w_{j}s_{i^{\prime}}}{p_{j}}=\beta_{it^{\prime}}+\gamma_{jt^{\prime}}.$

  3. (iii)

If $(i^{\prime},j)\in M_{t^{\prime}}$ and $i$ is not matched in
$M_{t^{\prime}}$, it follows $i^{\prime}<i$, which gives
$\frac{w_{j}s_{i}}{p_{j}}\leq\frac{w_{j}s_{i^{\prime}}}{p_{j}}=\gamma_{jt^{\prime}}.$

  4. (iv)

If $(i,j^{\prime})\in M_{t^{\prime}}$ and $j$ is not matched in
$M_{t^{\prime}}$, it follows
$\sigma_{t^{\prime}}(j^{\prime})<\sigma_{t^{\prime}}(j)$, and hence
$\frac{w_{j}}{p_{j}}\leq\frac{w_{j^{\prime}}}{p_{j^{\prime}}}$. This
immediately concludes
$\frac{w_{j}s_{i}}{p_{j}}\leq\frac{w_{j^{\prime}}s_{i}}{p_{j^{\prime}}}=\beta_{it^{\prime}}.$

  5. (v)

The case where both $i$ and $j$ are unmatched in $M_{t^{\prime}}$ contradicts
the definition of $M_{t^{\prime}}$ in Algorithm 4.

∎

###### Proof of Theorem 3.2.

Weak duality, Lemma 3.4 and Lemma 3.3 imply

$\displaystyle\kappa\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\kappa}\geq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\geq\left(1-\frac{2}{\kappa}\right)\cdot{\textsc{Alg}}.$

Using $\kappa=4$ concludes
${\textsc{Alg}}\leq\frac{\kappa}{1-2/\kappa}\cdot{\textsc{Opt}}=8\cdot{\textsc{Opt}}.$
∎

We finally observe that Algorithm 4 indeed cannot achieve a good competitive
ratio if speeds are job-dependent.

######  Lemma 3.5.

Algorithm 4 has a competitive ratio of at least $\Omega(n)$ for minimizing the
total weighted completion time on speed-ordered unrelated machines, even on
two machines and if $w_{j}=1$ for all jobs $j$.

###### Proof.

Let $0<\epsilon<1$. Consider an instance composed of $n$ jobs and $2$
machines, where $w_{j}=1$ for all jobs $j$, $p_{1}=1$ and $p_{j}=1+\epsilon$
for all $2\leq j\leq n$. The processing speeds are given by
$s_{11}=s_{21}=\epsilon$, and $s_{1j}=1$ and $s_{2j}=\epsilon$ for all $2\leq
j\leq n$. Note that the machines are speed-ordered. Algorithm 4 completes at
time $\frac{1}{\epsilon}$ job $1$ on machine $1$ before any other job. Thus,
${\textsc{Alg}}\geq\frac{n}{\epsilon}$. Another solution is to schedule jobs
$2,\ldots,n$ on machine $1$, and job $1$ on machine $2$, giving an objective
of at most $n^{2}+\frac{1}{\epsilon}$. For $\epsilon<n^{-2}$, this concludes
that $\frac{{\textsc{Alg}}}{{\textsc{Opt}}}\geq\Omega(n)$. ∎

###  3.2 A Non-Clairvoyant Algorithm

The non-clairvoyant setting is more difficult. This is because the schedules
of speed-aware algorithms, such as PF, are not as easy to describe, as it was
the case for clairvoyant algorithms. However, for unit weights, related
machines and many alive jobs, i.e., $\lvert J(t)\rvert\geq m$, one solution of
($\text{CP}_{t}$) is to schedule all jobs on all machines with the same rate,
i.e., do Round Robin on every machine. We can describe this schedule without
knowing anything about the speeds. However, in the few-job regime, i.e.,
$\lvert J(t)\rvert<m$, this approach violates the packing constraints of the
jobs, i.e., $\sum_{i}y_{ijt}>1$. This is where the speed order comes into
play: we partition a job’s available rate only to the $\lvert J(t)\rvert$
fastest machines. For the final algorithm (Algorithm 5), we prove below a
guarantee for unrelated machines, and a constant upper bound for related
machines in Section B.2.

Algorithm 5 Round Robin for speed-ordered machines

0: time $t$, speed-ordered machines $s_{1j}\geq\ldots\geq s_{mj}$

Use rates $y_{ijt}=\lvert J(t)\rvert^{-1}\cdot\mathds{1}\left[i\leq\lvert
J(t)\rvert\right]$ at time $t$.

######  Theorem 3.6.

Algorithm 5 has a competitive ratio of at most
$\mathcal{O}(\log(\min\\{n,m\\}))$ for minimizing the total completion time on
speed-ordered unrelated machines.

We prove Theorem 3.6 via dual-fitting based on ($\text{DLP}_{\alpha}$), where
$w_{j}=1$ for every job $j$. Fix an instance and the algorithm’s schedule. For
every time $t$, we write $m_{t}=\min\\{m,\lvert J(t)\rvert\\}$, and we define
$\beta_{it}=\frac{1}{i}\cdot\lvert J(t)\rvert\cdot\mathds{1}\left[i\leq\lvert
J(t)\rvert\right]$ for every machine $i$, and
$\gamma_{jt}=\mathds{1}\left[j\in J(t)\right]$ for every job $j$.

Let $\kappa=\Theta(\log(\min\\{n,m\\}))$. Intuitively, this factor upper
bounds $\sum_{i=1}^{m_{t}}\frac{1}{i}$, which will be necessary when handling
$\sum_{i}\beta_{it}$. For related machines, we can alter the definition of
$\beta_{it}$ and thus have a constant $\kappa$, which eventually implies a
constant upper bound on the competitive ratio.

For every time $t$, consider the sorted (ascending) list $Z^{t}$ composed of
values $\frac{q_{jt}}{p_{j}}$ for every $j\in U_{t}$. We define $\zeta_{t}$ as
the value at the index $\lfloor\frac{1}{2}\lvert U_{t}\rvert\rfloor$ in
$Z^{t}$. Consider the following duals:

  * •

$\bm{\bar{}}{a}_{j}=\sum_{t^{\prime}=0}^{C_{j}}\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
for every job $j$,

  * •

$\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\beta_{it^{\prime}}\zeta_{t^{\prime}}$ for every machine $i$ and time $t$,
and

  * •

$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\gamma_{jt^{\prime}}\zeta_{t^{\prime}}$ for every job $j$ and time $t\geq
r_{j}$.

We prove the following bound on Alg in Section B.1.

######  Lemma 3.7.

$\Omega(1)\cdot{\textsc{Alg}}\leq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}$

This lemma, weak LP duality, and the feasibility of the crafted duals (Lemma
3.8) imply Theorem 3.6 for $\alpha=\kappa$.

######  Lemma 3.8.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{it}=\bm{\bar{}}{b}_{it}$ and
$c_{jt}=\bm{\bar{}}{c}_{jt}$ is feasible for ($\text{DLP}_{\alpha}$) if
$\alpha=\kappa$.

###### Proof.

First observe that the dual assignment is non-negative. Let $i\in I,j\in J$
and $t\geq r_{j}$. Since the rates of Algorithm 5 imply
$q_{jt}=\sum_{\ell=1}^{m_{t}}\frac{s_{\ell j}}{\lvert J(t)\rvert}$, we have

$\displaystyle\frac{\bm{\bar{}}{a}_{j}s_{ij}}{p_{j}}-\frac{s_{ij}\cdot
t}{p_{j}}$
$\displaystyle\leq\sum_{t^{\prime}=t}^{C_{j}}\frac{s_{ij}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]=\sum_{t^{\prime}=t}^{C_{j}}\frac{s_{ij}}{q_{jt^{\prime}}}\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]\leq\sum_{t^{\prime}=t}^{C_{j}}\frac{s_{ij}}{\sum_{\ell=1}^{m_{t^{\prime}}}\frac{s_{\ell
j}}{\lvert J(t^{\prime})\rvert}}\cdot\zeta_{t^{\prime}}.$ (1)

Consider any time $t^{\prime}$ with $t\leq t^{\prime}\leq C_{j}$. If
$i\leq\lvert J(t^{\prime})\rvert$, by the speed order,
$\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell j}\geq\sum_{\ell=1}^{i}s_{\ell j}\geq
i\cdot s_{ij}$, and thus

$\frac{s_{ij}}{\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell j}}\cdot\lvert
J(t^{\prime})\rvert\cdot\zeta_{t^{\prime}}\leq\frac{1}{i}\cdot\lvert
J(t^{\prime})\rvert\cdot\zeta_{t^{\prime}}=\beta_{it^{\prime}}\cdot\zeta_{t^{\prime}}.$

Otherwise, that is, $i>\lvert J(t^{\prime})\rvert$, we conclude by the speed
order, $\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell j}\geq\sum_{\ell=1}^{\lvert
J(t^{\prime})\rvert}s_{\ell j}\geq\lvert J(t^{\prime})\rvert\cdot s_{ij}$.
Therefore,

$\frac{s_{ij}}{\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell j}}\cdot\lvert
J(t^{\prime})\rvert\cdot\zeta_{t^{\prime}}\leq\frac{\lvert
J(t^{\prime})\rvert}{\lvert
J(t^{\prime})\rvert}\cdot\zeta_{t^{\prime}}=\gamma_{jt^{\prime}}\cdot\zeta_{t^{\prime}},$

because $t^{\prime}\leq C_{j}$. Put together, (1) is at most

$\displaystyle\sum_{t^{\prime}=t}^{C_{j}}\beta_{it^{\prime}}\zeta_{t^{\prime}}+\sum_{t^{\prime}=t}^{C_{j}}\gamma_{jt^{\prime}}\zeta_{t^{\prime}}\leq\kappa(\bm{\bar{}}{b}_{it}+\bm{\bar{}}{c}_{jt}),$

which verifies the dual constraint. ∎

######  Lemma 3.9.

Algorithm 4 has a competitive ratio of at least $\Omega(\log(\min\\{n,m\\}))$
for minimizing the total completion time on speed-ordered unrelated machines,
even if processing speeds are exclusively from $\\{0,1\\}$.

###### Proof.

Consider an instance of $m$ unit-sized jobs $[m]$ and $m$ machines $[m]$.
Every job $j\in[m]$ has on machine $i\in[m]$ a processing speed equal to
$s_{ij}=\mathds{1}\left[i\leq m-j+1\right]$. First observe that
${\textsc{Opt}}\leq m$, because we can process and complete every job
$j\in[m]$ exclusively on machine $m-j+1$ at time $1$. We now calculate the
algorithm’s objective value. To this end, we argue that in the algorithm’s
schedule holds $C_{j}=1+\sum_{i=1}^{j-1}\frac{1}{m-i+1}$ for every job $j$.
Then, ${\textsc{Alg}}=\sum_{j=1}^{m}C_{j}=\Omega(m\log m)$ concludes the
statement.

We first observe that $C_{1}=1$, because job $1$ receives in interval
$I_{1}=[0,C_{1})$ on every machine a rate equal to $\frac{1}{m}$. We now argue
iteratively for $j=2,\ldots,m$ that $C_{j}=1+\sum_{i=1}^{j-1}\frac{1}{m-i+1}$.
Consequently, in interval $I_{j}=[C_{j-1},C_{j})$ must be exactly jobs
$j,\ldots,m$ alive. Fix a job $j$ with $2\leq j\leq m$ and let $2\leq i\leq
j$. Since $j$ receives progress on exactly $m-j+1$ machines, there are $m-i+1$
alive jobs in $I_{i}$, and $I_{i}$ has length $\frac{1}{m-i+2}$, its total
progress in $I_{i}$ is equal to $\frac{m-j+1}{(m-i+1)(m-i+2)}$. Further, $j$’s
progress is equal to $\frac{m-j+1}{m}$ in $I_{1}$. Summing over all intervals
$I_{i}$ with $1\leq i\leq j$ concludes that $j$’s progress until the end of
$I_{j}$ is equal to

$\frac{m-j+1}{m}+\sum_{i=2}^{j}\frac{m-j+1}{(m-i+1)(m-i+2)}=1,$

asserting that $1+\sum_{i=1}^{j-1}\frac{1}{m-i+1}$ is indeed $j$’s completion
time in the algorithm’s schedule. ∎

##  4 Experimental Evaluation

Figure 2: Real experiments on a _HiKey 970_ board. The experiments are each
repeated 3 times with the same workload but different random noise for speed
predictions. Shaded areas show the standard deviation.

#### Setup

We perform experiments on real hardware running representative jobs, which
enables us to perform a realistic evaluation. The setup uses a _HiKey 970_
board [Lin] with a _Kirin 970_ Arm big.LITTLE SoC featuring 4  _big_ cores and
4  _LITTLE_ cores, running Android 8.0. This is a representative smartphone
platform. The _big_ cores always offer a higher performance than the _LITTLE_
cores (speed-ordered) because they support out-of-order execution at higher
frequency and larger caches (see also Figure 1, all speedups are $>1$). Our
workload comprises 100 randomly selected single-threaded jobs from the well-
established _PARSEC-3.0_ [ZBBL16], _SPLASH-3_ [SLKR16], and Polybench [YP15]
benchmark suites. These benchmarks represent various use cases from video
transcoding, rendering, compression, etc. The arrival times are drawn from a
Poisson distribution with varying rate parameter to study different system
loads. We characterized all jobs offline to get accurate speed $s_{ij}$ and
job volume $p_{j}$ values. Speed predictions are created with controllable
error by $\bm{\hat{}}{s}_{ij}=s_{ij}\cdot y_{ij}$, where $y_{ij}$ follows a
log-normal distribution $ln(y_{ij})\sim\mathcal{N}(0,\sigma^{2})$. Note that
the predictions do not consider slowdown effects on real hardware, e.g., due
to shared resource contention, adding additional inaccuracy.

Additionally, we perform synthetic experiments (Appendix C), which use similar
workload and core configurations, but are only simulated. An advantage is that
rates must not be transformed to actual schedules. The results are in line
with the results of our hardware experiments.

#### Algorithms

We consider all algorithms presented in previous sections. Additionally, we
consider Round Robin (RR), which distributes a job evenly over all machines,
and Iterative Greedy (Algorithm 6), which at any time iteratively schedules
the job $j$ on machine $i$ which has the maximum $\bm{\hat{}}{s}_{ij}$ among
all unassigned alive jobs and free machines. We show that Iterative Greedy is
not competitive (lower bound of $\Omega(n)$).

Algorithm 6 Iterative Greedy

0: time $t$, speed predictions $\\{\bm{\hat{}}{s}_{ij}\\}$

1: $I^{\prime}\leftarrow I,J^{\prime}\leftarrow J(t)$

2: while $I^{\prime}\neq\emptyset\land J^{\prime}\neq\emptyset$ do

3: $(i,j)=\operatorname*{arg\,max}_{i\in I^{\prime},j\in
J^{\prime}}w_{j}\bm{\hat{}}{s}_{ij}$

4: $I^{\prime}\leftarrow I^{\prime}\setminus\\{i\\},J^{\prime}\leftarrow
J^{\prime}\setminus\\{j\\}$

5: Schedule job $j$ on machine $i$ with rate $y_{ijt}=1$ at time $t$.

6: end while

######  Lemma 4.1.

Algorithm 6 has a competitive ratio of at least $\Omega(n)$ for minimizing the
total completion time on unrelated machines, even if
$s_{ij}=\bm{\hat{}}{s}_{ij}$ for all jobs $j$ and machines $i$.

###### Proof.

Let $\epsilon>0~{}$ and $n>m\geq 2$ such that $\frac{n-1}{m-1}$ is an integer.
Consider a unit-weight instance of one job with $p_{1}=\frac{n-1}{m-1}$,
$s_{11}=1+\epsilon$ and $s_{i1}=1$ for $2\leq i\leq m$, and $n-1$ jobs with
$p_{j}=\epsilon$ and $s_{1j}=1$ and $s_{ij}=\epsilon$ for $2\leq j\leq n,2\leq
i\leq m$. Algorithm 6 first schedules job 1 on machine 1, and the $n-1$ others
on the remaining $m-1$ machines. Since the completion time of job $1$ is equal
to $\frac{n-1}{(1+\epsilon)(m-1)}$, jobs $2,\ldots,n$ will complete at time at
least $\frac{n-1}{m-1}$ only on machines $2,\ldots,m$ if
$\epsilon<\frac{m}{n-m-1}$, hence this allocation will remain until the end of
the instance. This implies a total completion time of
$\Omega(\frac{n^{2}}{m})$ for jobs $2,\ldots,n$. Another solution is to
schedule all jobs $2,\ldots,n$ on machine 1 with a total completion time of at
most $\mathcal{O}(\epsilon n^{2})$, and job $1$ latest at time
$\mathcal{O}(\frac{n}{m})$ on any other machine. This implies that Algorithm 6
has a competitive ratio of at least $\Omega(n)$. ∎

#### Results

Figure 2 presents the results of the hardware experiments. We exclude PF
because it produces fractional schedules which are often difficult to convert
into real schedules [IKM18], and Greedy WSPT, because, given incorrect
predictions, it significantly underperforms in synthetic experiments. We
repeat each experiment 3 times with the same workload (jobs and arrival times)
but different random noisy speed predictions and plot the average and standard
deviation of the average completion times.

Under low system load (Figure 2a), the number of active jobs is mostly $\leq$
4, i.e., it is mostly feasible to only use the _big_ cores. Consequently, the
algorithms that exploit the speed-ordered property (red) consistently perform
best. Algorithms with speed predictions (blue) perform equally well for
accurate predictions but their performance deteriorates for very noisy
predictions. RR always uses all cores and thus shows a low performance.

Under high system load (Figure 2b), the number of active jobs is mostly $>$ 4,
thus, _LITTLE_ cores have to be used. RR and speed-ordered RR perform
similarly, as both mostly use the same cores. For low prediction noise
($\sigma<1$), Maximum Density performs best, but also requires most
information (speed predictions and clairvoyant). For higher prediction noise,
speed-ordered Maximum Density is better because too noisy speed predictions
result in bad schedules. Iterative Greedy performs best among the non-
clairvoyant algorithms, but does not offer any theoretical guarantees.

Figure 3: Distribution of the system load with speed-ordered Round Robin
(Algorithm 5).

#### Load analysis

Figure 3 shows the distribution of system load during the experiments with
speed-ordered Round Robin (Algorithm 5). At low job arrival rate (1 task/min),
the system load is $\leq$ 4 during 87 % of the time. This means that during
the majority of the time, it is possible to only use the _big_ cores,
explaining why speed predictions or clairvoyance bring little benefit over the
speed-ordered setting as in Figure 2a. In contrast, the system load is $\leq$
4 during 43 % of the time at a high job arrival rate (4 tasks/min), reaching
up to 46. Accurate speed and job volume predictions are much more beneficial
in this case, explaining the larger differences between algorithms in Figure
2b.

#### Summary

Speed predictions are beneficial in the average case if they are relatively
accurate. With inaccurate predictions, relying on the speed-ordering instead
is beneficial. _In summary, our experiments show the power of speed
predictions and speed-ordering for online scheduling in real-world settings._

##  5 Conclusion and Future Directions

We initiated research on speed-oblivious algorithms with two models motivated
by real-world observations. Future directions include settling the asymptotic
competitive ratio for (non-)clairvoyant speed-oblivious algorithms on speed-
ordered unrelated machines, shrinking the upper bound of PF to a small
constant, and investigating speed-oblivious algorithms for other objective
functions such as the total flow time, potentially also in the speed-scaling
model.

## References

  * [ABK+18] Luciana Arantes, Evripidis Bampis, Alexander V. Kononov, Manthos Letsios, Giorgio Lucarelli, and Pierre Sens.  Scheduling under uncertainty: A query-based approach.  In IJCAI, pages 4646–4652, 2018.
  * [AE20] Susanne Albers and Alexander Eckl.  Explorable uncertainty in scheduling with non-uniform testing times.  In WAOA, volume 12806 of Lecture Notes in Computer Science, pages 127–142. Springer, 2020.
  * [AGK12] S. Anand, Naveen Garg, and Amit Kumar.  Resource augmentation for weighted flow-time explained by dual fitting.  In SODA, pages 1228–1241. SIAM, 2012.
  * [AGS22] Antonios Antoniadis, Peyman Jabbarzade Ganje, and Golnoosh Shahkarami.  A novel prediction setup for online speed-scaling.  In SWAT, volume 227 of LIPIcs, pages 9:1–9:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [ALT21] Yossi Azar, Stefano Leonardi, and Noam Touitou.  Flow time scheduling with uncertain processing time.  In STOC, pages 1070–1080. ACM, 2021.
  * [ALT22] Yossi Azar, Stefano Leonardi, and Noam Touitou.  Distortion-oblivious algorithms for minimizing flow time.  In SODA, pages 252–274. SIAM, 2022.
  * [ARM13] ARM Limited.  big.LITTLE Technology: The Future of Mobile, 2013.
  * [AS01] Susanne Albers and Günter Schmidt.  Scheduling with unexpected machine breakdowns.  Discret. Appl. Math., 110(2-3):85–99, 2001.
  * [BE98] Allan Borodin and Ran El-Yaniv.  Online computation and competitive analysis.  Cambridge University Press, 1998.
  * [BKL21] Marcin Bienkowski, Artur Kraska, and Hsiang-Hsuan Liu.  Traveling repairperson, unrelated machines, and other stories about average completion times.  In ICALP, volume 198 of LIPIcs, pages 28:1–28:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [BOSW22] Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei.  Scheduling with speed predictions.  CoRR, abs/2205.01247, 2022.
  * [BSS21] Nikhil Bansal, Aravind Srinivasan, and Ola Svensson.  Lift-and-round to improve weighted completion time on unrelated machines.  SIAM J. Comput., 50(3), 2021.
  * [CGKM09] Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara.  A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation.  In STOC, pages 679–684. ACM, 2009.
  * [DEMM20] Christoph Dürr, Thomas Erlebach, Nicole Megow, and Julie Meißner.  An adversarial model for scheduling with testing.  Algorithmica, 82(12):3630–3675, 2020.
  * [DIL+22] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Algorithms with prediction portfolios.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [DJST09] Florian Diedrich, Klaus Jansen, Ulrich M. Schwarz, and Denis Trystram.  A survey on approximation algorithms for scheduling with machine unavailability.  In Algorithmics of Large and Complex Networks, volume 5515 of Lecture Notes in Computer Science, pages 50–64. Springer, 2009.
  * [EHM+21] Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, and Bertrand Simon.  Speed-robust scheduling - sand, bricks, and rocks.  In IPCO, volume 12707 of Lecture Notes in Computer Science, pages 283–296. Springer, 2021.
  * [ELM+12] Leah Epstein, Asaf Levin, Alberto Marchetti-Spaccamela, Nicole Megow, Julián Mestre, Martin Skutella, and Leen Stougie.  Universal sequencing on an unreliable machine.  SIAM J. Comput., 41(3):565–586, 2012.
  * [FR98] Dror G. Feitelson and Larry Rudolph.  Metrics and benchmarking for parallel job scheduling.  In JSSPP, volume 1459 of Lecture Notes in Computer Science, pages 1–24. Springer, 1998.
  * [GBA+18] Ujjwal Gupta, Manoj Babu, Raid Ayoub, Michael Kishinevsky, Francesco Paterna, and Ümit Y. Ogras.  STAFF: online learning with stabilized adaptive forgetting factor and feature selection algorithm.  In DAC, pages 177:1–177:6. ACM, 2018.
  * [GIK+12] Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, and Kirk Pruhs.  Scheduling heterogeneous processors isn’t as easy as you think.  In SODA, pages 1242–1253. SIAM, 2012.
  * [GMUX20] Varun Gupta, Benjamin Moseley, Marc Uetz, and Qiaomin Xie.  Greed works - online algorithms for unrelated machine stochastic scheduling.  Math. Oper. Res., 45(2):497–516, 2020.
  * [HSSW97] Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein.  Scheduling to minimize average completion time: Off-line and on-line approximation algorithms.  Math. Oper. Res., 22(3):513–544, 1997.
  * [IKM18] Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala.  Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints.  J. ACM, 65(1):3:1–3:33, 2018.
  * [IKMP14] Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs.  Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors.  In FOCS, pages 531–540. IEEE Computer Society, 2014.
  * [IKQP21] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.  Non-clairvoyant scheduling with predictions.  In SPAA, pages 285–294. ACM, 2021.
  * [IL23] Sungjin Im and Shi Li.  Improved approximations for unrelated machine scheduling.  In SODA, pages 2917–2946. SIAM, 2023.
  * [Jäg21] Sven Joachim Jäger.  Approximation in deterministic and stochastic machine scheduling.  PhD thesis, Technical University of Berlin, Germany, 2021.
  * [JMM+03] Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V. Vazirani.  Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP.  J. ACM, 50(6):795–824, 2003.
  * [KC03] Jae-Hoon Kim and Kyung-Yong Chwa.  Non-clairvoyant scheduling for weighted flow time.  Inf. Process. Lett., 87(1):31–37, 2003.
  * [KPSH15] Heba Khdr, Santiago Pagani, Muhammad Shafique, and Jörg Henkel.  Thermal constrained resource management for mixed ILP-TLP workloads in dark silicon chips.  In DAC, pages 179:1–179:6. ACM, 2015.
  * [Kuh55] H. W. Kuhn.  The hungarian method for the assignment problem.  Naval Research Logistics Quarterly, 2(1-2):83–97, 1955.
  * [Li20] Shi Li.  Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations.  SIAM J. Comput., 49(4), 2020.
  * [Lin] Linaro 96Boards.  Hikey970.  https://96boards.org/product/hikey970/.
  * [LLMV20] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In SODA, pages 1859–1877. SIAM, 2020.
  * [LM22] Alexander Lindermayr and Nicole Megow.  Permutation predictions for non-clairvoyant scheduling.  In SPAA, pages 357–368. ACM, 2022.
  * [LM23] Alexander Lindermayr and Nicole Megow.  Repository of papers on algorithms with predictions, 2023.  URL: https://algorithms-with-predictions.github.io/.
  * [LSS03] Xiwen Lu, René Sitters, and Leen Stougie.  A class of on-line scheduling algorithms to minimize total completion time.  Oper. Res. Lett., 31(3):232–236, 2003.
  * [LX21] Shi Li and Jiayi Xian.  Online unrelated machine load balancing with predictions revisited.  In ICML, volume 139 of Proceedings of Machine Learning Research, pages 6523–6532. PMLR, 2021.
  * [MPT94] Rajeev Motwani, Steven J. Phillips, and Eric Torng.  Non-clairvoyant scheduling.  Theor. Comput. Sci., 130(1):17–47, 1994.
  * [MS04] Nicole Megow and Andreas S. Schulz.  On-line scheduling to minimize average completion time revisited.  Oper. Res. Lett., 32(5):485–490, 2004.
  * [MV22] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  Commun. ACM, 65(7):33–35, 2022.
  * [PSK18] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ML predictions.  In NeurIPS, pages 9684–9693, 2018.
  * [PST04] Kirk Pruhs, Jirí Sgall, and Eric Torng.  Online scheduling.  In Handbook of Scheduling. Chapman and Hall/CRC, 2004.
  * [RPMH21] Martin Rapp, Anuj Pathania, Tulika Mitra, and Jörg Henkel.  Neural network-based performance prediction for task migration on S-NUCA many-cores.  IEEE Trans. Computers, 70(10):1691–1704, 2021.
  * [RYR+22] Efraim Rotem, Adi Yoaz, Lihu Rappoport, Stephen J Robinson, Julius Yuli Mandelblat, Arik Gihon, Eliezer Weissmann, Rajshree Chabukswar, Vadim Basin, Russell Fenger, et al.  Intel Alder Lake CPU Architectures.  IEEE Micro, 42(3):13–19, 2022.
  * [S+56] Wayne E Smith et al.  Various optimizers for single-stage production.  Naval Research Logistics Quarterly, 3(1-2):59–66, 1956.
  * [SLKR16] Christos Sakalis, Carl Leonardsson, Stefanos Kaxiras, and Alberto Ros.  Splash-3: A properly synchronized benchmark suite for contemporary research.  In ISPASS, pages 101–111. IEEE Computer Society, 2016.
  * [SS02a] Andreas S. Schulz and Martin Skutella.  The power of $\alpha$-points in preemptive single machine scheduling.  Journal of Scheduling, 5(2):121–133, 2002.
  * [SS02b] Andreas S. Schulz and Martin Skutella.  Scheduling unrelated machines by randomized rounding.  SIAM J. Discret. Math., 15(4):450–469, 2002.
  * [SZ20] Clifford Stein and Mingxian Zhong.  Scheduling when you do not know the number of machines.  ACM Trans. Algorithms, 16(1):9:1–9:20, 2020.
  * [The19] The kernel development community.  Energy Aware Scheduling – The Linux Kernel Documentation, 2019.  https://www.kernel.org/doc/html/v5.3/scheduler/sched-energy.html.
  * [YP15] Tomofumi Yuki and Louis-Noël Pouchet.  Polybench 4.0, 2015.
  * [ZBBL16] Xusheng Zhan, Yungang Bao, Christian Bienia, and Kai Li.  PARSEC3.0: A multicore benchmark suite with network stacks and SPLASH-2X.  SIGARCH Comput. Archit. News, 44(5):1–16, 2016.

##  Appendix A Details on Algorithms with Speed Predictions

###  A.1 Full Analysis of Greedy WSPT with Speed Predictions

In this section, we present an error-dependent competitive ratio for Greedy
WSPT with speed predictions and eventually prove Theorem 2.6. The analysis is
inspired by [GMUX20], but uses a different approach for proving the
feasibility of the crafted duals. In particular, we need less scaling
parameters than Gupta et al. See 2.6

Fix an instance and the algorithm’s schedule. Let $\kappa\geq 1$ and
$0<\theta<1$ be constants. We assume w.l.o.g. by scaling the instance that all
processing requirements and release dates are integer multiples of $\kappa$.
Recall that $\bm{\hat{}}{\delta}_{ij}=\frac{w_{j}\bm{\hat{}}{s}_{ij}}{p_{j}}$
and
$\bm{\hat{}}{r}_{ij}=\max\\{r_{j},\theta\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}\\}$.
We write for every job $j$ and machine $i$

$Q_{ij}=w_{j}\Bigg{(}\bm{\hat{}}{r}_{ij}+\mu_{1}\frac{\bm{\hat{}}{r}_{ij}}{\theta}+\frac{p_{j}}{s_{ij}}+\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}\geq\bm{\hat{}}{\delta}_{ij}\end{subarray}}\frac{p_{j^{\prime}}}{s_{ij^{\prime}}}\Bigg{)}+\frac{p_{j}}{s_{ij}}\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}\end{subarray}}w_{j^{\prime}}.$

Also, recall that the algorithm uses the values $\bm{\hat{}}{Q}_{ij}$ to
assign a job $j$ at time $r_{j}$ to machine
$g(j)=\operatorname*{arg\,min}_{i}\bm{\hat{}}{Q}_{ij}$:

$\bm{\hat{}}{Q}_{ij}=w_{j}\Bigg{(}\bm{\hat{}}{r}_{ij}+\frac{\bm{\hat{}}{r}_{ij}}{\theta}+\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}+\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}\geq\bm{\hat{}}{\delta}_{ij}\end{subarray}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\Bigg{)}+\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}\end{subarray}}w_{j^{\prime}}.$

We now introduce a linear programming relaxation of our problem. As we
consider a non-preemptive scheduling problem here, we can define a stronger
linear program relaxation than ($\text{LP}_{\alpha}$) [SS02b]:

min $\displaystyle\sum_{i,j,t}w_{j}\cdot
x_{ijt}\cdot\left(\frac{1}{2}+\frac{s_{ij}}{p_{j}}\cdot\left(t+\frac{1}{2}\right)\right)$
(NP-LP) s.t. $\displaystyle\sum_{i,t\geq r_{j}}\frac{x_{ijt}s_{ij}}{p_{j}}\geq
1$ $\displaystyle\forall j$ $\displaystyle\sum_{j}x_{ijt}\leq 1$
$\displaystyle\forall i,t$ $\displaystyle x_{ijt}\geq 0$ $\displaystyle\forall
i,j,t$ $\displaystyle x_{ijt}=0$ $\displaystyle\forall i,j,t<r_{j}$

This relaxation has an integrality gap of $2$ [SS02b]. The dual of (NP-LP) can
be written as follows:

max $\displaystyle\quad\sum_{j}a_{j}-\sum_{i,t}b_{it}$ (NP-DLP) s.t.
$\displaystyle\frac{a_{j}s_{ij}}{p_{j}}-b_{it}\leq
w_{j}\left(s_{ij}\frac{t+1/2}{p_{j}}+\frac{1}{2}\right)\quad\forall i,j,t\geq
r_{j}$ (2) $\displaystyle a_{j},b_{it}\geq 0\qquad\forall i,j,t$

We define a solution for (NP-DLP) which depends on the schedule produced by
the algorithm. Let $U_{i}(t)=\\{j\in J\mid g(j)=i\land t<C_{j}\\}$. Note that
$U_{i}(t)$ includes unreleased jobs at time $t$. Consider the following dual
assignment:

  * •

$\bm{\bar{}}{a}_{j}=Q_{g(j)j}$ for every job $j$ and

  * •

$\bm{\bar{}}{b}_{it}=\mu\cdot\sum_{j\in U_{i}(\kappa\cdot t)}w_{j}$ for every
machine $i$ and time $t$.

We first show that the objective value of (NP-DLP) for
$(\bm{\bar{}}{a}_{j},\bm{\bar{}}{b}_{it})$ is close to the objective value of
the algorithm.

######  Lemma A.1.

$\sum_{j}\bm{\bar{}}{a}_{j}\geq{\textsc{Alg}}$

###### Proof.

Consider the algorithm’s schedule. Let $x_{i}(t)$ denote the amount of time
(not volume) the currently processed job on machine $i$ requires to complete.
If there is no job running on machine $i$ at time $t$, we define $x_{i}(t)=0$.
We now calculate the contribution of some job $j$ to the algorithm’s objective
value Alg. Suppose that $j$ gets assigned to $g(j)=i$. Then, $j$ might delay
other jobs with smaller predicted density which have been already assigned to
$i$, i.e., are part of $M_{i}(j)$. Further, $j$ might be delayed by jobs which
have higher predicted density and are part of $M_{i}(j)$. Finally, $j$’s
completion time cannot be less than $\bm{\hat{}}{r}_{ij}+\frac{p_{j}}{s_{ij}}$
due to the definition of the algorithm, and this value might be delayed
further by $x_{i}(\bm{\hat{}}{r}_{ij})$. In total, we conclude that the
contribution of $j$ to Alg is at most

$w_{j}\Bigg{(}\bm{\hat{}}{r}_{ij}+x_{i}(\bm{\hat{}}{r}_{ij})+\frac{p_{j}}{s_{ij}}+\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}\geq\bm{\hat{}}{\delta}_{ij}\end{subarray}}\frac{p_{j^{\prime}}}{s_{ij^{\prime}}}\Bigg{)}+\frac{p_{j}}{s_{ij}}\sum_{\begin{subarray}{c}j^{\prime}\in
M_{i}(j)\\\
\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}\end{subarray}}w_{j^{\prime}}.$

This value is indeed at most $Q_{ij}$, because if at time
$\bm{\hat{}}{r}_{ij}$ some job $k$ is being processed, it must be that
$\bm{\hat{}}{r}_{ik}\leq\bm{\hat{}}{r}_{ij}$, and thus

$x_{i}(\bm{\hat{}}{r}_{ij})\leq\frac{p_{k}}{s_{ik}}\leq\mu_{1}\frac{p_{k}}{\bm{\hat{}}{s}_{ik}}\leq\mu_{1}\frac{\bm{\hat{}}{r}_{ik}}{\theta}\leq\mu_{1}\frac{\bm{\hat{}}{r}_{ij}}{\theta}.$

The statement then follows by summation of all jobs and the observation that
this contribution only affects jobs that were handled before job $j$. ∎

######  Lemma A.2.

$\sum_{i,t}\bm{\bar{}}{b}_{it}=\frac{\mu}{\kappa}{\textsc{Alg}}$

###### Proof.

Since we assumed that all release dates and processing times in $J$ are
integer multiples of $\kappa$, all all job completions occur at integer
multiples of $\kappa$. Thus, $\sum_{t}\sum_{j\in U_{i}(\kappa\cdot
t)}w_{j}=\frac{1}{\kappa}\sum_{t}\sum_{j\in U_{i}(t)}w_{j}$ for every machine
$i$, and we conclude

$\sum_{i,t}\bm{\bar{}}{b}_{it}=\mu\sum_{i,t}\sum_{j\in U_{i}(\kappa\cdot
t)}w_{j}=\frac{1}{\kappa}\sum_{i,t}\sum_{j\in
U_{i}(t)}w_{j}=\frac{\mu}{\kappa}\cdot{\textsc{Alg}}.$

∎

These two lemmas give the following corollary.

######  Corollary A.3.

$\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}\geq\left(1-\frac{\mu}{\kappa}\right)\cdot{\textsc{Alg}}$.

Second, we show that scaling the crafted duals makes them feasible for (NP-
DLP).

######  Lemma A.4.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}/\lambda$ and
$b_{it}=\bm{\bar{}}{b}_{it}/\lambda$ gives a feasible solution for (NP-DLP)
for a constant $\lambda>0$ that satisfies $\lambda\geq 2\mu(2+\theta)$ and
$\lambda\geq\mu_{1}(\frac{1}{\theta}+\mu_{2}\cdot\kappa)$.

###### Proof.

Since our defined variables are non-negative by definition, it suffices to
show that this assignment satisfies (2). Fix a job $j$, a machine $i$ and a
time $t\geq r_{j}$. We assume that no new job arrives after $j$, since such a
job may only increase $\bm{\bar{}}{b}_{it}$ while $\bm{\bar{}}{a}_{j}$ stays
unchanged. We define a partition of $M_{i}(j)$ into high priority and low
priority jobs with respect to $j$, and into completed and unfinished jobs with
respect to time $\kappa\cdot t$:

  * •

$H_{U}=\\{j^{\prime}\in
M_{i}(j):\bm{\hat{}}{\delta}_{ij^{\prime}}\geq\bm{\hat{}}{\delta}_{ij}\land
C_{j^{\prime}}>\kappa\cdot t\\}$ and $H_{C}=\\{j^{\prime}\in
M_{i}(j):\bm{\hat{}}{\delta}_{ij^{\prime}}\geq\bm{\hat{}}{\delta}_{ij}\land
C_{j^{\prime}}\leq\kappa\cdot t\\}$,

  * •

$L_{U}=\\{j^{\prime}\in
M_{i}(j):\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}\land
C_{j^{\prime}}>\kappa\cdot t\\}$ and $L_{C}=\\{j^{\prime}\in
M_{i}(j):\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}\land
C_{j^{\prime}}\leq\kappa\cdot t\\}$.

We write $H=H_{C}\cup H_{U}$, $L=L_{C}\cup L_{U}$ and
$\delta_{ij}=\frac{w_{j}s_{ij}}{p_{j}}$. Due to the choice of $g(j)$ in the
algorithm, $\bm{\hat{}}{Q}_{g(j)j}\leq\bm{\hat{}}{Q}_{i^{\prime}j}$ for every
machine $i^{\prime}$. Hence, we have
$\bm{\bar{}}{a}_{j}=Q_{g(j)j}\leq\mu_{1}\cdot\bm{\hat{}}{Q}_{g(j)j}\leq\mu_{1}\cdot\bm{\hat{}}{Q}_{ij}$,
and using that,

$\displaystyle\frac{\bm{\bar{}}{a}_{j}\cdot s_{ij}}{\lambda p_{j}}$
$\displaystyle\leq\mu_{1}\frac{\bm{\hat{}}{Q}_{ij}\cdot s_{ij}}{\lambda
p_{j}}$
$\displaystyle=\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\bm{\hat{}}{r}_{ij}+\frac{\bm{\hat{}}{r}_{ij}}{\theta}+\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}+\sum_{j^{\prime}\in
H}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\mu_{1}\frac{s_{ij}w_{j}}{\lambda
p_{j}}(2+\theta)\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\mu\frac{w_{j}}{\lambda}\left(2+\theta\right)+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\frac{w_{j}}{2}+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L}w_{j^{\prime}},$

where the second inequality is due to
$(1+\frac{1}{\theta})\bm{\hat{}}{r}_{ij}\leq(1+\frac{1}{\theta})r_{j}+(1+\theta)\frac{p_{j}}{\bm{\hat{}}{s}_{ij}}$,
which follows from the definition of $\bm{\hat{}}{r}_{ij}$, and the last
inequality requires $\lambda\geq 2\mu(2+\theta)$. Thus, asserting the dual
constraint (2) reduces to proving

$\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L}w_{j^{\prime}}\leq\delta_{ij}t+\frac{\bm{\bar{}}{b}_{it}}{\lambda}.$

To this end, first note that for all $j^{\prime}\in L$ holds

$w_{j^{\prime}}\frac{\bm{\hat{}}{s}_{ij^{\prime}}}{p_{j^{\prime}}}=\bm{\hat{}}{\delta}_{ij^{\prime}}<\bm{\hat{}}{\delta}_{ij}=\frac{w_{j}\bm{\hat{}}{s}_{ij}}{p_{j}}=\frac{\delta_{ij}\bm{\hat{}}{s}_{ij}}{s_{ij}}\Longrightarrow\frac{s_{ij}}{\delta_{ij}\bm{\hat{}}{s}_{ij}}w_{j^{\prime}}\leq\frac{\bm{\hat{}}{s}_{ij^{\prime}}}{p_{j^{\prime}}},$
(3)

and for all $j^{\prime}\in H$

$\delta_{ij}\leq\mu_{2}\cdot\bm{\hat{}}{\delta}_{ij}\leq\mu_{2}\cdot\bm{\hat{}}{\delta}_{ij^{\prime}}=\frac{w_{j^{\prime}}\bm{\hat{}}{s}_{ij^{\prime}}}{p_{j^{\prime}}}\Longrightarrow\delta_{ij}\frac{p_{j}^{\prime}}{\bm{\hat{}}{s}_{ij^{\prime}}}\leq
w_{j^{\prime}}.$ (4)

Using these two inequalities gives

$\displaystyle\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H_{C}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}+\sum_{j^{\prime}\in
H_{U}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L_{C}}w_{j^{\prime}}+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L_{U}}w_{j^{\prime}}$
$\displaystyle=\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H_{C}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}+\frac{s_{ij}}{\delta_{ij}\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L_{C}}w_{j^{\prime}}\right)+\delta_{ij}\frac{\mu_{1}}{\lambda}\sum_{j^{\prime}\in
H_{U}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L_{U}}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\left(1+\frac{1}{\theta}\right)r_{j}+\sum_{j^{\prime}\in
H_{C}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}+\sum_{j^{\prime}\in
L_{C}}\frac{p_{j^{\prime}}}{\bm{\hat{}}{s}_{ij^{\prime}}}\right)+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
H_{U}}w_{j^{\prime}}+\frac{\mu_{1}}{\lambda}\frac{s_{ij}}{\bm{\hat{}}{s}_{ij}}\sum_{j^{\prime}\in
L_{U}}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\frac{r_{j}}{\theta}+\mu_{2}\left(r_{j}+\sum_{j^{\prime}\in
M_{i}(j):\kappa\cdot t\geq
C_{j^{\prime}}}\frac{p_{j^{\prime}}}{s_{ij^{\prime}}}\right)\right)+\frac{\mu_{1}}{\lambda}\mu_{2}\sum_{j^{\prime}\in
M_{i}(j):\kappa\cdot t<C_{j^{\prime}}}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}\frac{\mu_{1}}{\lambda}\left(\frac{t}{\theta}+\mu_{2}\cdot\kappa\cdot
t\right)+\frac{\mu}{\lambda}\sum_{j^{\prime}\in U_{i}(\kappa\cdot
t)}w_{j^{\prime}}$
$\displaystyle\leq\delta_{ij}t+\frac{\bm{\bar{}}{b}_{it}}{\lambda}.$

In the first inequality we use (4) and (3). In order to understand the third
inequality, first recall that $M_{i}(j)$ contains all jobs that are assigned
to machine $i$ but unstarted at time $r_{j}$. Thus, the total processing
duration of these jobs that are completed within time $\kappa\cdot t$ can be
at most $\kappa\cdot t-r_{j}$. The last inequality follows from
$\lambda\geq\mu_{1}(\frac{1}{\theta}+\mu_{2}\cdot\kappa)$ and the definition
of $\bm{\bar{}}{b}_{it}$. ∎

###### Proof of Theorem 2.6.

We set $\kappa=\frac{23}{6}\mu$, $\theta=\frac{2}{3}$ and
$\lambda=\frac{16}{3}\mu^{2}$. Then, weak duality, Corollary A.3 and Lemma A.4
imply

$\displaystyle{\textsc{Opt}}\geq\sum_{j}a_{j}-\sum_{i,t}b_{it}=\frac{1}{\lambda}\left(\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}\right)=\left(\frac{1-\mu/\kappa}{\lambda}\right)\cdot{\textsc{Alg}}.$

Since $\kappa>\mu$ and $\lambda>0$, we conclude that

${\textsc{Alg}}\leq\frac{\frac{16}{3}\cdot\mu^{2}}{1-\frac{6}{23}}\cdot{\textsc{Opt}}=\frac{368}{51}\cdot\mu^{2}\cdot{\textsc{Opt}}.$

∎

###  A.2 Full Analysis of Proportional Fairness with Speed Predictions

This section contains the detailed analysis of PF with speed predictions, and
thus the proof of Theorem 2.7. It is based on the analysis of the speed-aware
PF given in [IKM18].

See 2.7

Fix an instance and PF’s schedule. Let $\kappa\geq 1$ and $0<\lambda<1$ be
constants which we fix later. Recall that $q_{jt}$ denotes the progress of job
$j$ at time $t$. For every $t$, consider the sorted (ascending) list $Z^{t}$
composed of $w_{j}$ copies of $\frac{q_{jt}}{p_{j}}$ for every $j\in U_{t}$.
Note that $Z^{t}$ has length $W_{t}$. We define $\zeta_{t}$ as the value at
the index $\lfloor\lambda W_{t}\rfloor$ in $Z^{t}$.

We first state the KKT conditions with multipliers $\\{\eta_{it}\\}_{i}$ and
$\\{\theta_{jt}\\}_{j\in J(t)}$ of the optimal solution $\\{y_{ijt}\\}_{i,j}$
of ($\text{CP}_{t}$) the algorithm uses at time $t$:

$\displaystyle\frac{\bm{\hat{}}{s}_{ij}w_{j}}{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt}}$
$\displaystyle\leq\theta_{jt}+\eta_{it}\quad\forall t,\forall i,\forall j\in
J(t)$ (5) $\displaystyle
y_{ijt}\left(\frac{\bm{\hat{}}{s}_{ij}w_{j}}{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt}}-(\theta_{jt}+\eta_{it})\right)$
$\displaystyle=0\quad\forall t,\forall i,\forall j\in J(t)$ (6)
$\displaystyle\theta_{jt}\left(\sum_{i}y_{ijt}-1\right)$
$\displaystyle=0\quad\forall t,\forall j\in J(t)$ (7)
$\displaystyle\eta_{it}\left(\sum_{j}y_{ijt}-1\right)$
$\displaystyle=0\quad\forall t,\forall i$ (8)
$\displaystyle\theta_{jt},\eta_{it}$ $\displaystyle\geq 0\quad\forall
t,\forall i,\forall j\in J(t)$ (9)

We have the following dual assignment:

  * •

$\bm{\bar{}}{a}_{j}=\sum_{t^{\prime}=0}^{C_{j}}\bm{\bar{}}{a}_{jt^{\prime}}$,
where
$\bm{\bar{}}{a}_{jt^{\prime}}=w_{j}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$,
for every job $j$,

  * •

$\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\zeta_{t^{\prime}}\eta_{it^{\prime}}$ for every machine $i$ and time $t$,
and

  * •

$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{t^{\prime}=t}^{C_{j}}\zeta_{t^{\prime}}\theta_{jt^{\prime}}$
for every job $j$ and time $t\geq r_{j}$.

The following three lemmas will conclude that the dual objective value of this
assignment is close the algorithm’s objective value, and thus prove 2.8.

######  Lemma A.5.

$\sum_{j}\bm{\bar{}}{a}_{j}\geq\lambda\cdot{\textsc{Alg}}$

###### Proof.

Consider a time $t$ and the list $Z^{t}$. Observe that $\sum_{j\in
U_{t}}\bm{\bar{}}{a}_{jt}$ contains for every job $j$ which satisfies
$\frac{q_{jt}}{p_{j}}\leq\zeta_{t}$ its weight $w_{j}$. By the definitions of
$Z_{t}$ and $\zeta_{t}$, we conclude that this is at least $\lambda W_{t}$,
i.e., $\sum_{j\in U_{t}}\bm{\bar{}}{a}_{jt}\geq\lambda W_{t}$. The statement
then follows by summing over all times $t$. ∎

######  Lemma A.6.

At any time $t$, $\sum_{i}\eta_{it}+\sum_{j\in J(t)}\theta_{jt}\leq W_{t}$.

###### Proof.

At any time $t$ holds

$\displaystyle\sum_{i}\eta_{it}+\sum_{j\in J(t)}\theta_{jt}$
$\displaystyle=\left(\sum_{i}\eta_{it}\sum_{j\in
J(t)}y_{ijt}\right)+\left(\sum_{j\in J(t)}\theta_{jt}\sum_{i}y_{ijt}\right)$
$\displaystyle=\sum_{i}\sum_{j\in J(t)}y_{ijt}(\eta_{it}+\theta_{jt})$
$\displaystyle=\sum_{i}\sum_{j\in
J(t)}y_{ijt}\frac{\bm{\hat{}}{s}_{ij}w_{j}}{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt}}$
$\displaystyle=\sum_{j\in
J(t)}\sum_{i}\bm{\hat{}}{s}_{ij}y_{ijt}\frac{w_{j}}{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt}}=\sum_{j\in
J(t)}w_{j}\leq W_{t}.$

The first equality is due to (7) and (8), and the third equality due to (6). ∎

######  Lemma A.7.

At any time $t$, $\sum_{i}\bm{\bar{}}{b}_{it}+\sum_{j\in J:t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\leq\frac{4}{(1-\lambda)\kappa}W_{t}$.

###### Proof.

Fix a time $t$. Observe that for every $t^{\prime}\geq t$ the definitions of
$Z_{t^{\prime}}$ and $\zeta_{t^{\prime}}$ imply
$(1-\lambda)W_{t^{\prime}}\leq\sum_{j\in
U_{t^{\prime}}}w_{j}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\geq\zeta_{t^{\prime}}\right]$.
Thus,

$\zeta_{t^{\prime}}\cdot(1-\lambda)W_{t^{\prime}}\leq\sum_{j\in
U_{t^{\prime}}}w_{j}\cdot\zeta_{t^{\prime}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\geq\zeta_{t^{\prime}}\right]\leq\sum_{j\in
U_{t^{\prime}}}w_{j}\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\geq\zeta_{t^{\prime}}\right].$
(10)

We define a partition $\\{M_{k}\\}_{k\geq 1}$ of the time interval
$[t,\infty)$ such that the total weight of unfinished jobs at all times during
$M_{k}$ is part of $(\frac{1}{2^{k}}W_{t},\frac{1}{2^{k-1}}W_{t}]$. Fix a
$k\geq 1$. Rearranging (10) and estimating the total weight of unfinished jobs
in a partition against both its upper and lower bound yields

$\displaystyle\sum_{t^{\prime}\in M_{k}}\zeta_{t^{\prime}}$
$\displaystyle\leq\sum_{t^{\prime}\in M_{k}}\frac{1}{1-\lambda}\sum_{j\in
U_{t^{\prime}}}\frac{w_{j}}{W_{t^{\prime}}}\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\geq\zeta_{t^{\prime}}\right]$
$\displaystyle\leq\frac{1}{1-\lambda}\sum_{t^{\prime}\in M_{k}}\sum_{j\in
U_{t^{\prime}}}\frac{w_{j}}{W_{t^{\prime}}}\cdot\frac{q_{jt^{\prime}}}{p_{j}}$
$\displaystyle\leq\frac{2^{k}}{(1-\lambda)W_{t}}\sum_{t^{\prime}\in
M_{k}}\sum_{j\in U_{t^{\prime}}}w_{j}\cdot\frac{q_{jt^{\prime}}}{p_{j}}$
$\displaystyle\leq\frac{2^{k}\cdot W_{t}}{(1-\lambda)W_{t}\cdot
2^{k-1}}=\frac{2}{1-\lambda}.$

The definitions of $\bm{\bar{}}{b}_{it}$ and $\bm{\bar{}}{c}_{jt}$ and Lemma
A.6 imply

$\displaystyle\sum_{i}\bm{\bar{}}{b}_{it}+\sum_{j\in J:t\geq
r_{j}}\bm{\bar{}}{c}_{jt}$
$\displaystyle=\left(\sum_{i}\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\eta_{it^{\prime}}\cdot\zeta_{t^{\prime}}\right)+\left(\sum_{j\in J:t\geq
r_{j}}\frac{1}{\kappa}\sum_{t^{\prime}=t}^{C_{j}}\theta_{jt^{\prime}}\cdot\zeta_{t^{\prime}}\right)$
$\displaystyle=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\zeta_{t^{\prime}}\left(\sum_{i}\eta_{it^{\prime}}+\sum_{j\in
J(t^{\prime})}\theta_{jt^{\prime}}\right)\leq\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\zeta_{t^{\prime}}W_{t^{\prime}}.$

By dividing the time after $t$ into the partition $\\{M_{k}\\}_{k\geq 1}$ and
using our bound on $\sum_{t^{\prime}\in M_{k}}\zeta_{t^{\prime}}$, we conclude
that this is at most

$\displaystyle\frac{1}{\kappa}\sum_{k\geq 1}\sum_{t^{\prime}\in
M_{k}}\zeta_{t^{\prime}}W_{t^{\prime}}\leq\frac{1}{\kappa}\sum_{k\geq
1}\frac{W_{t}}{2^{k-1}}\sum_{t^{\prime}\in
M_{k}}\zeta_{t^{\prime}}\leq\frac{2}{\kappa(1-\lambda)}W_{t}\sum_{k\geq
1}\frac{1}{2^{k-1}}\leq\frac{4}{\kappa(1-\lambda)}W_{t}.$

The last inequality uses a bound on the geometric series. ∎

See 2.8

###### Proof.

Follows directly from Lemmas A.5 and A.7. ∎

See 2.9

###### Proof.

First observe that for every $t$ and $j$ holds

$\sum_{i}\bm{\hat{}}{s}_{ij}y_{ijt}\leq\mu_{1}\sum_{i}s_{ij}y_{ijt}=\mu_{1}\cdot
q_{jt}.$ (11)

Fix a job $j$, a machine $i$ and a time $t\geq r_{j}$.

$\displaystyle\frac{\bm{\bar{}}{a}_{j}s_{ij}}{p_{j}}-w_{j}\cdot\frac{t\cdot
s_{ij}}{p_{j}}$ $\displaystyle\leq
s_{ij}\cdot\sum_{t^{\prime}=t}^{C_{j}}\frac{\bm{\bar{}}{a}_{jt^{\prime}}}{p_{j}}$
$\displaystyle=s_{ij}\cdot\sum_{t^{\prime}=t}^{C_{j}}\frac{w_{j}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
$\displaystyle=s_{ij}\cdot\sum_{t^{\prime}=t}^{C_{j}}\frac{w_{j}}{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt^{\prime}}}\cdot\frac{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt^{\prime}}}{q_{jt^{\prime}}}\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
$\displaystyle\leq\mu_{1}\cdot\mu_{2}\cdot\sum_{t^{\prime}=t}^{C_{j}}\frac{\bm{\hat{}}{s}_{ij}w_{j}}{\sum_{i^{\prime}}\bm{\hat{}}{s}_{i^{\prime}j}y_{i^{\prime}jt^{\prime}}}\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
$\displaystyle\leq\mu\cdot\sum_{t^{\prime}=t}^{C_{j}}\left(\eta_{it^{\prime}}+\theta_{jt^{\prime}}\right)\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
$\displaystyle\leq\mu\cdot\sum_{t^{\prime}=t}^{C_{j}}\left(\eta_{it^{\prime}}+\theta_{jt^{\prime}}\right)\cdot\zeta_{t^{\prime}}$
$\displaystyle\leq\mu\kappa\cdot\frac{1}{\kappa}\left(\sum_{t^{\prime}\geq
t}\eta_{it^{\prime}}\cdot\zeta_{t^{\prime}}\right)+\mu\kappa\cdot\left(\frac{1}{\kappa}\sum_{t^{\prime}=t}^{C_{j}}\theta_{jt^{\prime}}\cdot\zeta_{t^{\prime}}\right)$
$\displaystyle=\mu\kappa\cdot\bm{\bar{}}{b}_{it}+\mu\kappa\cdot\bm{\bar{}}{c}_{jt}.$

The second inequality uses (11) and the third inequality uses (5). Since
$\alpha=\kappa\mu$, this dual assignment indeed satisfies the constraint of
($\text{DLP}_{\alpha}$). ∎

##  Appendix B Details on Round Robin for Speed-Ordered Machines

###  B.1 Missing Details for the Analysis for Unrelated Machines

This section contains missing details for the proof of Theorem 3.6, which we
firstly restate:

See 3.6

######  Proposition B.1.

At any time $t$,
$\sum_{i}\beta_{it}\leq\mathcal{O}(\log(\min\\{n,m\\}))\cdot\lvert
U_{t}\rvert$.

###### Proof.

At any time $t$,

$\sum_{i\in I}\beta_{it}=\sum_{i=1}^{m_{t}}\frac{1}{i}\cdot\lvert
J(t)\rvert\leq\lvert
U_{t}\rvert\sum_{i=1}^{m_{t}}\frac{1}{i}\leq\mathcal{O}(\log(\min\\{n,m\\}))\cdot\lvert
U_{t}\rvert,$

where in the last inequality we use that $m_{t}=\min\\{m,\lvert
J(t)\rvert\\}\leq\min\\{m,n\\}$. ∎

######  Proposition B.2.

At any time $t$, $\sum_{j\in J:r_{j}\geq t}\gamma_{jt}\leq\lvert U_{t}\rvert$.

######  Lemma B.3.

$\sum_{j}\bm{\bar{}}{a}_{j}\geq\frac{1}{2}\cdot{\textsc{Alg}}$.

###### Proof.

Analogous to the proof of Lemma A.5. ∎

######  Lemma B.4.

At any time $t$, $\sum_{i}\bm{\bar{}}{b}_{it}\leq\mathcal{O}(1)\cdot\lvert
U_{t}\rvert$.

###### Proof.

Analogous to the proof of Lemma A.7 when using Proposition B.1 and the fact
that $\kappa=\Theta(\log(\min\\{m,n\\}))$. ∎

######  Lemma B.5.

At any time $t$, $\sum_{j\in J:r_{j}\geq
t}\bm{\bar{}}{c}_{jt}\leq\mathcal{O}(1)\cdot\lvert U_{t}\rvert$.

###### Proof.

Analogous to the proof of Lemma A.7 when using Proposition B.2. ∎

Observe that Lemma B.3, Lemma B.4 and Lemma B.5 imply Lemma 3.7. It remains
the proof of Theorem 3.6:

###### Proof of Theorem 3.6.

Weak duality, Lemma 3.7 and Lemma 3.8 imply

$\displaystyle\kappa\cdot{\textsc{Opt}}$
$\displaystyle\geq{\textsc{Opt}}_{\kappa}\geq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\geq\Omega(1)\cdot{\textsc{Alg}}.$

We conclude the proof by noting that $\kappa=\Theta(\log(\min\\{m,n\\}))$. ∎

###  B.2 Full Analysis of Round Robin for Speed-Ordered Related Machines

######  Theorem B.6.

Algorithm 5 has a competitive ratio of at most 216 for minimizing the total
completion time on speed-ordered related machines.

We prove this theorem using a dual-fitting proof based on
($\text{DLP}_{\alpha}$), where $w_{j}=1$ and $s_{i}=s_{ij}$ for every job $j$
and every machine $i$. Fix an instance and the algorithm’s schedule. For every
time $t$ we write $m_{t}=\min\\{m,\lvert J(t)\rvert\\}$. We define for every
machine $i$ and any time $t$

$\beta_{it}=\frac{s_{i}}{\sum_{\ell=1}^{m_{t}}s_{\ell}}\cdot\lvert
J(t)\rvert\cdot\mathds{1}\left[i\leq\lvert J(t)\rvert\right],$

and $\gamma_{jt}=\mathds{1}\left[j\in J(t)\right]$ for every job $j$ and any
time $t$.

Observe the following bounds when summing up these values:

######  Proposition B.7.

At any time $t$, $\sum_{i}\beta_{it}\leq\lvert U_{t}\rvert$.

######  Proposition B.8.

At any time $t$, $\sum_{j\in J(t)}\gamma_{jt}\leq\lvert U_{t}\rvert$.

Let $\kappa\geq 1$ and $0<\lambda<1$ be constants. For every $t$, consider the
sorted (ascending) list $Z^{t}$ composed of values $\frac{q_{jt}}{p_{j}}$ for
every $j\in U_{t}$. We define $\zeta_{t}$ as the value at the index
$\lfloor\lambda\lvert U_{t}\rvert\rfloor$ in $Z^{t}$. Consider the following
duals:

  * •

$\bm{\bar{}}{a}_{j}=\sum_{t^{\prime}=0}^{C_{j}}\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]$
for every job $j$,

  * •

$\bm{\bar{}}{b}_{it}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\beta_{it^{\prime}}\zeta_{t^{\prime}}$ for every $i$ and $t$, and

  * •

$\bm{\bar{}}{c}_{jt}=\frac{1}{\kappa}\sum_{t^{\prime}\geq
t}\gamma_{jt^{\prime}}\zeta_{t^{\prime}}$ for every $j$ and $t\geq r_{j}$.

######  Lemma B.9.

$\sum_{j}\bm{\bar{}}{a}_{j}\geq\lambda\cdot{\textsc{Alg}}$.

###### Proof.

Analogous to the proof of Lemma A.5. ∎

######  Lemma B.10.

At any time $t$,
$\sum_{i}\bm{\bar{}}{b}_{it}\leq\frac{4}{(1-\lambda)\kappa}\lvert
U_{t}\rvert$.

###### Proof.

Analogous to the proof of Lemma A.7 when using Proposition B.7. ∎

######  Lemma B.11.

At any time $t$, $\sum_{j\in J:r_{j}\geq
t}\bm{\bar{}}{c}_{jt}\leq\frac{4}{(1-\lambda)\kappa}\lvert U_{t}\rvert$.

###### Proof.

Analogous to the proof of Lemma A.7 when using Proposition B.8. ∎

Lemmas B.9, B.10 and B.11 conclude the following bound between Alg and the
objective value of the crafted duals.

######  Lemma B.12.

$(\lambda-\frac{8}{(1-\lambda)\kappa}){\textsc{Alg}}\leq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}$

We finally prove that the crafted duals are feasible under certain conditions.

######  Lemma B.13.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{it}=\bm{\bar{}}{b}_{it}$ and
$c_{jt}=\bm{\bar{}}{c}_{jt}$ is feasible for ($\text{DLP}_{\alpha}$) if
$\alpha=\kappa$ and $s_{i}=s_{ij}$ for all machines $i$ and jobs $j$.

###### Proof.

First observe that the dual assignment is non-negative. Let $i\in I,j\in J$
and $t\geq r_{j}$. Since the rates of Algorithm 5 imply
$q_{jt}=\sum_{\ell=1}^{m_{t}}\frac{s_{\ell}}{\lvert J(t)\rvert}$, we have

$\displaystyle\frac{\bm{\bar{}}{a}_{j}s_{i}}{p_{j}}-\frac{s_{i}\cdot
t}{p_{j}}\leq\sum_{t^{\prime}=t}^{C_{j}}\frac{s_{i}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]=\sum_{t^{\prime}=t}^{C_{j}}\frac{s_{i}}{q_{jt^{\prime}}}\cdot\frac{q_{jt^{\prime}}}{p_{j}}\cdot\mathds{1}\left[\frac{q_{jt^{\prime}}}{p_{j}}\leq\zeta_{t^{\prime}}\right]\leq\sum_{t^{\prime}=t}^{C_{j}}\frac{s_{i}}{\sum_{\ell=1}^{m_{t^{\prime}}}\frac{s_{\ell}}{\lvert
J(t^{\prime})\rvert}}\cdot\zeta_{t^{\prime}}$ (12)

Consider any time $t^{\prime}$ with $t\leq t^{\prime}\leq C_{j}$. If
$i\leq\lvert J(t^{\prime})\rvert$, the definition of $\beta_{it^{\prime}}$
yields

$\frac{s_{i}}{\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell}}\cdot\lvert
J(t^{\prime})\rvert\cdot\zeta_{t^{\prime}}=\beta_{it^{\prime}}\cdot\zeta_{t^{\prime}}.$

Otherwise, $i>\lvert J(t^{\prime})\rvert$, the fact that $s_{1}\geq\ldots\geq
s_{m}$ implies
$\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell}\geq\sum_{\ell=1}^{\lvert
J(t^{\prime})\rvert}s_{\ell}\geq\lvert J(t^{\prime})\rvert\cdot s_{i}$, and
thus

$\frac{s_{i}}{\sum_{\ell=1}^{m_{t^{\prime}}}s_{\ell}}\cdot\lvert
J(t^{\prime})\rvert\cdot\zeta_{t^{\prime}}\leq\frac{\lvert
J(t^{\prime})\rvert}{\lvert
J(t^{\prime})\rvert}\cdot\zeta_{t^{\prime}}=\gamma_{jt^{\prime}}\cdot\zeta_{t^{\prime}},$

because $t^{\prime}\leq C_{j}$. Put together, (12) is at most

$\displaystyle\sum_{t^{\prime}=t}^{C_{j}}\beta_{it^{\prime}}\zeta_{t^{\prime}}+\sum_{t^{\prime}=t}^{C_{j}}\gamma_{jt^{\prime}}\zeta_{t^{\prime}}\leq\kappa(\bm{\bar{}}{b}_{it}+\bm{\bar{}}{c}_{jt}),$

which verifies the dual constraint. ∎

###### Proof of Theorem B.6.

Weak duality, Lemma B.12 and Lemma B.13 imply

$\displaystyle\kappa\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\kappa}\geq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{i,t}\bm{\bar{}}{b}_{it}-\sum_{j,t\geq
r_{j}}\bm{\bar{}}{c}_{jt}\geq\left(\lambda-\frac{8}{(1-\lambda)\kappa}\right)\cdot{\textsc{Alg}}.$

Setting $\kappa=72$ and $\lambda=\frac{2}{3}$ concludes ${\textsc{Alg}}\leq
216\cdot{\textsc{Opt}}$. ∎

##  Appendix C Further Details on Experimental Results

###  C.1 Implementation Details

We implemented the schedulers as separate applications running in _userspace_
, scheduling jobs via Linux _affinity masks_ , which indicate for each process
on which core it may be executed. The schedulers compute a schedule every 2 s
based on the currently active jobs and their (predicted) characteristics. The
schedulers are provided with the process IDs of the tasks in the workload,
potentially along with predictions, and only manage these processes via
affinity masks. Other processes may run on any core, but their load is
negligible.

We use _native_ input set for the _PARSEC-3.0_ jobs. For the _SPLASH-3_ jobs,
we use both the _large_ input set and custom input sizes to study the impact
of different input data (see Figure 1). The _Polybench_ jobs use their
standard hard-coded inputs. We discard jobs that execute for less than 30 s on
a _big_ core to reduce measurement noise, and discard jobs that use more than
512 MB RAM because the _HiKey 970_ board has only 6 GB RAM and Android does
not support swap. Overall, this results in 43 combinations of jobs and input
data, i.e., some jobs are repeated in the workloads.

###  C.2 Simulation Experiments

The experiments on real hardware are slow, hence we can only study a limited
set of workload scenarios. We therefore additionally test many different
scenarios in synthetic experiments in simulation. These synthetic experiments
also model an 8-core processor. We create 20 random workloads with 100
synthetic jobs, whose arrival times are drawn from a Poisson distribution and
with random characteristics: 4 _LITTLE_ cores with speed 1, 4 _big_ cores with
job-dependent speeds from $\mathcal{U}(2,6)$, and
$p_{j}\sim\mathcal{U}(60,600)$. Speed predictions are same as in the hardware
experiments, i.e., $\bm{\hat{}}{s}_{ij}=s_{ij}\cdot y_{ij}$.

Figure 4: Synthetic experiments. The experiments are each repeated 20 times
with different random workloads.

Figure 4 shows the results of the synthetic experiments, including the
fractional schedulers Greedy WSPT and PF. Unlike the real experiments, we are
not restricted to a single workload and instead run 20 different workloads and
plot the average results. Inaccurate speed predictions in Greedy WSPT result
in large idle times, greatly deteriorating the performance. PF performs
similar to or worse than Maximum Density, depending on the system load. The
other algorithms perform similar to the experiments on the real platform,
confirming that the results are not depending on a specific workload.