# Minimalistic Predictions to Schedule Jobs with
Online Precedence Constraints

Alexandra Lassota EPFL, Switzerland, funded by the Swiss National Science
Foundation project _Complexity of Integer Programming_ (207365) Alexander
Lindermayr University of Bremen, Faculty of Mathematics and Computer Science,
Germany<EMAIL_ADDRESS>Nicole Megow 22footnotemark:
2 Jens Schlöter 22footnotemark: 2

###### Abstract

We consider non-clairvoyant scheduling with _online_ precedence constraints,
where an algorithm is oblivious to any job dependencies and learns about a job
only if all of its predecessors have been completed. Given strong
impossibility results in classical competitive analysis, we investigate the
problem in a learning-augmented setting, where an algorithm has access to
predictions without any quality guarantee. We discuss different prediction
models: novel problem-specific models as well as general ones, which have been
proposed in previous works. We present lower bounds and algorithmic upper
bounds for different precedence topologies, and thereby give a structured
overview on which and how additional (possibly erroneous) information helps
for designing better algorithms. Along the way, we also improve bounds on
traditional competitive ratios for existing algorithms.

##  1 Introduction

Cloud computing is a popular approach to outsource heavy computations to
specialized providers [Hay08]. Concepts like Function-as-a-Service (FaaS)
offer users on demand the execution of complex computations in a specific
domain [LRLE17, SBW19]. Such tasks are often decomposed into smaller jobs,
which then depend on each other by passing intermediate results. The structure
of such tasks heavily relies on the users input and internal dependencies
within the users system. It might require diverse jobs to solve different
problems with distinct inputs.

From the providers perspective, the goal is thus to schedule jobs with
different priorities and interdependencies which become known only when
certain jobs are completed and their results can be evaluated. From a more
abstract perspective, we face _online precedence constraint scheduling_ : new
jobs arrive only if certain jobs have been completed but the set of jobs and
their dependencies are unknown to the scheduler. As tasks might have different
priorities, it is a natural objective to minimize the total (average) weighted
completion time of the jobs. We focus on _non-clairvoyant_ schedulers that do
not know a job’s processing requirement in advance [MPT94], and we allow
_preemptive_ schedules, i.e., jobs can be interrupted and resumed later. We
present and analyze (non-)clairvoyant algorithms and prove impossibility
results for this problem.

Competitive analysis is a widely used technique to assess the performance of
online algorithms [BE98]. The _competitive ratio_ of an algorithm is the
maximum ratio over all instances between its objective value and the objective
value of an _offline_ optimal solution. In our setting, an offline optimal
solution is the best schedule that can be computed with complete information
and unbounded running time on the instance. We say that an algorithm is
$\rho$-competitive if its competitive ratio is at most $\rho$.

It is not hard to see that for our problem, we cannot hope for good worst-case
guarantees: consider an instance of $n-1$ initially visible jobs with zero
weight such that exactly one of these jobs triggers at its completion the
arrival of a job with positive weight. Since the initial jobs are
indistinguishable, in the worst-case, any algorithm completes the positive-
weight job last. An offline optimal solution can distinguish the initially
visible jobs and immediately processes the one which triggers the positive-
weight job. This already shows that no deterministic algorithm can have a
better competitive ratio than $\Omega(n)$ for $n$ jobs. Notice that this
strong impossibility result holds even for (seemingly) simple precedence
graphs that consist of a collection of chains. In practice, such topology is
highly relevant as, e.g., a sequential computer program executes a path
(chain) of instructions that upon execution depends on the evaluation of
control flow structures (cf. [All70]).

To overcome such daunting lower bounds, we consider closer-to-real-world
approaches to go beyond worst-case analysis. In particular, we study
augmenting _algorithms with predictions_ [MV20, MV22]. The intuition is that
in many applications, we can learn certain aspects of the uncertainty by
considering historical data such as dependencies between jobs for certain
computations and inputs. While these predictions might not reflect the current
instance, they can contain enough information to design algorithms that break
pessimistic worst-case lower bounds. Besides specifying the type of
information, this requires a measure for a prediction’s quality. This allows
parameterized performance guarantees of algorithms w.r.t. the amount of
information a prediction contains. Important performance indicators are
_consistency_ , that is the competitive ratio for best-possible predictions,
and _robustness_ , that is an upper bound on the competitive ratio for any
prediction.

Despite the immense research interest in learning augmented algorithms
[ALP23], the particular choice of prediction models remains often undiscussed.
In this work, we discuss various models and analyze their strengths and
weaknesses. In particular, we present the first learning-augmented algorithms
for scheduling with (online) precedence constraints. The question driving our
research is:

> _Which particular minimal information is required to achieve reasonable
> performance guarantees for scheduling with online precedence constraints?_

Our starting point is the analysis of the two most common models, _full input_
predictions, c.f. [PSK18, ALT21, ALT22, IKQP21, AGS22, BLMS+22, EdLMS22] and
action predictions, c.f. [ACE+20, BMS20, LMS22, LM22, ELM+22, AGKP22, JM22].
Our main focus is on a hierarchy of refined prediction models based on their
entropy. That is, one can compute a prediction for a weaker model using a
prediction from a stronger one, but not vice versa. We predict quantities
related to the weight of unknown jobs which is in contrast to previous work
which assumes predictions on the jobs’ processing times or machine speeds
(except [CHS22]).

For each prediction model, we analyze its power and limits by providing
efficient algorithms and lower bounds on the best-possible performance
guarantees w.r.t. these models and the topological properties of the
precedence constraints.

###  1.1 Problem Definition and Prediction Models

An instance of our problem is composed of a set $J$ of $n$ jobs and a
precedence graph $G=(J,E)$, which is an acyclic directed graph (DAG). Every
job $j\in J$ has a processing requirement $p_{j}\geq 0$ and a weight
$w_{j}\geq 0$. An edge $(j^{\prime},j)\in E$ indicates that $j$ can only be
started if $j^{\prime}$ has been completed. If there is a directed path from
$j^{\prime}$ to $j$ in $G$, then we say that $j$ is a _successor_ of
$j^{\prime}$ and that $j^{\prime}$ is a _predecessor_ of $j$. If that path
consists of a single edge, we call $j$ and $j^{\prime}$ a _direct_ successor
and predecessor, respectively. For a fixed precedence graph $G$, we denote by
$\omega$ the _width_ of $G$, which is the length of the longest anti-chain in
$G$.

An algorithm can process a job $j$ at a time $t\geq r_{j}$ with a rate
$R_{j}^{t}\geq 0$, which describes the amount of processing the job receives
at time $t$. The completion time $C_{j}$ of a job $j$ is the first time $t$
which satisfies $\sum_{t^{\prime}=0}^{t}R_{j}^{t^{\prime}}\geq p_{j}$. On a
single machine a total rate of $1$ can be processed at any time $t$, thus we
require $\sum_{j\in J}R_{j}^{t}\leq 1$. At any time $t$ in a schedule, let
$F_{t}=\left\\{j\;\mid\;C_{j}>t\text{ and }\forall j^{\prime}\text{ s.t.
}(j^{\prime},j)\in E\colon C_{j^{\prime}}<t\right\\}$ denote the set of
unfinished jobs without unfinished predecessors in $G$. We refer to such jobs
as _front jobs_. In the online setting, a job is revealed to the algorithm
once all predecessors have been completed. The algorithm is completely
oblivious to $G$, and, in particular, it does not know whether a front job has
successors. Thus, at any time $t$ an algorithm only sees jobs $j\in$ $F_{t}$
with weights $w_{j}$ but not their processing times $p_{j}$. Note that the
sets $F_{t}$ heavily depend on an algorithm’s actions. At the start time
$t=0$, an algorithm sees $F_{0}$, and until the completion of the last job, it
does not know the total number of jobs. An algorithm can at any time $t$ only
process front jobs, hence we further require that $R_{j}^{t}=0$ for all $j\in
J\setminus F_{t}$. The objective of our problem is to minimize $\sum_{j\in
J}w_{j}C_{j}$. For a fixed instance, we denote the optimal objective value by
Opt and for a fixed algorithm, we denote its objective value by Alg.

We study different topologies of precedence graphs. In addition to general
DAGs, we consider _in-forests_ resp.  _out-forests_ , where every node has at
most one outgoing resp. incoming edge. Further, we study _chains_ , which is a
precedence graph that is an in-forest and an out-forest simultaneously. If an
in- or out-forest has only one connected component, we refer to it as _in-_
and _out-tree_ , respectively.

Two of the most studied prediction models are: a full input prediction, which
is a prediction on the set of jobs with processing times and weights, and the
complete precedence graph, and an _action prediction_ , which is a prediction
on a full priority order over all jobs predicted to be part of the instance
(_static_) or a prediction on which job to schedule next whenever a machine
idles (_adaptive_).

Both prediction models require a significant amount of information on the
input or an optimal algorithm. This might be unrealistic or costly to obtain
and/or not necessary. We aim for minimalistic extra information and quantify
its power.

The set of front jobs $F_{0}$ does not give sufficient information for
obtaining a competitive ratio better than $\Omega(n)$, as shown above. For a
job $v\in F_{0}$, we define the set $S(v)$ consisting of $v$ and its
successors, and we let $w(S(v)):=\sum_{u\in S(v)}w_{u}$. We consider various
predictions on the set $S(v)$:

  * _Weight predictions:_

Predictions $\bm{\hat{}}{W}_{v}$ on the total weight $w(S(v))$ of each front
job $v\in F_{0}$.

  * _Weight order predictions:_

The _weight order_ $\preceq_{0}$ over $F_{0}$ sorts the jobs $v\in F_{0}$ by
non-increasing $w(S(v))$, i.e., $v\preceq_{0}u$ implies $w(S(v))\geq w(S(u))$.
We assume access to a prediction $\bm{\hat{}}{\preceq}_{0}$ on $\preceq_{0}$.

  * _Average predictions:_

Predictions $\hat{a}_{v}$ on the average weight $a(S(v))=\frac{\sum_{u\in
S(v)}w_{u}}{\sum_{u\in S(v)}p_{u}}$ of each front job $v\in F_{0}$.

For each of these three models, we distinguish _static_ and _adaptive_
predictions. Static predictions refer to predictions only on the initial front
jobs $F_{0}$, and adaptive predictions refer to a setting where we receive
access to a new prediction whenever a job becomes visible.

###  1.2 Our Results

Our results can be separated into two categories. First, we consider the
problem of scheduling with online precedence constraints with access to
additional _reliable_ information. In particular, we consider all the
aforementioned prediction models and design upper and lower bounds for the
online problem enhanced with access to the respective additional information.
We classify the power of the different models when solving the problem on
different topologies.

For the second type of results, we drop the assumption that the additional
information is accurate and turn our pure online results into learning-
augmented algorithms. We define suitable error measures for the different
prediction models to capture the accuracy of the predictions, and give more
fine-grained competitive ratios depending on these measures. We also extend
our algorithms to achieve robustness.

Next, we give an overview of our results for these categories. We state all
results for the single machine setting but show in Appendix D that they extend
to identical parallel machines.

#### Reliable additional information

Table 1 summarizes our results for the pure online setting enhanced with
reliable additional information. Our main results are a $4$-competitive
algorithms for chains and out-forests with weight predictions, and a
$H_{\omega}$-competitive algorithm for out-forests with adaptive weight order
predictions, where $H_{k}$ is the $k$th harmonic number. The results show that
additional information significantly improves the (worst-case) ratio compared
to the setting with no predictions.

Table 1: Summary of bounds on the competitive ratio given reliable information. We denote by $P$ the total processing time and by $H_{k}$ the $k$th harmonic number. Prediction Model | Topology | Bound
---|---|---
Actions | DAG | $\Theta(1)$
Input | DAG | $\Theta(1)$
Adaptive weights | Out-Forests | $\Theta(1)$
Adaptive weights | In-Trees | $\Omega(\sqrt{n})$
Static weights | Out-Trees | $\Omega(n)$
Static weights | Chains | $\Theta(1)$
Adaptive weight order | Out-Forests | $\mathcal{O}(H_{\omega})$
Static weight order | Chains | $\mathcal{O}(H^{2}_{\omega}\sqrt{P})$
Adaptive averages | Chains | $\Omega(\sqrt{n})$
No Prediction | Chains | $\Omega(n)$

Our main non-clairvoyant algorithm, given correct weight predictions, has a
competitive ratio of at most $4$ for online out-forest precedence constraints
on a single machine. This improves even for offline precedence constraints
upon previous best-known bounds of $8$ [Jäg21] and 10 [GGKS19] for this
problem, although these bounds also hold in more general settings. To achieve
this small constant, we generalize the Weighted Round Robin algorithm (WRR)
[MPT94, KC03] for non-clairvoyant scheduling _without_ precedence constraints,
which advances jobs proportional to their weight, to our setting. We handle
each out-tree as a super-job and update its remaining weight when a sub-job
completes. If the out-tree is a chain, this can be done even if only _static_
weight predictions are given. Otherwise, when an out-tree gets divided into
multiple remaining out-trees, the distribution of the remaining weight is
unknown, thus we have to rely on _adaptive_ predictions. Due to the increased
dynamics of gaining partial weight of these super-jobs, the original analysis
of WRR is not applicable. Instead, we use the dual-fitting technique, which
has been previously used for offline precedence constraints [GGKS19]. While
their analysis builds on offline information and is infeasible in our model,
we prove necessary conditions on an algorithm to enable the dual-fitting,
which are fulfilled even in our limited information setting. Surprisingly, we
also show that a more compact linear programming (LP) relaxation, which does
not consider transitive precedences, is sufficient for our result. In
particular, compared to the LP used in [GGKS19], it allows us to craft simple
duals which do not involve gradient-type values of the algorithm’s rates.

