<figure><img src="image_1.png" /></figure>

HAL
open science

# Robust Online Coflow Scheduling from Predictions

Olivier Brun, Balakrishna Prabhu, Aminata Sangho

► To cite this version:

Olivier Brun, Balakrishna Prabhu, Aminata Sangho. Robust Online Coflow Scheduling from Predictions. 2026. [hal-05483454](https://hal.science/hal-05483454v1)

HAL Id: hal-05483454

https://laas.hal.science/hal-05483454v1

Preprint submitted on 29 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC0 1.0 - Universal - International License
# Robust Online Coflow Scheduling from Predictions

Olivier Brun

Balakrishna J. Prabhu

Aminata Sangho *

January 29, 2026

## Abstract

In this paper, we introduce an online scheduling framework for minimizing the total weighted average completion time of coflows, in scenarios where both flow sizes and release times are unknown. Instead of relying on exact flow sizes, the framework leverages potentially inaccurate predictions. At each decision point, it selects a subset of coflows by solving a Minimum Unscheduled Weight Problem (MUWP), and then applies a variant of the Sincronia algorithm—adapted to operate directly on the predicted sizes. We prove that the proposed approach achieves provably strong competitive guarantees, and extensive simulations demonstrate that it outperforms baseline methods both on average and in worst-case instances.

## 1 Introduction

Along with the emergence of Big Data frameworks like MapReduce, Hadoop, and Spark [13, 34], cloud computing has spurred the widespread use of massively parallel algorithms on huge datasets. In between consecutive computing stages, these parallel algorithms generate massive data transfers in datacenter networks, which can account for up to 50% of total job execution times [11].

While the scheduling of parallel tasks is a fairly mature research area, the scheduling of data flows in datacenter networks has only received attention since 2012 with the seminal work of Chowdhury and Stoica in which the coflow concept was introduced [9]. A coflow is a networking abstraction that represents a collection of related, parallel data flows that occur together

*All the authors are with LAAS-CNRS, University of Toulouse, CNRS, INSA, 31400 Toulouse, France.
E-mails: {brun, balakrishna.prabhu, aminata.sangho}@laas.fr.
between two consecutive stages of a parallel application. The Coflow Completion Time (CCT) is the time it takes for the slowest flow in the collection to finish, and coflow scheduling aims at minimizing the average CCT of concurrent coflows. The coflow scheduling problem has been considered either as an offline optimization problem, in which coflows have known release dates, and as an online optimization problem, where coflows arrive over time at unknown instants.

In the present work, we consider both the offline and online coflow scheduling problems in a setting in which unreliable predictions on flow sizes are revealed to the scheduler upon coflow arrivals. This is in contrast to the traditional settings considered in the literature: the clairvoyant one, where upon a coflow's arrival, the exact volume, source, and destination of every constituent flow are revealed to the scheduler, and the non-clairvoyant, where only the number of flows and their endpoints are revealed, while flow volumes remain unknown. The setting considered in our work can be interpreted as an intermediate one in which exact flow sizes remain uncertain but nevertheless predictions bring some information on the values that they can take. We do not focus on how predictions are obtained. They could for instance be obtained from historical execution data using machine learning algorithms, or may be obtained with flow sampling techniques. The key point is that they are assumed to be unreliable. The core research question investigated in the paper is therefore how to effectively leverage these imperfect predictions for robust coflow scheduling.

## 1.1 Contributions

We consider the offline as well as online scheduling problem for the coflows with the objective of minimizing average CCT when only predictions on the flow volumes are available. The predictions are assumed to lie in the interval $[\mu_{min}x, \mu_{max}x]$, with $x$ being the actual value. The quantity $\nu := \mu_{max}/\mu_{min}$ can be seen as a measure of uncertainty on flow sizes with $\nu = 1$ corresponding to perfect predictions.

Our main contributions are for the online scheduling problem for which we propose an algorithm based on the Select and Permute (SP) algorithm [19] which is one of the main references for constructing online coflow scheduling algorithms from offline ones [2, 28]. We first correct a small error in the competitive ratio of SP (see Theorem 2). It was claimed in [19] that there exists an online coflow scheduling algorithm with a competitive ratio of 12. We shall show that this ratio is in fact 20. As a consequence of this error, a minor modification of the SP algorithm is required for coflow scheduling.
We remark that a similar error also appears in [2, 28] in which incorrect
competitive ratios have been claimed for their online algorithm that is based
on SP.

The online algorithm we propose, which we call SPPred, runs the cor-
rected SP on the predicted values. For this, the scheduling and execution
intervals of SP have to be appropriately increased so as to ensure that coflows
scheduled in an interval are able to finish within that interval. We first give
the competitive ratio of SPPred in terms of v (see Theorem 4) in a general
setting. We then provide an online algorithm with a competitive ratio of
4v(4 + v). This ratio is consistent in that we recover the competitive ratio
of 20 when the predictions match the true values, that is v = 1.

For the offline scheduling problem (which is also an integral part of the
permute step of SP), we first show that the CCT of offline Sincronia [2]
is at most min(4ν², ∑ₖ wₖ/minₖwₖ) of the optimal value. Here wₖ is the
weight of coflow k. This upper bound is consistent since it coincides with
that of Sincronia when there is no error in the predictions. Further, it is
robust since the approximation ratio is bounded even when ν → ∞. Note
that the results for the offline problem first appeared without proofs in [6].
We provide all the proofs of these results (see Theorem 3) as well as new
simulation results.

Finally, we provide results from numerical experiments that show that,
in practice, both SPPred and Sincronia on predictions have an average
performance that remains close to that obtained when these algorithms are
fed with true values of the flow sizes.

1.2 Related Work

Since the introduction of the coflow concept by Chowdhury and Stoica [9],
several coflow scheduling algorithms have been proposed [32]. The problem
can be viewed as a concurrent open-shop (COS) scheduling problem, but with
coupled resources as transmitting a flow requires capacity on both the input
and output ports. Most studies have focused on minimizing the average
CCT in the clairvoyant case, that is, assuming complete information on the
coflows. Even under this simplifying assumption, the problem is known to
be NP-hard [12] and inapproximable below a factor of 2 [29]. The offline
minimisation of the average CCT can be formulated as an integer linear
problem (ILP) [22], but this approach does not scale well. Research has
therefore focused on approximation algorithms and heuristics [2, 3, 33, 31].

One of the first clairvoyant schedulers for minimizing the average CCT
was Varys [12], which is still a basic reference today as it introduced many
key concepts. Varys schedules coflows iteratively by considering at each
stage the bottleneck port (given the remaining coflows to be scheduled), and
choosing the coflow with the least volume on that port. The rate allocation
to the flows of the chosen coflow is calculated so that they all terminate
simultaneously. Another popular scheduler is Sincronia, a 4-approximation
algorithm which was proposed by Agarwal et al. in [2] and provided the best
known approximation ratio until very recently [28]. Sincronia is presented
in details in Section 3.2.

While the above discussion focus on offline coflow scheduling, Khuller
et al. proposed in [19] a framework called Select and Permute (SP), which
provides guarantees in an online setting using offline approximation algo-
rithms. The SP framework was leveraged in many subsequent works on
coflow scheduling, and we also do so. With Sincronia, it was argued to
lead to a 12-approximation for online Coflow Scheduling. We shall see that
the correct competitive ratio is 20.

Although algorithms such as Varys or Sincronia provide fairly efficient
solutions to the coflow scheduling problem, they require a *priori* informa-
tion about the coflows, which is difficult to obtain in practice. Existing
non-clairvoyant solutions such as Aalo [10] generalize the Least Attained
Service (LAS) scheduling discipline to solve this problem (see also [35, 14]).
However, they fail to identify the flows transmitted on bottleneck ports
which result in a poor rate allocation. The Fai algorithm [21] attempts to
solve this problem. Another very relevant work is [5] in which Bhimaraju et
al. propose the BlindFlow algorithm for non-clairvoyant coflow scheduling.
This algorithm, which generalizes the round robin (RR) scheduling disci-
pline, is shown to be 8 *p*-approximate, where *p* is the maximum number of
flows that any coflow can have.

To the extent of our knowledge, the present paper is the first one to
present performance guarantees in a setting in which the actual flow sizes are
unknown, but unreliable predictions on them are available. The improve-
ment of online algorithms via ML predictions is a recent line of research
which has attracted a lot of studies in the last few years, in particular for
online scheduling, see e.g. [25, 24, 8, 4]. Though coflow scheduling signif-
icantly differs from the more traditional scheduling problems addressed in
these references, our work is inspired by them, and in particular [25, 16].

In the context of coflow scheduling, an interesting alternative to ML
predictions was proposed in [17, 18]. The focus of these paper is on getting
reliable estimates of coflow sizes by transmitting a small sample of flows,
rather than deriving performance guarantees for the scheduling algorithms.
In contrast, our work assumes that predictions are known (we do not need
them to come from ML) and uses bounds on the predictions to give perfor-
mance guarantees on the scheduling algorithms. In that respect their work
is complementary to ours: the estimates/predictions from their sampling
techniques can be used as inputs in our algorithms.

Finally, it should be pointed out that the present work is a follow-up of
[6], which focused on the offline setting with predictions. For completeness,
we recall in Section 5 the main results in [6], as well as the proofs of these
results. Some new simulation results for the offline setting are also presented
in Section 7.3. We emphasize however that the main focus of the present
paper is on online scheduling from predictions for which a novel scheduling
scheme is proposed.

1.3 Organization

The remainder of the paper is organized as follows. Section 2 introduces the main notations and presents the formulation of the coflow scheduling problem, while Section 3 provides all the required background material. Section 4 presents our first contribution: the corrected competitive ratio of the SP algorithm proposed by Khuller et al. in [19]. Section 5 is devoted to offline coflow scheduling with predictions. Section 6 presents our main contribution: an online scheduling framework for the realistic setting where neither flow sizes nor release times are known, but only imperfect predictions are available. Section 7 reports numerical results evaluating the performance of our approach. Finally, Section 8 concludes the paper and outlines directions for future research.

2 Problem Statement and main results

We consider a version of the coflow scheduling problem in which unreliable
predictions on the flow sizes are revealed to the coflow scheduler instead
of the actual values. The datacenter network is modeled as a non-blocking
switch with *m* input ports and *m* output ports which all have unit capacity,
that is, at most one unit of data can be transferred through any port at a
time. Moreover, a port can be allocated to at most one flow at a time, that
is, its capacity cannot be shared between two or more flows in a given time
slot. We denote by $\mathcal{L} = \{1, \dots, 2m\}$ the set of ports.

We assume a fixed time horizon, and let $C = \{1, 2, \dots, n\}$ be the set of coflows arriving in this time frame. Each coflow $k$ consists of a collection of flows $F_k = \{1, 2, \dots, n_k\}$, where each flow $j$ is characterized by its input port $s_{k,j}$, its output port $t_{k,j}$, and an unknown volume $v_{k,j} \in \mathbb{N}^*$ which represents
the number of data units that must be transferred between the input and output ports. Moreover, it is assumed that coflow $k$ arrives at time $r_k$ in the system and has weight $w_k$. The objective is to design an online coflow scheduling algorithm that minimizes the weighted coflow completion time (CCT)

$$ \sum_{k \in C} w_k C_k, \qquad (1) $$

where $C_k$ is the completion time of coflow $k \in C$.

Let us first consider an offline optimal scheduler which would know the release times $r_k$ ahead of time, as well as the actual flow sizes $v_{k,j}$. Defining the decision variable $x_{k,j}^t$ as 1 if flow $j$ of coflow $k$ is transmitted at time $t$, and 0 otherwise, the optimization problem solved by the offline optimal scheduler is as follows

$$ \text{Minimize} \quad \sum_{k \in C} w_k C_k \qquad (\text{C-OPT}) $$

s.t.

$$ \sum_{t=1}^{T} x_{k,j}^{t} = v_{k,j}, \quad j \in F_k, k \in C, \qquad (2) $$

$$ C_k \geq t x_{k,j}^t, \quad t = 1, \dots, T, j \in F_k, k \in C, \qquad (3) $$

$$ \sum_{k \in C} \sum_{j \in F_{\ell,k}} x_{k,j}^t \leq 1, \quad t = 1, \dots, T, \ell \in \mathcal{L}, \qquad (4) $$

$$ x_{k,j}^t = 0, \quad t < r_k, j \in F_k, k \in C, \qquad (5) $$

$$ x_{k,j}^t \in \{0,1\}, \quad t = 1, \dots, T, j \in F_k, k \in C, \qquad (6) $$

where $T$ is a sufficiently large constant and $F_{\ell,k}$ represents the set of flows of coflow $k$ that use port $\ell$, either as input port or as output port. Constraints (2) and (3) together ensure that all flows of coflow $k$ are completed by time $C_k$. Constraint (4) is a capacity constraint imposing that at most one flow is transmitted on any port at a time. Clearly, a clairvoyant offline optimal scheduler exploits extra information that is not available to a non-clairvoyant offline or online scheduler and the optimal value of Problem (C-OPT) is a lower bound on the weighted CCT that it can achieve.

Here, we consider a version of this coflow scheduling problem in which only predictions on the actual volumes of coflows are given. More precisely, we assume that when a coflow $k$ arrives, the scheduler receives predicted
flow sizes $\hat{v}_{k,j} \in \mathbb{N}^*$. Although the exact values $v_{k,j}$ remain unknown, they are bounded within a known prediction accuracy range:

$$ \frac{\hat{v}_{k,j}}{\mu_{\max}} \le v_{k,j} \le \frac{\hat{v}_{k,j}}{\mu_{\min}}, \qquad (7) $$

where $\mu_{\min}$ and $\mu_{\max}$ are known constants. In the following, we denote by $\nu$ the ratio $\mu_{max}/\mu_{min}$. This quantity measures the uncertainty on the actual flow sizes, with perfect predictions corresponding to the minimum value $\nu = 1$ and terrible predictions obtained for $\nu \to \infty$. We shall devise robust coflow scheduling algorithms for two different settings:

* the offline setting in which we assume that all coflow are present in the system at time 0,

* the online setting in which coflows arrive over time and neither their release times nor their actual flow sizes are known in advance.

For both settings, we obtain bounds on the performance of the proposed algorithms which depend on the uncertainty $\nu$.

Our algorithm for the offline setting is based on Sincronia<fnref n="1" /> [2] while the online one is based on SP [19]. We briefly describe<fnref n="2" /> SP here since our first contribution corrects its statement for coflow scheduling. SP proceeds by epochs. In every epoch it executes two steps: select and permute. In the select step, a subset of coflows is chosen from ones that have been released but have not yet completed by this epoch. The subset is selected using an $(\alpha, \beta)$-approximation algorithm for Minimum Unscheduled Weight Problem (MUWP) (see Section 3.3 for precise definitions). In the permute step, the selected subset is executed using an offline scheduling algorithm that has an approximation ratio of $\gamma$ for weighted CCT.

Let $W = \sum_k w_k$ be the total weights of the coflows.

**Theorem 1** (Theorem 1 in [19] for coflows). For coflow scheduling, SP as described above is $2\alpha\beta + \gamma$-competitive for coflow scheduling with an additional $\alpha W$ term.

<footnote n="1">¹Sincronia is similar to Ahmadi’s algorithm [3] for offline coflow scheduling. Both algorithms have the same approximation ratio of 4 and their analysis is based on similar techniques. We will mainly use Sincronia to refer to the offline algorithm with the implicit assumption that the two algorithms are interchangeable. We will explicitly refer to Ahmadi’s algorithm whenever disambiguation is needed.</footnote>

<footnote n="2">²See Section 3 for details</footnote>
By taking Garg's (2,2)-approximation algorithm [15] for MUWP as the select step and Ahmadi's 4-approximation algorithm as the permute step, we get:

**Corollary 1 (Corollary 5 in [19]).** *There exists a 12-competitive algorithm for coflow scheduling.*

To quote footnote 2 of [19], “We make the critical assumption that the offline $\gamma$-approximation algorithm does not increase the makespan of the given subset of jobs, (...). For the scheduling models studied in this paper, this assumption will indeed hold. In fact, if it can be shown that the $\gamma$-approximation algorithm also approximates the makespan criteria within some factor $\mu$, then it is straightforward to incorporate this into the model, at the expense of an additional $\mu$ factor in the approximation guarantee.”

As we argue in Sec. 4, this critical assumption of not increasing the makespan is not respected for Ahmadi's algorithm that SP uses in the permute step for coflow scheduling. Hence, Corollary 1 cannot be deduced from Theorem 1. On the other hand, there exists an offline algorithm that respects the makespan [26]. However, there is no non-trivial and useful value of $\gamma$ for it. Thus, Theorem 1 is too restrictive for coflows scheduling and cannot be used as is for practical algorithms. For SP to be of practical applicability, it has to be flexible by allowing the offline scheduling algorithm to increase the makespan of the selected subset of coflows.

Let $\phi$ be the factor by which the makespan needs to be stretched for the offline algorithm to guarantee completion of selected coflows by next decision epoch. An offline scheduling algorithm is thus characterized by the couple $(\gamma, \phi)$.

**Theorem 2 (Modified version of Theorem 1 in [19] for coflows).** For coflow scheduling, SP as described above is $(2\phi\alpha\beta + \gamma)$-competitive with an additional $\phi\alpha W$ term.

**Remark 1.** We would like to point out that the Theorem 1 in [19] is stated for a general optimization framework which is then applied to COS and coflows. Our modification is only relevant for coflow scheduling. For COS, we believe that their result can be applied as is.

With this definition, Sincronia can be shown to have $\phi = 2$, and the correct statement for Corollary 1 becomes:

**Corollary 2 (Corrected Corollary 5 in [19]).** There exists a 20-competitive algorithm for coflow scheduling.
The above contribution is independent of whether scheduling is based on predictions or not. It corrects a mistake in an oft-cited result (see [2, 28]) for constructing an online coflow scheduling algorithm with performance guarantees.

Our main contributions related to scheduling with prediction are to derive the approximation ratio for Sincronia in the offline setting with predictions and the competitive ratio for SP in the online setting with predictions. More precisely, for the offline setting, we shall prove the following result.

**Theorem 3 (Sincronia with predictions).** The order generated by Sincronia executed on predicted values has an approximation ratio of $\min(4\nu^2, \frac{2W}{w_{\min}})$, with $w_{\min} = \min_k w_k$. Its stretch factor with prediction is 2 as before.

For our online algorithm, which we shall call SPPred, the $(\alpha, \beta)$ approximation algorithm for MUWP as well as the $(\gamma, \phi)$-approximate offline scheduling algorithm are both run on the predicted values. Unlike in SP, the $k$th decision (resp. execution) epoch is no longer $\phi\alpha\tau_k$ but $\phi\alpha\nu\tau_k$. Further, the MUWP will be run with a different deadline. The complete algorithm, which we shall call SPPred is presented later in Algorithm 2 for which we shall show the following result.

**Theorem 4.** SPPred has a competitive ratio of $(2\phi\alpha\beta\nu + \gamma\nu^2)$-competitive with an additive $\phi\alpha\nu W$ term.

**Corollary 3.** With Garg's algorithm in the select step and Sincronia in the permute step, Algorithm 2 has a competitive ratio of $16\nu + 4\nu^2$.

In the above result, we have chosen to ignore the $\frac{2W}{w_{\min}}$ term in Theorem 3 as will be explained in Section 6. We also mention that both the Theorems 3 and 4 are consistent as by setting $\nu = 1$ (predictions correspond to true values) we recover the approximation and competitive ratio for the algorithms on the true values.

Before presenting the proofs of these results, we review below background material on the COS problem and on MUWP which is required for understanding our own contributions in Sections 4, 5 and 6.

# 3 Background Material

## 3.1 Reduction to Concurrent Open Shop Scheduling

The analysis of coflow scheduling algorithms often leverages a known reduction to the COS problem [19]. To explain this reduction, define $p_{\ell,k} =$
$\sum_{j \in F_{k,l}} v_{k,j}$ as the actual transmission time of coflow $k$ at port $l$. Given an instance $I$ of the coflow scheduling problem, we can construct an instance $I'$ of the COS problem, where each port $l$ in $I$ is mapped to a machine in $I'$, each coflow $k$ in $I$ corresponds to a job in $I'$, and the processing time of job $k$ on machine $l$ in $I'$ is set as $p_{l,j}$. Note that a key difference between the two problems is that while in problem (C-OPT) a flow has to be transmitted simultaneously on its input and output ports, this constraint is relaxed in the COS problem.

The COS problem can be formulated as the following linear-programming problem:

$$ \text{Minimize} \quad \sum_{k \in \mathcal{C}} w_k C_k \qquad (P) $$

s.t

$$ \sum_{k \in S} p_{l,k} C_k \geq f_l(S), \quad l \in \mathcal{L} \text{ and } S \subseteq \mathcal{C}, \qquad (8) $$

$$ C_k \geq 0, \quad k \in \mathcal{C}, \qquad (9) $$

where $f_l(S)$ is defined as

$$ f_l(S) = \frac{1}{2} \sum_{k \in S} (p_{l,k})^2 + \frac{1}{2} \left( \sum_{k \in S} p_{l,k} \right)^2, \qquad (10) $$

for each port $l \in \mathcal{L}$ and each subset $S \subseteq \mathcal{C}$ of coflows. Inequalities (8) correspond to the so-called parallel inequalities [27, 30]. In non-preemptive single-machine scheduling problems, these inequalities define the convex hull of feasible completion time vectors in the absence of precedence constraints. Note that there is an exponential number of such inequalities. It is proven in [2] (see Lemma 1) that the optimal value of Problem (P) provides a lower bound for the coflow scheduling problem, that is, $\sum_{k \in \mathcal{C}} w_k C_k^* \leq \sum_{k \in \mathcal{C}} w_k C_k^{OPT}$, where the $C_k^*$ are the optimal values of the completion times in Problem (P) whereas the $C_k^{OPT}$ are the completion times in an optimal schedule. This directly follows from the fact that a feasible solution for $I$ also yields a feasible solution for $I'$.

For later use, we note that the dual problem of (P) is as follows
$$ \text{Maximize} \sum_{\ell \in \mathcal{L}} \sum_{S \subseteq \mathcal{C}} f_{\ell}(S) y_{\ell,S} \qquad (\text{D}) $$

s.t

$$ \sum_{S:k \in S} \sum_{\ell \in \mathcal{L}} p_{\ell,k} y_{\ell,S} \leq w_k, \quad \text{for all } k \in \mathcal{C}, \qquad (11) $$

$$ y_{\ell,S} \geq 0, \quad \text{for all } \ell \in \mathcal{L} \text{ and } S \subseteq \mathcal{C}. \qquad (12) $$

## 3.2 Clairvoyant Coflow Scheduling with Sincronia

Sincronia is one of the most popular clairvoyant coflow scheduling algorithms [2]. It guarantees a 4-approximation, the best known approximation ratio until recently [28]. We shall describe below the algorithm used by Sincronia to schedule a set of coflows.

Sincronia first computes a $\sigma$-order, that is, a priority order over coflows. If $\sigma(k) < \sigma(k')$, then the flows of coflow $k$ are transmitted in the datacenter network with strict priority over the flows of coflow $k'$. Sincronia then uses a greedy rate allocation which preserves the $\sigma$-order, that is, it is guaranteed that coflow $k$ will be completed before coflow $k'$ (that is $C_k \le C_{k'}$) if $\sigma(k) < \sigma(k')$. The method for computing the $\sigma$-order is based on the reduction to the COS problem discussed in Section 3.1. Sincronia solves Problem (P) with a primal-dual algorithm, which is shown in Alg. 1.

<caption>**Algorithm 1** Sincronia primal-dual algorithm</caption>

1: $y_{\ell,A} \leftarrow 0$ for all $\ell \in \mathcal{L}$ and $A \subseteq \mathcal{C}$.
2: $S \leftarrow \mathcal{C}$
3: **for** $t = n \dots 1$ **do**
4: &nbsp;&nbsp;&nbsp;&nbsp;$b \leftarrow \text{argmax}_{\ell \in \mathcal{L}} \sum_{k \in S} p_{\ell,k}$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Bottleneck port
5: &nbsp;&nbsp;&nbsp;&nbsp;$k^* \leftarrow \text{argmin}_{k \in S} \left( \frac{w_k}{p_{b,k}} \right)$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Largest weighted proc. time
6: &nbsp;&nbsp;&nbsp;&nbsp;$C'_{k^*} \leftarrow \sum_{k \in S} p_{b,k}$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Set primal variable
7: &nbsp;&nbsp;&nbsp;&nbsp;$y_{b,S} \leftarrow \frac{w_{k^*}}{p_{b,k^*}}$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Set dual variable
8: &nbsp;&nbsp;&nbsp;&nbsp;$w_k \leftarrow w_k - w_{k^*} \frac{p_{b,k}}{p_{b,k^*}}$ for all $k \in S$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Update weights
9: &nbsp;&nbsp;&nbsp;&nbsp;$\sigma(t) \leftarrow k^*$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Set priority of coflow $k^*$
10: &nbsp;&nbsp;&nbsp;&nbsp;$S \leftarrow S \setminus \{k^*\}$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Remove $k^*$ from unscheduled coflows
11: **end for**

It is easy to prove that Algorithm 1 produces a primal feasible solution and a dual feasible solution for problems (P) and (D). It is also shown in
[3] that this algorithm finds an ordering of jobs on machines, say 1, 2, ..., n, such that the completion time of job k is $C'_{k} = \max_{l} \sum_{j \le k} p_{l,j}$ and

$$ \sum_{k \in C} w_k C'_k \le 2 \sum_{k \in C} w_k C_k^* \le 2 \sum_{k \in C} w_k C_k^{OPT}, $$

where $C_k^{OPT}$ and $C_k^*$ are as defined at the end of Section 3.1. Moreover, as shown in [2] (see Lemma 3), under any rate allocation policy that is work conserving, order-preserving and preemptive, the completion time $C_k$ of coflow k in instance I is at most twice the completion time obtained with Algorithm 1 for the corresponding job in I', that is, $C_k \le 2C'_k$. As the greedy rate allocation of Sincronia satisfies these properties, under this rate allocation, we have

$$ \sum_{k \in S} w_k C_k \le 2 \sum_{k \in S'} w_k C'_k \le 4 \sum_{k \in C} w_k C_k^{OPT}, $$

so that computing the order in which coflows should be processed with Algorithm 1, and then allocating rates following the greedy rate allocation<fnref n="3" /> of Sincronia, provides a 4-approximation, as formally stated in Theorem 5.

**Theorem 5** (Theorem 1 in [2]). Sincronia achieves average coflow completion time within $4 \times$ of the optimal average coflow completion time.

## 3.3 Minimum unscheduled weight problem

The online scheduling algorithm that we propose in Section 6 takes scheduling decisions at discrete points in time. At each decision epoch, the algorithm selects a subset of coflows among those in the system for transmission. The selection is done by solving an instance of the Minimum Unscheduled Weight Problem (MUWP). Let R be the set of coflows in the system at the current decision epoch, and D be the time until the next decision epoch. The goal is to find a subset $S \subseteq R$ of coflows which can be completed in at most D units of time and minimizes the unscheduled weight $W(R \setminus S) = \sum_{k \in R \setminus S} w_k$. Formally, the problem is as follows

<footnote n="3">³The greedy step is replaced by the MoveEdgesBack subroutine in Ahmadi’s algorithm. See [3] for details.</footnote>
$$ \text{Minimize} \quad W(R \setminus S) \qquad (C-MUWP) $$

s.t.

$$ \sum_{t=1}^{D} x_{k,j}^{t} = v_{k,j}, \quad j \in F_{k}, k \in S, \qquad (13) $$

$$ \sum_{k \in S} \sum_{j \in F_{\ell,k}} x_{k,j}^{t} \leq 1, \quad t = 1, \dots, D, \ell \in \mathcal{L}, \qquad (14) $$

$$ x_{k,j}^{t} \in \{0,1\}, \quad t = 1, \dots, D, j \in F_{k}, k \in S. \qquad (15) $$

where the decision variable $x_{k,j}^t$ is 1 if flow $j$ of coflow $k$ is transmitted at time $t$, and 0 otherwise. Constraint (13) states that all flows of all selected coflows $k \in S$ have to be fully transmitted by the next decision epoch, whereas constraint (14) imposes that each port transmits at most one flow at any time.

As proposed in [19], MUWP in the coflow environment can be solved by leveraging the reduction to the COS problem presented in Section 3.1. Let $I$ be the instance of MUWP in the coflow environment, and let $I'$ be the corresponding instance in the COS environment. For the latter instance, an integer linear programming formulation of the problem is as follows

$$ \text{Minimize} \quad \sum_{j \in R'} w_k(1 - x_k) \qquad (\text{MUWP}) $$

s.t.

$$ \sum_{k \in R'} p_{\ell,k} x_k \leq D, \quad \forall \ell \in \mathcal{L}, \qquad (16) $$

$$ x_k \in \{0,1\}, \quad \forall k \in R'. \qquad (17) $$

where the binary decision variable $x_k$ is 1 if job $k \in R'$ is selected, and 0 otherwise. We shall denote by $W^*(R', D)$ the optimal value of problem (MUWP). We will refer to the latter as MUWP from now on.

Given an algorithm $A$ for MUWP, we let $W^A(R', D)$ be the unscheduled weight of the solution produced by this algorithm on instance $I'$. Algorithm $A$ is an $(\alpha, \beta)$-approximation if it finds a subset of jobs which can be completed in at most $\alpha D$ units of time and has unscheduled weight at most $\beta$ times that of the subset of jobs with minimum unscheduled weight that completes by $D$, that is,
$$W^A(R', \alpha D) \leq \beta W^*(R', D).$$

A simple polynomial-time (2, 2)-approximation for MUWP was proposed by Garg et al. in [15]. The approximation is based on the LP relaxation obtained from (MUWP) by replacing the constraints $x_k \in \{0, 1\}$ by $0 \le x_k \le 1$, and then rounding the optimal fractional solution. This is formally stated in Lemma 1 below. For completeness, we provide a proof of this result in Appendix A.2.

**Lemma 1** (Section 5 in [15]). Given an instance $I'$ of MUWP with job set $R'$ and deadline $D$, let $x^*$ be an optimal solution of the linear programming relaxation of MUWP. Define $S' = \{k \in R' : x_k^* \ge \frac{1}{2}\}$. All jobs in $S'$ can be completed by time $2D$ and $W(R' \setminus S') \le 2W^*(R', D)$.

*Proof.* See Appendix A.2. □

<figure><img src="image_3.png" /></figure>

Note that an algorithm for the MUWP in the COS environment directly yields an algorithm for the coflow environment: a coflow in $I$ is selected if the corresponding job in $I'$ is selected by the algorithm. Thus, the algorithm proposed by Garg et al. in [15] can be applied for solving the MUWP in the coflow environment.

## 3.4 Select and Permute

SP as the name suggests works in two steps: select and permute. Define $\tau_k = 2^{k-1}$ as the $k$th scheduling instant. The $k$th scheduling interval, $[2^{k-1}, 2^k)$ is of length $\tau_k$. Let $R_k$ be the set of unscheduled coflows at $\tau_k$. These are the flows that have been released by $\tau_k$ but have not yet been scheduled. First in the select step, a subset, $S_k$, of coflows is selected from the output of an $(\alpha, \beta)$-approximation algorithm for MUWP when applied on $R_k$. The subset $S_k$ is such that all coflows in $S_k$ are guaranteed to finish execution in an interval of length $\alpha\tau_k$. Further, the weight of unscheduled coflows (that is, coflows in $R_k \setminus S_k$) is at most $\beta$ times the optimal solution of MUWP. Next, in the permute step, the coflows from $S_k$ are then scheduled in the current execution interval $[\alpha\tau_k, \alpha\tau_{k+1})$ using a $\gamma$-approximation offline scheduling algorithm for coflows (for example, the order-based algorithm Sincronia has an approximation ratio of 4). Fig. 1 provides a pictorial representation of SP. It is to be noted that the decision intervals are not the same as the execution intervals.
<figure><img src="image_4.png" /><figcaption>Figure 1: Pictorial representation of the Select and Permute algorithm [19].</figcaption></figure>

# 4 Corrected competitive ratio of SP

The competitive ratio of 12 for SP is derived in [19] by taking Garg's (2, 2)-approximation for MUWP as the select step and Ahmadi's 4-approximation algorithm [3] as the permute step. By plugging the values of $(\alpha, \beta, \gamma) = (2, 2, 4)$ in Theorem 1, the claimed ratio of 12 is obtained.

The (2, 2) approximation ratio of Garg's algorithm is valid in the coflow environment only under assumption that the makespan of the offline scheduling algorithm in the permute step of SP for the coflow environment does not exceed the deadline $\alpha\tau_k$ for the $k$th batch of coflows. This is precisely the assumption that is stated in footnote 2 of [19]. Recall that Garg's algorithm guarantees that the equivalent batch of COS instance will finish execution in $\alpha\tau_k$ but does not guarantee the same for the coflow instance. For coflows it remains to be shown that the $k$th batch of coflows will finish in $\alpha\tau_k$.

Let $I$ and $D$ refer to the same quantities as in problem (MUWP) in Sec. 3.3. Garg's algorithm returns a subset of coflows that can finish in at most $2D$ in the equivalent COS instance. The makespan assumption requires that the offline scheduling algorithm in the permute step respect this deadline of $2D$. This assumption is stated in Lemma 5 in [19] which we state below.

**Lemma 2 (Lemma 5 in [19]).** In polynomial time, we can find a schedule for coflow instance I that completes in $2D$, and whose total unscheduled weight is at most $2W$.

While the above result is technically true, that is there exists an algo-
<figure><img src="image_5.png" /><figcaption>Figure 2: Counterexample showing Ahmadi’s algorithm is not idle-time free (based on Figure 11 in [2])</figcaption></figure>

rithm (see Algorithm 1 in [26] and Lemma 1 in [3]) that can finish in $2D$, the schedule thus obtained need not match the one generated by Ahmadi’s algorithm that is used in the permute step of SP. The algorithm of [26] that is able to finish in $2D$ does not have a non-trivial approximation ratio for the weighted CCT. Since the competitive ratio of SP is based on the approximation ratio $\gamma$ for the permute step, the algorithm of [26] cannot be used in the permute step. Instead, SP uses Ahmadi’s algorithm which has a $\gamma = 4$ approximation ratio. However, as shown in the example in Fig. 2 (which is similar to the example in Fig. 11 in the Tech report of [2]), Ahmadi’s algorithm does not finish in the same time as the equivalent COS instance. At each output port, the ratio of weight to the flow volume is the larger for Coflow 1. Therefore, Ahmadi’s algorithm will give higher priority to Coflow 1. Next, in its MoveEdgesBack step (cf. Sec. 3.2), the algorithm will try to move some of the flows of Coflow 2 to fill empty slots during the execution of the flows of Coflow 1. Since there are no empty spaces, Coflow 1 will be executed entirely before Coflow 2 starts execution. Thus, the makespan of Ahmadi’s algorithm will be $2\tau$ while that of the corresponding COS instance is $\tau + 1$. That is, Ahmadi’s algorithm is not able to respect the makespan of the COS instance as required by Lemma 2. Note that there is a coflow schedule with makespan $\tau + 1$: send flow of Coflow 2 going between ports $(\tau + 1, j)$ in time-slot $j$ and flow $(j, j)$ of Coflow 1 in other time-slots.

The fact that Ahmadi’s algorithm cannot generate this schedule means Lemma 2 is not applicable to Ahmadi’s algorithm (or Sincronia) and cannot be used to deduce the competitive ratio of 12 from Theorem 1. One has
to allow the makespan to be stretched by some factor determined by the offline scheduling algorithm. In the specific case of Ahmadi's algorithm as the permute step, it can be shown that the makespan is at most twice that of the COS instance. As a consequence, to derive a competitive ratio for SP with Ahamdi's algorithm in the permute step, Lemma 2 has to be replaced by:

**Lemma 3.** *Ahmadi's algorithm can find in polynomial time a schedule for coflow instance I that completes in 4D and whose unscheduled weight is at most 2W.*

*Proof.* See Appendix A.2. □

<figure><img src="image_6.png" /></figure>

The above discussion shows that the current statement of Theorem 1 is too restrictive and does not allow SP to use Sincronia in its permute step. Further, the restriction is such that the algorithm that can be used in the permute step do not lead to a meaningful competitive ratio for online scheduling of coflows. In order for Theorem 1 to be useful for coflows, SP has to allow the offline algorithm to finish later than the minimum makespan. This additional time means that the execution intervals will need to be stretched accordingly. Further, to be able to obtain a guarantee on the competitive ratio, the offline algorithm in the permute step has to provide simultaneous guarantees on both its makespan as well as its weighted CCT. For this reason, we define the guarantee of the offline scheduling algorithm as a pair: one number for the makespan and the other for the weighted CCT.

**Definition 1.** An offline coflow scheduling algorithm is a $(\gamma, \phi)$-approximation if

1. its weighted coflow completion time is within a factor $\gamma$ of the minimum one; and

2. its makespan is within a factor $\phi$ with respect to that of equivalent COS instance.

With this definition, Theorem 1 can be generalized as follows so that a larger and more practical class of algorithms can be considered in the permute step as stated in Theorem 2 which we recall here.

**Theorem 2** (Modified version of Theorem 1 in [19] for coflows). For coflow scheduling, SP as described above is $(2\phi\alpha\beta + \gamma)$-competitive with an additional $\phi\alpha W$ term.
<figure><img src="image_7.png" /><figcaption>Figure 3: Pictorial representation of the modified Select and Permute algorithm for coflows.</figcaption></figure>

*Proof of Theorem 2.* Consider a $(\alpha, \beta)$-approximation algorithm for MUWP as the select step and a $(\gamma, \phi)$-approximation algorithm for offline coflow scheduling as the permute step.

Since the permute step stretches the makespan by at most $\phi$, we can conclude that an $(\alpha, \beta)$ approximation for MUWP on the equivalent COS instance translates to a $(\phi\alpha, \beta)$ approximation for MUWP on the coflow instance. The rest of the proof is the same as for Theorem 1 in [19] with $\alpha$ replaced by $\phi\alpha$. $\square$

The flexibility factor of $\phi$ in the makespan means that the SP algorithm itself will have to be modified. The $k$th execution interval in Fig. 1 will now become [$\phi\alpha\tau_k, \phi\alpha\tau_{k+1}$) as shown in Fig. 3. This is the only change that is needed in SP; all the other steps can be executed as before.

Since Garg’s algorithm is (2, 2) approximate and Ahmadi’s algorithm is (4, 2) approximate, we arrive at the corrected competitive ratio claimed in Corollary 2 (stated below) for SP with these two algorithms as subroutines.

**Corollary 2** (Corrected Corollary 5 in [19]). There exists a 20-competitive algorithm for coflow scheduling.

Similarly, the competitive ratio of Sincronia is 20, and not 12 as incorrectly stated in [2]. More generally, all competitive ratios obtained for online coflow scheduling using Khuller’s framework have to be corrected (see, e.g., [28]).
# 5 Offline Coflow Scheduling With Predictions

In this section, we consider the offline setting in which all coflows are present in the system at time 0. Actual flow sizes are unavailable and only unreliable ML predictions on them can be used for scheduling coflows. We establish the approximation ratio of Sincronia when ran on predictions as a function of the prediction error. This is done in two steps. First, we obtain in Section 5.1 an upper bound on the approximation ratio which depends on the quality of the predictions. Then, in Section 5.2, we obtain an upper bound which is independent of predictions.

## 5.1 Sincronia with Predictions

Define $\hat{p}_{l,k} = \sum_{j \in F_{k,l}} \hat{v}_{k,j}$ as the predicted transmission time of coflow $k$ at port $l$. This predicted value is related to the actual one through the inequalities

$$ \mu_{min} p_{l,k} \leq \hat{p}_{l,k} \leq \mu_{max} p_{l,k}, \qquad (18) $$

for all ports $l \in \mathcal{L}$ and all coflows $k \in \mathcal{C}$. We consider the completion times obtained with Sincronia when Algorithm 1 is ran over the predictions $\hat{p}_{l,k}$ instead of the actual processing times $p_{l,k}$.

When ran on predictions, Sincronia produces a $\sigma$-order and compute coflow completion times $\hat{C}_k$ which are a feasible primal solution, that is, $\hat{C}$ is a feasible solution to Problem (P) in which the actual processing times $p_{l,k}$ have been replaced by the predicted processing times $\hat{p}_{l,k}$. Likewise, the constants $f_l(S)$ have been replaced by the constants $\hat{f}_l(S)$ obtained by using the predicted values $\hat{p}_{l,k}$ instead of the actual values $p_{l,k}$. As a primal-dual algorithm, Sincronia also computes the dual variables $\hat{y}_{l,S}$ which provide a feasible solution to dual problem in which predicted processing times are used instead of the actual ones.

We shall assume for simplicity that Sincronia schedule the coflows in the order $1, 2, \dots, n$, which implies that $\hat{C}_1 \leq \hat{C}_2 \leq \dots \leq \hat{C}_n$. Our goal is to obtain an upper bound on the approximation ratio obtained by scheduling coflows in that order, as a function of $\nu = \mu_{max}/\mu_{min}$. Note that $\hat{C}_k$ is only the estimated completion time of coflow $k$. In the following we denote by $\tilde{C}_k$ the actual completion time of coflow $k \in \mathcal{C}$ obtained by scheduling coflows in the order $1, 2, \dots, n$. We first establish a bound on the predicted weighted sum of completion times.
**Lemma 4.** Let $\hat{C}_k$ be the predicted completion time of coflow $k$ when Algorithm 1 is ran over the predictions, and $C_k^{OPT}$ be its completion time in an optimal schedule. Then

$$ \sum_{k \in C} w_k \hat{C}_k \le \frac{2 \mu_{max}^2}{\mu_{min}} \sum_{k \in C} w_k C_k^{OPT}, \qquad (19) $$

*Proof.* See Appendix B.1. □

We now use Lemma 4 to establish the approximation ratio of the prediction-based Sincronia algorithm.

**Proposition 1.** In the offline setting, scheduling coflows in the order determined by Sincronia with predictions as inputs yields a schedule whose weighted sum of completion times is at most $4\nu^2$ the optimal one.

*Proof.* See Appendix B.2. □

Note that the approximation ratio in Proposition 1 is identical to that of Sincronia for perfect predictions, that is, when $\nu = 1$. However, the bound in Proposition 1 suggests that Sincronia is not robust to prediction errors, as its approximation ratio grows unboundedly as the ratio $\nu$ increases. We shall see in Section 5.2 that this is not the case.

To illustrate the above result, consider the scenario where, although unreliable, the relative prediction error on flow sizes is guaranteed to lie in the interval $[-\frac{1}{2}, \frac{1}{2}]$ uniformly for all flows $j$ and all coflow $k \in C$. In that case, it is easy to see $\mu_{min} = \frac{1}{2}$, $\mu_{max} = \frac{3}{2}$ and $\nu = 3$, so that Sincronia with predictions as inputs guarantees a 36-approximation, that is, a worst-case approximation ratio which is $9 \times$ that of Sincronia when ran over the actual flow sizes. As we shall see in Section 7, the experimental performance of the prediction-based Sincronia algorithm is far better than this theoretical guarantee.

## 5.2 Approximation ratio independent of predictions

The bound in Proposition 1 depends upon the quality of predictions. If $\mu_{min}$ is close to 0, then the bound goes towards infinity. This happens because the bound makes use of the completion times, $\hat{C}_k$, computed from the predicted processing times, $\hat{p}_{\ell,k}$s, which can highly different from the actual processing times. For example, the predictions can be of the order of $\epsilon$ a small quantity while the actual ones could be of the order of 1. The
predicted completion times will be of the order of $\epsilon$ which is much smaller than the actual completion times which will be of the order of 1.

A bound that does not suffer from this drawback can be obtained from the observation that Sincronia is an order-based scheduling algorithm. Its total weighted completion time will be upper bounded by that of the worst-case order, that is:

$$ \sum_k w_k \tilde{C}_k \leq \max_{\sigma} \sum_k w_{\sigma(k)} C_{\sigma(k)}. \qquad (20) $$

Beside, the optimal total weighted completion time is at least that of the last coflow in an optimal order:

$$ \sum_k w_k C_k^{OPT} \geq w_{\sigma^*(n)} C_{\sigma^*(n)} \geq \left( \min_k w_k \right) \max_{\ell} \sum_k p_{\ell,k} $$

where $\sigma^*(n)$ is the index of the coflow finishing last. The second inequality is a consequence of the fact that the latest completion time cannot be earlier than the time required to empty the most loaded link failing which there will be a coflow that would not have finished.

Combining the above two observations, we get the following bound on the approximation ratio of Sincronia with predictions:

$$ \frac{\sum_k w_k \tilde{C}_k}{\sum_k w_k C_k^{OPT}} \leq \frac{\max_{\sigma} \sum_k w_{\sigma(k)} C_{\sigma(k)}}{(\min_k w_k) \max_{\ell} \sum_k p_{\ell,k}} \qquad (21) $$

Using this inequality, we arrive at the following approximation ratio.

**Proposition 2.** In the offline setting, Sincronia with predictions is a 2W/w<sub>min</sub> approximation algorithm, where W = $\sum_k w_k$ and w<sub>min</sub> = $\min_k w_k$.

*Proof.* See Appendix B.3. □

Note that Proposition 2 implies that Sincronia is robust to prediction errors. In particular, when all coflow weights are equal, as considered in Section 7, we have W = nw<sub>min</sub> and the average CCT of Sincronia with predictions as inputs cannot be worse than 2n the optimal one, independently of the prediction error.

We are now in a position to prove Theorem 1 which is restated below.

**Theorem 3 (Sincronia with predictions).** The order generated by Sincronia executed on predicted values has an approximation ratio of $\min(4\nu^2, \frac{2W}{w_{min}})$, with $w_{min} = \min_k w_k$. Its stretch factor with prediction is 2 as before.
*Proof.* Combining the upper bounds in Proposition 1 and Proposition 2, we obtain our final upper bound of $\min\{4\nu^2, 2W/w_{min}\}$ on the approximation ratio of the prediction-based algorithm. $\square$

# 6 Online Coflow Scheduling With Predictions

We consider an online version of the coflow scheduling problem, where coflows arrive over time at unknown instants. Upon arrival of a coflow, unreliable predictions on the volumes of its flows are revealed to the scheduler. Predicted and actual values of flow volumes are related through (7), but the actual volumes are known only upon flow completion. The objective of the scheduler is to minimize the weighted coflow completion time $\sum_{k \in C} w_k C_k$, as described in Section 2.

The algorithm that we propose, SPPred, is directly inspired from the SP algorithm proposed by Khuller et al. in [19] for the online scheduling problem with known flow volumes. We adapt their algorithm to handle the uncertainty on flow volumes. SPPred takes scheduling decisions at discrete points in time $\tau_0, \tau_1, \tau_2, \dots$, where $\tau_0 = 0$ and $\tau_k = 2^{k-1}$ for $k \ge 1$. We denote by $I_k$ the time interval $[\tau_k, \tau_{k+1})$, and by $xI_k$ the time interval $[x\tau_k, x\tau_{k+1})$. Let $R_k$ be the set of coflows released but not yet scheduled before $\tau_k$ by the algorithm. SPPred works as follows:

1. At time $\tau_k$, the algorithm selects a subset of coflows $S_k \subseteq R_k$ by solving an instance of the Minimum Unscheduled Weight Problem (MUWP) in the COS environment with predicted processing times $\hat{p}_{\ell,k}$ as inputs. The instance is defined by the set of jobs $R_k$ and by the deadline $\mu_{max} D$, where $D = \tau_{k+1} - \tau_k$. As problem (MUWP) is NP-hard, it is solved using an $(\alpha, \beta)$-approximation algorithm as in SP. For example, Garg's algorithm [15] is a $(2, 2)$ approximation. For all ports $\ell \in \mathcal{L}$

$$ \sum_{j \in S_k} \hat{p}_{\ell,j} \le \alpha \mu_{max} D, \\ \sum_{j \in R_k \setminus S_k} w_j \le \beta \hat{W}^*(R_k, \mu_{max} D), \qquad (22) $$

where $\hat{W}^*(R_k, \mu_{max} D)$ represents the optimal objective value of problem (MUWP).

2. Schedule the set of coflows $S_k$ in the time interval $\phi\alpha\nu I_k$ using a $(\gamma, \phi)$ offline scheduling algorithm with predictions as inputs. Here $(\gamma, \phi)$ is
<figure><img src="image_8.png" /><figcaption>Figure 4: Pictorial representation of SPPred which is the Select and Permute algorithm run on predictions.</figcaption></figure>

the approximation couple for the algorithm when run on true values. For example, Sincronia is a (4, 2)-approximation. The release times of the coflows $j \in S_k$ are ignored.

The algorithm is summarized pictorially in Fig. 4 and algorithmically in Algorithm 2. We note that there are two major differences with respect to SP. First, the execution intervals are now stretched by a factor $\phi\alpha\nu$ instead of $\phi\alpha$, and second the MUWP step is solved with a deadline of $\mu_{max}D$ instead of $D$.

<caption>**Algorithm 2 SPPred:** Online Coflow Scheduling Algorithm with Predictions as Inputs</caption>

1: $k \leftarrow 0, \tau_0 \leftarrow 0$
2: **while** $\tau_k < T$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;$A_k = \{j \in J : r_j \le \tau_k\}$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Coflows released by time $\tau_k$
4: &nbsp;&nbsp;&nbsp;&nbsp;$R_k = A_k \setminus \bigcup_{t<k} S_t$ &nbsp;&nbsp;&nbsp;&nbsp;▷ Coflows released but not yet scheduled at time $\tau_k$
5: &nbsp;&nbsp;&nbsp;&nbsp;Select $S_k \subseteq R_k$ by solving (MUWP) with deadline $\mu_{max}D$ using an $(\alpha, \beta)$ approximation algorithm
6: &nbsp;&nbsp;&nbsp;&nbsp;Schedule coflows in $S_k$ over $\phi\alpha\nu I_k$ using a $(\gamma, \phi)$ approximation of-line scheduling algorithm with predictions as inputs
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$k \leftarrow k + 1, \tau_k \leftarrow 2^{k-1}$
8: **end while**
We now proceed to the analysis of SPPred and begin with the first step of the algorithm. As proven in Lemma 1, Garg’s algorithm provides a (2, 2)-approximation for the MUWP problem when processing times are known. However, in the first step of SPPred, coflows are selected on the basis of predicted processing times. Lemma 5 provides guarantees on the quality of an (α, β)-approximation algorithm when it is given predictions as inputs instead of the actual processing times.

**Lemma 5.** Let A be an an $(\alpha, \beta)$-approximation for problem (MUWP) in the COS environment. Given a set of jobs R and their predicted processing times, let $\hat{S}^A$ be the set of jobs selected by algorithm A when executed with the deadline $\mu_{max}D$. Let $W^*(R, D)$ be the optimal value of problem (MUWP) for the instance defined by the same set of jobs, but with their actual processing times and the deadline D. Then all jobs selected by algorithm A can be completed in at most $\alpha\nu D$ time units and

$$W(R \setminus \hat{S}^A) \leq \beta W^*(R, D). \qquad (23)$$

*Proof.* See Appendix A.3. □

Lemma 5 provides the key ingredient for extending the online COS scheduling algorithm proposed in [19] to the case of uncertain processing times. The details of the algorithm are given in Appendix B.4 (see Algorithm 3). This algorithm is very similar to Algorithm 2. At each decision epoch $\tau_k$, it first select a subset of jobs $S_k$ among those in the system by solving problem (MUWP) with an $(\alpha, \beta)$-approximation. It then schedules the selected jobs in the time interval $\alpha\nu I_k$ using an offline scheduling algorithm ran over predictions and providing a $\gamma\nu^2$-approximation. The competitive ratio of this algorithm with respect to the offline optimum is given in Theorem 6. The derivation of this competitive ratio relies on Lemma 5 and closely follows the proof of Theorem 1 in [19].

**Theorem 6.** For the online COS scheduling problem with job set J and predictions as inputs, Algorithm 3 is $(2\alpha\beta\nu+\gamma\nu^2)$-competitive, with an additive $\alpha\nu W$ term, where $W = \sum_{j \in J} w_j$.

*Proof.* See Appendix B.4. □

Note that Lemma 5 implies that Garg’s algorithm is a $(2\nu, 2)$-approximation for problem (MUWP) when ran over predictions. For the MUWP problem in the coflow environment, (C-MUWP), combining Sincronia and Garg’s
algorithm provides a (4$\nu$, 2)-approximation when ran over predictions, as formally stated in Corollary 4.

**Corollary 4.** *Combining Sincronia and Garg's algorithm with deadline $\mu_{max}D$ provides a (4$\nu$, 2)-approximation for the MUWP in the coflow environment when ran over predictions.*

*Proof.* The proof closely follows that of Lemma 3, except that the last job on each and every machine finishes at latest at time $4\nu D$ when predictions are used instead of time $4D$ when processing times are known. The rest of the proof is identical. □

The above corollary can be generalized to a $(\gamma, \phi)$-approximation offline scheduling algorithm by replacing $(2\nu, 2)$ with $(2\phi\nu, 2)$. This allows us to translate the competitive ratio of the equivalent COS instance stated in Theorem 6 to the coflow instance as was done for the case without predictions in Section 4 where Theorem 2 was obtained from Theorem 1 by replacing $\alpha$ with $\phi\alpha$.

Assuming an $(\alpha, \beta)$-approximation algorithm for the select step and a $(\gamma, \phi)$-approximation algorithm for the permute step both when run on true values, we obtain our main results for the competitive ratio for SP when run on predictions.

**Theorem 4.** *SPPred has a competitive ratio of $(2\phi\alpha\beta\nu + \gamma\nu^2)$-competitive with an additive $\phi\alpha\nu W$ term.*

Note that the competitive ratio of Theorem 4 is not robust to prediction errors, in contrast to the approximation ratio of Theorem 3. This mainly comes from the requirement that all selected coflows be finished by the end of the interval $\phi\alpha\nu I_k$. As the prediction error $\nu$ grows, coflows are scheduled over longer and longer intervals.

A practical version of SPPred is when Garg's algorithm is used for the select step and Sincronia is used for the permute step. Theorem 4 can then be used to establish the competitive ratio for this version of SPPred as mentioned in Corollary 1 (restated below).

**Corollary 3.** *With Garg's algorithm in the select step and Sincronia in the permute step, Algorithm 2 has a competitive ratio of $16\nu + 4\nu^2$.*

**Remark 2.** In Corollary 3, we have not taken the robust version of the approximation ratio on Sincronia because, while it might make robust the $4\nu^2$ term in the competitive ratio, it will not alter the lack of robustness
of SPPred itself. Further, it will require accounting for the total weights of coflows served in each interval which is not straightforward. While this latter can be upper bounded by $W/w_{min}$, this will now appear as an multiplicative term and would lead to a large competitive ratio anyway.

As depicted in Figure 4, SPPred has been designed to ensure that all coflows selected at decision epoch $\tau_k$ are finished at latest at time $\phi\alpha\nu\tau_{k+1}$, that is, at time $4\nu\tau_{k+1}$ for the practical version of SPPred discussed above. It may however happen that all selected coflows are completed well before this conservative deadline. An obvious improvement of SPPred, which is referred to as A-SPPred in the following, initiates the next transmission as soon as either the last flow of the currently selected coflows completes or a new decision epoch is triggered. This event-driven adjustment allows the scheduler to avoid idle times and to react earlier to newly arrived coflows. In Section 7.4, we mostly present the numerical results obtained with this version of SPPred.

# 7 Numerical results

In this section, we compare the average CCTs obtained with our prediction-based algorithms against that of the clairvoyant Sincronia on random problem instances. We first describe the procedure for generating these instances in Section 7.1. We then report the results obtained for the offline setting in Section 7.3. Finally, Section 7.4 is devoted to the results obtained for the online scheduling of coflows.

## 7.1 Instance Generation

We generate random problem instances using a publicly available coflow workload generator [1]. The workload generator is based on a real-world trace with 526 coflows, which was obtained from a one-hour long run of Hive/MapReduce jobs on a 3000-machine cluster with 150 racks MapReduce cluster at Facebook [1]. The workload generator allows upsampling the Facebook trace to a desired number of ports ($L$) and coflows ($n$), while preserving the original workload characteristics of the Facebook trace.

To compare the performance of our scheduling algorithms under various conditions, we generate multiple configurations by varying the number of ports $L$ and coflows $n$ as follows. We consider small instances for which $L = 8$ and $L = 12$ as well as large instances for which $L = 20$ or $L = 40$. The offline optimum can be computed for small instances, while for larger
instances the baseline is the Clairvoyant Sincronia. It is assumed that the first L/2 ports are always input ports, while the remaining L/2 ports are output ports. The capacity of each port is normalized to 1. For each value of L, the number of coflows is either n = L/2 or n = L. We generate 100 random problem instances for each configuration of L and n.

Given a problem instance, we generate 1000 random flow size predictions as follows. For each coflow $k \in C$ and each flow $j \in F_k$, we compute the predicted flow volume from its actual volume $v_{k,j}$ with $\hat{v}_{k,j} = v_{k,j} \times U$, where $U$ is a random variable drawn from the uniform distribution over $[1 - \delta, 1 + \delta]$. It follows that $\mu_{min} = 1 - \delta$, $\mu_{max} = 1 + \delta$ and $\nu = (1 + \delta)/(1 - \delta)$. For $\delta \approx 0$, we thus have almost perfect predictions, while when $\delta$ approaches 1 we get terrible predictions. We vary the coefficient $\delta$ over the set $\{0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.99\}$ to evaluate the impact of prediction quality on scheduling performance.

## 7.2 Methodology

As mentioned above, we shall report below the numerical results obtained for both the offline and online settings.

In Section 7.3, we consider the offline setting in which all coflows are present in the system at time 0. For small instances, we compare the average CCT $C^{Pred}$ of the prediction-based Sincronia described in Section 5 against the lower bound $C^{LP}$ for the relaxed problem (P). For larger instances, $C^{LP}$ can no longer be computed and the comparison is made against the average CCT $C^{CL}$ of the clairvoyant Sincronia which knows the exact flow sizes.

The results obtained in the online setting are reported in Section 7.4. In that section, we compare the average CCT $C^{A-SPPred}$ obtained with our online prediction-based algorithm A-SPPred against the average CCT $C^{CL}$ obtained with an offline clairvoyant Sincronia, which would know both the exact flow sizes and the coflow release dates ahead of time. The comparison also includes the average CTT $C^{SPCL}$ of the online version of Sincronia, which would know the exact flow sizes but not the coflow arrival times. Note that the latter algorithm combines the SP scheme with the offline clairvoyant Sincronia.

Finally, in Section 7.4 we also study the relevance of anticipating decision epochs in the online algorithm. To that end, we compare the average CCT $C^{SPPred}$ of SPPred against the average CCT $C^{A-SPPred}$ of its anticipated version. The comparison also includes the average CTT $C^{A-SPCL}$ of the online clairvoyant Sincronia in which decision epochs are anticipated.
## 7.3 Offline Results

### 7.3.1 Small Instances

We first study small instances for which $L = 8$ or $L = 12$. For these instances, we compare the average CCT $C^{\text{Pred}}$ of the prediction-based Sincronia against the lower bound $C^{\text{LP}}$ obtained by solving the linear program (P) with Gurobi. Table 1 shows the ratios $C^{\text{Pred}}/C^{\text{LP}}$ obtained for the configurations $(L, n) = (8, 4)$ and $(L, n) = (8, 8)$, while Table 2 shows the values of the same ratio for the configurations $(L, n) = (12, 6)$ and $(L, n) = (12, 12)$.

<table><caption>Table 1: Mean, standard deviation and quartiles of $C^{\text{Pred}}/C^{\text{LP}}$ for $(L, n) = (8, 4)$ and $(L, n) = (8, 8)$.</caption><thead><tr><th rowspan="2">δ</th><th colspan="4">L = 8 n = 4</th><th colspan="4">L = 8 n = 8</th></tr><tr><th>mean</th><th>std</th><th>Q1</th><th>Q3</th><th>mean</th><th>std</th><th>Q1</th><th>Q3</th></tr></thead><tbody><tr><td>0.00</td><td>1.080</td><td>0.064</td><td>1.020</td><td>1.123</td><td>1.079</td><td>0.047</td><td>1.045</td><td>1.107</td></tr><tr><td>0.10</td><td>1.079</td><td>0.059</td><td>1.025</td><td>1.121</td><td>1.079</td><td>0.041</td><td>1.044</td><td>1.108</td></tr><tr><td>0.20</td><td>1.078</td><td>0.055</td><td>1.033</td><td>1.121</td><td>1.081</td><td>0.038</td><td>1.049</td><td>1.107</td></tr><tr><td>0.30</td><td>1.078</td><td>0.052</td><td>1.037</td><td>1.112</td><td>1.083</td><td>0.037</td><td>1.054</td><td>1.107</td></tr><tr><td>0.40</td><td>1.079</td><td>0.049</td><td>1.040</td><td>1.110</td><td>1.086</td><td>0.035</td><td>1.059</td><td>1.108</td></tr><tr><td>0.50</td><td>1.081</td><td>0.048</td><td>1.044</td><td>1.114</td><td>1.091</td><td>0.034</td><td>1.065</td><td>1.113</td></tr><tr><td>0.60</td><td>1.083</td><td>0.046</td><td>1.046</td><td>1.112</td><td>1.095</td><td>0.033</td><td>1.070</td><td>1.119</td></tr><tr><td>0.70</td><td>1.085</td><td>0.044</td><td>1.052</td><td>1.115</td><td>1.100</td><td>0.033</td><td>1.077</td><td>1.122</td></tr><tr><td>0.80</td><td>1.088</td><td>0.042</td><td>1.054</td><td>1.119</td><td>1.105</td><td>0.033</td><td>1.081</td><td>1.127</td></tr><tr><td>0.99</td><td>1.092</td><td>0.041</td><td>1.060</td><td>1.121</td><td>1.115</td><td>0.033</td><td>1.090</td><td>1.137</td></tr></tbody></table>

<table><caption>Table 2: Mean, standard deviation and quartiles of $C^{\text{Pred}}/C^{\text{LP}}$ for $(L, n) = (12, 6)$ and $(L, n) = (12, 12)$.</caption><thead><tr><th rowspan="2">δ</th><th colspan="4">L = 12 n = 6</th><th colspan="4">L = 12 n = 12</th></tr><tr><th>mean</th><th>std</th><th>Q1</th><th>Q3</th><th>mean</th><th>std</th><th>Q1</th><th>Q3</th></tr></thead><tbody><tr><td>0.00</td><td>1.076</td><td>0.053</td><td>1.039</td><td>1.109</td><td>1.097</td><td>0.048</td><td>1.063</td><td>1.123</td></tr><tr><td>0.10</td><td>1.080</td><td>0.049</td><td>1.042</td><td>1.109</td><td>1.096</td><td>0.041</td><td>1.067</td><td>1.128</td></tr><tr><td>0.20</td><td>1.082</td><td>0.046</td><td>1.045</td><td>1.112</td><td>1.097</td><td>0.037</td><td>1.070</td><td>1.122</td></tr><tr><td>0.30</td><td>1.085</td><td>0.043</td><td>1.049</td><td>1.115</td><td>1.099</td><td>0.035</td><td>1.074</td><td>1.123</td></tr><tr><td>0.40</td><td>1.087</td><td>0.042</td><td>1.052</td><td>1.119</td><td>1.102</td><td>0.034</td><td>1.079</td><td>1.126</td></tr><tr><td>0.50</td><td>1.090</td><td>0.041</td><td>1.056</td><td>1.122</td><td>1.106</td><td>0.033</td><td>1.081</td><td>1.128</td></tr><tr><td>0.60</td><td>1.094</td><td>0.041</td><td>1.060</td><td>1.126</td><td>1.111</td><td>0.033</td><td>1.085</td><td>1.134</td></tr><tr><td>0.70</td><td>1.097</td><td>0.040</td><td>1.064</td><td>1.130</td><td>1.116</td><td>0.034</td><td>1.090</td><td>1.136</td></tr><tr><td>0.80</td><td>1.101</td><td>0.040</td><td>1.069</td><td>1.131</td><td>1.121</td><td>0.034</td><td>1.096</td><td>1.139</td></tr><tr><td>0.99</td><td>1.108</td><td>0.040</td><td>1.080</td><td>1.134</td><td>1.132</td><td>0.034</td><td>1.104</td><td>1.150</td></tr></tbody></table>

In both tables, as the parameter $\delta$ increases, the ratio $C^{\text{Pred}}/C^{\text{LP}}$ in-
creases. This trend is expected, as higher prediction errors lead to less ac-
curate scheduling decisions and therefore more sub-optimal outcomes. We
observe that the increase is slightly more pronounced in configurations with
a larger number of coflows and ports. Overall, Sincronia with predictions
demonstrates strong robustness even under severe prediction errors, as the
average degradation remains under 13.2% in the worst case.

<figure><img src="image_9.png" /><figcaption>Figure 5: Minimum, maximum and average values of $C^{\text{Pred}}/C^{\text{LP}}$ as a function of $\delta$ for two small problem instances.</figcaption></figure>

Out of the 100 random instances generated for the configuration (L, n) = (8, 4), we chose an arbitrary one. Similarly, we chose one of the random instances generated for (L, n) = (12, 12). Figure 5 shows the minimum, maximum and mean values of $C^{\text{Pred}}/C^{\text{LP}}$ obtained over these instances as a function of $\delta$. For perfect predictions, that is for $\delta = 0$, the prediction-based Sincronia gives the same results as the clairvoyant one, as expected, and its average CCT is very close to the lower bound. Its performance degrades as $\delta$ increases, but even for the worst predictions, we always have $C^{\text{Pred}} \le 1.4 \times C^{\text{LP}}$. On average, the performance degradation with respect to the lower bound is at most 15%.

Figure 6 shows the empirical distributions of the ratio $C^{\text{Pred}}/C^{\text{LP}}$ for $(L, n) = (8, 4)$ and $\delta \in \{0, 0.5, 0.99\}$. For perfect predictions, the histogram is strongly skewed left, with a concentration at 1.0 which is expected. For the other values of $\delta$, the distribution spreads out and is more dispersed, but the distribution still remains concentrated on small values.
<figure><img src="image_10.png" /><figcaption>Figure 6: Histograms of $C^{\text{Pred}}/C^{\text{LP}}$ for $(L, n) = (8, 4)$ and for $\delta = 0$ (left), $\delta = 0.5$ (middle) and $\delta = 0.99$ (right).</figcaption></figure>

### 7.3.2 Large Instances

We now consider larger problem instances with $L = 20$ or $L = 40$. For these instances the lower bound $C^{\text{LP}}$ cannot be computed. So we choose as reference the clairvoyant Sincronia (CL) and study the ratio $C^{\text{Pred}}/C^{\text{CL}}$.

<table><caption>Table 3: Mean, standard deviation and quartiles of $C^{\text{Pred}}/C^{\text{CL}}$ for $(L, n) = (20, 10)$ and $(L, n) = (20, 20)$.</caption><thead><tr><th rowspan="2">δ</th><th colspan="4">L = 20 n = 10</th><th colspan="4">L = 20 n = 20</th></tr><tr><th>mean</th><th>std</th><th>Q1</th><th>Q3</th><th>mean</th><th>std</th><th>Q1</th><th>Q3</th></tr></thead><tbody><tr><td>0.00</td><td>1.000</td><td>0.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>0.000</td><td>1.000</td><td>1.000</td></tr><tr><td>0.10</td><td>1.002</td><td>0.007</td><td>0.999</td><td>1.005</td><td>1.000</td><td>0.008</td><td>0.998</td><td>1.004</td></tr><tr><td>0.20</td><td>1.004</td><td>0.011</td><td>0.999</td><td>1.009</td><td>1.001</td><td>0.011</td><td>0.995</td><td>1.008</td></tr><tr><td>0.30</td><td>1.005</td><td>0.014</td><td>0.997</td><td>1.013</td><td>1.002</td><td>0.014</td><td>0.992</td><td>1.011</td></tr><tr><td>0.40</td><td>1.007</td><td>0.017</td><td>0.996</td><td>1.017</td><td>1.003</td><td>0.015</td><td>0.991</td><td>1.014</td></tr><tr><td>0.50</td><td>1.009</td><td>0.019</td><td>0.997</td><td>1.019</td><td>1.005</td><td>0.017</td><td>0.992</td><td>1.018</td></tr><tr><td>0.60</td><td>1.010</td><td>0.020</td><td>0.998</td><td>1.021</td><td>1.007</td><td>0.018</td><td>0.994</td><td>1.022</td></tr><tr><td>0.70</td><td>1.013</td><td>0.022</td><td>0.998</td><td>1.027</td><td>1.010</td><td>0.019</td><td>0.996</td><td>1.027</td></tr><tr><td>0.80</td><td>1.015</td><td>0.023</td><td>0.999</td><td>1.032</td><td>1.013</td><td>0.021</td><td>0.998</td><td>1.031</td></tr><tr><td>0.99</td><td>1.019</td><td>0.025</td><td>1.003</td><td>1.038</td><td>1.020</td><td>0.022</td><td>1.004</td><td>1.039</td></tr></tbody></table>

Results are given in Table 3 for $L = 20$, and in Table 4 for $L = 40$. As expected, under perfect predictions ($\delta = 0$), all configurations yield a ratio of 1. The standard deviation remains low, with a maximum of 0.025, indicating low dispersion around the average value. We observe that even for terrible predictions ($\delta = 0.99$), the prediction-based Sincronia performs almost as well as the clairvoyant one, demonstrating the robustness of the proposed approach to prediction errors.

Figure 7 shows a monotonic degradation with increasing values of $\delta$.
<table><caption>Table 4: Mean, standard deviation and quartiles of $C^{\text{Pred}}/C^{\text{CL}}$ for $(L, n) = (40, 20)$ and $(L, n) = (40, 40)$.</caption><thead><tr><th rowspan="2">δ</th><th colspan="4">L = 40 n = 20</th><th colspan="4">L = 40 n = 40</th></tr><tr><th>mean</th><th>std</th><th>Q1</th><th>Q3</th><th>mean</th><th>std</th><th>Q1</th><th>Q3</th></tr></thead><tbody><tr><td>0.00</td><td>1.000</td><td>0.000</td><td>1.000</td><td>1.000</td><td>1.000</td><td>0.000</td><td>1.000</td><td>1.000</td></tr><tr><td>0.10</td><td>0.999</td><td>0.009</td><td>0.997</td><td>1.003</td><td>1.001</td><td>0.008</td><td>0.995</td><td>1.004</td></tr><tr><td>0.20</td><td>1.000</td><td>0.011</td><td>0.995</td><td>1.005</td><td>1.001</td><td>0.012</td><td>0.995</td><td>1.007</td></tr><tr><td>0.30</td><td>1.001</td><td>0.013</td><td>0.995</td><td>1.006</td><td>1.003</td><td>0.013</td><td>0.996</td><td>1.009</td></tr><tr><td>0.40</td><td>1.003</td><td>0.015</td><td>0.995</td><td>1.009</td><td>1.005</td><td>0.014</td><td>0.996</td><td>1.012</td></tr><tr><td>0.50</td><td>1.004</td><td>0.016</td><td>0.995</td><td>1.010</td><td>1.007</td><td>0.015</td><td>0.998</td><td>1.015</td></tr><tr><td>0.60</td><td>1.006</td><td>0.016</td><td>0.998</td><td>1.014</td><td>1.010</td><td>0.016</td><td>1.001</td><td>1.018</td></tr><tr><td>0.70</td><td>1.009</td><td>0.016</td><td>0.998</td><td>1.017</td><td>1.013</td><td>0.016</td><td>1.003</td><td>1.022</td></tr><tr><td>0.80</td><td>1.011</td><td>0.017</td><td>1.000</td><td>1.019</td><td>1.016</td><td>0.017</td><td>1.005</td><td>1.026</td></tr><tr><td>0.99</td><td>1.016</td><td>0.019</td><td>1.003</td><td>1.027</td><td>1.023</td><td>0.018</td><td>1.012</td><td>1.034</td></tr></tbody></table>

across the different configurations, which confirms the intuitive and expected behavior: larger prediction errors lead to worse scheduling outcomes. Nevertheless, the prediction-based Sincronia maintains high robustness even under very poor predictions, as the average degradation is less than 3%.

Figure 8 shows the empirical distributions of the ratio $C^{\text{Pred}}/C^{\text{CL}}$ for $(L, n) = (40, 40)$ and $\delta \in \{0, 0.5, 0.99\}$. As $\delta$ increases, the distribution widens and shifts slightly to the right, indicating performance degradation. However, the overall deviation remains limited, demonstrating the robustness of the prediction-based scheduling approach. Note that there are also some rare cases where the prediction-based algorithm performs even better than the clairvoyant one (the clairvoyant Sincronia although usually very efficient, is not optimal).

## 7.4 Online Results

The procedure for generating the online instances is similar to the one described in Section 7.1. We consider two different values for the number of ports ($L = 20$ and $L = 40$), two different values for the number of coflows ($n = 50$ and $n = 100$), and 100 random instances for each of the four combinations of $n$ and $L$.

The arrival rate is calibrated so that the workload injected by incoming coflows matches the average service capacity of the system. Specifically, the parameter $p$ of the geometric inter-arrival distribution is chosen as the inverse of the average workload contributed by a single coflow, where this workload is measured as the product of (i) the average processing time re-
<figure><img src="image_11.png" /><figcaption>Figure 7: Average values of $C^{\text{Pred}}/C^{\text{CL}}$ for different prediction errors. The number of ports $L$ and the number $N$ of coflows are indicated on the x-axis.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 8: Histograms of $C^{\text{Pred}}/C^{\text{CL}}$ for $(L, n) = (40, 40)$ and for $\delta = 0$ (left), $\delta = 0.5$ (middle) and $\delta = 0.99$ (right).</figcaption></figure>

quired by a coflow on a port and (ii) the average number of ports simultaneously used by a coflow. This choice ensures that, on average, the system operates under a balanced load regime. With this calibration, we obtain $p = 0.25$ for $L = 20$, which corresponds to a mean inter-arrival time of 4 time slots and a standard deviation of approximately 3.46 time slots, and $p = 0.45$ for $L = 40$ yielding a mean inter-arrival time of about 2.22 time slots and a standard deviation of 1.65.

We compare the average CCT $C^{\text{A-SPPred}}$ obtained with our online anticipated prediction-based algorithm against the average CCT $C^{\text{CL}}$ obtained with a clairvoyant Sincronia, which would know both the exact flow sizes and the coflow arrival times in advance.

As can be seen from Table 5, the ratio $C^{\text{A-SPPred}}/C^{\text{CL}}$ increases sharply as the prediction error increases. Under perfect predictions, our algorithm
<table><caption>Table 5: Mean, standard deviation and quartiles of $C^{A-SPPred}/C^{CL}$ for $L = 20$ and $n \in \{50, 100\}$.</caption><thead><tr><th rowspan="2">δ</th><th colspan="4">L = 20 n = 50</th><th colspan="4">L = 20 n = 100</th></tr><tr><th>mean</th><th>std</th><th>Q1</th><th>Q3</th><th>mean</th><th>std</th><th>Q1</th><th>Q3</th></tr></thead><tbody><tr><td>0.00</td><td>1.576</td><td>0.083</td><td>1.525</td><td>1.629</td><td>1.505</td><td>0.064</td><td>1.473</td><td>1.552</td></tr><tr><td>0.10</td><td>1.638</td><td>0.089</td><td>1.582</td><td>1.694</td><td>1.586</td><td>0.065</td><td>1.539</td><td>1.628</td></tr><tr><td>0.20</td><td>1.749</td><td>0.091</td><td>1.682</td><td>1.813</td><td>1.735</td><td>0.070</td><td>1.687</td><td>1.786</td></tr><tr><td>0.30</td><td>1.947</td><td>0.105</td><td>1.873</td><td>2.020</td><td>1.971</td><td>0.081</td><td>1.925</td><td>2.027</td></tr><tr><td>0.40</td><td>2.238</td><td>0.126</td><td>2.155</td><td>2.331</td><td>2.294</td><td>0.097</td><td>2.245</td><td>2.361</td></tr><tr><td>0.50</td><td>2.653</td><td>0.155</td><td>2.554</td><td>2.758</td><td>2.739</td><td>0.117</td><td>2.669</td><td>2.828</td></tr><tr><td>0.60</td><td>3.254</td><td>0.195</td><td>3.134</td><td>3.387</td><td>3.385</td><td>0.147</td><td>3.288</td><td>3.488</td></tr><tr><td>0.70</td><td>4.250</td><td>0.261</td><td>4.098</td><td>4.419</td><td>4.450</td><td>0.199</td><td>4.324</td><td>4.594</td></tr><tr><td>0.80</td><td>6.232</td><td>0.399</td><td>6.009</td><td>6.498</td><td>6.575</td><td>0.311</td><td>6.385</td><td>6.805</td></tr><tr><td>0.99</td><td>118.791</td><td>8.761</td><td>113.778</td><td>124.908</td><td>127.843</td><td>7.346</td><td>122.870</td><td>133.349</td></tr></tbody></table>

achieves on average an empirical competitive ratio around 1.58 (resp. 1.51) compared to the clairvoyant offline Sincronia for $n = 50$ (resp. $n = 100$) coflow arrivals. But this empirical competitive ratio becomes 118.8 (resp. 127.8) for $\delta = 0.99$. Note that in the latter case, the size of execution intervals is multiplied by a factor $\nu = 199$ to account for the uncertainty on flow sizes.

<figure><img src="image_13.png" /><figcaption>Figure 9: Minimum, maximum and mean ratio values of $C^{A-SPPred}/C^{CL}$ as a function of $\delta$ from one instance for $(L, n) = (40, 50)$ (left) and $(L, n) = (40, 100)$ (right)</figcaption></figure>

Figure 9 shows the minimum, maximum, and mean ratio values of the ratio $C^{A-SPPred}/C^{CL}$ for one of the 100 random instances generated for the configurations with $L = 40$ and $n = 50$ (left) or $n = 100$ (right). For both instances, the ratio is below 2 for perfect predictions and remains under 7 for $\delta \le 0.8$ (that is, for $\nu \le 9$). We note however the exponential trend of the performance degradation as $\delta$ increases.
<figure><img src="image_14.png" /><figcaption>Figure 10: Histograms of $C^{A-SPPred}/C^{CL}$ in the online setting for (L, n) = (40, 100) and for $\delta \in \{0, 0.5, 0.99\}$.</figcaption></figure>

Figure 10 presents the empirical distributions of the ratio $C^{A-SPPred}/C^{CL}$ for three values of $\delta$ in the online setting with $L = 40$ ports and $n = 100$ coflows arriving over time. For perfect predictions, A-SPPred provides solutions whose average CCT is at most 1.9× that of those obtained with the clairvoyant Sincronia, whereas the theoretical upper bound is 20 in that case. For $\delta = 0.99$, the average CCTs can be as high as 150× those obtained with the clairvoyant Sincronia. Nevertheless, this is to be compared with the theoretical upper bound which is $16\nu + 4\nu^2 = 161,588$ for $\nu = 199$.

<figure><img src="image_15.png" /><figcaption>Figure 11: Values of $C^{SPPred}/C^{CL}$ and $C^{A-SPPred}/C^{CL}$ as functions of $\delta$ for $L = 20$ and $n \in \{50, 100\}$. Shaded areas indicate the min-max range across all the 100 instances. Values of $C^{SPCL}/C^{CL}$ and $C^{A-SPCL}/C^{CL}$ are also shown.</figcaption></figure>

Figure 11 shows a clear and consistent performance gap between the classical SP scheme and its anticipative variant A-SP for $L = 20$ and
$n \in \{50, 100\}$. For all values of $\delta \le 0.8$, **A-SPPred** achieves significantly lower average CCT than **SPPred**, providing a performance which remains fairly close to that of the offline clairvoyant **Sincronia**. For $\delta \le 0.6$, it even outperforms the clairvoyant SP on average. We also note that the performance degradation induced by increasing prediction error is markedly milder for **A-SPPred** than for **SPPred**. The superiority of the anticipative scheme is confirmed for $L = 40$ and $n \in \{50, 100\}$, as shown in Figure 12.

<figure><img src="image_16.png" /><figcaption>Figure 12: Values of $C^{SPPred}/C^{CL}$ and $C^{A-SPPred}/C^{CL}$ as functions of $\delta$ for $L = 40$ and $n \in \{50, 100\}$. Shaded areas indicate the min-max range across all the 100 instances. Values of $C^{SPCL}/C^{CL}$ and $C^{A-SPCL}/C^{CL}$ are also shown.</figcaption></figure>

# 8 Conclusion

Our framework for online coflow scheduling leverages unreliable predictions on flow sizes to provide worst-case performance guarantees. Numerical results show that the results obtained in practice are much better than what the worst-case bounds suggest. For large instances and moderate inaccuracy of predictions, the prediction-based online algorithm performs almost as well as the one feed with exact flow sizes as inputs. Further investigation is required to verify whether these findings hold under alternative prediction-error models. This is a subject to be explored in future research.
References

[1] Saksham Agarwal and Rachit Agarwal. Coflow workload generator. https://github.com/sincronia-coflow/workload-generator.

[2] Saksham Agarwal, Rachit Agarwal, Shijin Rajakrishnan, David Shmoys, Akshay Narayan, and Amin Vahdat. Sincronia: Near-Optimal Network Design for Coflows. In *Proc. ACM SIGCOMM*, pages 16–29, 2018.

[3] Saba Ahmadi, Samir Khuller, Manish Purohit, and Sheng Yang. On Scheduling Coflows. *Algorithmica*, 82(12):3604–3629, December 2020.

[4] Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Yael Tauman Kalai, editor, *ITCS 2023*, volume 251 of *LIPIcs*, pages 11:1–11:22, 2023.

[5] Akhil Bhimaraju, Debanuj Nayak, and Rahul Vaze. Non-clairvoyant scheduling of coflows. In *WiOPT 2020*, pages 81–88, Volos, Greece, June 2020. IEEE.

[6] Olivier Brun, Balakrishna J. Prabhu, and Oumayma Haddaji. Prediction-based coflow scheduling. In *2024 22nd International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt)*, pages 185–192, 2024.

[7] Zhi-Long Chen and Nicholas G. Hall. Supply chain scheduling: Conflict and cooperation in assembly systems. *Discrete Applied Mathematics*, 55(6):1072–1089, 2007.

[8] Woo-Hyung Cho, Shane G. Henderson, and David B. Shmoys. Scheduling with predictions. *CoRR*, abs/2212.10433, 2022.

[9] Mosharaf Chowdhury and Ion Stoica. Coflow: A networking abstraction for cluster applications. In *Proc. ACM HotNets*, pages 31–36, Redmond, Washington, 2012.

[10] Mosharaf Chowdhury and Ion Stoica. Efficient coflow scheduling without prior knowledge. *SIGCOMM Comput. Commun. Rev.*, 45(4):393–406, August 2015.

[11] Mosharaf Chowdhury, Matei Zaharia, Justin Ma, Michael I. Jordan, and Ion Stoica. Managing data transfers in computer clusters with
orchestra. In *Proceedings of the ACM SIGCOMM 2011 Conference*, SIGCOMM '11, pages 98–109, New York, NY, USA, 2011. Association for Computing Machinery.

[12] Mosharaf Chowdhury, Yuan Zhong, and Ion Stoica. Efficient Coflow Scheduling with Varys. In *Proc. ACM SIGCOMM*, pages 443–454, 2014.

[13] Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified data processing on large clusters. *Commun. ACM*, 51(1):107–113, 2008.

[14] Yuanxiang Gao, Hongfang Yu, Shouxi Luo, and Shui Yu. Information-agnostic coflow scheduling with optimal demotion thresholds. In *IEEE ICC*, 2016.

[15] Naveen Garg, Amit Kumar, and Vinayaka Pandit. Order scheduling models: Hardness and algorithms. In V. Arvind and Sanjiva Prasad, editors, *FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science*, pages 96–107, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.

[16] Sungjin Im. Non-clairvoyant scheduling with predictions. In *Proc. International Symposium on Artificial Intelligence and Mathematics 2022 (ISAIM 2022)*, Fort Lauderdale, Florida, USA, Jan 3-5, 2022.

[17] Akshay Jajoo, Y. Charlie Hu, and Xiaojun Lin. A Case for Sampling-Based Learning Techniques in Coflow Scheduling. *IEEE/ACM Trans. Netw.*, 30(4):1494–1508, January 2022.

[18] Akshay Jajoo, Y. Charlie Hu, Xiaojun Lin, and Nan Deng. Slearn: A case for task sampling based learning for cluster job scheduling. *IEEE Transactions on Cloud Computing*, 11(3):2664–2680, July 2023.

[19] Samir Khuller, Jingling Li, Pascal Sturmfels, Kevin Sun, and Prayaag Venkat. Select and permute: An improved online framework for scheduling to minimize weighted completion time. *Theoretical Computer Science*, 795:420–431, 2019.

[20] Joseph Y.-T. Leung, Haibing Li, and Michael Pinedo. Scheduling orders for multiple product types to minimize total weighted completion time. *Discrete Applied Mathematics*, 155(8):945–970, 2007.
[21] Libin Liu, Hong Xu, Chengxi Gao, and Peng Wang. Bottleneck-aware coflow scheduling without prior knowledge. In *IEEE INFOCOM Workshops 2020*, pages 50–55, 2020.

[22] Youcef Magnouche, Sébastien Martin, Jérémie Leguay, Francesco De Pellegrini, Rachid Elazouzi, and Cédric Richier. Branch-and-benders-cut algorithm for the weighted coflow completion time minimization problem. In *Proc.INOC 2022, Aachen, Germany*, 2022.

[23] Monaldo Mastrolilli, Maurice Queyranne, Andreas S. Schulz, Ola Svensson, and Nelson A. Uhan. Minimizing the sum of weighted completion times in a concurrent open shop. *Oper. Res. Lett.*, 38(5):390–395, 2010.

[24] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In Thomas Vidick, editor, *ITCS 2020*, volume 151 of *LIPIcs*, pages 14:1–14:18, USA, January 2020.

[25] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In *Advances in Neural Information Processing Systems*, volume 31, 2018.

[26] Zhen Qiu, Cliff Stein, and Yuan Zhong. Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks. In *Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures*, SPAA '15, pages 294–303, New York, NY, USA, June 2015. Association for Computing Machinery.

[27] M. Queyranne. Structure of a simple scheduling polyhedron. *Mathematical Programming*, 58:263–285, 1993.

[28] Laars Rohwedder and Leander Schnaars. 3.415-approximation for coflow scheduling via iterated rounding. In *52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)*, 2025.

