## 3 Materials and Methods
### Workflow Scheduling
```
Input: Workflow \(\mathcal{W}=(\mathcal{T},\mathcal{A})\), prediction model \(\mathcal{M}\) Output: A list of stages \(\mathcal{S}\)
1\(\mathcal{S}\leftarrow\emptyset\)
2\(\mathcal{Q}\leftarrow\langle t:|\mathcal{N}^{in}(t)|,\;\forall t\in\mathcal{T}\rangle\)
3\(\mathcal{P}_{mem}\leftarrow\langle t:\mathcal{M}.\textit{predict\_mem}(t,d_{ t}),\;\forall t\in\mathcal{T}\rangle\)\(\triangleright\)Memoryprediction for each task in \(\mathcal{T}\)
4\(\mathcal{P}_{time}\leftarrow\langle t:\mathcal{M}.\textit{predict\_ time}(t,d_{t}),\;\forall t\in\mathcal{T}\rangle\)\(\triangleright\)Time prediction for each task in \(\mathcal{T}\)
5\(\mathcal{T}\leftarrow\textit{sort\_decreasing}(\mathcal{T},\mathcal{P}_{mem})\)
6 while\(\mathcal{T}\
eq\emptyset\)do
7\(\mathcal{T}_{free}\leftarrow\{t\in\mathcal{T}\;|\;\mathcal{Q}[t]==0\}\)
8\(t\leftarrow\textit{get\_first}(\mathcal{T}_{free})\)
9\(\textit{mem}_{t}\leftarrow\textit{P}_{mem}[t]\)
10\(S_{sel}\leftarrow\{s_{i}\in\mathcal{S}\;|\;mem_{t}\leq C_{s_{i}}\;\text{and}\; \
exists(t^{\prime},t)^{n}\in\mathcal{A},n>0,\forall t^{\prime}\in s_{i}\cup s _{i+1}\cup\cdots\cup s_{k}\}\)
11 if\(\mathcal{S}_{sel}\
eq\emptyset\)then
12\(\textit{duration}\leftarrow\langle s:\max_{t^{\prime}\in\mathcal{P}_{time}[t^{ \prime}]},\forall s\in\mathcal{S}_{sel}\rangle\)
13\(\textit{increase}\leftarrow\langle s:\max\{\mathcal{P}_{time}[t],\textit{duration}[s]\}-\textit{duration}[s],\forall s\in\mathcal{S}_{sel}\rangle\)
14\(s\leftarrow\textit{argmin}_{s^{\prime}\in\mathcal{S}_{sel}}\textit{increase}\)
15\(C_{s}\leftarrow\mathbb{C}_{s}-\textit{mem}_{t}\)
16\(s\gets s\cup\{t\}\)
17
18 else
19\(s\leftarrow\emptyset\)
20\(s\leftarrow\sup\{t\}\)
21\(C_{s}\leftarrow C_{s}-\textit{mem}_{t}\)
22\(\mathcal{S}\leftarrow\mathcal{S}\cup\{s\}\)
23\(\mathcal{T}\leftarrow\mathcal{T}\setminus\{t\}\)
24//Consolidation step
25\(\mathcal{S}_{mov}\leftarrow\{s\in\mathcal{S}\;|\;\mathcal{N}^{out}(t)|==0,\; \forall t\in s\}\)
26 if\(\mathcal{S}_{mov}\
eq\emptyset\)then
27 for\(s_{i}\in\mathcal{S}_{mov}\)do
28 for\(s_{i}\in\mathcal{S}\;|\;j>i\)do
29\(\textit{mem}_{s_{i}\cup s_{j}}\leftarrow\sum\limits_{t\in\mathbb{N}_{i}\cup s _{j}}\mathcal{P}_{mem}[t]\)
30 if\(\textit{mem}_{s_{i}\cup s_{j}}\leq\mathcal{C}\)then
31\(s_{j}\gets s_{i}\cup s_{j}\)
32\(\mathcal{S}\leftarrow\mathcal{S}\setminus s_{i}\)
33 break
34
35 return\(\mathcal{S}\)
```  
**Algorithm 1**The IIWM scheduler. If there exist one or more candidate stages \(\mathcal{S}_{sel}\) (Line 11), the best one is chosen based on the minimum marginal increase. Specifically, for each of these stages, the expected increase of the execution time is estimated (Lines 12-13), assigning the task \(t\) to the stage \(s\) with the lowest value (Lines 14-16). Otherwise (Line 17), a newly created stage is allocated for \(t\) and added to the list \(\mathcal{S}\) (Lines 18-21). Once the task \(t\) is assigned to the stage \(s\), the residual capacity \(C_{s}\) is updated (Lines 15, 20). Then, the residual in-degree for every task in the out-neighborhood of \(t\) (Line 22) is decremented by updating the dictionary \(\mathcal{Q}\), so as to allow the assignment of these tasks in the next iterations. Finally, the assigned task \(t\) is removed from the set of workflow nodes \(\mathcal{T}\) (Line 23). The second part of the algorithm (Lines 25-34) performs a consolidation step with the goal of reducing the number of allocated stages by merging some of them if possible, with a consequential improvement in the global throughput. The stages involved in the consolidation step, namely the movable stages (\(\mathcal{S}_{mov}\)), are those containing tasks with a zero out-degree (Line 25). This means that no task in such stages blocks the execution of another one, so they can be moved forward and merged with subsequent stages if the available capacity \(C\) is not exceeded. For each movable stage \(s_{i}\) (Line 27), another stage \(s_{j}\) from \(\mathcal{S}\) is searched among the subsequent ones, such that its residual capacity is enough to enable the merging with \(s_{i}\) (Lines 28-30).