In the more restricted model of weight order predictions, WRR cannot be
applied, as the rate computation crucially relies on _precise_ weight values.
We observe, however, that WRR’s rates at the start of an instance have the
same ordering as the known chain order. We show that guessing rates for chains
in a way that respects the ordering compromises only a factor of at most
$H_{\omega}$ in the competitive ratio. If the weight order is adaptive, we
show a competitive ratio of $4\cdot H_{\omega}$. Otherwise, we give a worse
upper bound and evidence that this might be best-possible for this algorithm.

#### Learning-augmentation

We extend our algorithmic results by designing suitable error measures for the
different prediction models and proving error-dependent competitive ratios.
Finally, we show how existing techniques can be used to give these algorithms
a robustness of $\mathcal{O}(\omega)$ at the loss of only a constant factor in
the error-dependent guarantee. Note that a robustness $\mathcal{O}(\omega)$
matches the lower bound for the online problem without access to additional
information.

###  1.3 Further Related Work

Scheduling jobs with precedence constraints to minimize the sum of (weighted)
completion times has been one of the most studied scheduling problems for more
than thirty years. The offline problem is known to be NP-hard, even for a
single machine [Law78, LK78], and on two machines, even when precedence
constraints form chains [DLY91, Tim03]. Several polynomial-time algorithms
based on different linear programming formulations achieve an approximation
ratio of $2$ on a single machine, whereas special cases are even solvable
optimally; we refer to [CS05, AM09] for comprehensive overviews. For
scheduling on $m$ parallel identical machines, the best known approximation
factor is $3-1/m$ [HSSW97].

For scheduling with online precedence constraints, strong and immediate lower
bounds rule out a competitive ratio better than $\Omega(n)$ for the min-sum
objective. Therefore, online scheduling has been mainly studied in a setting
where jobs arrive online but once a job arrives its processing time, weight,
and relation to other (already arrived) jobs is revealed [HSSW97, CPS+96,
BKL21]. Similarly, we are not aware of any previous learning-augmented
algorithm for online precedence constraints and/or weight predictions.
Previous work on minimizing the total completion time focussed on the setting
where jobs either arrive online and/or are clairvoyant [PSK18, IKQP21, LM22,
DIL+22, BDK+22].

##  2 Robustness via Time-Sharing

Before we move to concrete algorithmic results, we quickly argue that any
$\rho$-competitive algorithm for scheduling with online precedence constraints
of width $\omega$ can be extended to a
$\mathcal{O}(\min\\{\rho,\omega\\})$-competitive algorithm. In particular, if
$\rho$ depends on a prediction’s quality, this ensures that this algorithm is
robust against arbitrarily bad predictions.

To this end, consider the algorithm which at any time $t$ shares the machine
equally among all front jobs $F_{t}$, i.e., gives every job $j\in F_{t}$ rate
$R_{j}^{t}=\frac{1}{\lvert F_{t}\rvert}\geq\frac{1}{\omega}$. For a fixed job
$j$, compared to its completion time in a fixed optimal schedule, the
completion time in the algorithm’s schedule can be delayed by at most a factor
of $\omega$. We conclude:

######  Proposition 2.1.

There is an $\omega$-competitive non-clairvoyant single-machine algorithm for
minimizing the total weighted completion time of jobs with online precedence
constraints.

We can now use the _time-sharing technique_ to combine this
$\omega$-competitive algorithm with any other algorithm for scheduling online
precedence constraints while retaining the better competitive ratio of both up
to a factor of $2$.

######  Theorem 2.2 ([PSK18, LM22]).

Given two deterministic algorithms with competitive ratios
$\rho_{\mathcal{A}}$ and $\rho_{\mathcal{B}}$ for minimizing the total
weighted completion time with online precedence constraints on identical
machines, there exists an algorithm for the same problem with a competitive
ratio of at most $2\cdot\min\\{\rho_{\mathcal{A}},\rho_{\mathcal{B}}\\}$.

In [PSK18, LM22] there is an additional monotonicity requirement which we
claim to be unnecessary; see Appendix E.

##  3 Action Predictions

Action predictions give an optimal algorithm. Hence, following accurate
predictions clearly results in an optimal solution. To define an error measure
for erroneous static and adaptive action predictions, let
$\hat{\sigma}:J\to[n]$ be the order in which a fixed static or adaptive action
prediction suggests to process jobs. In case of static action predictions, we
receive the predicted order initially, meaning that it might predict a set of
jobs $\hat{J}$ different to the actual $J$. During the analysis, we can simply
remove the jobs $\hat{J}\setminus J$ from $\hat{\sigma}$ as they do not have
any effect on the schedule for the actual instance. For the jobs in
$J\setminus\hat{J}$, we define the static action prediction algorithm to just
append them to the end of the order $\hat{\sigma}$ once they are revealed.
Thus, we can still treat $\hat{\sigma}$ as a function from $J$ to $[n]$. We
analyse an algorithm which follows a static or adaptive action prediction
using the permutation error introduced in [LM22]. To this end, let
$\sigma:J\to[n]$ be the order of a fixed optimal solution for instance $J$,
and $\mathcal{I}(J,\hat{\sigma})=\\{(j^{\prime},j)\in
J^{2}\mid\sigma(j^{\prime})<\sigma(j)\land\hat{\sigma}(j^{\prime})>\hat{\sigma}(j)\\}$
be the set of inversions between the permutations $\sigma$ and $\hat{\sigma}$.
Applying the analysis of [LM22] yields the following theorem.

######  Theorem 3.1.

Given static or adaptive action predictions, there exists an efficient
$\mathcal{O}(\min\left\\{1+\eta,\omega\right\\})$-competitive non-clairvoyant
algorithm for minimizing the total weighted completion time on a single
machine with online precedence constraints, where
$\eta=\sum_{(j^{\prime},j)\in\mathcal{I}(J,\hat{\sigma})}(w_{j^{\prime}}p_{j}-w_{j}p_{j^{\prime}})$.

##  4 Full Input Predictions

We can use full input predictions to compute static action predictions
$\hat{\sigma}$. In general, computing $\hat{\sigma}$ requires exponential
running time as the problem is NP-hard. For special cases, e.g., chains, there
are efficient algorithms [Law78].

While following $\hat{\sigma}$ allows us to achieve the guarantee of Theorem
3.1, the error $\eta$ does not directly depend on the predicted input but on
an algorithm which computed actions for that input. Thus, we aim at designing
error measures depending directly on the “similarity” between the predicted
and actual instance. As describing the similarity between two graphs is a
notoriously difficult problem on its own, we leave open whether there is a
meaningful error for general topologies. However, we give an error measure for
chains. The key idea of this error is to capture additional cost that any
algorithm pays due to both, _absent predicted_ weights and _unexpected actual_
weights. This is in the same spirit as the universal cover error for graph
problems in [BLMS+22]. Assuming that the predicted and actual instance only
differ in the weights, our error $\Lambda=\Gamma_{u}+\Gamma_{a}$ considers the
optimal objective values $\Gamma_{u}$ and $\Gamma_{a}$ for the problem
instances that use $\\{(w_{j}-\bm{\hat{}}{w}_{j})_{+}\\}_{j}$ and
$\\{(\bm{\hat{}}{w}_{j}-w_{j})_{+}\\}_{j}$ as weights, respectively. Then,
$\Gamma_{u}$ and $\Gamma_{a}$ measure the cost for _unexpected_ and _absent_
weights. In the appendix, we generalize this idea to also capture other
differences of the predicted and actual chains and prove the following
theorem.

######  Theorem 4.1.

Given access to an input prediction, there exists an efficient algorithm for
minimizing the total weighted completion time of unit-size jobs on a single
machine with online chain precedence constraints with a competitive ratio of
at most $\mathcal{O}(\min\left\\{1+\Lambda,\omega\right\\})$, where
$\Lambda=\Gamma_{u}+\Gamma_{a}$.

##  5 Weight Value Predictions

We now switch to more problem-specific prediction models, starting with weight
value predictions. We first prove strong lower bounds for algorithms with
access to static weight predictions on out-trees and adaptive predictions on
in-trees. Then, we give $4$-competitive algorithms for accurate static
predictions on chains, and adaptive weight predictions on out-forest
precedence constraints, and finally extend these results to obtain robust
algorithms with error dependency.

The lower bound for out-trees adds a dummy root $r$ to the pure online lower
bound composed of $\Omega(n)$ zero weight jobs, where exactly one hides a
valuable job. In the static prediction setting we thus only receive a
prediction for $r$, which does not help any algorithm to improve.

######  Observation 5.1.

Any algorithm which has only access to static weight predictions has a
competitive ratio of at least $\Omega(n)$, even if the precedence constraint
graph is an out-tree.

For in-trees and adaptive weight predictions, we prove the following lower
bound.

######  Lemma 5.2.

Any algorithm which has only access to adaptive weight predictions has a
competitive ratio of at least $\Omega(\sqrt{n})$, even for in-tree precedence
constraints.

###### Proof.

Consider an in-tree instance with unit-size jobs and root $r$ of weight $0$.
There are $\sqrt{n}$ chains of length $2$ with leaf weights $0$ and inner
weights $1$ which are connected to $r$. Further, there are $n-2\sqrt{n}-1$
leaves with weight 0, which are connected to a node $v$ with weight $1$, which
itself is a child of $r$. Note that the weight prediction for all potential
front jobs except $r$ is always $1$. Thus, even the adaptive predictions do
not help, and we can assume that the algorithm first processes the children of
$v$, giving a total objective of at least
$\Omega((n-2\sqrt{n}-1)^{2}+(n-2\sqrt{n}-1)\sqrt{n})=\Omega(n\sqrt{n})$, while
processing the other leaves first yields a value of at most
$\mathcal{O}((2\sqrt{n})^{2}+(2\sqrt{n}+n-2\sqrt{n}))=\mathcal{O}(n)$. ∎

###  5.1 Algorithms for Reliable Information

We present algorithms assuming access to _correct_ static or adaptive weight
predictions and prove their competitiveness on online chain and out-forest
precedence constraints using a unified analysis framework. This uses a dual-
fitting argumentation inspired by an analysis of an algorithm for known
precedence constraints [GGKS19]. The framework only requires a condition on
the rates at which an algorithm processes front jobs, hence it is independent
of the considered prediction model. Let $U_{t}$ refer to the set of unfinished
jobs at time $t$, i.e., $U_{t}=\bigcup_{v\in F_{t}}S(v)$. Denote by
$w(J^{\prime})$ the total weight of jobs in a set $J^{\prime}$. We write
$W(t)$ for $w(U_{t})$.

######  Theorem 5.3.

If an algorithm for online out-forest precedence constraints satisfies at
every time $t$ and $j\in F_{t}$ that $w(S(j))\leq\rho\cdot R_{j}^{t}\cdot
W(t)$, where $R_{j}^{t}$ is the processing rate of $j$ at time $t$, it is at
most $4\rho$-competitive for minimizing the total weighted completion time on
a single machine.

We first present algorithms for weight predictions and derive results using
Theorem 5.3, and finally prove the theorem.

#### Static Weight Values for Chains

We give an algorithm for correct static weight predictions. As 5.1 rules out
well-performing algorithms for out-tree precedence constraints with static
weight predictions, we focus on chains. Correct static weight predictions mean
access to the total weight $W_{c}$ of every chain $c$ in the set of chains
$\mathcal{C}$.

Algorithm 1 Weighted Round Robin on Chains

0: Chains $\mathcal{C}$, initial total weight $W_{c}$ for each
$c\in\mathcal{C}$.

1: $t\leftarrow 0$ and $W_{c}(t)\leftarrow W_{c}$ for every $c\in\mathcal{C}$.

2: while $U_{t}\neq\emptyset$ do

3: Process the front job of every chain $c$ at rate
$\frac{W_{c}(t)}{\sum_{c}W_{c}(t)}$

4: $t\leftarrow t+1$

5: If a job $j$ in chain $c$ finished, $W_{c}(t)\leftarrow W_{c}(t)-w_{j}$

6: end while

7: Schedule remaining jobs in an arbitrary order.

Algorithm 1, essentially, executes a classical weighted round robin algorithm
where the rate at which the front job of a chain $c$ is executed at time $t$
is proportional to the total weight of unfinished jobs in that chain,
$W_{c}(t)$. As this definition is infeasible for unfinished chains with
$W_{c}(t)=0$, we process these in an arbitrary order in the end. As they have
no weight, this does not negatively affect the objective.

Despite initially only having access to the weights $W_{c}(t)$ for $t=0$, the
algorithm can compute $W_{c}(t)$ for any $t>0$ by subtracting the weight of
finished jobs of $c$ from the initial $W_{c}$ (cf. Line $5$). Thus,
$W_{c}(t)=w(S(j))$ holds for any time $t$ and every $j\in F_{t}$, where $c$ is
the corresponding chain of job $j$. Further, $W(t)=\sum_{c}W_{c}(t)$. We
conclude that, for any $t$ and $j\in F_{t}$, it holds
$R_{j}^{t}=\frac{w(S(j))}{W(t)}$. Using Theorem 5.3 with $\rho=1$, we derive
the following result:

######  Theorem 5.4.

Given correct weight predictions, Algorithm 1 is a non-clairvoyant
$4$-competitive algorithm for minimizing the total weighted completion time of
jobs with online chain precedence constraints on a single machine.

#### Adaptive Weight Values for Out-Forests

5.1 states that static weight predictions are not sufficient to obtain
$\mathcal{O}(1)$-competitive algorithms for out-forests. The reason is that
we, in contrast to chains, cannot recompute $\bm{\hat{}}{W}_{j}$ whenever a
new front job $j$ appears. For adaptive predictions, however, we do not need
to recompute $\bm{\hat{}}{W}_{j}$, as we simply receive a new prediction.
Thus, we can process every front job $j\in F_{t}$ with rate
$R_{j}^{t}=\frac{\bm{\hat{}}{W}_{j}}{\sum_{j^{\prime}\in
F_{t}}\bm{\hat{}}{W}_{j^{\prime}}}$. For correct predictions, Theorem 5.3
directly implies the following.