[29] Sushant Sachdeva and Rishi Saket. Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover. In *2013 IEEE Conf. on Computational Complexity*, 2013.

[30] Andreas S. Schulz. Scheduling to minimize total weighted completion time: Performance guarantees of lp-based heuristics and lower bounds. In *Conf. on Integer Prog. and Combinatorial Optimization*, 1996.
[31] Li Shi, Yang Liu, Junwei Zhang, and Thomas Robertazzi. Coflow scheduling in data centers: routing and bandwidth allocation. *IEEE Trans. Parallel Distrib. Syst.*, 32(11):2661–2675, 2021.

[32] Shuo Wang, Jiao Zhang, Tao Huang, Jiang Liu, Tian Pan, and Yunjie Liu. A survey of coflow scheduling schemes for data center networks. *IEEE Commun. Mag.*, 56(6):179–185, 2018.

[33] Zhiliang Wang, Han Zhang, Xingang Shi, Xia Yin, Yahui Li, Haijun Geng, Qianhong Wu, and Jianwei Liu. Efficient scheduling of weighted coflows in data centers. *IEEE Trans. on Par. and Dist. Systems*, 30(9), 2019.

[34] Matei Zaharia, Mosharaf Chowdhury, Michael J Franklin, Scott Shenker, Ion Stoica, et al. Spark: Cluster computing with working sets. *HotCloud*, 10(10-10):95, 2010.