######  Theorem 5.5.

Given correct adaptive weight predictions, there exists a non-clairvoyant
$4$-competitive algorithm for minimizing the total weighted completion time of
jobs with online out-forest precedence constraints on a single machine.

#### Full proof of Theorem 5.3

Fix an algorithm satisfying the conditions of Theorem 5.3. Let Alg be the
objective value of the algorithm’s schedule for a fixed instance. We introduce
a linear programming relaxation similar to the one in [GGKS19] for our problem
on a machine running at lower speed $\frac{1}{\alpha}$, for some $\alpha\geq
1$. Let ${\textsc{Opt}}_{\alpha}$ denote the optimal objective value for the
problem with speed $\frac{1}{\alpha}$. As the completion time of every job is
linear in the machine speed, we have
${\textsc{Opt}}_{\alpha}\leq\alpha\cdot{\textsc{Opt}}$. The variable $x_{j,t}$
denotes the fractional assignment of job $j$ at time $t$. The first constraint
ensures that every job receives enough amount of processing to complete, the
second constraint restricts the avaible rate per time to $\frac{1}{\alpha}$,
and the final constraint asserts that no job can be completed before its
predecessors.

min $\displaystyle\sum_{j,t}w_{j}\cdot t\cdot\frac{x_{j,t}}{p_{j}}$
($\text{LP}_{\alpha}$) s.t. $\displaystyle\sum_{t}\frac{x_{j,t}}{p_{j}}\geq 1$
$\displaystyle\forall j$ $\displaystyle\sum_{j}\alpha\cdot x_{j,t}\leq 1$
$\displaystyle\forall t$ $\displaystyle\sum_{s\leq
t}\frac{x_{j,s}}{p_{j}}\geq\sum_{s\leq
t}\frac{x_{j^{\prime},s}}{p_{j^{\prime}}}$ $\displaystyle\quad\forall
t,\forall(j,j^{\prime})\in E$ $\displaystyle x_{j,t}\geq 0$
$\displaystyle\forall j,t$

The dual of ($\text{LP}_{\alpha}$) can be written as follows.

max $\displaystyle\sum_{j}a_{j}-\sum_{t}b_{t}$ ($\text{DLP}_{\alpha}$) s.t.
$\displaystyle\sum_{s\geq t}\left(\sum_{j^{\prime}:(j,j^{\prime})\in
E}c_{s,j\to j^{\prime}}-\sum_{j^{\prime}:(j^{\prime},j)\in
E}c_{s,j^{\prime}\to j}\right)$ $\displaystyle\leq\alpha\cdot b_{t}\cdot
p_{j}-a_{j}+w_{j}\cdot t\;\;\quad\forall j,t$ (1) $\displaystyle
a_{j},b_{t},c_{t,j\to j^{\prime}}\geq 0\quad\qquad\qquad\forall
t,\forall(j,j^{\prime})\in E$

Let $\kappa>1$ be a constant which we fix later. We define a variable
assignment for ($\text{DLP}_{\alpha}$) as follows:
$\bm{\bar{}}{a}_{j}=\sum_{s\geq 0}\bm{\bar{}}{a}_{j,s}$ for every job $j$,
where $\bm{\bar{}}{a}_{j,s}=w_{j}$ if $s\leq C_{j}$ and
$\bm{\bar{}}{a}_{j,s}=0$ otherwise, $\bm{\bar{}}{b}_{t}=\frac{1}{\kappa}\cdot
W(t)$ for every time $t$, and $\bm{\bar{}}{c}_{t,j^{\prime}\to j}=w(S(j))$ if
$j,j^{\prime}\in U_{t}$, and $\bm{\bar{}}{c}_{t,j^{\prime}\to j}=0$ otherwise,
for every time $t$ and edge $(j^{\prime},j)\in E$.

We show in the following that the variables
$(\bm{\bar{}}{a}_{j},\bm{\bar{}}{b}_{t},\bm{\bar{}}{c}_{t,j\to j^{\prime}})$
define a feasible solution for ($\text{DLP}_{\alpha}$) and achieve an
objective value close to Alg. Weak duality then implies Theorem 5.3. First,
consider the objective value.

######  Lemma 5.6.

$\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{t}\bm{\bar{}}{b}_{t}=(1-\frac{1}{\kappa}){\textsc{Alg}}$.

###### Proof.

Note that $\bm{\bar{}}{a}_{j}=w_{j}C_{j}$, and thus
$\sum_{j}\bm{\bar{}}{a}_{j}={\textsc{Alg}}$. Also, since the weight $w_{j}$ of
a job $j$ is contained in $W(t)$ if $t\leq C_{j}$, we conclude
$\sum_{t}\bm{\bar{}}{b}_{t}=\frac{1}{\kappa}{\textsc{Alg}}$. ∎

Second, we show that the duals are feasible for ($\text{DLP}_{\alpha}$).

######  Lemma 5.7.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{t}=\bm{\bar{}}{b}_{t}$ and
$c_{t,j\to j^{\prime}}=\bm{\bar{}}{c}_{t,j\to j^{\prime}}$ is feasible for
($\text{DLP}_{\alpha}$) if $\alpha\geq\kappa\rho$ and
$\frac{w(S(j))}{W(t)}\leq\rho R_{j}^{t}$ for any time $t$ for $j\in F_{t}$ and
the algorithm’s rates $R_{j}^{t}$.

###### Proof.

Since our defined variables are non-negative by definition, it suffices to
show that this assignment satisfies (1). Fix a job $j$ and a time $t\geq 0$.
By observing that $\bm{\bar{}}{a}_{j}-t\cdot w_{j}\leq\sum_{s\geq
t}\bm{\bar{}}{a}_{j,s}$, it suffices to verify

$\sum_{s\geq t}\left(\bm{\bar{}}{a}_{j,s}+\sum_{(j,j^{\prime})\in
E}\bm{\bar{}}{c}_{s,j\to j^{\prime}}-\sum_{(j^{\prime},j)\in
E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}\right)\leq\alpha\bm{\bar{}}{b}_{t}p_{j}.$
(2)

To this end, we consider the terms of the left side for all times $s\geq t$
separately. For any $s$ with $s>C_{j}$, the left side of (2) is zero, because
$\bm{\bar{}}{a}_{j,s}=0$ and $j\notin U_{s}$.

Otherwise, if $s\leq C_{j}$, let $t_{j}^{*}$ be the first point in time after
$t$ when $j$ is available, and let $s\in[0,t_{j}^{*})$. Then, $j\in U_{s}$,
and since each vertex in an out-forest has at most one direct predecessor,
there must be a unique job $j_{1}\in U_{s}$ with $(j_{1},j)\in E$. Thus,
$\bm{\bar{}}{c}_{s,j_{1}\to j}=w(S(j))$ and $\bm{\bar{}}{c}_{s,j\to
j^{\prime}}=w(S(j^{\prime}))$ for all $(j,j^{\prime})\in E$. Observe that in
out-forests, we have $S(j^{\prime})\cap S(j^{\prime\prime})=\emptyset$ for all
$j^{\prime}\neq j^{\prime\prime}$ with $(j,j^{\prime}),(j,j^{\prime\prime})\in
E$. This implies $\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}=w(S(j))-w_{j}$ and $\sum_{(j,j^{\prime})\in
E}\bm{\bar{}}{c}_{s,j\to j^{\prime}}-\sum_{(j_{1},j)\in
E}\bm{\bar{}}{c}_{s,j_{1}\to j}=-w_{j}$. Hence,

$\bm{\bar{}}{a}_{j,s}+\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}-\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}\leq
w_{j}-w_{j}=0.$

Therefore, proving (2) reduces to proving

$\sum_{s=t^{*}_{j}}^{C_{j}}\left(w_{j}+\sum_{(j,j^{\prime})\in
E}\bm{\bar{}}{c}_{s,j\to j^{\prime}}-\sum_{(j^{\prime},j)\in
E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}\right)\leq\alpha\bm{\bar{}}{b}_{t}p_{j}.$
(3)

Now, let $s\in[t_{j}^{*},C_{j})$. There cannot be an unfinished job preceding
$j$, thus $\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}=0$.
Observe that if there is a job $j^{\prime}\in U_{s}$ with $(j,j^{\prime})\in
E$, the fact that $j\in U_{s}$ implies $j^{\prime}\in U_{s}$, and thus
$\bm{\bar{}}{c}_{s,j\to j^{\prime}}=w(S(j^{\prime}))$ by definition. Using
again the fact that the sets $S(j^{\prime})$ are pairwise disjoint for all
direct successors $j^{\prime}$ of $j$, i.e., for all $(j,j^{\prime})\in E$,
this yields $\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}=w(S(j))-w_{j}$, and further gives

$w_{j}+\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}-\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to
j}=w(S(j)).$

Thus, the left side of (3) is equal to $\sum_{s=t^{*}_{j}}^{C_{j}}w(S(j))$.

The facts that $W(t_{1})\geq W(t_{2})$ at any $t_{1}\leq t_{2}$ and that $j$
is processed by $R_{j}^{t^{\prime}}$ units at any time
$t^{\prime}\in[t_{j}^{*},C_{j}]$ combined with the assumption
$\frac{w(S(j))}{W(t)}\leq\rho\cdot R_{j}^{t}$ imply the following:

$\sum_{s=t^{*}_{j}}^{C_{j}}\frac{w(S(j))}{W(t)}\leq\sum_{s=t^{*}_{j}}^{C_{j}}\frac{w(S(j))}{W(s)}\leq\sum_{s=t^{*}_{j}}^{C_{j}}\rho\cdot
R_{j}^{s}\leq\rho\cdot p_{j}.$

Rearranging it, using the definition of $\bm{\bar{}}{b}_{t}$ and
$\alpha\geq\kappa\rho$ gives

$\sum_{s=t^{*}_{j}}^{C_{j}}w(S(j))\leq\rho\cdot p_{j}\cdot
W(t)=\rho\kappa\cdot p_{j}\cdot\bm{\bar{}}{b}_{t}\leq\alpha\cdot
p_{j}\cdot\bm{\bar{}}{b}_{t},$

which implies (3) and thus proves the statement. ∎

###### Proof of Theorem 5.3.

We set $\alpha=\rho\kappa$. Weak LP duality, Lemma 5.7, and Lemma 5.6 imply

${\rho\kappa}\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\rho\kappa}\geq\sum_{j}\bm{\bar{}}{a}_{j}-\sum_{t}\bm{\bar{}}{b}_{t}=\left(1-\frac{1}{\kappa}\right)\cdot{\textsc{Alg}}.$

Choosing $\kappa=2$, we conclude that ${\textsc{Alg}}\leq
4\rho\cdot{\textsc{Opt}}$. ∎

###  5.2 Learning-Augmented Algorithms

In this section, we extend the algorithms presented in Section 5.1 to achieve
a smooth error-dependency in the case of inaccurate predictions, while
preserving constant consistency. Further, we use the time-sharing technique
(cf. Section 2) to ensure a robustness of $\mathcal{O}(\omega)$.

#### Static Weight Predictions for Chains

Here, the main challenges are as follows: we only have access to the
potentially wrong predictions $\bm{\hat{}}{W}_{c}$ on the total chain weight
for all $c\in\mathcal{C}$ and, therefore, we execute Algorithm 1 using
$\bm{\hat{}}{W}_{c}$ instead of $W_{c}$. In particular, the weight of a chain
$c$ might be _underpredicted_ , $\bm{\hat{}}{W}_{c}<W_{c}$, or _overpredicted_
, $\bm{\hat{}}{W}_{c}>W_{c}$. This means that $\sum_{c}\bm{\hat{}}{W}_{c}$ may
not be the accurate total weight of the instance and that the recomputation of
$W_{c}(t)$ in Line $5$ may be inaccurate. In Section B.1, we show how to
encode the error due to underpredicted chains in an instance $\mathcal{C}_{u}$
and the error due to overpredicted chains in an instance $\mathcal{C}_{o}$,
similar to an error-dependency proposed in [BMS20] for online set cover. We
prove the following result:

######  Theorem 5.8.

For minimizing the total weighted completion time of jobs with online chain
precedence constraints on a single machine, there is a non-clairvoyant
algorithm with predicted chain weights with a competitive ratio of at most

$\mathcal{O}(1)\cdot\min\left\\{1+\frac{{\textsc{Opt}}(\mathcal{C}_{o})+\omega\cdot{\textsc{Opt}}(\mathcal{C}_{u})}{{\textsc{Opt}}},\omega\right\\}.$

#### Adaptive Weight Predictions for Out-Forests

To capture the quality of an adaptive prediction, we intuitively need to
measure its quality over the whole execution. To this end, we use the maximal
distortion factor of the weight predictions of every possible front job, which
in fact can be any job in $J$. We prove in Section B.2:

######  Theorem 5.9.

For minimizing the total weighted completion time on a single machine with
online out-forest precedence constraint and adaptive weight predictions, there
is a non-clairvoyant algorithm with a competitive ratio of at most

$\mathcal{O}(1)\cdot\min\left\\{\max_{v\in
J}\frac{\bm{\hat{}}{W}_{v}}{w(S(v))}\cdot\max_{v\in
J}\frac{w(S(v))}{\bm{\hat{}}{W}_{v}},\omega\right\\}.$

##  6 Weight Order Predictions

We consider static and adaptive weight order predictions. As strong lower
bounds hold for in-trees, even for the more powerful adaptive weight
predictions (cf. 5.2), we focus on chains and out-forest precedence
constraints.

Further, we introduce an error measure for wrongly predicted orders. A natural
function on orders is the _largest inversion_ , i.e., the maximum distance
between the position of a front job in an order prediction
$\bm{\hat{}}{\preceq}_{t}$ and the true order $\preceq_{t}$. However, if all
out-trees have almost the same weight, just perturbed by some small constant,
this function indicates a large error for the reverse order, although it will
arguably perform nearly as good as the true order. To mitigate this
overestimation, we first introduce $\epsilon$-approximate inversions.
Formally, for every precision constant $\epsilon>0$, we define

$\mathcal{L}(\epsilon)=\max_{t,j\in F_{t}}\left|\left\\{i\in
F_{t}\bigg{|}\frac{w(S(j))}{1+\epsilon}\geq w(S(i))\land
i\bm{\hat{}}{\preceq}_{t}j\right\\}\right|.$

Note that $\mathcal{L}(\epsilon)\geq 1$ for every $\epsilon>0$, because
$\bm{\hat{}}{\preceq}_{t}$ is reflexive. We define the _$\epsilon$
-approximate largest inversion_ error as
$\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}.$ We show performance guarantees
depending on this error which hold for any $\epsilon>0$. Therefore, we
intuitively get a pareto frontier between the precision $(1+\epsilon)$ and
$\mathcal{L}(\epsilon)$, the largest distance of inversions which are worse
than the precision. A configurable error with such properties has been applied
to other learning-augmented algorithms [APT22, BLMS+22].

###  6.1 Adaptive Weight Order

We introduce Algorithm 2, which exploits access to the adaptive order
$\bm{\hat{}}{\preceq}_{t}$. In a sense, the idea of the algorithm is to
emulate Algorithm 1 for weight predictions. Instead of having access to the
total remaining weight of every out-tree to computing rates, Algorithm 2 uses
$\bm{\hat{}}{\preceq}_{t}$ to approximate the rates. For every front job $j\in
F_{t}$, let $i_{j}$ be the position of $j$ in $\bm{\hat{}}{\preceq}_{t}$.
Recall that $H_{k}$ denotes the $k$th harmonic number.

Algorithm 2 Adaptive weight order algorithm

0: Time $t$, front jobs $F_{t}$, adaptive order $\bm{\hat{}}{\preceq}_{t}$.

1: Process every $j\in F_{t}$ with rate $(H_{\lvert F_{t}\rvert}\cdot
i_{j})^{-1}$, where $i_{j}$ is the position of $j$ in
$\bm{\hat{}}{\preceq}_{t}$.

######  Theorem 6.1.

For any $\epsilon>0$, Algorithm 2 has a competitive ratio of at most
$4H_{\omega}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}$ for minimizing
the total weighted completion time on a single machine with online out-forest
precedence constraints.

###### Proof.

We first observe that the rates of the algorithm are feasible, because
$\sum_{j\in F_{t}}\frac{1}{H_{\lvert F_{t}\rvert}\cdot i_{j}}=\frac{H_{\lvert
F_{t}\rvert}}{H_{\lvert F_{t}\rvert}}=1$.

Fix a time $t$ and an $\epsilon>0$. Assume that
$j_{1}\bm{\hat{}}{\preceq}_{t}\ldots\bm{\hat{}}{\preceq}_{t}j_{\lvert
F_{t}\rvert}$, and fix a front job $j_{i}\in F_{t}$. The algorithm processes
$j_{i}$ at time $t$ with rate $R_{j_{i}}^{t}=(H_{\lvert F_{t}\rvert}\cdot
i)^{-1}\geq(H_{\omega}\cdot i)^{-1}.$ Note that showing
$\frac{w(S(j_{i}))}{W(t)}\leq
H_{\omega}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}\cdot L^{t}_{j_{i}}$
implies the theorem via Theorem 5.3. Assume otherwise, i.e.,
$\frac{w(S(j_{i}))}{W(t)}>\frac{1}{i}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}$.
For the sake of readability, we define $K_{>}=\\{k\in[i-1]\mid
w(S(i_{k}))>\frac{w(S(j_{i}))}{1+\epsilon}\\}$ and $K_{\leq}=\\{k\in[i]\mid
w(S(i_{k}))\leq\frac{w(S(j_{i}))}{1+\epsilon}\\}$. Since in an out-forest the
sets $S(j)$ are pairwise disjoint for all front jobs $j\in F_{t}$,

$\displaystyle 1\geq\sum_{k\in[i]}\frac{w(S(i_{k}))}{W(t)}\geq\sum_{k\in
K_{>}}\frac{w(S(i_{k}))}{W(t)}+\sum_{k\in K_{\leq}}\frac{w(S(i_{k}))}{W(t)}.$

Consider the second sum. First, observe that this sum has at most
$\mathcal{L}(\epsilon)$ many terms, including the one for $j_{i}$, and that
each such term is at most $\frac{w(S(j_{i}))}{W(t)}$. Then, observe that every
term in the first sum is at least $\frac{w(S(j_{i}))}{(1+\epsilon)W(t)}$.
Thus, we can further lower bound the sum of the two sums by

$\displaystyle\frac{1}{1+\epsilon}\sum_{k\in
K_{>}}\frac{w(S(j_{i}))}{W(t)}+\frac{1}{\mathcal{L}(\epsilon)}\sum_{k\in
K_{\leq}}\frac{w(S(j_{i}))}{W(t)}$
$\displaystyle\geq\frac{1}{\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}}\sum_{k\in[i]}\frac{w(S(j_{i}))}{W(t)}>\sum_{k=1}^{i}\frac{1}{i}=1.$

This is a contradiction. ∎

Using this theorem, we conclude the following corollary.

######  Corollary 6.2.

There exists a non-clairvoyant weight-oblivious algorithm for the problem of
minimizing the total weighted completion time of $n$ jobs on a single machine
with a competitive ratio of at most $\mathcal{O}(\log n)$ when given access to
the order of the job’s weights.

###  6.2 Static Weight Order

If we only have access to $\bm{\hat{}}{\preceq}_{0}$, a natural approach would
be to compute the initial rates as used in Algorithm 2 and just not update
them. As 5.1 rules out well-performing algorithms for out-trees, we focus on
chains. Even for chains, we show that this algorithm has a competitive ratio
of at least $\Omega(\omega\cdot H_{\omega})$.

######  Lemma 6.3.

The variant of Algorithm 2 that computes the rates using
$\bm{\hat{}}{\preceq}_{0}$ instead of $\bm{\hat{}}{\preceq}_{t}$ is at least
$\Omega(\omega\cdot H_{\omega})$-competitive, even if
$\bm{\hat{}}{\preceq}_{0}$ equals $\preceq_{0}$.

###### Proof.

Consider an instance with $\omega$ chains, each with a total weight of one.
Then, $\preceq_{0}$ is just an arbitrary order of the chains. Recall that the
algorithm starts processing the chains $c$ with rate $(H_{\omega}\cdot
i_{c})^{-1}$, where $i_{c}$ is the position of $c$ in the order. We define the
first $\omega-1$ chains to have their total weight of one at the very first
job and afterwards only jobs of weight zero. Chain $\omega$, the slowest
chain, has its total weight on the last job. We define the chains $c$ to
contain a total of $d\cdot H_{\omega}\cdot i_{c}$ jobs with unit processing
times, for some common integer $d$. This means that the algorithm finishes all
chains at the same time. The optimal solution value for this instance is
$\omega\cdot(\omega+1)+\omega-1+d\cdot H_{\omega}\cdot\omega$, where
$\omega\cdot(\omega+1)$ is the optimal sum of completion times for the first
$\omega-1$ chains, $d\cdot H_{\omega}\cdot\omega$ is the cost for processing
the last chain, and $\omega-1$ is the cost for delaying the last chains by the
$\omega-1$ time units needed to process the first jobs of the first $\omega-1$
chains. The solution value of the algorithm is at least $d\cdot
H_{\omega}^{2}\cdot\omega^{2}$ as this is the cost for just processing the
last chain. Thus, for large $d$, the competitive ratio tends to
$H_{\omega}\cdot\omega$. ∎

However, the lower bound instance of the lemma requires $\omega$ to be “small”
compared to the number of jobs, in case of unit jobs, or to
$P:=\sum_{j}p_{j}$, otherwise. We exploit this to prove the following theorem
in Appendix C.

######  Theorem 6.4.

For any $\epsilon>0$, Algorithm 2 has a competitive ratio of at most
$\mathcal{O}(H_{\omega}^{2}\sqrt{P}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\})$
when computing rates with $\bm{\hat{}}{\preceq}_{0}$ instead of
$\bm{\hat{}}{\preceq}_{t}$ at any time $t$. For unit jobs, it is
$\mathcal{O}(H_{\omega}^{2}\sqrt{n}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\})$-competitive.

##  7 Average Predictions

Recall that an average predictions give access to predicted values
$\hat{a}_{v}$ on $a(S(v))=(\sum_{u\in S(v)}w_{u})/(\sum_{u\in S(v)}p_{u})$ for
each $v\in F_{t}$. We show the following lower bound for chains with unit
jobs, where average predictions coincide with the average weight of the jobs
in the respective chain. The lower bound exploits that we can append jobs of
weight zero to a chain in order to manipulate the average weight of the chain
until all chains have the same average.

######  Lemma 7.1.

Any algorithm which has only access to correct adaptive average predictions is
at least $\Omega(\sqrt{n})$-competitive even for chain precedence constraints
with unit jobs.

###### Proof.

Consider an instance composed of $\sqrt{n}\in\mathbb{N}$ chains of unit jobs,
where the first two jobs of the first chain have weights 1 resp. $n-\sqrt{n}$,
followed by $n-\sqrt{n}-1$ zero weight jobs. The other $\sqrt{n}-1$ chains are
single jobs with weight $1$. For an algorithm, all chains look identical since
the first jobs have weight $1$ and the average of every chain is equal to $1$.
Therefore, an adversary can ensure that the algorithm processes the first
chain last, giving an objective value of
$\sum^{\sqrt{n}}_{i=1}i+(\sqrt{n}+1)(n-\sqrt{n})=\Omega(n\sqrt{n})$, while a
solution which schedules the heavy weight job initially achieves an objective
value of at most
$1+2(n-\sqrt{n})+\sum^{\sqrt{n}-1}_{i=1}(3+i)=\mathcal{O}(n)$. The adaptivity
of the predictions does not help for this lower bound as the algorithm would
only receive meaningful updates once it finishes the first job of the first
chain, which is too late. ∎

##  8 Final Remarks

We initiated the study of learning-augmented algorithms for scheduling with
online precedence constraints by considering a hierarchy of prediction models
based on their entropy. For several models of the hierarchy, we were able to
show that the predicted information is sufficient to break lower bounds for
algorithms without predictions. We hope that our approach leads to more
discussions on the identification of the “right” prediction model in learning-
augmented algorithm design. As a next research step, we suggest investigating
the missing bounds for our prediction models, e.g., an upper bound for average
predictions.