[35] Tong Zhang, Fengyuan Ren, Ran Shu, and Bo Wang. Scheduling coflows with incomplete information. In *2018 IEEE/ACM 26th International Symposium on Quality of Service (IWQoS)*, pages 1–10, 2018.

# A Minimum Unscheduled Weight Problem

## A.1 A simple result on the optimal value of the MUWP problem in the COS environment

We prove a simple result about the optimal values of two instances of the MUWP problem with the same deadline when the job set of one of the instance is a subset of the job set of the other instance.

**Lemma 6.** Consider two instances of problem (MUWP) with the same deadline *D* and job sets *J* and *J'* such that *J* ⊆ *J'*. Then $W^*(J, D) \le W^*(J', D)$.

*Proof.* Consider an optimal solution for the instance with job set *J'* and let *S'* be the set of jobs selected in this optimal solution. Define $S = J \cap S'$ and note that *S* is a feasible for the instance with job set *J*, so that $W(J \setminus S) \ge W^*(J, D)$. We clearly have
$$ 
\begin{align*}
j \in J \setminus S &\implies j \in J \text{ and } j \notin J \cap S', \\
&\implies j \in J \text{ and } j \notin S', \\
&\implies j \in J' \text{ and } j \notin S', \\
&\implies j \in J' \setminus S',
\end{align*}
$$

so that $J \setminus S \subseteq J' \setminus S'$. It then follows that

$$ 
\begin{align*}
W^*(J', D) = W(J' \setminus S') &= \sum_{j \in J' \setminus S'} w_j \\
&\geq \sum_{j \in J \setminus S} w_j \\
&= W(J \setminus S) \geq W^*(J, D).
\end{align*}
$$

□

## A.2 Proofs of results in Section 3.3

In this section, we present the proofs of Lemmata 1 and 3. We begin with the proof of Lemma 1, which can also be found in [15].

*Proof of Lemma 1.* Clearly, $S'$ is a feasible solution of Problem (MUWP) for the instance defined by the job set $R'$ and the deadline $2D$. Indeed, by definition of $S'$, we have $2x_k^* \geq 1$ for all $k \in S'$, so that

$$ \sum_{k \in S'} p_{\ell,k} \leq 2 \sum_{k \in S'} p_{\ell,k} x_k^* \leq 2 \sum_{k \in R'} p_{\ell,k} x_k^* \leq 2D, $$

for all $\ell \in \mathcal{L}$. Moreover, as $1 - x_k^* > \frac{1}{2}$ for all $k \notin S'$, we have

$$ 
\begin{align*}
W(R' \setminus S') &= \sum_{k \in R' \setminus S'} w_k \leq 2 \sum_{k \in R' \setminus S'} w_k (1 - x_k^*) \\
&\leq 2 \sum_{k \in R'} w_k (1 - x_k^*) \\
&\leq 2 W^*(R', D),
\end{align*}
$$

where the last inequality follows from the fact that $x^*$ is an optimal solution for a relaxation of the original integer-programming problem (MUWP). □
We now present the proof of Lemma 3, which follows along the same lines as the one of Lemma 5 in [19].

*Proof of Lemma 3.* Let $I$ be the instance of the MUWP problem (C-MUWP) with coflow set $R$ and deadline $D$, and let $I'$ be the corresponding instance in the COS environment with job set $R'$ and the same deadline. Define $W'$ as the optimal unscheduled weight for the MUWP on $I'$, and define $W$ similarly. As shown in Lemma 4 of [19], we have $W' \le W$.

With the algorithm of Garg [15], we can obtain a subset of jobs $S'$ such that the last job on each and every machine $\ell$ finishes by time $2D$, that is $\sum_{k \in S'} p_{\ell,k} \le 2D$, and the total unscheduled weight is at most $2W'$, that is, $\sum_{k \in R' \setminus S'} w_k \le 2W'$. Consider any schedule for the jobs in $S'$ without idle time such that jobs are processed in the same order on each machine. Under this schedule, the last job $k$ to finish on each machine $\ell$ has a completion time $C'_k$ such that $C'_k \le 2D$. Let $S$ be the set of coflows in $I$ corresponding to the jobs in $S'$, and consider a priority order such that the coflows in $S$ complete in the same order as the corresponding jobs in $S'$ under the above-mentioned schedule. As shown in [2] (see Lemma 3), under any rate allocation policy that is work conserving, preemptive and preserves this completion order, coflow $k$ in instance $I$ is the last one to finish on every port and its completion time $C_k$ is such that $C_k \le 2C'_k \le 4D$. As Ahmadi's algorithm (or, equivalently, the greedy rate allocation of Sincronia) satisfies these properties, we conclude that all jobs in $S$ complete by time $4D$. $\square$

### A.3 Proof of Lemma 5

Before proving Lemma 5, we first establish an inequality between the optimal total unscheduled weight obtained by solving the MUWP problem with predicted processing times and the one that would be obtained if the actual processing times were known.

**Lemma 7.** Let $R \subseteq J$ be a subset of jobs. Define $\hat{W}^*(R, D)$ as the optimal value of the MUWP for the instance defined by the set of jobs $R$, the predicted processing times $\{\hat{p}_{i,j}\}_{i \in M, j \in R}$ and the deadline $D$. Let $W^*(R, D)$ be the optimal value that would be obtained with the actual processing times $\{p_{i,j}\}_{i \in M, j \in R}$ for the same set of jobs and the same deadline. Provided that condition (18) is satisfied, we have

$$ \hat{W}^*(R, \mu_{max}D) \le W^*(R, D) \le \hat{W}^*(R, \mu_{min}D) \quad (24) $$
*Proof.* We first prove the inequality $\hat{W}^*(R, \mu_{max}D) \le W^*(R, D)$. Let $S^*$ be an optimal solution of MUWP for the instance defined by the actual processing times $p_{i,j}$. We thus have $\sum_{j \in S^*} p_{i,j} \le D$. As $p_{i,j} \ge \hat{p}_{i,j}/\mu_{max}$ for all $i \in M$ and $j \in R$, we have $\sum_{j \in S^*} \hat{p}_{i,j} \le \mu_{max} D$, which implies that $S^*$ is a feasible solution for the instance defined by the predicted processing times and the deadline $\mu_{max}D$. Hence, $\hat{W}^*(R, \mu_{max}D) \le W^*(R, D)$, as claimed.

We now show the other inequality. To this end, let $\hat{S}^*$ be an optimal solution of MUWP for the instance defined by the predicted processing times and the deadline $\mu_{min}D$. We thus have $\sum_{j \in \hat{S}^*} \hat{p}_{i,j} \le \mu_{min}D$. As $\mu_{min}p_{i,j} \le \hat{p}_{i,j}$ for all $i \in M$ and $j \in R$, we have $\sum_{j \in \hat{S}^*} p_{i,j} \le D$, which shows that $\hat{S}^*$ is a feasible solution for the MUWP instance defined by the actual processing times and the deadline $D$. It follows that $W^*(R, D) \le \hat{W}^*(R, \mu_{min}D)$. $\square$

Consider now an $(\alpha, \beta)$-approximation algorithm $A$ for the MUWP problem. As already mentioned, when executed with a set of jobs $R$ and a deadline $D$, this algorithm provides a subset of jobs $S^A \subseteq R$ such that all jobs in $S^A$ can be completed in an interval of length $\alpha D$. Moreover, it is guaranteed that

$$W^A(R, \alpha D) = \sum_{j \in R \setminus S^A} w_j \le \beta W^*(R, D).$$

The quantity $W^A(R, \alpha D)$ represents the total unscheduled weight at time $\alpha D$ with algorithm $A$, and, as all jobs in $S^A$ have been completed at that time, it corresponds to the total weight of the jobs in $R \setminus S^A$. As in our case jobs are selected on the basis of predicted processing times, we need to adapt the above guarantees. Lemma 5 provides the desired result.

*Proof of Lemma 5.* As algorithm $A$ is an $(\alpha, \beta)$-approximation, all jobs could be completed in an interval of length $\alpha \mu_{max} D$ if their processing times were equal to their predicted processing times, that is,

$$\sum_{j \in \hat{S}^A} \hat{p}_{i,j} \le \alpha \mu_{max} D.$$

As $\mu_{min}p_{i,j} \le \hat{p}_{i,j}$ for all $i \in M$ and $j \in R$, it implies that

$$\sum_{j \in \hat{S}^A} p_{i,j} \le \alpha \nu D,$$

so that all jobs in $\hat{S}^A$ can be completed in an interval of length $\alpha \nu D$, as claimed. Moreover, if $A$ is an $(\alpha, \beta)$-approximation, we also have
$$W(R \setminus \hat{S}^A) \leq \beta \hat{W}^*(R, \mu_{\max} D) \leq \beta W^*(R, D),$$

where the second inequality follows from Lemma 7. □

# B Proofs of Results in Section 5

## B.1 Proof of Lemma 4

*Proof of Lemma 4.* Let $\hat{C}_k$ and $\hat{y}_{\ell,S}$ be the primal and dual variables, respectively, obtained after the execution of Algorithm 1 with the predictions as inputs. We then have for each coflow $k$

$$\sum_{\ell \in \mathcal{L}} \hat{p}_{\ell,k} \sum_{S \subseteq \mathcal{C}, k \in S} \hat{y}_{\ell,S} = w_k.$$

Consider the dual variables $y_{\ell,S}$ defined as follows: $y_{\ell,S} = \mu_{\min} \hat{y}_{\ell,S}$ for all $\ell \in \mathcal{L}$ and all $S \subseteq \mathcal{C}$. We then have

$$\begin{align*}
\sum_{\ell \in \mathcal{L}} p_{\ell,k} \sum_{S \subseteq \mathcal{C}, k \in S} y_{\ell,S} &= \sum_{\ell \in \mathcal{L}} p_{\ell,k} \sum_{S \subseteq \mathcal{C}, k \in S} \mu_{\min} \hat{y}_{\ell,S}, \\
&\leq \sum_{\ell \in \mathcal{L}} \hat{p}_{\ell,k} \sum_{S \subseteq \mathcal{C}, k \in S} \hat{y}_{\ell,S}, \\
&= w_k,
\end{align*}$$

which shows that the dual variables $(y_{\ell,S})_{\ell \in \mathcal{L}, S \subseteq \mathcal{C}}$ provide a feasible solution to problem D. It also follows from the proof of Theorem 5 in [2] that

$$\begin{align*}
\sum_{k \in \mathcal{C}} w_k \hat{C}_k &\leq 2 \sum_{t=1}^{n} \hat{f}_{b(t)}(S(t)) \hat{y}_{b(t),S(t)}, \\
&\leq \frac{2}{\mu_{\min}} \sum_{t=1}^{n} \hat{f}_{b(t)}(S(t)) y_{b(t),S(t)},
\end{align*}$$

In addition,
$$
\begin{align*}
\hat{f}_{\ell}(S) &= \frac{1}{2} \sum_{k \in S} (\hat{p}_{\ell,k})^2 + \frac{1}{2} \left( \sum_{k \in S} \hat{p}_{\ell,k} \right)^2, \\
&\leq \frac{1}{2} \sum_{k \in S} (\mu_{max} p_{\ell,k})^2 + \frac{1}{2} \left( \sum_{k \in S} \mu_{max} p_{\ell,k} \right)^2, \\
&= \mu_{max}^2 f_{\ell}(S),
\end{align*}
$$

for all $\ell \in \mathcal{L}$ and all $S \subseteq \mathcal{C}$, so that

$$
\begin{align*}
\sum_{k \in \mathcal{C}} w_k \hat{C}_k &\le \frac{2}{\mu_{min}} \mu_{max}^2 \sum_{t=1}^n f_{b(t)}(S(t)) y_{b(t),S(t)}, \\
&\le \frac{2 \mu_{max}^2}{\mu_{min}} \sum_{\ell \in \mathcal{L}} \sum_{S \subseteq \mathcal{C}} f_{\ell}(S) y_{\ell,S}^*, \\
&\le \frac{2 \mu_{max}^2}{\mu_{min}} \sum_{k \in \mathcal{C}} w_k C_k^{OPT},
\end{align*}
$$

where the first inequality follows from the feasibility of $(y_{\ell,S})_{\ell \in \mathcal{L}, S \subseteq \mathcal{C}}$ as a
solution to problem D, and the last one follows from the weak duality theorem.
□

B.2 Proof of Proposition 1

*Proof of Proposition 1.* We assume that $\hat{C}_1 \le \hat{C}_2 \le \dots \le \hat{C}_n$, that is, Sicronia with predictions as inputs schedules coflows in the order $1, 2, \dots, n$. Let $\tilde{C}_k$ be the actual completion time of coflow $k \in \mathcal{C}$ when coflows are scheduled in that order. It follows from Lemma 2 in [3] (see also the corresponding result on the Greedy allocation in [2]) that

$$
\tilde{C}_j \le 2 \max_{\ell \in \mathcal{L}} \sum_{k=1}^{j} p_{\ell,k}, \quad \text{for all } j \in \mathcal{C}.
$$

When coflow *j* is scheduled by Algorithm 1, the set of unscheduled
coflows is {1, 2, ..., *j*} and the predicted completion time of coflow *j* is set
to

$$
\hat{C}_j = \max_{\ell \in \mathcal{L}} \sum_{k=1}^{j} \hat{p}_{\ell,k} \geq \mu_{min} \times \max_{\ell \in \mathcal{L}} \sum_{k=1}^{j} p_{\ell,k}.
$$
It thus follows that $\tilde{C}_j \le 2 \times \hat{C}_j / \mu_{min}$, so that

$$ \sum_{j \in C} w_j \tilde{C}_j \le \frac{2}{\mu_{min}} \sum_{j \in C} w_j \hat{C}_j, \\ \le 4 \left( \frac{\mu_{max}}{\mu_{min}} \right)^2 \sum_{j \in C} w_j C_j^{OPT}, $$

where the last inequality follows from Lemma 4. □

## B.3 Proof of Proposition 2

*Proof of Proposition 2.* For a given order $\sigma$, we have the following inequality bounding the completion times of coflows:

$$ C_{\sigma(k)} \le 2 \max_{\ell} \sum_{j=1}^{k} p_{\ell, \sigma(j)} \quad (25) $$

from which we can bound the numerator of the RHS of (21) as

$$ \begin{aligned} \max_{\sigma} \sum_{k} w_{\sigma(k)} C_{\sigma(k)} &\le 2 \max_{\sigma} \sum_{k} w_{\sigma(k)} \max_{\ell} \sum_{j=1}^{k} p_{\ell, \sigma(j)} \\ &\le 2 \max_{\sigma} \left( \sum_{k} w_{\sigma(k)} \right) \max_{\ell} \sum_{j=1}^{n} p_{\ell, \sigma(j)} \\ &= 2 \left( \sum_{k} w_k \right) \max_{\ell} \sum_{j=1}^{n} p_{\ell, j} \end{aligned} \quad (26) $$

For the second inequality, we have replaced $k$ by $n$ in $\sum_{j=1}^{k} p_{\ell, \sigma(j)}$ which makes this sum independent of $k$. For the equality in the third line, observe that $\sum_{j=1}^{k} p_{\ell, \sigma(j)}$ as well as the first sum are independent of the order since we are now including all the $n$ coflows and not just the first $k$. The claimed ratio now follows by substituting (26) into (21). □

## B.4 Online Concurrent Open Shop Scheduling With Predictions

We consider an online version of the concurrent open shop problem in which jobs arrive over time with unknown processing times. Nevertheless, unreliable predictions on processing times are available for scheduling jobs. More
precisely, we consider a time horizon $T$ and let $n$ be the number of jobs that arrive by $T$. We consider the set of jobs $J = \{1, \dots, n\}$ and denote by $r_j$ the time at which job $j$ is released. Each job $j$ requires processing time $p_{i,j}$ on machine $i \in M$, where $M = \{1, \dots, m\}$ is the set of machines. The actual processing times $p_{i,j}$ are unknown to the scheduler, but it is assumed that when job $j$ arrives in the system, predictions $\hat{p}_{i,j}$ on its processing times are revealed to the scheduler, which can freely use them for scheduling jobs. Throughout the paper, it is assumed that predicted and actual processing times are related by

$$ \mu_{min} p_{i,j} \leq \hat{p}_{i,j} \leq \mu_{max} p_{i,j}, \qquad (27) $$

where $\mu_{min}$ and $\mu_{max}$ are two constants known to the scheduler. Therefore, the scheduler knows that the actual processing $p_{i,j}$ of job $j$ on machine $i$ is in the interval $[\hat{p}_{i,j}/\mu_{max}, \hat{p}_{i,j}/\mu_{min}]$. In the following, we denote by $\nu$ the ratio $\mu_{max}/\mu_{min}$.

We denote by $C_{i,j}$ the completion time of job $j$ on machine $i$ and by $C_j = \max_i C_{i,j}$ its completion time. The goal is to devise an online scheduling algorithm which minimizes $\sum_{j \in J} w_j C_j$, where $w_j$ is the weight of job $j$. The algorithm must make online scheduling decisions based solely on the predicted processing times of the jobs in the system at the time at which the decision is taken. We also aim at providing performance guarantees for this algorithm with respect to an offline optimal scheduler which would know the release times $\{r_j\}_{j \in J}$ ahead of time, as well as the actual processing times $p_{i,j}$.

The online scheduling algorithm that we propose is directly inspired from [19], in which an online scheduling algorithm is proposed for the concurrent open shop problem with known processing times. We adapt this algorithm to the setting in which processing times are unknown, but unreliable predictions on them satisfying (27) are available. The algorithm takes scheduling decisions at discrete points in time $\tau_0, \tau_1, \tau_2, \dots$, where $\tau_0 = 0$ and $\tau_k = 2^{k-1}$ for $k \geq 1$. We denote by $I_k$ the time interval $[\tau_k, \tau_{k+1})$, and by $xI_k$ the time interval $[x\tau_k, x\tau_{k+1})$. Let $R_k$ be the set of jobs released but not yet scheduled before $\tau_k$ by the algorithm. The algorithm is very similar to Algorithm 2. It works as follows:

1. At time $\tau_k$, the algorithm selects a subset of jobs $S_k \subseteq R_k$ by solving an instance of the Minimum Unscheduled Weight Problem (MUWP) with predicted processing times as inputs. The instance is defined by
the set of jobs $R_k$ and by the deadline $\mu_{max} D$, where $D = \tau_{k+1} - \tau_k$:

$$ \text{Minimize} \quad \sum_{S \subseteq R_k} w_j \qquad (\text{MUWP } \tau_k) $$

s.t.

$$ \sum_{j \in S} \hat{p}_{i,j} \le \mu_{max} D, \quad \forall i \in M. \qquad (28) $$

As the above problem is NP-hard, it is solved using an $(\alpha, \beta)$-approximation, that is, an algorithm which guarantees that

$$ \sum_{j \in S_k} \hat{p}_{i,j} \le \alpha \mu_{max} D \quad \text{and} \quad \sum_{j \in R_k \setminus S_k} w_j \le \beta \hat{W}^*(R_k, \mu_{max} D), \qquad (29) $$

where $\hat{W}^*(R_k, \mu_{max} D)$ represents the optimal objective value of problem (MUWP $\tau_k$). Note that it follows from (27) that all selected jobs can be scheduled in an interval of length $\alpha \nu D$, whatever the actual processing times $p_{i,j} \in [\hat{p}_{i,j}/\mu_{max}, \hat{p}_{i,j}/\mu_{min}]$.

2. Schedule the set of jobs $S_k$ in the time interval $\alpha \nu I_k$ using an of-line scheduling algorithm which provides a $\gamma$-approximation when the actual processing times are known, and a $\gamma \nu^2$-approximation when predicted processing times are used instead. The release times of the jobs $j \in S_k$ are ignored.

The algorithm is summarized in Algorithm 3. In this algorithm, the set $A_k$ represents the set of jobs released by time $\tau_k$. The set $R_k$ of jobs released but not yet scheduled at time $\tau_k$ is obtained from $A_k$ by removing the jobs selected for scheduling at previous decision epochs. The algorithm first selects a subset of jobs among those in $R_k$ by solving problem (MUWP $\tau_k$). This is done with an $(\alpha, \beta)$-approximation. This subset of jobs is then scheduled over the interval $\alpha \nu I_k$.
**Algorithm 3** Online Job Scheduling Algorithm with Predictions as Inputs

1: $k \leftarrow 0, \tau_0 \leftarrow 0$

2: **while** $\tau_k < T$ **do**

3: $A_k = \{j \in J : r_j \le \tau_k\}$ ▷ Jobs released at time $\tau_k$

4: $R_k = A_k \cup \bigcup_{t<k} S_t^A$ ▷ Jobs released but not yet scheduled at time $\tau_k$

5: Select $S_k \subseteq R_k$ by solving (MUWP $\tau_k$) with an $(\alpha, \beta)$-approximation

6: Schedule jobs in $S_k$ over $\alpha \nu I_k$ using a $\gamma$-approximation for the offline scheduling problem

7: $k \leftarrow k + 1, \tau_k \leftarrow 2^{k-1}$

8: **end while**

We now proceed to the analysis of Algorithm 3. It closely follows the analysis done in [19] for the case of known processing times. The main difference is that relies on Lemma 5 which provides guarantees on the quality of an $(\alpha, \beta)$-approximation when it is given predictions as inputs instead of the actual processing times.

**Lemma 8.** Let $W_t$ be the total weight of jobs that complete after time $t$ in Algorithm 3 (including the weights of jobs not yet released at time $t$). Similarly, let $W_t^{OPT}$ be the total weight of jobs that complete after time $t$ in an offline optimal schedule OPT produced by a scheduler which would know both the release times and the actual processing times ahead of time. Then, for any $k \ge 0$, we have $W_{\alpha\nu\tau_{k+1}} \le \beta W_{\tau_k}^{OPT}$.

*Proof.* The term $W_{\alpha\nu\tau_{k+1}}$ corresponds to the weights of jobs that are completed after time $\alpha\nu\tau_{k+1}$ by the algorithm. At time $\tau_k$, the algorithm selects a subset of jobs $S_k \subseteq R_k$ by solving problem (MUWP $\tau_k$) with an $(\alpha, \beta)$-approximation algorithm $A$, and with as inputs the set of jobs $R_k$, their predicted processing times and the deadline $\mu_{max}(\tau_{k+1} - \tau_k) = \mu_{max}\tau_k$. As these jobs are processed from time $\alpha\nu\tau_k$ onwards, Lemma 5 implies that they are all completed at latest at time $\alpha\nu\tau_k + \alpha\nu\tau_k = \alpha\nu\tau_{k+1}$. Hence, $W_{\alpha\nu\tau_{k+1}}$ is the sum of only two terms: the weights of jobs $j \in R_k \setminus S_k$ that are not scheduled by Algorithm 3 for processing in the interval $\alpha\nu I_k$ among those in $R_k$, and the weights of jobs $j \in J \setminus A_k$ that are released after time $\tau_k$.

We first analyze the first term. It follows from Lemma 5 that

$$W(R_k \setminus S_k) \le \beta W^*(R_k, \tau_k).$$

By definition of $R_k$, we have $R_k \subseteq A_k$. According to Lemma 6, this implies that $W^*(R_k, \tau_k) \le W^*(A_k, \tau_k)$, so that
$$W(R_k \setminus S_k) \leq \beta W^*(A_k, \tau_k).$$

Now, among the jobs in $A_k$, the offline optimum OPT has scheduled only a subset $S_k^{OPT}$ in the time interval $[0, \tau_k)$, which is of length $\tau_k$. The subset $S_k^{OPT}$ is clearly a feasible solution for the instance of MUWP defined by the set $A_k$ of jobs, their actual processing times and the deadline $\tau_k$, so that $W(A_k \setminus S_k^{OPT}) \geq W^*(A_k, \tau_k)$. We thus conclude that

$$W(R_k \setminus S_k) \leq \beta W(A_k \setminus S_k^{OPT}).$$

We now consider the second term, that is, the total weight $W(J \setminus A_k)$ of jobs that are released after time $\tau_k$. Clearly, all those jobs are neither completed by Algorithm 3 by time $\alpha\nu\tau_{k+1}$, nor completed by OPT by time $\tau_k$. Hence,

$$ 
\begin{aligned}
W_{\alpha\nu\tau_{k+1}} &= W(R_k \setminus S_k) + W(J \setminus A_k), \\
&\leq \beta W(A_k \setminus S_k^{OPT}) + W(J \setminus A_k), \\
&\leq \beta \{W(A_k \setminus S_k^{OPT}) + W(J \setminus A_k)\}, \\
&= \beta W_{\tau_k}^{OPT},
\end{aligned}
$$

which concludes the proof. □

As a direct consequence of Lemma 8, we have the following result.

**Corollary 5.** Let $L$ be the smallest time index such that the offline optimal schedule OPT finishes by time $\tau_L$, that is, $C_j^{OPT} < \tau_L$ for all $j \in J$. Under the schedule produced by Algorithm 3, all jobs are completed by time $\alpha\nu\tau_{L+1}$.

*Proof.* As OPT finishes by time $\tau_L$, its unscheduled weight $W_{\tau_L}^{OPT}$ at that time is 0. It then follows from Lemma 8 that $W_{\alpha\nu\tau_{L+1}} = 0$, which implies that all jobs are completed by time $\alpha\nu\tau_{L+1}$ under the schedule produced by Algorithm 3. □

We now analyze the second step of Algorithm 3, in which it decides the order in which the jobs in $S_k$ should be processed in the interval $\alpha\nu I_k$. This is done by solving an offline scheduling problem in which the set of jobs is $S_k$, release times are ignored and the objective is to minimize the weighted completion of jobs. Predicted processing times are used instead of their unknown actual values. We assume that a feasible schedule is obtained
using a $\gamma$-approximate scheduling algorithm. We shall further assume in the following that this approach yields an approximation ratio at most $\gamma\nu^2$ with respect to an optimal schedule that would be obtained with the actual processing times.

**Lemma 9.** Given a job $j \in S_k$, let $C_j$ be its completion time under Algorithm 3 and define $\delta_j = C_j - \alpha\nu\tau_k$. Let $C_j^{OPT}$ be its completion time in the offline optimal schedule OPT. It holds that

$$ \sum_{j \in J} w_j \delta_j \leq \gamma \nu^2 \sum_{j \in J} C_j^{OPT}. $$

*Proof.* Let $C_j^{OPT}(S_k)$ be the completion time of job $j \in S_k$ in an optimal solution of the offline scheduling problem when the set of jobs is restricted to $S_k$. Similarly, let $C_j^0(S_k)$ be its completion time in an optimal solution of the offline scheduling problem, assuming that the schedule starts at time 0 and all job release times are ignored. Since the scheduling algorithm with predictions provide a $\gamma\nu^2$-approximation for the scheduling problem with $S_k$ as job set and no deadlines, we have

$$ \sum_{j \in S_k} w_j \delta_j \leq \gamma \nu^2 \sum_{j \in S_k} C_j^0(S_k). $$

With Lemma 2 in [19], it implies that

$$ \sum_{j \in S_k} w_j \delta_j \leq \gamma \nu^2 \sum_{j \in S_k} C_j^{OPT}(S_k), \qquad (30) $$

From Corollary 5, we know that under the schedule produced by Algorithm 3 all jobs are completed by time $\alpha\nu\tau_{L+1}$. This implies that $S_1, \dots, S_L$ is a partition of $J$. It then follows from (30) that

$$ \sum_{j \in J} w_j \delta_j = \sum_{k=1}^{L} \sum_{j \in S_k} w_j \delta_j \leq \gamma \nu^2 \sum_{k=1}^{L} \sum_{j \in S_k} C_j^{OPT}(S_k), $$

and it yields

$$ \sum_{j \in J} w_j \delta_j \leq \gamma \nu^2 \sum_{j \in J} w_j C_j^{OPT}, $$

as claimed.

□
Proof of Theorem 6. We first observe that

$$W_{\alpha\nu\tau_k} = \sum_{t=k}^{L} \sum_{j \in S_t} w_j,$$

for all $k \in \{0, 1, \dots, L\}$, so that

$$\sum_{j \in S_k} w_j = W_{\alpha\nu\tau_k} - W_{\alpha\nu\tau_{k+1}}, \quad k = 0, \dots, L. \qquad (31)$$

Recall that $S_1, \dots, S_L$ is a partition of $J$. Since by definition $\delta_j = C_j - \alpha\nu\tau_k$ for all $j \in S_k$, we have

$$\begin{aligned}
\sum_{j \in J} w_j C_j &= \sum_{k=0}^{L} \sum_{j \in S_k} w_j (\alpha \nu \tau_k + \delta_j), \\
&= \alpha \nu \sum_{k=1}^{L} \tau_k \sum_{j \in S_k} w_j + \sum_{j \in J} w_j \delta_j, \\
&= \alpha \nu \sum_{k=1}^{L} \tau_k (W_{\alpha \nu \tau_k} - W_{\alpha \nu \tau_{k+1}}) + \sum_{j \in J} w_j \delta_j, \\
&= \alpha \nu \left\{ \sum_{k=1}^{L} \tau_k W_{\alpha \nu \tau_k} - \sum_{k=2}^{L} \tau_{k-1} W_{\alpha \nu \tau_k} \right\} + \sum_{j \in J} w_j \delta_j, \\
&= \alpha \nu W_{\alpha \frac{\mu_{max}}{\mu_{min}}} + \alpha \nu \sum_{k=2}^{L} (\tau_k - \tau_{k-1}) W_{\alpha \nu \tau_k} + \sum_{j \in J} w_j \delta_j,
\end{aligned}$$

where the second equality follows from $\tau_0 = 0$, the third one is obtained with (31) and the fourth one follows from $W_{\alpha\nu\tau_{L+1}} = 0$. The last equality is obtained with $\tau_1 = 1$. Observing that $\tau_k - \tau_{k-1} \le 2 \times (\tau_{k-1} - \tau_{k-2})$ for all $k \ge 2$, we obtain

$$\sum_{j \in J} w_j C_j < \alpha \nu W_{\alpha \frac{\mu_{max}}{\mu_{min}}} + 2\alpha \nu \sum_{k=1}^{L-1} (\tau_k - \tau_{k-1}) W_{\alpha \nu \tau_{k+1}} + \sum_{j \in J} w_j \delta_j.$$

It is clear that $W_{\alpha \frac{\mu_{max}}{\mu_{min}}} \le W$. Together with Lemmas 8 and 9, it yields
$$ \sum_{j \in J} w_j c_j^A \le \alpha \nu W + 2\alpha \beta \nu \sum_{k=1}^{L-1} (\tau_k - \tau_{k-1}) W_{\tau_k}^{OPT} + \gamma \nu^2 \sum_{j \in J} w_j C_j^{OPT}. \quad (32) $$

On another side, we have

$$ \sum_{j \in J} w_j C_j^{OPT} = \sum_{k=0}^{L-1} \sum_{j \in S_k^{OPT}} w_j C_j^{OPT} \ge \sum_{k=1}^{L-1} \tau_k \sum_{j \in S_k^{OPT}} w_j, $$

where the inequality follows from $C_j^{OPT} \ge \tau_k$ for all $j \in S_k^{OPT}$ and $\tau_0 = 0$. Observing that

$$ W_{\tau_k}^{OPT} = \sum_{t=k}^{L-1} \sum_{j \in S_t^{OPT}} w_j, $$

we obtain

$$ \sum_{j \in S_k^{OPT}} w_j = W_{\tau_k}^{OPT} - W_{\tau_{k+1}}^{OPT}, \quad k = 0, \dots, L-1, $$

so that

$$ \begin{aligned} \sum_{j \in J} w_j C_j^{OPT} &\ge \sum_{k=1}^{L-1} \tau_k (W_{\tau_k}^{OPT} - W_{\tau_{k+1}}^{OPT}), \\ &= \sum_{k=1}^{L-1} \tau_k W_{\tau_k}^{OPT} - \sum_{k=1}^{L-1} \tau_{k-1} W_{\tau_k}^{OPT}, \\ &= \sum_{k=1}^{L-1} (\tau_k - \tau_{k-1}) W_{\tau_k}^{OPT}, \end{aligned} \quad (33) $$

where the first equality is obtained with $\tau_0 = 0$ and $W_{\tau_L}^{OPT} = 0$. Combining (32) and (33), we finally obtain

$$ \sum_{j \in J} w_j C_j < \alpha \nu W + \{2\alpha\beta\nu + \gamma\nu^2\} \sum_{j \in J} w_j C_j^{OPT}. $$

□
**Remark 3.** Under perfect predictions, i.e. $\mu_{\min} = \mu_{\max} = 1$. Algorithm 3 achieves a $(2\alpha\beta + \gamma)$-competitive ratio, as the online algorithm proposed in [19] for known processing times.

As we have seen, [15] proposed a polynomial-time (2,2)-approximation for Problem (MUWP) (see Lemma 1). Several 2-approximation algorithms were proposed in [7, 15, 20, 23] for the offline concurrent open shop model with identical job release times. Algorithm 3 can be implemented using the (2,2)-approximation for (MUWP) in its first phase, and one of the 2-approximation algorithms mentioned above for the offline scheduling problem. In that case, it follows from Theorem 6 that Algorithm 3 is a $(8+2\nu)\nu$-competitive polynomial-time algorithm.