## References

  * [ACE+20] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon.  Online metric algorithms with untrusted predictions.  In ICML, volume 119 of Proceedings of Machine Learning Research, pages 345–355. PMLR, 2020.
  * [AGKP22] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi.  Online algorithms with multiple predictions.  In ICML, volume 162 of Proceedings of Machine Learning Research, pages 582–598. PMLR, 2022.
  * [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.
  * [All70] Frances E Allen.  Control flow analysis.  ACM Sigplan Notices, 5(7):1–19, 1970.
  * [ALP23] ALPS contributors.  Algorithms with predictions paper-tracker, 2023.
  * [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.
  * [AM09] Christoph Ambühl and Monaldo Mastrolilli.  Single machine precedence constrained scheduling is a vertex cover problem.  Algorithmica, 53(4):488–503, 2009.
  * [APT22] Yossi Azar, Debmalya Panigrahi, and Noam Touitou.  Online graph algorithms with predictions.  In SODA, pages 35–66. SIAM, 2022.
  * [BBEM12] Olivier Beaumont, Nicolas Bonichon, Lionel Eyraud-Dubois, and Loris Marchal.  Minimizing weighted mean completion time for malleable tasks scheduling.  In IPDPS, pages 273–284. IEEE Computer Society, 2012.
  * [BDK+22] Evripidis Bampis, Konstantinos Dogeas, Alexander V. Kononov, Giorgio Lucarelli, and Fanny Pascual.  Scheduling with untrusted predictions.  In IJCAI, pages 4581–4587. ijcai.org, 2022.
  * [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.
  * [BLMS+22] Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, and Michelle Sweering.  A universal error measure for input predictions applied to online graph problems.  In NeurIPS, 2022.
  * [BMS20] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  In NeurIPS, 2020.
  * [CHS22] Woo-Hyung Cho, Shane G. Henderson, and David B. Shmoys.  Scheduling with predictions.  CoRR, abs/2212.10433, 2022.
  * [CPS+96] Soumen Chakrabarti, Cynthia A. Phillips, Andreas S. Schulz, David B. Shmoys, Clifford Stein, and Joel Wein.  Improved scheduling algorithms for minsum criteria.  In ICALP, volume 1099 of Lecture Notes in Computer Science, pages 646–657. Springer, 1996.
  * [CS05] José R. Correa and Andreas S. Schulz.  Single-machine scheduling with precedence constraints.  Math. Oper. Res., 30(4):1005–1021, 2005.
  * [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.
  * [DLY91] Jianzhong Du, Joseph Y.-T. Leung, and Gilbert H. Young.  Scheduling chain-structured tasks to minimize makespan and mean flow time.  Inf. Comput., 92(2):219–236, 1991.
  * [EdLMS22] Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, and Jens Schlöter.  Learning-augmented query policies for minimum spanning tree with uncertainty.  In ESA, volume 244 of LIPIcs, pages 49:1–49:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [ELM+22] Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, and Jens Schlöter.  Robustification of online graph exploration methods.  In AAAI, pages 9732–9740. AAAI Press, 2022.
  * [GGKS19] Naveen Garg, Anupam Gupta, Amit Kumar, and Sahil Singla.  Non-clairvoyant precedence constrained scheduling.  In ICALP, volume 132 of LIPIcs, pages 63:1–63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [Hay08] Brian Hayes.  Cloud computing.  Commun. ACM, 51(7):9–11, 2008.
  * [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.
  * [IKQP21] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.  Non-clairvoyant scheduling with predictions.  In SPAA, pages 285–294. ACM, 2021.
  * [Jäg21] Sven Joachim Jäger.  Approximation in deterministic and stochastic machine scheduling.  PhD thesis, Technical University of Berlin, Germany, 2021.
  * [JM22] Billy Jin and Will Ma.  Online bipartite matching with advice: Tight robustness-consistency tradeoffs for the two-stage model.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [KC03] Jae-Hoon Kim and Kyung-Yong Chwa.  Non-clairvoyant scheduling for weighted flow time.  Inf. Process. Lett., 87(1):31–37, 2003.
  * [Law78] Eugene L. Lawler.  Sequencing jobs to minimize total weighted completion time subject to precedence constraints.  Annals of Discrete Mathematics, 2:75–90, 1978.
  * [LK78] Jan Karel Lenstra and A. H. G. Rinnooy Kan.  Complexity of scheduling under precedence constraints.  Oper. Res., 26(1):22–35, 1978.
  * [LM22] Alexander Lindermayr and Nicole Megow.  Permutation predictions for non-clairvoyant scheduling.  In SPAA, pages 357–368. ACM, 2022.
  * [LMS22] Alexander Lindermayr, Nicole Megow, and Bertrand Simon.  Double coverage with machine-learned advice.  In ITCS, volume 215 of LIPIcs, pages 99:1–99:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [LRLE17] Theo Lynn, Pierangelo Rosati, Arnaud Lejeune, and Vincent C. Emeakaroha.  A preliminary review of enterprise serverless cloud computing (function-as-a-service) platforms.  In CloudCom, pages 162–169. IEEE Computer Society, 2017.
  * [McN59] Robert McNaughton.  Scheduling with deadlines and loss functions.  Management science, 6(1):1–12, 1959.
  * [MPT94] Rajeev Motwani, Steven Phillips, and Eric Torng.  Nonclairvoyant scheduling.  Theoretical computer science, 130(1):17–47, 1994.
  * [MV20] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  In Beyond the Worst-Case Analysis of Algorithms, pages 646–662. Cambridge University Press, 2020.
  * [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.
  * [SBW19] Mohammad Shahrad, Jonathan Balkind, and David Wentzlaff.  Architectural implications of function-as-a-service computing.  In MICRO, pages 1063–1075. ACM, 2019.
  * [Tim03] Vadim G. Timkovsky.  Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity.  Eur. J. Oper. Res., 149(2):355–376, 2003.

##  Appendix A Input Predictions

This section is devoted to the proof of Theorem 4.1.

Let $\bm{\hat{}}{\mathcal{C}}$ denote the set of predicted chains, and let
$\bm{\hat{}}{w}_{j}$ denote the predicted weight of a job $j$ of the instance.
All processing requirements are equal to $1$, and the algorithm is aware of
this. We assume w.l.o.g. that
$\lvert\bm{\hat{}}{\mathcal{C}}\rvert=\lvert\mathcal{C}\rvert$ by adding
chains with zero (predicted) weight, and that predicted and actual chains have
the same identities. That is, there exists exactly one predicted chain
$c_{i}\in\bm{\hat{}}{\mathcal{C}}$ for each actual chain
${\bm{\hat{}}{c}}_{i}\in\mathcal{C}$, which an algorithm can match to each
other.

Our error measure further requires that there exists for every actual job a
predicted counterpart, and vice versa. For a chain $c$ let $|c|$ denote the
number of jobs of chain $c$. We define augmentations of $\mathcal{C}$ and
$\bm{\hat{}}{\mathcal{C}}$ as follows. Let $\mathcal{C}^{\prime}$ be composed
of all jobs of $\mathcal{C}$, and additionally, for every paired chains
$c_{i}\in\mathcal{C}$ and ${\bm{\hat{}}{c}}_{i}\in\bm{\hat{}}{\mathcal{C}}$:

  * •

if $\lvert{\bm{\hat{}}{c}}_{i}\rvert>\lvert c_{i}\rvert$, we add
$\lvert{\bm{\hat{}}{c}}_{i}\rvert-\lvert c_{i}\rvert$ jobs $J_{u}$ with weight
$0$ at the end of $c_{i}$ in $\mathcal{C}^{\prime}$. Note that
${\textsc{Opt}}(\mathcal{C})={\textsc{Opt}}(\mathcal{C}^{\prime})$.

  * •

if $\lvert c_{i}\rvert>\lvert{\bm{\hat{}}{c}}_{i}\rvert$, we add $\lvert
c_{i}\rvert-\lvert{\bm{\hat{}}{c}}_{i}\rvert$ jobs $J_{a}$ with predicted
weight $0$ at the end of ${\bm{\hat{}}{c}}_{i}$ in
$\bm{\hat{}}{\mathcal{C}}^{\prime}$.

Note that this construction ensures
${\textsc{Opt}}(\bm{\hat{}}{\mathcal{C}})={\textsc{Opt}}(\bm{\hat{}}{\mathcal{C}}^{\prime})$.

For the sake of analysis, assume w.l.o.g. that both $\mathcal{C}^{\prime}$ and
$\bm{\hat{}}{\mathcal{C}}^{\prime}$ share the same set of jobs $J^{\prime}$.
Let $n^{\prime}=\lvert J^{\prime}\rvert$. We define
${\textsc{Opt}}(\\{w^{\prime}_{j}\\}_{j})$ as the objective of an optimal
solution for $J^{\prime}$ where a job $j$ has weight $w^{\prime}_{j}$. We
further define

${\textsc{Opt}}(\\{w^{\prime}_{j}\\}_{j},\\{w_{j}\\}_{j})=\max\left\\{\sum_{j\in
J^{\prime}}w^{\prime}_{j}C^{*}_{j}\mid\\{C^{*}_{j}\\}_{j}\text{ is an optimal
schedule for }\\{w_{j}\\}_{j}\right\\}.$

Given two fixed augmented instances $\mathcal{C}^{\prime}$ and
$\bm{\hat{}}{\mathcal{C}}^{\prime}$, we define the input prediction error
$\Lambda=\Gamma_{u}+\Gamma_{a}$:

  * •

a job $j\in J^{\prime}$ has _unexpected actual_ weight if
$w_{j}>\bm{\hat{}}{w}_{j}$. The prediction error due to all unexpected weights
can be expressed as
$\Gamma_{u}={\textsc{Opt}}(\\{\max\\{\bm{\hat{}}{w}_{j},w_{j}\\}-w_{j}\\}_{j},\\{w_{j}\\}_{j})$.

  * •

a job $j\in J^{\prime}$ has _absent predicted_ weight if
$\bm{\hat{}}{w}_{j}>w_{j}$. The prediction error due to all absent weights can
be expressed as
$\Gamma_{a}={\textsc{Opt}}(\\{\max\\{w_{j},\bm{\hat{}}{w}_{j}\\}-\bm{\hat{}}{w}_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$.

See 4.1

Recall that $\mathcal{O}(\omega)$-robustness can be achieved via Propositions
2.1 and 2.2. Thus, we can prove the theorem by deriving an
$\mathcal{O}(1+\Lambda)$-competitive algorithm.

###### Proof.

We analyze the following algorithm:

  1. 1)

Efficiently compute an optimal solution based on $\bm{\hat{}}{\mathcal{C}}$
[Law78]. This yields an non-preemptive schedule for the predicted instance,
i.e., an order of the jobs.

  2. 2)

Follow the computed solution. The following situations might occur:

    1. a)

a chain finishes earlier than expected. In this case, discard the remaining
predicted jobs of this chain in the precomputed schedule.

    2. b)

a chain continues although there are no more jobs in this chain in the
algorithms schedule. In this case, schedule the remaining jobs in an arbitrary
order at the end of the precomputed schedule.

Let Alg denote the objective value of this algorithm. We first observe that
${\textsc{Alg}}\leq{\textsc{Opt}}(\\{w_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$.
To see this, recall that the algorithm first follows an optimal schedule for
jobs $J^{\prime}\setminus J_{u}$ and then schedules all unexpected jobs
$J_{u}$ at the end due to case b). Since jobs $J_{u}$ have predicted weight
$0$ in $\bm{\hat{}}{\mathcal{C}}^{\prime}$, we can assume that an optimal
solution for $\bm{\hat{}}{\mathcal{C}}^{\prime}$ first schedules jobs
$J^{\prime}\setminus J_{u}$ as our algorithm with the same objective value and
makespan as our algorithm, and then schedules jobs $J_{u}$ in any order. Since
${\textsc{Opt}}(\\{w_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$ is an upper
bound on the actual objective for any such order, the inequality follows. It
further holds that

$\displaystyle{\textsc{Opt}}(\\{w_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$
$\displaystyle\leq{\textsc{Opt}}(\\{\max\\{w_{j},\bm{\hat{}}{w}_{j}\\}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$
$\displaystyle={\textsc{Opt}}(\\{\bm{\hat{}}{w}_{j}\\}_{j})+{\textsc{Opt}}(\\{\max\\{w_{j},\bm{\hat{}}{w}_{j}\\}-\bm{\hat{}}{w}_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$
$\displaystyle\leq{\textsc{Opt}}(\\{\bm{\hat{}}{w}_{j}\\}_{j},\\{w_{j}\\}_{j})+{\textsc{Opt}}(\\{\max\\{w_{j},\bm{\hat{}}{w}_{j}\\}-\bm{\hat{}}{w}_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$
$\displaystyle\leq{\textsc{Opt}}(\\{\max\\{\bm{\hat{}}{w}_{j},w_{j}\\}\\}_{j},\\{w_{j}\\}_{j})+{\textsc{Opt}}(\\{\max\\{w_{j},\bm{\hat{}}{w}_{j}\\}-\bm{\hat{}}{w}_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$
$\displaystyle\leq{\textsc{Opt}}(\\{w_{j}\\}_{j})+{\textsc{Opt}}(\\{\max\\{\bm{\hat{}}{w}_{j},w_{j}\\}-w_{j}\\}_{j},\\{w_{j}\\}_{j})+{\textsc{Opt}}(\\{\max\\{w_{j},\bm{\hat{}}{w}_{j}\\}-\bm{\hat{}}{w}_{j}\\}_{j},\\{\bm{\hat{}}{w}_{j}\\}_{j})$
$\displaystyle={\textsc{Opt}}(\\{w_{j}\\}_{j})+\Lambda.$

We finally observe that
${\textsc{Opt}}(\\{w_{j}\\}_{j})={\textsc{Opt}}(\mathcal{C})$, as jobs $J_{a}$
do not influence the objective value of an optimal solution. ∎

##  Appendix B Weight Value Predictions

###  B.1 A Learning-Augmented Algorithm for Chains

We give a formal proof of the following theorem.

See 5.8

In order to give the proof, we first formally define the _predicted instance_
(including $\mathcal{C}_{o}$ and $\mathcal{C}_{u}$).

######  Definition B.1 (predicted instances).

The _predicted instance_ $\bm{\hat{}}{\mathcal{C}}$, the _underpredicted
subinstance_ $\mathcal{C}_{u}$, and the _overpredicted subinstance_
$\mathcal{C}_{o}$ are constructed by considering for every
$c=[j_{1},\ldots,j_{\ell}]\in\mathcal{C}$ the following cases:

  1. (i)

if $\bm{\hat{}}{W}_{c}=W_{c}$, then the chain ${\bm{\hat{}}{c}}=c$ with job
weights $\bm{\hat{}}{w}_{j}=w_{j}$ for all $j\in c$ is added to
$\bm{\hat{}}{\mathcal{C}}$.

  2. (ii)

if $\bm{\hat{}}{W}_{c}<W_{c}$, then the chain
${\bm{\hat{}}{c}}=[j_{1},\ldots,j_{k}]$, where $k$ is the smallest index s.t.
$\bm{\hat{}}{W}_{c}\leq\sum_{i=1}^{k}w_{i}$, with weights
$\bm{\hat{}}{w}_{j_{i}}=w_{j_{i}}$ for all $1\leq i\leq k-1$ and
$\bm{\hat{}}{w}_{j_{k}}=\bm{\hat{}}{W}_{c}-\sum_{i=1}^{k-1}w_{i}$ is added to
$\bm{\hat{}}{\mathcal{C}}$. Additionally, a chain
$c_{u}=[\bot,j_{k+1},\ldots,j_{\ell}]$ with weights
$\bm{\hat{}}{w}_{j_{i}}=w_{j_{i}}$ for all $k+1\leq i\leq\ell$ and
$\bm{\hat{}}{w}_{\bot}=\sum_{i=1}^{k}w_{i}-\bm{\hat{}}{W}_{c}$ is added to
$\mathcal{C}_{u}$, where the processing requirement of $\bot$ is equal to the
total processing requirement of ${\bm{\hat{}}{c}}$.

  3. (iii)

if $\bm{\hat{}}{W}_{c}>W_{c}$, then chain
${\bm{\hat{}}{c}}=[j_{1},\ldots,j_{\ell}]$ with weights
$\bm{\hat{}}{w}_{j_{i}}=w_{j_{i}}$ for all $1\leq i\leq\ell-1$ and
$\bm{\hat{}}{w}_{j_{\ell}}=\bm{\hat{}}{W}_{c}-\sum_{i=1}^{\ell-1}w_{i}$ is
added to $\bm{\hat{}}{\mathcal{C}}$. Additionally, a chain $c_{o}=[\top]$ is
added to $\mathcal{C}_{o}$, where the weight of $\top$ is equal to
$\bm{\hat{}}{W}_{c}-\sum_{i=1}^{\ell}w_{i}$ and its processing requirement is
equal to the total processing requirement of ${\bm{\hat{}}{c}}$.

Finally, $\mathcal{C}_{p}$ is a copy of $\bm{\hat{}}{\mathcal{C}}$ where for
every overpredicted chain
${\bm{\hat{}}{c}}=[j_{1},\ldots,j_{\ell}]\in\bm{\hat{}}{\mathcal{C}}$ the
weight of its last job $j_{\ell}$ is set to $w_{j_{\ell}}$, the weight of the
job in the actual instance. This weight is strictly smaller than the weight
$\bm{\hat{}}{w}_{j_{\ell}}=\bm{\hat{}}{W}_{c}-\sum_{i=1}^{\ell-1}w_{i}$ of the
job in instance $\bm{\hat{}}{\mathcal{C}}$.

Note that for every ${\bm{\hat{}}{c}}\in\bm{\hat{}}{\mathcal{C}}$, we have
$\sum_{j\in{\bm{\hat{}}{c}}}\bm{\hat{}}{w}_{j}=\bm{\hat{}}{W}_{c}$, i.e., the
predicted weights are correct for $\bm{\hat{}}{\mathcal{C}}$. In the
following, we nevertheless call a chain
${\bm{\hat{}}{c}}\in\bm{\hat{}}{\mathcal{C}}$ overpredicted resp.
underpredicted if that is true for its corresponding chain in $\mathcal{C}$.
Since every job $j$ of $\mathcal{C}_{p}$ is also part of $\mathcal{C}$ with
the same processing requirement and a weight of at most $w_{j}$ and the chains
in $\mathcal{C}_{p}$ are prefixes of the chains in $\mathcal{C}$, we conclude:

######  Proposition B.2.

${\textsc{Opt}}(\mathcal{C}_{p})\leq{\textsc{Opt}}(\mathcal{C})$.

We use the algorithm of Proposition 2.1 in combination with the times-haring
of Theorem 2.2 to define Algorithm 3.

Algorithm 3 Learning-augmented WRR on Chains

1: Execute Algorithm 1 with rate $\frac{1}{2}$ using the predicted chain
weights.

2: Execute the algorithm of Proposition 2.1 with rate $\frac{1}{2}$.

######  Lemma B.3.

Algorithm 3 with predicted chain weights achieves an objective value of at
most

$\mathcal{O}(1)\cdot{\textsc{Opt}}(\mathcal{C}_{p})+\mathcal{O}(1)\cdot({\textsc{Opt}}(\mathcal{C}_{o})+\omega\cdot{\textsc{Opt}}(\mathcal{C}_{u})).$

###### Proof.

We first argue that
${\textsc{Opt}}(\bm{\hat{}}{\mathcal{C}})\leq\mathcal{O}(1)\cdot{\textsc{Opt}}(\mathcal{C}_{p})+\mathcal{O}(1)\cdot{\textsc{Opt}}(\mathcal{C}_{o})$.
To this end, consider the instance $\mathcal{C}_{p}\cup\mathcal{C}_{o}$. Every
correctly predicted or underpredicted chain in $\bm{\hat{}}{\mathcal{C}}$ is
contained as an identical copy in $\mathcal{C}_{p}$. For every overpredicted
chain ${\bm{\hat{}}{c}}\in\bm{\hat{}}{\mathcal{C}}$ with weight
$\bm{\hat{}}{W}_{\bm{\hat{}}{c}}$ in $\bm{\hat{}}{\mathcal{C}}$, all jobs of
${\bm{\hat{}}{c}}$ are contained with a total weight of $W_{\bm{\hat{}}{c}}$
in $\mathcal{C}_{p}$ and the remaining weight of
$\bm{\hat{}}{W}_{\bm{\hat{}}{c}}-W_{\bm{\hat{}}{c}}$ is contained in
$\mathcal{C}_{o}$. Additionally, it is ensured by the processing requirement
of the jobs in $\mathcal{C}_{o}$ that their weight can only be gained when
processing at least the total processing requirement of ${\bm{\hat{}}{c}}$.
This implies that the time to gain weight
$\bm{\hat{}}{W}_{\bm{\hat{}}{c}}-W_{\bm{\hat{}}{c}}$ of every overpredicted
chain ${\bm{\hat{}}{c}}\in\bm{\hat{}}{\mathcal{C}}$ in
$\mathcal{C}_{p}\cup\mathcal{C}_{o}$ takes as least as long as in
$\bm{\hat{}}{\mathcal{C}}$, and thus
${\textsc{Opt}}(\bm{\hat{}}{\mathcal{C}})\leq{\textsc{Opt}}(\mathcal{C}_{p}\cup\mathcal{C}_{o})$.
Finally, it is not hard to see that
${\textsc{Opt}}(\mathcal{C}_{p}\cup\mathcal{C}_{o})\leq
2\cdot{\textsc{Opt}}(\mathcal{C}_{p})+2\cdot{\textsc{Opt}}(\mathcal{C}_{o})$
as ${\textsc{Opt}}(\mathcal{C}_{p})$ and ${\textsc{Opt}}(\mathcal{C}_{o})$ can
be executed in parallel by preemptively sharing the machine, yielding the
claimed bound.

We now show that
${\textsc{Alg}}\leq\mathcal{O}(1)\cdot({\textsc{Opt}}(\bm{\hat{}}{\mathcal{C}})+\omega\cdot{\textsc{Opt}}(\mathcal{C}_{u}))$
for Algorithm 3, which implies the statement. First consider the execution of
Algorithm 1 in the first line. We may assume that the algorithm processes the
artificial job added to each overpredicted chain in
$\bm{\hat{}}{\mathcal{C}}$, as it only increases its objective. Further,
Algorithm 1 stops processing an underpredicted chain $c\in\mathcal{C}$ when a
total weight of $\bm{\hat{}}{W}_{c}$ has been completed on $c$ and only
finishes them at the very end of the schedule. This concludes that the total
objective of Algorithm 1 _without_ the weighted completion times of the jobs
processed in Line $7$ is at most
$\mathcal{O}(1)\cdot{\textsc{Opt}}(\bm{\hat{}}{\mathcal{C}})$. But, due to
Proposition 2.1 and line two of the algorithm, we conclude that Algorithm 3
always processes such chains that are only completed in Line $7$ of Algorithm
1 with a rate of at least $\frac{1}{2\omega}$ and, thus, delays the completion
the jobs in these chains by a factor of at most $2\omega$ compared to an
optimal solution. By observing that the total weight of jobs processed in Line
$7$ by Algorithm 1 is exactly equal to the total weight of chains in
$\mathcal{C}_{u}$, and the fact that the jobs in a chain $c\in\mathcal{C}_{u}$
can only be processed after time equal to the total processing requirement of
the corresponding chain in $\bm{\hat{}}{\mathcal{C}}$, we conclude the stated
bound. ∎

###  B.2 Adaptive weight predictions for out-forests

Algorithm 4 Weighted Round Robin on out-forests

0: Out-forest $T$ and adaptive weight predictions.

1: $t\leftarrow 0$

2: while $F_{t}\neq\emptyset$ do

3: Process every $v\in F_{t}$ with rate
$R_{j}^{t}=\frac{\bm{\hat{}}{W}_{j}}{\sum_{i\in F_{t}}\bm{\hat{}}{W}_{i}}$

4: $t\leftarrow t+1$

5: end while

See 5.9

###### Proof.

To prove the theorem, we show that Algorithm 4 is
$\mathcal{O}(\eta)$-competitive for

$\eta=\max_{v\in J}\frac{\bm{\hat{}}{W}_{v}}{W_{v}}\cdot\max_{v\in
J}\frac{W_{v}}{\bm{\hat{}}{W}_{v}}.$

Then, Proposition 2.1 and Theorem 2.2 imply the theorem.

By Theorem 5.3, it suffices to show that $\frac{w(S(j))}{W(t)}\leq\eta\cdot
R_{j}^{t}$ holds for any point in time $t$ during the execution of Algorithm 4
and any $j\in F_{t}$, where $R_{j}^{t}$ is the rate with which the algorithm
processes $j$ at point in time $t$. Consider a fixed point in time $t$ and an
arbitrary $j\in F_{t}$. Then, the algorithm processes $j$ with rate
$R_{j}^{t}=\frac{\bm{\hat{}}{W}_{j}}{\sum_{i\in F_{t}}\bm{\hat{}}{W}_{i}}$ by
definition. We can conclude

$\displaystyle\frac{w(S(j))}{W(t)}=\frac{w(S(j))}{\sum_{i\in F_{t}}w(S(i))}$
$\displaystyle=\frac{\bm{\hat{}}{W}_{j}\cdot\frac{w(S(j))}{\bm{\hat{}}{W}_{j}}}{\sum_{i\in
F_{t}}\bm{\hat{}}{W}_{i}\cdot\frac{w(S(i))}{\bm{\hat{}}{W}_{i}}}$
$\displaystyle\leq\frac{\left(\max_{v\in
J}\frac{w(S(v))}{\bm{\hat{}}{W}_{v}}\right)\cdot\bm{\hat{}}{W}_{j}}{\left(\min_{v\in
J}\frac{w(S(v))}{\bm{\hat{}}{W}_{v}}\right)\cdot\sum_{i\in
F_{t}}\bm{\hat{}}{W}_{i}}$ $\displaystyle=\max_{v\in
J}\frac{\bm{\hat{}}{W}_{v}}{w(S(v))}\cdot\max_{v\in
J}\frac{w(S(v))}{\bm{\hat{}}{W}_{v}}\cdot\frac{\bm{\hat{}}{W}_{j}}{\sum_{i\in
F_{t}}\bm{\hat{}}{W}_{i}}$ $\displaystyle=\eta\cdot R_{j}^{t}.$

∎

##  Appendix C Static Weight Order

See 6.4

###### Proof.

Recall that $P$ denotes the sum over all job processing times in the instance.
For a subset of chains $S$, let ${\textsc{Opt}}(S)$ denote the optimal
objective value for the subinstance induced by $S$. For a single chain $c$,
${\textsc{Opt}}(c)$ is just the cost for processing chain $c$ with rate $1$ on
a single machine. Clearly, ${\textsc{Opt}}(S)\geq\sum_{c\in
S}{\textsc{Opt}}(c)$. Let ${\textsc{Alg}}(S)$ denote the sum of weighted
completion times of the jobs that belong to chains in $S$ in the schedule
computed by the algorithm.

In the first part of the proof, we assume that all chains $c_{i}$ have a total
processing time of at most $\sqrt{P}$. This only decreases the objective value
of Opt. For Alg, we will analyze the additional cost caused by longer chains
afterwards. In a sense, we assume that Alg, for each chain $c$, has to pay all
weight that appears after $\sqrt{P}$ processing times units of the chain two
times: Once artificially after exactly $\sqrt{P}$ time units of the chain have
been processed and once at the point during the processing where the weight
actually appears. This assumption clearly only increases Alg. In the first
part of the proof, we analyze only the artificial cost for such weights and
ignore the actual cost. In the context of our algorithm this is equivalent to
assuming the chains have total processing times of at most $\sqrt{P}$. In the
second part of the proof we will analyze the actual cost for the jobs that
appear after $\sqrt{P}$ time units in their chain.

#### First Part.

Assume
$c_{1}\bm{\hat{}}{\preceq}_{0}c_{2}\bm{\hat{}}{\preceq}_{0}\ldots\bm{\hat{}}{\preceq}_{0}c_{\omega}$.
Therefore, the algorithm processes chain $c_{i}$ with rate $(H_{\omega}\cdot
i)^{-1}$. This directly implies ${\textsc{Alg}}(c_{i})=H_{\omega}\cdot
i\cdot{\textsc{Opt}}(c_{i})$ and, thus,

${\textsc{Alg}}=\sum_{i=1}^{\omega}H_{\omega}\cdot
i\cdot{\textsc{Opt}}(c_{i}).$

Let $\mathcal{C}_{k}=\\{c_{1},\ldots,c_{k}\\}$ for every $k\in[\omega]$. We
first analyze ${\textsc{Alg}}(\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})$. For
the chains in $\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)}$, we get

$\displaystyle{\textsc{Alg}}(\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})$
$\displaystyle=\sum_{i=1}^{3\cdot\mathcal{L}(\epsilon)}H_{\omega}\cdot
i\cdot{\textsc{Opt}}(c_{i})$ $\displaystyle\leq H_{\omega}\cdot
3\cdot\mathcal{L}(\epsilon)\cdot\sum_{i=1}^{3\cdot\mathcal{L}(\epsilon)}{\textsc{Opt}}(c_{i})$
$\displaystyle\leq H_{\omega}\cdot
3\cdot\mathcal{L}(\epsilon)\cdot{\textsc{Opt}},$

meaning that, for $\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)}$, we achieve the
desired competitive ratio.

Next, consider the chains in
$\mathcal{C}\setminus\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)}$, i.e., the
chains $c_{i}$ with $i>3\cdot\mathcal{L}(\epsilon)$. To analyze the cost for
these chains $C_{i}$, we continue by lower bounding ${\textsc{Opt}}(c_{i})$.
To that end, consider ${\textsc{Opt}}(\mathcal{C}_{i})$. The definition of
$\mathcal{L}(\epsilon)$ implies that there are at most $\mathcal{L}(\epsilon)$
chains $c_{j}\in\mathcal{C}_{i}$ with $W_{c_{i}}\geq(1+\epsilon)W_{c_{j}}$.
For all other chains $c_{j}$ in $\mathcal{C}_{i}$, we have
$\frac{W_{c_{i}}}{(1+\epsilon)}<W_{c_{j}}$. Thus, there are
$i-\mathcal{L}(\epsilon)$ chains in $\mathcal{C}_{i}$ with a weight of at
least $\frac{W_{c_{i}}}{(1+\epsilon)}$. Since we consider chains with
$i>3\cdot\mathcal{L}(\epsilon)$, it holds $i-\mathcal{L}(\epsilon)\geq 1$. We
can lower bound ${\textsc{Opt}}(\mathcal{C}_{i})$ by assuming that all such
chains consist only of a single job with weight
$\frac{W_{c_{i}}}{(1+\epsilon)}$ and ignoring the up-to
$\mathcal{L}(\epsilon)$ other chains. These assumptions only decrease
${\textsc{Opt}}(\mathcal{C}_{i})$. Since in this relaxation all jobs have an
equal weight and length, an optimal solution for it processes the jobs in an
arbitrary order, giving

$\displaystyle{\textsc{Opt}}(\mathcal{C}_{i})$
$\displaystyle\geq\sum_{j=1}^{i-\mathcal{L}(\epsilon)}j\cdot\frac{W_{c_{i}}}{1+\epsilon}$
$\displaystyle=\frac{(i-\mathcal{L}(\epsilon)+1)\cdot(i-\mathcal{L}(\epsilon))\cdot
W_{c_{i}}}{2\cdot(1+\epsilon)}$ $\displaystyle=\frac{((i+1)\cdot
i+\mathcal{L}(\epsilon)^{2}-2\cdot
i\cdot\mathcal{L}(\epsilon)-\mathcal{L}(\epsilon))\cdot
W_{c_{i}}}{2\cdot(1+\epsilon)}$ $\displaystyle\geq\frac{(i+1)\cdot i-3\cdot
i\cdot\mathcal{L}(\epsilon)}{2\cdot(1+\epsilon)}\cdot W_{c_{i}}.$

Since we still assume that each chain has a total processing time of at most
$\sqrt{P}$, we can observe ${\textsc{Opt}}(c_{i})\leq\sqrt{P}\cdot W_{c_{i}}$.
This yields:

$\displaystyle\frac{2\cdot(1+\epsilon)}{(i+1)\cdot i-3\cdot
i\cdot\mathcal{L}(\epsilon)}\cdot\sqrt{P}\cdot{\textsc{Opt}}(\mathcal{C}_{i})\geq{\textsc{Opt}}(c_{i}).$

We can therefore conclude

$\displaystyle{\textsc{Alg}}(\mathcal{C}\setminus\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})$
$\displaystyle=\sum_{i=3\cdot\mathcal{L}(\epsilon)+1}^{\omega}H_{\omega}\cdot
i\cdot{\textsc{Opt}}(c_{i})$
$\displaystyle\leq\sum_{i=3\cdot\mathcal{L}(\epsilon)+1}^{\omega}H_{\omega}\cdot\frac{2\cdot(1+\epsilon)}{(i+1)-3\cdot\mathcal{L}(\epsilon)}\cdot\sqrt{P}\cdot{\textsc{Opt}}(\mathcal{C}_{i})$
$\displaystyle\leq 2\cdot(1+\epsilon)\cdot
H_{\omega}\cdot\sqrt{P}\cdot{\textsc{Opt}}\sum_{i=3\cdot\mathcal{L}(\epsilon)+1}^{\omega}\frac{1}{(i+1)-3\cdot\mathcal{L}(\epsilon)}$
$\displaystyle\leq 2\cdot(1+\epsilon)\cdot H_{\omega}\cdot
H_{\omega-3\mathcal{L}(\epsilon)+1}\cdot\sqrt{P}\cdot{\textsc{Opt}}$
$\displaystyle\leq 2\cdot(1+\epsilon)\cdot
H_{\omega}^{2}\cdot\sqrt{P}\cdot{\textsc{Opt}}.$

We can finish the first part of the proof by combining the bounds for
${\textsc{Alg}}(\mathcal{C}\setminus\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})$
and ${\textsc{Alg}}(\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})$:

$\displaystyle{\textsc{Alg}}(\mathcal{C})$
$\displaystyle={\textsc{Alg}}(\mathcal{C}\setminus\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})+{\textsc{Alg}}(\mathcal{C}_{3\cdot\mathcal{L}(\epsilon)})$
$\displaystyle\leq 5\cdot
H_{\omega}^{2}\cdot\sqrt{P}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}\cdot{\textsc{Opt}}.$

#### Second Part.

It remains to analyze the additional cost incurred by chains with a total
processing time of more than $\sqrt{P}$. To that end, consider the set $J_{L}$
of jobs that, in any schedule, cannot be started before $\sqrt{P}$ time units
have past. For a job $j\in J_{L}$, the predecessors of $j$ in the chain of $j$
must have a total processing time of at least $\sqrt{P}$.

Let ${\textsc{Alg}}(J_{L})$ and ${\textsc{Opt}}(J_{L})$ denote the weighted
completion times of the jobs in $J_{L}$ in the optimal solution and the
schedule computed by Alg, respectively. Then,

$\frac{{\textsc{Alg}}(J_{L})}{{\textsc{Opt}}(J_{L})}\leq\frac{\sum_{j\in
J_{L}}P\cdot w_{j}}{\sum_{j\in J_{L}}\sqrt{P}\cdot w_{j}}=\sqrt{P}.$

Thus, the additional cost of the jobs in $J_{L}$ asymptotically does not
worsen the competitive ratio. ∎

##  Appendix D Extension to Parallel Machines

We generalize in this section our main results for weight value and adaptive
weight order predictions (Theorems 5.4, 5.5 and 6.1) to parallel identical
machines. Compared to the single machine, the competitive ratios of these
results only increase additively by $2$. Formally, we consider the scheduling
problem where we are given $m$ parallel identical machines and an algorithm
can again assign at any time $t$ to every front job $j\in F_{t}$ a rate
$R_{j}^{t}\in[0,1]$. Opposed to the single machine model, the rates now have
to satisfy $\sum_{j}R_{j}^{t}\leq m$ at any time $t$. Using McNaughton’s wrap-
around-rule [McN59], we can transform these rates to an actual schedule that
processes any job at any point in time on at most one machine.

We prove the following generic result, which is a generalization of Theorem
5.3.

######  Theorem D.1.

If an algorithm for scheduling weighted jobs with online out-forest precedence
constraints on parallel identical machines satisfies at any time $t$ and for
every $j\in F_{j}$ that

$R_{j}^{t}<1\Longrightarrow m\cdot\frac{w(S(j))}{W(t)}\leq\rho\cdot
R_{j}^{t},$

where $R_{j}^{t}$ denotes the processing rate of $j$ at time $t$, it is at
most $2+4\rho$-competitive for minimizing the total weighted completion time.

We first apply this theorem to derive competitive ratios of algorithms with
weight value and adaptive weight order predictions for parallel identical
machines, and finally prove Theorem D.1.

###  D.1 Static Weight Values for Chains

Algorithm 5 WDEQ on Chains

0: Set of chains $\mathcal{C}$, initial total weight $W_{c}$ of every chain
$c\in\mathcal{C}$.

1: $t\leftarrow 0$

2: $W_{c}(t)\leftarrow W_{c}$ for every chain $c$.

3: while $U_{t}\neq\emptyset$ do

4: $C\leftarrow\\{c_{1},\ldots,c_{k}\\}$

5: $m^{\prime}\leftarrow m$

6: while $\exists c\in C$ such that
$m^{\prime}\cdot\frac{W_{c}(t)}{\sum_{c}W_{c}(t)}\geq 1$ do

7: Process the first job $j\in I_{t}$ in chain $c$ with rate $R_{j}^{t}=1$

8: $C\leftarrow C\setminus\\{c\\},m^{\prime}\leftarrow m^{\prime}-1$

9: end while

10: For every chain $c\in C$, process the first job $j$ by
$R_{j}^{t}=m^{\prime}\cdot\frac{W_{c}(t)}{\sum_{c}W_{c}(t)}$

11: $t\leftarrow t+1$

12: If some job $j$ in chain $c$ finished, set $W_{c}(t)\leftarrow
W_{c}(t)-w_{j}$

13: end while

14: Schedule remaining jobs arbitrarily.

Recall Algorithm 1 for a single machine, which assigns rates proportional to a
chains remaining total weight. These rates fulfill by definition that they can
be scheduled on a single machine, i.e., sum up to at most $1$. On $m$ parallel
identical machines, we intuitively have $m$ times as much processing power
compared to a single machine. A straightforward approach to exploit this
observation would be to scale the single machine rates by a factor of $m$,
i.e., process chain $c$ with rate $m\cdot\frac{W_{c}(t)}{\sum_{c}W_{c}(t)}$.
These rates clearly some up to at most $m$. However, a single chain might
receive a rate more than $1$, which is disallowed. To circumvent this issue,
we cap such rates at $1$. The final algorithm (Algorithm 5) therefore first
identifies chains with large remaining weight and assigns them rate $1$, and
then splits the remaining processing power among the remaining chains. For
non-clairvoyant scheduling of weighted jobs on parallel identical machines
without precedence constraints, this approach is known to be $2$-competitive
[BBEM12].

Using the same observation as for Algorithm 1, we conclude that every job
$j$’s rate, when being less than 1, is at most $m\cdot\frac{w(S(j))}{W(t)}$.
Then, Theorem D.1 implies immediately the following corollary.

######  Corollary D.2.

Algorithm 5 is a non-clairvoyant algorithm for the problem of minimizing the
total weighted completion time on $m$ parallel identical machines with online
chain precedence constraints with a competitive ratio of at most $6$, when
given access to accurate static weight predictions.

###  D.2 Adaptive Weight Values for Out-Forests

In a similar fashion, we can extend the algorithm for adaptive weight values
on out-forests to the parallel machine environment, and thereby generalize
Theorem 5.5. To this end, we consider the algorithm which processes every
front job $j\in F_{t}$ with rate
$R_{j}^{t}=\min\left\\{1,m\frac{\bm{\hat{}}{W}_{j}}{\sum_{j^{\prime}\in
F_{t}}\bm{\hat{}}{W}_{j^{\prime}}}\right\\}$. This immediately implies that if
$R_{j}^{t}<1$, then $R_{j}^{t}=m\frac{\bm{\hat{}}{W}_{j}}{\sum_{j^{\prime}\in
F_{t}}\bm{\hat{}}{W}_{j^{\prime}}}=m\frac{w(S(j))}{W(t)}$ for correct
predictions. We derive the following corollary via Theorem D.1 with $\rho=1$.

######  Corollary D.3.

Given correct weight predictions, there exists a non-clairvoyant
$6$-competitive algorithm for minimizing the total weighted completion time on
$m$ parallel identical machines with online out-forest precedence constraints
.

###  D.3 Adaptive Weight Order for Out-Forests

For adaptive weight order predictions, we essentially use the exact same trick
from the previous section and derive Algorithm 6.

Algorithm 6 Adaptive weight order algorithm for parallel identical machines

0: Time $t$, front jobs $F_{t}$, adaptive order $\bm{\hat{}}{\preceq}_{t}$

Process every $j\in F_{t}$ with rate
$R_{j}^{t}=\min\left\\{1,\frac{m}{H_{\lvert F_{t}\rvert}\cdot
i_{j}}\right\\}$, where $i_{j}$ is the position of $j$ in
$\bm{\hat{}}{\preceq}_{t}$.

Observe that using the proof of Theorem 6.1, we conclude at any time $t$ and
for every $j\in F_{t}$ that if $R_{j}^{t}<1$, then

$m\cdot\frac{w(S(j))}{W(t)}\leq m\cdot
H_{\omega}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}\cdot\frac{1}{H_{\lvert
F_{t}\rvert}\cdot
i_{j}}=H_{\omega}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}\cdot
R_{j}^{t}.$

Using Theorem D.1, we conclude our result for adaptive weight order
predictions.

######  Corollary D.4.

For any $\epsilon>0$, Algorithm 6 has a competitive ratio of at most
$2+4H_{\omega}\cdot\max\\{1+\epsilon,\mathcal{L}(\epsilon)\\}$ for minimizing
the total weighted completion time on $m$ parallel identical machines with
online out-forest precedence constraints.

###  D.4 Proof of Theorem D.1

The proof is by dual-fitting and is inspired by [GGKS19]. Fix an instance, an
algorithm which fulfills the stated property, and this algorithm’s schedule.
We first introduce a linear programming relaxation [GGKS19] for our problem on
parallel identical machines which are running at lower speed
$\frac{1}{\alpha}$, for some $\alpha\geq 1$. By denoting the value of an
optimal solution for the problem with speed $\frac{1}{\alpha}$, we conclude
${\textsc{Opt}}_{\alpha}\leq\alpha\cdot{\textsc{Opt}}$.

min $\displaystyle\sum_{j,t}w_{j}\cdot t\cdot\frac{x_{j,t}}{p_{j}}$
($\text{P-LP}_{\alpha}$) s.t. $\displaystyle\sum_{t}\frac{x_{j,t}}{p_{j}}\geq
1$ $\displaystyle\forall j$ $\displaystyle\sum_{j}\alpha\cdot x_{j,t}\leq m$
$\displaystyle\forall t$ $\displaystyle\sum_{s\leq
t}\frac{x_{j,s}}{p_{j}}\geq\sum_{s\leq
t}\frac{x_{j^{\prime},s}}{p_{j^{\prime}}}$ $\displaystyle\quad\forall
t,(j,j^{\prime})\in E$ $\displaystyle x_{jt}\geq 0$ $\displaystyle\forall j,t$

The dual of ($\text{P-LP}_{\alpha}$) can be written as follows.

max $\displaystyle\sum_{j}a_{j}-m\sum_{t}b_{t}$ ($\text{P-DLP}_{\alpha}$) s.t.
$\displaystyle a_{j}-w_{j}\cdot t+\sum_{s\geq t}\left(\sum_{(j,j^{\prime})\in
E}c_{s,j\to j^{\prime}}-\sum_{(j^{\prime},j)\in E}c_{s,j^{\prime}\to
j}\right)\leq\alpha\cdot b_{t}\cdot p_{j}\qquad$ $\displaystyle\forall j,t$
(4) $\displaystyle a_{j},b_{t},c_{t,j\to j^{\prime}}\geq 0\qquad$
$\displaystyle\forall j,t,(j,j^{\prime})\in E$

On a single machine, we use the dual linear program to compare the algorithm’
objective to the optimal objective at any time. Unfortunately, showing
feasibility of the dual variables which encode the algorithm’s schedule
crucially require to satisfy $m\frac{W_{c_{j}}(t)}{W(t)}\leq\rho\cdot
R_{j}^{t}$ for some $\rho\geq 1$ at _any_ time and for _every_ job $j$.
However, if there is a heavy weight chain, we can only assign it a rate at of
at most $1$. Thus, in general we cannot satisfy this inequality for any
constant $\rho$. To resolve this issue, we instead use a second lower bound
for the optimal objective value, and bound the total objective of the
algorithm incurred by rates equal to $1$ against it. This intuitively explains
the slightly larger competitive ratio compared to the single machine setting.

We say that a job $j\in U_{t}$ _active_ at time $t$ if there exists
$j^{\prime}\in F_{t}$ such that $j\in S(j^{\prime})$ and
$R_{j^{\prime}}^{t}<1$, otherwise it is _inactive_. We remark that $j$ being
active at time $t$ implies $t\leq C_{j}$. For every time $t$ we denote the set
of active jobs by $A_{t}$. Note that $A_{t}\subseteq U_{t}$. Intuitively, we
will use the dual linear program as lower bound for all jobs in $A_{t}$, and
the following lower bound every time a job is inactive. For every job $j$, let
$chain_{j}$ be the total processing time of a chain’s prefix in $G$ until job
$j$ (including $j$). Note that ${\textsc{Opt}}\geq\sum_{j}w_{j}\cdot
chain_{j}$.

Let $\kappa>1$ be a constant which we fix later. We define a dual assignment
of ($\text{P-DLP}_{\alpha}$) based on the algorithm’s schedule:

  * •

$\bm{\bar{}}{a}_{j}=\sum_{s\geq 0}\bm{\bar{}}{a}_{j,s}$, where
$\bm{\bar{}}{a}_{j,s}\begin{cases}w_{j}\text{ if }j\text{ is active at time
}s\\\ 0\text{ otherwise}\end{cases}$ for every job $j$,

  * •

$\bm{\bar{}}{b}_{t}=\frac{1}{m\cdot\kappa}\cdot W(t)$ for every time $t$, and

  * •

$\bm{\bar{}}{c}_{t,j^{\prime}\to j}=\begin{cases}0\quad\text{if }j\notin
A_{t}\text{ or }j^{\prime}\notin A_{t}\\\ W(S(j))\end{cases}$ for every time
$t$ and edge $(j^{\prime},j)\in E$.

######  Lemma D.5.

$\sum_{j}\bm{\bar{}}{a}_{j}-m\sum_{t}\bm{\bar{}}{b}_{t}+\sum_{j}w_{j}\cdot
chain_{j}\geq(1-\frac{1}{\kappa})\cdot{\textsc{Alg}}$.

###### Proof.

Since the weight $w_{j}$ of a job $j$ is contained in $W(t)$ if $t\leq C_{j}$,
we conclude $\sum_{t}\bm{\bar{}}{b}_{t}=\frac{1}{m\cdot\kappa}{\textsc{Alg}}$.
Now consider a job $j$ and a time $t\leq C_{j}$. If $j$ is active at time $t$,
by definition $\bm{\bar{}}{a}_{j,s}=w_{j}$. Otherwise, $j$ or some predecessor
of $j$ is being processed with rate $1$. Hence, we conclude that the number of
times before $C_{j}$ when $j$ is inactive is at most $chain_{j}$. Therefore
$w_{j}C_{j}\leq\bm{\bar{}}{a}_{j}+w_{j}\cdot chain_{j}$ and
${\textsc{Alg}}\leq\sum_{j}\bm{\bar{}}{a}_{j}+\sum_{j}w_{j}\cdot chain_{j}$. ∎

######  Lemma D.6.

Assigning $a_{j}=\bm{\bar{}}{a}_{j}$, $b_{t}=\bm{\bar{}}{b}_{t}$ and
$c_{t,j\to j^{\prime}}=\bm{\bar{}}{c}_{t,j\to j^{\prime}}$ gives a feasible
solution for ($\text{P-DLP}_{\alpha}$) if there exists a $\rho\geq 1$ such
that $\alpha\geq\kappa\cdot\rho$ and the algorithm’s rates satisfy at any time
$t$ for every $j\in F_{t}$

$R_{j}^{t}<1\Longrightarrow m\cdot\frac{W_{c_{j}}(t)}{W(t)}\leq\rho\cdot
R_{j}^{t}.$ (5)

###### Proof.

Since our defined variables are non-negative by definition, it suffices to
show that this assignment satisfies (4). Fix a job $j$ and a time $t\geq 0$.
Let $c$ be $j$’s chain. By observing that $\bm{\bar{}}{a}_{j}-t\cdot
w_{j}\leq\sum_{s\geq t}\bm{\bar{}}{a}_{j,s}$, it suffices to verify

$\sum_{s\geq t}\left(\bm{\bar{}}{a}_{j,s}+\sum_{(j,j^{\prime})\in
E}\bm{\bar{}}{c}_{s,j\to j^{\prime}}-\sum_{(j^{\prime},j)\in
E}\bm{\bar{}}{c}_{s,j^{\prime}\to
j}\right)\leq\alpha\cdot\bm{\bar{}}{b}_{t}\cdot p_{j}.$ (6)

To this end, we consider the terms of the left side for all times $s\geq t$
separately. For any $s$ with $s>C_{j}$, the left side of (6) is zero, because
$\bm{\bar{}}{a}_{j,s}=0$ and $j\notin A_{s}$. Also note that at any time
$s\in[0,C_{j}]$ when $j$ is inactive, the left side of (6) is again zero.
Therefore, we restrict our attention in the following to times where $j$ is
active.

Let $t_{j}^{*}$ be the first point in time after $t$ when $j$ is available,
and let $s\in[0,t_{j}^{*})$ such that $j$ is active at time $s$. Observe that
$j\in A_{s}$ and since each vertex in an out-forest has at most one direct
predecessor, there must be a unique job $j_{1}\in A_{s}$ with $(j_{1},j)\in
E$. Thus $\bm{\bar{}}{c}_{s,j_{1}\to j}=w(S(j))=\sum_{(j^{\prime},j)\in
E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}$ and $\bm{\bar{}}{c}_{s,j\to
j^{\prime}}=w(S(j^{\prime}))$ for every $j^{\prime}$ with $(j,j^{\prime})\in
E$, because $j^{\prime}$ must also be unfinished and active, hence
$j^{\prime}\in A_{s}$. Using the fact that the sets $S(j^{\prime})$ are
pairwise disjoint for all direct successors $j^{\prime}$ of $j$, we conclude
$\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}=w(S(j))-w_{j}$
and, thus,

$\bm{\bar{}}{a}_{j,s}+\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}-\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}\leq
w_{j}-w_{j}=0.$

By defining $T_{j}=\\{t^{*}_{j}\leq s\leq C_{j}\mid j\text{ active at time
}s\\}$, we conclude that proving (6) reduces to proving

$\sum_{s\in T_{j}}\left(w_{j}+\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}-\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to
j}\right)\leq\alpha\cdot\bm{\bar{}}{b}_{t}\cdot p_{j}.$ (7)

Now, let $s\in T_{j}$. There cannot be an unfinished job preceding $j$, thus
$\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to j}=0$. Observe that
if there is a job $j^{\prime}\in A_{s}$ with $(j,j^{\prime})\in E$, the fact
that $j\in A_{s}$ gives $\bm{\bar{}}{c}_{s,j\to j^{\prime}}=w(S(j^{\prime}))$.
By again exploiting the out-forest topology, this yields

$w_{j}+\sum_{(j,j^{\prime})\in E}\bm{\bar{}}{c}_{s,j\to
j^{\prime}}-\sum_{(j^{\prime},j)\in E}\bm{\bar{}}{c}_{s,j^{\prime}\to
j}=w_{j}+\sum_{(j,j^{\prime})\in E}w(S(j^{\prime}))=w(S(j)),$

and hence implies that the left side of (7) is equal to $\sum_{s\in
T_{j}}w(S(j))$.

The facts that $W(t_{1})\geq W(t_{2})$ at any $t_{1}\leq t_{2}$ and that $j$
is processed by $R_{j}^{s}<1$ units at any time $s\in T_{j}$ imply combined
with (5) the following inequality:

$m\cdot\sum_{s\in T_{j}}\frac{w(S(j))}{W(t)}\leq m\cdot\sum_{s\in
T_{j}}\frac{w(S(j))}{W(s)}\leq\sum_{s\in T_{j}}\rho\cdot
R_{j}^{s}\leq\rho\cdot p_{j}.$

Rearranging it, using the definition of $\bm{\bar{}}{b}_{t}$ and the bound on
$\alpha$ gives

$\sum_{s\in T_{j}}w(S(j))\leq\rho\cdot p_{j}\cdot\frac{1}{m}\cdot
W(t)=\rho\cdot\kappa\cdot p_{j}\cdot\bm{\bar{}}{b}_{t}\leq\alpha\cdot
p_{j}\cdot\bm{\bar{}}{b}_{t},$

which implies (7) and thus proves the statement. ∎

###### Proof of Theorem D.1.

We set $\alpha=\kappa\cdot\rho$. The facts that
$\alpha\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\alpha}$ and $\sum_{j}w_{j}\cdot
chain_{j}\leq{\textsc{Opt}}$, weak duality and Lemma D.6 imply

$(1+\alpha)\cdot{\textsc{Opt}}\geq{\textsc{Opt}}_{\alpha}+{\textsc{Opt}}\geq\sum_{j}\bm{\bar{}}{a}_{j}-m\sum_{i,t}\bm{\bar{}}{b}_{t}+\sum_{j}w_{j}\cdot
chain_{j}.$

Using Lemma D.5 concludes

$(1+\alpha)\cdot{\textsc{Opt}}\geq\left(1-\frac{1}{\kappa}\right)\cdot{\textsc{Alg}},$

which, choosing $\kappa=2$, can be rearranged to
${\textsc{Alg}}\leq\left(\frac{1+2\rho}{1-\frac{1}{2}}\right)\cdot{\textsc{Opt}}=\left(2+4\rho\right)\cdot{\textsc{Opt}}$.
∎

##  Appendix E Time-Sharing without Monotonicity

We give a proof of the following theorem. The proofs given in [PSK18, LM22]
require both algorithms to be monotone, that is, for every two instances on
the same set of jobs but with processing requirements
$\\{p^{\prime}_{j}\\}_{j}$ and $\\{p_{j}\\}_{j}$ such that for all jobs holds
$p^{\prime}_{j}\leq p_{j}$, the algorithm’s objective value for
$\\{p^{\prime}_{j}\\}_{j}$ must be less or equal than the algorithm’s
objective value for $\\{p_{j}\\}_{j}$. In contrast, we do _not_ require
monotonicity. This even holds when scheduling jobs on unrelated machines,
where jobs receive a different progress on different machines. The only
requirement on both algorithms is that they are _progress-aware_. That is,
they can track the exact progress jobs have received so far at any point in
time, which is true for most algorithms in almost every model.

######  Theorem E.1.

Given two deterministic progress-aware algorithms $\mathcal{A}$ and
$\mathcal{B}$ with competitive ratios $\rho_{\mathcal{A}}$ and
$\rho_{\mathcal{B}}$ for minimizing the total weighted completion time with
online precedence constraints, there exists an algorithm for the same problem
with a competitive ratio of at most
$2\cdot\min\\{\rho_{\mathcal{A}},\rho_{\mathcal{B}}\\}$.

###### Proof.

We consider the algorithm which simulates each of both algorithms
$\mathcal{A}$ and $\mathcal{B}$ with a rate equal to $\frac{1}{2}$ on the same
set of jobs, i.e., in every time step it executes algorithm $\mathcal{A}$ in
the first half of the timestep, and algorithm $\mathcal{B}$ in the second
half. Additionally, it keeps track of how much each algorithm advances every
job. For any job $j$, both algorithms ignore the progress in the processing of
$j$ made by the other algorithm. In particular, if $\mathcal{A}$ finishes job
$j$, then $\mathcal{B}$ still simulates the processing of $j$ until the total
time spend by $\mathcal{B}$ on the (partially simulated) processing of $j$
equals $p_{j}$ (and vice versa if $\mathcal{B}$ finishes a job before
$\mathcal{A}$). We assume that an algorithm only can start successors of a job
$j$ once the (partially simulated) processing time spend _by the algorithm_ on
$j$ is at least $p_{j}$. We remark that his requires that the main algorithm
is able to manipulate the input for the sub-algorithms $\mathcal{A}$ and
$\mathcal{B}$. This ensures that the simulated completion times
$\tilde{C}^{\mathcal{A}}_{j}$, $\tilde{C}^{\mathcal{B}}_{j}$ for both
algorithms of every job $j$ are exactly doubled compared to the completion
times $C^{\mathcal{A}}_{j}$, $C^{\mathcal{B}}_{j}$ of $j$ in independent
schedules of both algorithms, i.e., $\tilde{C}^{\mathcal{A}}_{j}=2\cdot
C^{\mathcal{A}}_{j}$ and $\tilde{C}^{\mathcal{B}}_{j}=2\cdot
C^{\mathcal{B}}_{j}$. In the actual combined schedule, job $j$ clearly
completed not later than
$\min\\{\tilde{C}^{\mathcal{A}}_{j},\tilde{C}^{\mathcal{B}}_{j}\\}=2\cdot\min\\{C^{\mathcal{A}}_{j},C^{\mathcal{B}}_{j}\\}$,
implying the stated bound on its competitive ratio. ∎

We finally note that this argument also works when the share each of both
algorithms receives is parameterized by some $\lambda\in[0,1]$.