# Deadline-Aware Scheduling of Mixed-Criticality Tasks

Maxime Gonthier, Kyle Chard, Ian Foster, Loris Marchal, Frédéric Vivien

## ► To cite this version:

Maxime Gonthier, Kyle Chard, Ian Foster, Loris Marchal, Frédéric Vivien. Deadline-Aware Scheduling of Mixed-Criticality Tasks. ICPP '25 - 54th International Conference on Parallel Processing, Sep 2025, San Diego, CA, United States. hal-05190988

HAL Id: hal-05190988

https://inria.hal.science/hal-05190988v1

Submitted on 29 Jul 2025

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Deadline-Aware Scheduling of Mixed-Criticality Tasks

Maxime Gonthier

mgonthier@uchicago.edu

University of Chicago, Argonne

National Laboratory

Chicago, USA

Kyle Chard

chard@uchicago.edu

University of Chicago, Argonne

National Laboratory

Chicago, USA

Ian Foster

foster@anl.gov

University of Chicago, Argonne

National Laboratory

Chicago, USA

Loris Marchal

loris.marchal@cnrs.fr

CNRS, ÉTS Montréal

Montréal, Canada

Frédéric Vivien

frederic.vivien@inria.fr

INRIA

Lyon, France

## Abstract

High-performance computing centers and cloud providers host a wide variety of workloads, ranging from routine calibration tasks with no strict timing requirements to urgent real-time computations that must be completed within hard deadlines. Traditional approaches reserve resources for high-criticality tasks or preempt and kill lower-criticality tasks when necessary, resulting in wasted compute time and longer turnaround times for lower-criticality tasks. We suggest that a better solution is to interleave the execution of critical and non-critical tasks. We formulate a bi-objective optimization problem: guarantee that all critical tasks meet their deadlines, and minimize the maximum flow, defined as the time a task spends in the system, of non-critical tasks. We introduce a formal model, derive an approximation algorithm and a lower bound, and develop several heuristics based on the approximation framework. Through extensive simulations, based on synthetic and real-world workloads, we show that one of our heuristics reduces the maximum flow of non-critical tasks by up to 14% compared to static resource partitioning.

## Keywords

Task Scheduling, Deadline Scheduling, Deadline-aware Scheduler, Processor Scheduling

## 1 Introduction

Shared computing resources, such as high-performance computing (HPC) clusters and clouds, support the execution of diverse workloads submitted by a wide range of users. One aspect in which these workloads differ is their *criticality*, or time sensitivity. Some workloads, like performance benchmarks or routine testing, are not time sensitive. While others are very time sensitive, for example, the IonOrb workflow at the DIII-D National Fusion Facility [9], which is executed after every plasma shot (10–15 minutes) to trace particle trajectories inside the tokamak and identify potentially catastrophic instrument damage.

The simplest approach to support critical tasks is to statically reserve a portion of computing resources exclusively for these workloads, assigning all other tasks to a separate set of computing resources. To protect against missed deadlines during peaks in critical task submissions, providers typically over-provision the reserved compute pool for critical tasks. However, this strategy

can lead to performance degradation for low-criticality tasks and inefficient resource utilization, as computing capacity may remain idle. A hybrid approach, adopted by computing facilities such as Argonne Leadership Computing Facility (ALCF) and National Energy Research Scientific Computing Center (NERSC), shares resources between both critical and non-critical tasks, but prioritizes execution of critical tasks. Specifically, these facilities maintain an on-demand queue for critical tasks, such as the IonOrb workflow, and a “preemptable” queue for lower-priority tasks. When critical tasks are submitted to the on-demand queue, they are immediately scheduled, often leading to the termination of non-critical tasks without prior warning. Thus, this approach sacrifices computational efficiency to ensure that critical tasks meet their deadlines.

When using preemptable resources, applications are often encouraged to use checkpointing [3], a technique commonly used to recover from failures in HPC systems. Checkpointing enables an application to save its state and thus, if it is subsequently terminated, restart from that saved state. This concept is also called *preemption* in scheduling theory. While checkpointing can increase computational efficiency by preserving the state of terminated, it relies on implementation at the application level and can introduce significant overhead, thereby further reducing computational efficiency. Further, when checkpointing is performed in response to a termination signal, it may further delay execution of critical tasks.

While strategies such as reserving dedicated resources, relying on checkpointing and restarts, or terminating running tasks can be used to meet critical task requirements, they are inherently suboptimal. These strategies often lead to resource underutilization and wasted execution time. Therefore, there is a need for new scheduling approaches that allow for a shared pool of resources to be used for mixed-criticality tasks, without the need to interrupt tasks. In this paper, we propose a scheduling-based solution to share a set of computing resources for both critical and non-critical tasks. We define the scheduling problem as a dual objective problem: we want to complete all critical tasks before their deadlines and to minimize the maximum flow, defined as the time a task spends in the system, of non-critical tasks. Crucially, we operate in a non-preemptive, non-checkpointing, and online setting in order to reflect the reality of many production HPC systems where maintaining dedicated resources is not feasible, checkpointing is not possible, task termination is too costly, and where task arrival times cannot be predicted.

Our contributions are as follows:
(1) We introduce a formal model for mixed-criticality, online, non-preemptive scheduling on identical multiprocessors.

(2) We derive a 1/2-approximation algorithm for the problem of scheduling the maximum number of tasks before their deadlines on a parallel platform; we show how to use this algorithm to solve the general bi-objective problem.

(3) We derive a lower bound on the optimal maximum flow of non-critical tasks.

(4) We develop heuristics inspired by the approximation algorithm.

(5) We implement all heuristics and conduct extensive simulations, using both synthetic and real-world workloads. We show that by sharing resources we can meet critical task deadlines while also reducing non-critical task maximum flow. Our best heuristic reduces maximum flow by up to 13% over static partitioning and up to 14% over a state-of-the-art deadline-centered approach (EDF), while satisfying all deadlines in the offline case and incurring only a modest degradation in the online case.

The remainder of the paper is organized as follows. Section 2 presents our initial model. Section 3 reviews prior work in deadline-aware and mixed-criticality scheduling. Section 4 details the complexity of our problem and derives a theoretical lower bound on the maximum flow of non-critical tasks. Section 5 reformulates our bi-objective problem as a single-objective problem to derive a 1/2-approximation algorithm. Section 6 presents classic approaches that address our problem and presents our proposed heuristics. Section 7 evaluates both state-of-the-art approaches and our proposed heuristics in a variety of settings using synthetic and real workloads. Finally, Section 8 summarizes our contributions.

## 2 Problem Modeling

We consider the problem of scheduling a set of independent tasks on a parallel computer. The tasks are divided into two categories. The first set, $T_{critical} = \{T_1, \dots, T_m\}$ consists of critical tasks that must be computed before their deadlines. Each task $T_i$ includes its release date $r_i$, which is the time when the task and all its characteristics are made available to the scheduler; its duration or processing time $p_i$; and its deadline $d_i$. The second set, $T_{non-critical} = \{T_1, \dots, T_m\}$ consists of tasks without deadlines, that can be processed on a best-effort basis. Tasks also come with their release date $r_i$ and processing time $p_i$.

All tasks must be processed on a homogeneous platform made of $l$ identical processors $\mathbb{P} = \{P_1, \dots, P_l\}$, where each processor can run a single task at a time. Each task from $T_{critical}$ or $T_{non-critical}$ must be processed by one of the $l$ processors. Tasks are non-preemptible: once a task starts running, the processor executing it cannot be used by another task before its completion.

**Objective metrics.** The particularity of this scheduling problem lies in the fact that both sets of tasks follow two different objectives. On the one hand, we want to compute all critical tasks (or most of them) before their deadline. On the other hand, users submitting best-effort tasks want to minimize their processing time. We formally define a specific objective for each set of tasks, which leads to a bi-criteria scheduling problem.

The first objective is to **maximize the number of critical tasks completed before their deadlines**. In the classical $\alpha|\beta|\gamma$ Graham's notation for scheduling problems [13], this problem is noted $P|r_j| \sum (1 - U_j)$. It is often assumed that the computing platform is sufficiently large to accommodate all critical tasks, and as these tasks are more important than the others, this objective will often be transformed into a constraint, ensuring that all critical tasks are performed on time.

For the non-critical tasks, we define the flow of tasks (also called response time) following Bender et al. [4]. Let $C_j$ be the completion time of task $T_j$. The flow $F_j$ is defined as the time spent in the system: $F_j = C_j - r_j$. The second objective is to **minimize the maximum flow of non-critical tasks**. In Graham's notation, this is $P|r_j|\max F_j$.

## 3 Related Work

The problem of scheduling tasks with deadlines has been studied in the literature in different contexts. Prior theoretical work in scheduling theory has considered variants of our problem. In Section 4 we recall that both scheduling to maximize the number of tasks that meet their deadlines and scheduling to minimize the maximum flow are NP-complete problems, as well as some positive results. We review below the most relevant works first in the field of real-time systems, which contains more closely related results, including on mixed-criticality. We then mention related studies in the fields of on cloud workflows and urgent HPC, which approach similar notions.

**Real-time systems.** The problem of scheduling tasks with mixed-criticality has been studied in the context of real-time systems. Burns et al. [6] provides a recent survey of the work in this field. A real-time system is one in which a given set of tasks is repeatedly submitted, in a periodic or aperiodic manner, and where tasks have hard or soft deadlines. Fisher's work [10] shows that there is no optimal online algorithm for aperiodic tasksets with arbitrary deadlines, by showing that such an algorithm would require clairvoyance. However, optimal solutions do exist for periodic tasks with implicit deadlines on homogeneous multiprocessors [6]. Although this work addresses a scheduling problem similar to ours, it relies predominantly on preemptive tasks and often focuses on single-processor computing. More importantly, tasks are assumed to arrive repeatedly. However, in our context, there is no relationship between tasks that will be submitted in the future and tasks that were previously submitted. Hence, the work for real-time systems cannot be applied to our online nonclairvoyant, multiprocessor, nonpreemptive model.

**Cloud workflows with deadlines.** Workflows are a popular paradigm to manage tasks in cloud and grid environments [1]. The mapping of tasks is NP hard in that case as well, and sometimes time-sensitive. In the cloud, faster resources are generally more expensive than slower ones, and users try to minimize the total cost of running their applications. A reasonable solution is to choose the cheapest resources as long as critical tasks can still meet their deadlines [28]. Some use genetic algorithms to solve this multi-criteria mixed criticality problem [29].

Arabnejad et al. [2] have developed a deadline-aware workflow scheduling algorithm that addresses workflow scheduling under budget and deadline constraints in Infrastructure as a Service clouds.
The novelty of their work is satisfying both budget and deadline constraints. Calzarossa et al. [7] tackle cloud workflows where machines have performance variability by minimizing expected execution time and monetary cost via a genetic algorithm evaluated through Monte Carlo simulations. Hussain et al. [16] focuses on a cloud scenario in which tasks are primarily assigned to a free private cloud and only offloaded to a costly public cloud when necessary to meet some task deadline; they use HEFT and slack-based deadline assignments.

While all these methods focus on critical tasks, none of them addresses the scheduling of mixed criticality workloads.

Urgent HPC. Urgent HPC [25] addresses deadline scheduling by requiring not only that tasks complete by a specified time, but also that they begin execution almost immediately. They often use resource reservation exclusively for such tasks. They aim to predict the future release dates of critical tasks in order to reserve the right amount of resources [5]. Likewise, clusters running both production (high-criticality) and research (low-criticality) tasks often rely on resource reservations informed by predicted completion times to balance responsiveness and utilization [15].

# 4 Complexity and lower bound

We first present prior complexity results that show that our bi-objective problem is NP-hard. We then derive a lower bound on the maximum flow achievable by non-critical tasks.

## 4.1 NP-completeness

We consider the decision version of the bi-objective problem defined above, which can be stated as follows:

DEFINITION 1 (MIXEDCRITICALITY). Given two bounds K and F, is there a valid schedule for both critical and non-critical tasks on $ℓ$ processors such that at least K critical tasks are completed before their deadline, and such that the maximum flow of all non-critical tasks is not larger than F?

The problem of scheduling only critical tasks, which is denoted $P|r_j| \sum (1 - U_j)$ in Graham's notation, is the special case of the MIXEDCRITICALITY problem when $K = m$ and $F = +\infty$. This problem, in which tasks are scheduled based on release times and deadlines, belongs to a class of problems known as interval scheduling problems [12], which are proven to be NP-Complete. However, when $ℓ = 1$ and $r_j = 0$, that is, on a single processor when all tasks are available from the start, the problem can be solved in polynomial time (see Section 5.1). The scheduling problem for scheduling only non-critical tasks, $P|r_j| \max F_j$, is also NP-complete; however, the simple First-In-First-Out policy produces an optimal solution on a single processor ($ℓ = 1$) [4].

## 4.2 Lower bound

We are interested in deriving a (theoretical) lower bound on the maximum flow of the non-critical tasks as it enables to have an absolute assessment of the performance of the different algorithms, rather than be restricted to comparing the relative performance of these algorithms. There exists a lower bound for the online problem with a single processor where a task can be stopped but must then be restarted from scratch [8] (problem $1|online - r_j; restarts| \sum F_j$).

There exists an O(1) competitive algorithm [22] for the online problem of maximizing the number of critical tasks that meet their deadlines with several processors and preemption (problem $P|online - r_j; pmtn| \sum (1 - U_j)$). However, we are not aware of any lower bound for our mixed criticality problem as defined in Section 1.

To derive a lower bound, we follow an approach similar to that of [19]. We allow both preemption and migration: any task may be paused, resumed later, or moved between processors. Preemption also allows us to introduce time-sharing, i.e., share a processor time between tasks. We then fix a candidate maximum flow $F_{target}$. For the maximum flow in the instance to be not greater than $F_{target}$, each non-critical task $T_j$ should be completed at least at time $r_j + F_{target}$. We thus transform each non-critical task $T_j$ into a critical task with deadline $d_j = r_j + F_{target}$. With this setting, we create an non-decreasing sorted list $L$ of times that combines the release times $r_i$ and deadlines $d_i$ of all tasks in $T$:

$$L = \text{sorted}(\{r_i \in T\} \cup \{d_i \in T\}).$$

For each consecutive pair of times ($t_k, t_{k+1}$) in $L$, we introduce $x_{i,k}$, the total processing time assigned to task $T_i$ in interval $[t_k, t_{k+1}]$, regardless of which processor handles the task. During this interval, no new task arrives, and no task finishes, so the work allocation remains stable. From this model, we can build a linear program with the following constraints:

* **Allocated time within an interval:** The time allocated to a task $T_i$ during interval $[t_k, t_{k+1}]$ cannot exceed the length of the interval: $x_{i,k} \le t_{k+1} - t_k$.

* **Allocated time across processors:** The total time allocated across all tasks during any interval $[t_k, t_{k+1}]$ cannot exceed the total available processor time. With $ℓ$ processors we get: $\sum_{i=0}^{m} x_{i,k} \le ℓ \times (t_{k+1} - t_k)$.

* **Task completion:** The total time allocated to a task $T_i$ across all intervals must equal its total processing time $p_i$: $\sum_k x_{i,k} = p_k$.

* **Release times:** If an interval starts before the task release time $r_i$, no time can be allocated to that task in this interval: If $t_k < r_i$ then $x_{i,k} = 0$.

* **Deadlines:** If an interval extends beyond a task deadline $d_i$, no time can be allocated to that task in this interval: If $t_{k+1} > d_i$ then $x_{k,i} = 0$.

If the linear program has a solution, the resulting time allocations $x_{i,k}$ provide a feasible schedule in which preemption and migration are allowed and that respects all task deadlines. If there exists a solution under a given target $F_{target}$, then we can decrease the value of $F_{target}$ and use a binary search to find the smallest value for which the linear program remains feasible. Once no feasible solution can be found, the last valid value of $F_{target}$ is the minimum maximum flow $F_{max}$ that can be achieved while satisfying all task deadlines. This value will serve as our lower bound for the given taskset. Obviously, this bound may not be achievable as it relies on using tools (preemption and migration) that are not available in our context.
# 5 Transformation to a single-objective problem

As addressing a bi-objective problem can be complex, we introduce a method to convert it into a single-objective problem. Like we did in Section 4.2 to derive a lower-bound, we assume that we have a specified target maximum flow F for the non-critical tasks. This means that each non-critical task $T_j$ should be completed at least at time $r_j + F$. We thus transform each non-critical task $T_j$ into a critical task with deadline $d_j = r_j + F$ and aim to maximize the number of tasks finished before their deadline. In other words, in the modified problem, all tasks are critical; this corresponds to $P|r_j| \sum (1 - U_j)$. If we find a schedule where all tasks are done on time, this means we have a schedule where (i) all critical tasks are completed on time and (ii) the maximum flow of non-critical tasks is at most F. Provided we are able to design a good strategy for $P|r_j| \sum (1 - U_j)$, a binary search on the value of F allows to solve the initial Mixed-Criticality problem.

We first present two interesting special cases for the single-processor case where optimal solutions are known, before presenting an approximation algorithm for the general case.

## 5.1 Special case: single processor, tasks available at time 0

When all tasks are released at the beginning ($r_j = 0$ for each task $T_j$), and we have a single processor to compute them ($l = 1$) it is known that the Moore-Hodgson algorithm provides an optimal solution [21]. The algorithm first sorts tasks by non-decreasing deadlines. Tasks are added in this order to the schedule; if the deadline of the last added task cannot be met, the longest accepted task is removed from the current schedule.

## 5.2 Special case: single processor, tasks with strict time windows

On a single processor, when tasks have strict time windows, i.e., $d_j = r_j + p_j$ for all tasks, the problem of maximizing the number of completed tasks is similar to the *Interval Scheduling Maximization Problem*: it is known that the simple *Earliest Deadline First* strategy is optimal [18]. It sorts all tasks by deadlines. The task with smallest deadline is added to the current solution, and all tasks whose interval intersects with the newly added task are removed from the set of candidates. This procedure is repeated until the set of candidates is empty.

## 5.3 General case approximation algorithm

In a more complex version of the interval scheduling maximization problem, tasks are partitioned into groups. A compatible set of intervals is one in which no two intervals overlap, and each group contains at most one representative. This is known as the *Group Interval Scheduling Maximization Problem (GISMP)*. Each group of intervals corresponds to a single task and represents several alternative intervals in which it can be executed. Although this problem is NP-complete when there are more than two intervals per group, a 1/2-approximation algorithm exists for arbitrary groups [26].

We can transform the problem with general deadlines on a single processor ($1|r_j| \sum (1 - U_j)$) to GISMP as follows: for each task, we create a group of intervals, each interval corresponding to a possible

start time for the task. More formally, task $T_j$ is associated to the following group of intervals: $Int_j = [r_j, r_j + p_j], [r_j + 1, r_j + p_j + 1], \dots, [d_j - p_j, d_j]$.

In order to solve the general problem ($P|r_j| \sum (1 - U_j)$), we need a strategy that can handle any number of processors. We adapt the algorithm from Spieksma et al. [26] for this purpose (see Algorithm 1) and prove that it is a 1/2-approximation algorithm. This algorithm first computes all possible execution intervals for each tasks. Processors are considered one after the other: the full schedule for the first processor is built before the schedule for the second processor is considered, and so on. On the processor currently considered, the algorithm allocates tasks one by one so that the next selected interval is the one with the earliest finish time. Once a new task is scheduled, the remaining intervals of other tasks intersecting with the selected interval are removed from the set of candidates. Once no more tasks can be scheduled on a processor, the algorithm continues with the next processor.

**Algorithm 1 NON-POLY-GREEDY**

1: candidates $\leftarrow \mathbb{T}$

2: for each $P_i \in \mathbb{P}$ do

3: for each $T_j \in \text{candidates}$ do

4: $Int_j \leftarrow [r_j, r_j + p_j], [r_j + 1, r_j + p_j + 1], \dots, [d_j - p_j, d_j]$

5: $t \leftarrow 0$

6: while there exists an interval $[S, C]$ in some $Int_j$ with $S \ge t$ and $T_j \in \text{candidates}$ do

7: for each $T_j \in \text{candidates}$ do

8: Let $[S_j, C_j]$ be the first interval in $Int_j$ such that $S_j \ge t$

9: Select task $T_j$ with smallest $C_j$

10: Schedule $T_j$ on $P_i$ in time interval $[S_j, C_j]$

11: Remove $T_j$ from candidates

12: $t \leftarrow C_j$

We recall that for a maximization problem we say that an algorithm A is a $\rho$-approximation if, for any instance I, its execution time is polynomial in the size of I and if the quality $A(I)$ of the solution produced by A is at least $\rho \text{OPT}(I)$ where $\text{OPT}(I)$ is the quality of the optimal solution.

**THEOREM 1.** *Algorithm 1 always schedules at least half as many tasks with release times and deadlines as an optimal algorithm.*

**PROOF.** The idea of the proof is to partition the original instance I into two. The first part $I_1$ includes exactly the tasks that have been scheduled on some processor by Algorithm 1. The other part $I_2$ consists in all remaining tasks. Our goal is to prove that in each part, an optimal solution (denoted by OPT) cannot select more that $|I_1|$ tasks, which is the number of tasks scheduled by Algorithm 1.

This is easy to prove on $I_1$, which contains only $|I_1|$ tasks. We now consider $I_2$. We focus on a given processor $P_i$. Let $n_i$ be the number of tasks scheduled by Algorithm 1 on $P_i$ and let $F_1, F_2, \dots, F_{n_i}$ be their finish times. All tasks from $I_2$ have been rejected by Algorithm 1 from $P_i$, meaning that all their possible execution intervals intersect the interval of an already scheduled task. For each rejected interval $[S, F]$, we know that there exists some $F_j$ such that $S \le F_j$ and $F > F_j$ (otherwise it would have been selected by Algorithm 1). Hence, all intervals of $I_2$ are active at some $F_j$. Hence, at most one
interval of $I_2$ can be selected by OPT to be executed on $P_i$ for each of the $n_i$ dates $F_1, F_2, \dots, F_{n_i}$. Therefore, on processor $P_i$, OPT can schedule at most $n_i$ tasks of $I_2$. In total, OPT can schedule at most $\sum_i n_i = |I_1|$ tasks of $I_2$.

Thus, on the original instance which is the union of $I_1$ and $I_2$, OPT cannot scheduled more that $2|I_1|$ tasks. $\square$

As detailed in Algorithm 1, this strategy does not have a polynomial complexity, since we have to compute all possible intervals for each task and they may exist a large number of them ($\max_j d_j$ is not polynomial in the size of the problem). We propose in Algorithm 2 a polynomial-time version of Algorithm 1 strategy: instead of exhibiting all intervals, we recompute at each step what is the best candidate interval for each task.

**THEOREM 2.** *Algorithm 2 computes in polynomial time the solution of Algorithm 1.*

**COROLLARY 3.** GREEDY is a 1/2-approximation algorithm for the problem of scheduling the maximum number of tasks with release dates before their deadlines ($P|r_j| \sum(1 - U_j)$).

**Algorithm 2 GREEDY**

1: candidates $\leftarrow \mathcal{T}$

2: **for** each $P_i \in \mathbb{P}$ **do**

3: $t \leftarrow 0$

4: progress $\leftarrow$ true

5: **while** candidates $\neq \emptyset$ and progress **do**

6: $(j^*, \text{EFT}) \leftarrow (-1, +\infty)$

7: **for** each $T_j \in$ candidates **do**

8: EFT$_j \leftarrow \max(t, r_j) + p_j$

9: **if** EFT$_j \leq d_j$ and EFT$_j < \text{EFT}$ **then**

10: $(j^*, \text{EFT}) \leftarrow (j, \text{EFT}_j)$

11: **if** EFT $< +\infty$ **then**

12: Start $T_j^*$ on $P_i$ at time EFT $- p_j^*$

13: Remove $T_j^*$ from candidates

14: $t \leftarrow \text{EFT}$

15: **else**

16: progress $\leftarrow$ false

# 6 Algorithms

In this Section, we first present two classic approaches to solve the scheduling problem presented in Section 2. The first relies on a static allocation of processors for critical tasks (Section 6.1) and schedules tasks in a first-in, first-out fashion (FIFO), while the second combines common schemes for scheduling tasks with and without deadlines (Section 6.2). Then, Section 6.3 presents one of our contributions, a heuristic derived from Algorithms 1 and 2 with a focus on deadline slack. Finally, we discuss various improvements that can be added to the algorithms, such as temporal shifting (Section 6.4) and fallbacks (Section 6.5).

Apart from SPLIT-OFFLINE, all algorithms presented in this paper are applicable to both offline and online settings. We denote the set of tasks whose information is known at a certain time $t$ as $T_{available}$. In the offline setting, at $t=0$, $T_{available} = \mathcal{T}$ and each algorithm is executed once to produce the full schedule. In the online setting,

**Algorithm 3 SPLIT-OFFLINE**

1: **input:** $T_{critical}$, $\ell$

2: $T_{critical} \leftarrow$ critical tasks from $T_{available}$

3: Run binary search to find minimum number $p$ of processors to schedule all tasks from $T_{critical}$ on $p$ processors with EDF policy

4: $T_{non-critical} \leftarrow$ non-critical tasks from $T_{available}$ sorted by release time

5: **for** each $T_i \in T_{non-critical}$ **do**

6: Schedule $T_i$ on $P_j \in \mathbb{P}$ on one of the remaining $\ell - p$ processors with earliest available start time

whenever a new task arrives, we remove all scheduled but not running tasks from the current schedule and return them to $T_{available}$. Newly arrived tasks are added to $T_{available}$. The algorithm is then re-executed.

## 6.1 SPLIT-OFFLINE

As mentioned in the introduction, to address the challenge of having tasks with varying levels of criticality, some HPC resource providers dedicate a portion of their compute nodes to such tasks. Since the submission rate and number of such tasks is not known in advance, resources are often over-provisioned. To emulate such a static solution, we use a binary search to find the minimal set of nodes that enables all critical tasks to complete before their deadline. This is done offline, with a complete knowledge of all incoming tasks (see Algorithm 3). For a given number of processors, critical tasks are scheduled using EDF<fnref n="1" /> to check the feasibility of the setting. Once a fraction of processors is reserved for critical tasks, non-critical are allocated to other processors using a FIFO policy: scheduling online tasks to minimize their maximum flow is NP-complete, but FIFO is optimal when targeting a single processor (as outlined above); hence, we expect good results for non-critical tasks.

## 6.2 Earliest deadline first and first-in first-out

The Earliest Deadline First (EDF) approach is optimal for critical tasks in the sense that if a schedule exists that satisfies all deadlines, it will be found in an online mono-processor setting [20]. It has also been shown that, in a preemptive online setting, any set of tasks for which there exists a valid scheduling on $m$ processors will be successfully scheduled by EDF, if EDF is provided processors that are $(2 - 1/m)$ times faster [23]. We can then assume that EDF would be a reasonable approach for our problem. However, our goal is more complex, as we also aim to minimize the maximum flow of non-critical tasks. As was just recalled, FIFO is optimal in the non-preemptive online case to minimize the maximum flow with a single processor. We combine both strategies in the EDF+FIFO policy (Algorithm 4): critical tasks are first scheduled according to EDF, while non-critical tasks are scheduled in FIFO order.

## 6.3 GREEDY-SLACK

GREEDY, as described in Section 5.3, addresses our problem by first assigning a deadline to each non-critical task to convert it to a

<footnote n="1">¹EDF with temporal shifting, as explained in Section 6.4.</footnote>
**Algorithm 4 EDF+FIFO**

1: **input**: $T_{available}, P$

2: $T_{critical} \leftarrow$ critical tasks from $T_{available}$ sorted by deadline

3: **for** each $T_i \in T_{critical}$ **do**

4: Schedule $T_i$ on $P_j \in P$ with earliest available start time

5: $T_{non-critical} \leftarrow$ non-critical tasks from $T_{available}$ sorted by release time

6: **for** each $T_i \in T_{non-critical}$ **do**

7: Schedule $T_i$ on $P_j \in P$ with earliest available start time

**Algorithm 5 GREEDY-SLACK**

1: **input**: $T_{available}, P, target_flow, current_time$

2: Assign a deadline to non-critical tasks as $r_j + target_flow$

3: Sort $T_{available}$ by decreasing value of $d_j$ - ($\max(current_time, r_j) + p_j$)

4: **for** each $P_i \in P$ **do**

5: $t \leftarrow current_time$

6: **for** each $T_j \in T_{available}$ **do**

7: EST $\leftarrow \max(t, r_j)$

8: **if** EST + $p_j \le d_j$ **then**

9: Schedule $T_j$ on $P_i$

10: $t \leftarrow EST + p_j$

11: Remove $T_j$ from $T_{available}$

single-objective problem. It then employs a binary-search on a target maximum flow and schedules tasks with the aim to fit as many tasks as possible on the first processor before moving on to the second processor, and so on. We introduce here GREEDY-SLACK (Algorithm 5), a heuristic strategy that uses the same intuition but shifts the emphasis to deadlines. Instead of sorting tasks by earliest finish time as in GREEDY, we sort tasks by deadline slack, which represents the amount of time a task can remain in the queue before it must be immediately processed to meet its deadline (similar to the least-laxity-first algorithm [23]). More formally, for each released task $T_i$, we define $deadline_slack_j = d_j - (\max(t, r_j) + p_j)$, where $t$ is the current time. By changing the task order, we unfortunately lose the guarantee: GREEDY-SLACK is not an approximation algorithm. However, as we will see in the experiments, focusing on the slack can improve the performance.

## 6.4 Temporal shifting of scheduled tasks

Ensuring that every critical task meets its deadline is imperative in our problem; otherwise the schedule is unacceptable. To assist in this goal, we introduce here an aggressive temporal shifting technique based on the principle that a critical task may be postponed without consequence as long as its deadline is met. This idea extends the well-known EASY backfilling policy [17, 27], where some tasks may jump ahead in the queue as long as they do not delay the task at the head of the queue. In our approach, however, an entire subset of tasks may be shifted, as long as each delayed task's deadline remains satisfied. Note that temporal shifting is only beneficial for critical tasks: postponing non-critical tasks would impact their flow.

We integrate temporal shifting into EDF+FIFO and GREEDY-SLACK. We denote versions with temporal shifting with the suffix shift. To include temporal shifting, we modify the EDF+FIFO strategy as follows. Line 4 of Algorithm 4 is replaced by:

4': Schedule $T_i$ on the processor $P_j \in P$ which offers the earliest available start time $t_{min}$ such that any task $T_k$ scheduled on $P_j$ after $t_{min}$ will still meet its deadline

For GREEDY-SLACK, we modify Line 7 of Algorithm 5:

7': EST $\leftarrow$ earliest available start time on $P_i$ such that any $T_k$ scheduled on $P_i$ after EST can still meet its deadline

For the sake of fairness, SPLIT-OFFLINE employs EDF with temporal shifting to perform the offline scheduling of critical tasks.

## 6.5 EDF fallback for GREEDY-SLACK

We introduce GREEDY-SLACK-SHIFT*, a modified version of GREEDY-SLACK-SHIFT designed for online scheduling. In cases where the binary search of GREEDY-SLACK-SHIFT does not find a feasible solution for a given set of tasks, GREEDY-SLACK-SHIFT* instead falls back to using EDF's strategy for critical tasks, while using the same heuristic for non-critical tasks. As shown in Section 7.4.1, this allows us to maintain the same schedule quality while successfully scheduling a larger proportion of workloads.

## 7 Experimental evaluation

We evaluate our heuristics using a simulator with both a synthetic workload and a trace workload obtained from a real computing platform. Our simulator is an event-based batch scheduling simulator written in Python 3.10. We use the linear programming solver of the PuLP library [24] to compute the lower bound of Section 4.2.

Many parameters may affect scheduling performance, such as task interarrival time, proportion of critical vs. non-critical tasks, distribution of deadline slack, task processing times, and number of processors. Due to space limitations, we focus on varying the number $l$ of processors and the utilization level to explore the effect of the computing platform load. We define the load as:

$$Load = \frac{\frac{1}{m} \sum_{i=1}^{m} p_i}{l \times \text{mean interarrival time}}$$

A load of 100% thus corresponds to a situation where all processors should be busy computing continually in order to cope with the incoming tasks, which is usually not feasible due to task constraints. Varying the other parameters will typically reinforce or diminish the trends observed when varying the load.

In this section, we first describe how we create a representative synthetic workload before presenting the results of our experiments.

### 7.1 Representative workload

For the experiments reported in Sections 7.2–7.4, we use synthetic workloads. Specifically, we generate workloads of 500 tasks in Sections 7.2 and 7.4 to study a steady-state regime, and shorter workloads of 50 tasks in Section 7.3 to focus on bursts of tasks. In both cases, we use an equal number of critical and non-critical tasks. Task processing times are determined from a truncated normal distribution with a standard deviation of 20, a lower bound of 1, no upper bound, and a mean processing time of 20. Release times are
generated using the Poisson distribution with $\lambda$ chosen to match the desired load relative to the number of processors available, i.e., we compute:

$$ \lambda = \frac{\frac{1}{500} \sum_{i=1}^{500} p_i}{\ell \times \text{Load}} $$

Deadline slacks are generated from a truncated normal distribution with a standard deviation of 0.1, a lower bound of 0.1, no upper bound, and a mean of 5. Figure 1 shows an example workload if each task was to be started immediately on submission.

<figure><img src="image_2.png" /><figcaption>Figure 1: Number of processors required for one instance of our typical workload if each task was to be started immediately upon submission. Green tasks are non-critical tasks while blue task are critical tasks with deadlines.</figcaption></figure>

## 7.2 Performance on representative workload, with steady load

Figure 2 shows, in an offline setting, the ratio between each algorithm's maximum flow and the maximum flow obtained by the lower bound as we increase the load. We report the geometric mean over 30 workload instances. Since we report a ratio, lower is better. A ratio of 1 means that it matches the theoretical lower bound. The error bars represent the 25th and 75th percentiles of these ratios.

We first notice that EDF+FIFO performs poorly. It is significantly worse than all other strategies and its variant with time shifting. The offline SPLIT-OFFLINE strategy is competitive with other strategies, although it is consistently worse than GREEDY-SLACK-SHIFT. While GREEDY is relatively consistent as load increases, GREEDY-SLACK shows significant variance as the load increases, sometimes matching the lower bound and sometimes performing among the worst. Fortunately, adding temporal shifting addresses this problem, making GREEDY-SLACK-SHIFT the best solution in all cases, with consistent results very close to the lower bound.

For the following sections, we report only the best performing variant of each algorithm, namely EDF-SHIFT+FIFO, SPLIT-OFFLINE, and GREEDY-SLACK-SHIFT. Note that in the online setting, we include the EDF fallback to GREEDY-SLACK-SHIFT because it gives similar performance while completing more instances successfully, as will be shown in Section 7.4.1.

Figure 3 shows the same experiment as Figure 2 but in an online setting: each task is revealed to the schedulers only when it is released. There is one notable exception: SPLIT-OFFLINE still relies on global knowledge of the tasks in order to determine the number

<figure><img src="image_3.png" /><figcaption>Figure 2: Performance evaluation in an offline setting, with the representative workload parameters, 500 tasks, 8 processors and 30 random instances.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Figure 3: Online setting, with the representative workload parameters, 500 tasks, 8 processors and 30 random instances.</figcaption></figure>

of processors to reserve for critical tasks. We observe that GREEDY-SLACK-SHIFT* is again close to the lower bound as we increase load. The lower bound cannot always be met as it considers all tasks from the beginning and uses preemption and migration. Because of critical task deadlines, some heuristics are unable to find a solution in specific scenarios. We only compare the results in the scenarios where all heuristics successfully reach a solution. The number of successful scenarios (among 30) is indicated in parentheses for the different load values. Note that in the offline setting, each scheduler always finds an ordering that schedules all critical tasks before their deadlines for each instance, which is why we did not include this information on Figure 2. We report more detailed information on the success rate of heuristics in Section 7.4.1.

As in the offline setting, GREEDY-SLACK-SHIFT consistently produces schedules whose maximum flow is both lower than those of SPLIT-OFFLINE and EDF-SHIFT+FIFO and very close to the lower bound and, thus, to optimality. Besides, GREEDY-SLACK-SHIFT reduces the maximum flow in the online setting by up to 14 and 13% compared to SPLIT-OFFLINE and EDF-SHIFT+FIFO, respectively. Additionally, we measured that GREEDY-SLACK-SHIFT takes on average 36 ms to schedule one task in an online setting.
<figure><img src="image_5.png" /><figcaption>Figure 4: Representative workload parameters, 50 tasks, 8 processors, and 30 random instances, representing a burst with heavy load, followed by a period without task submission. Between parentheses is the number of instances successfully solved by all heuristics (out of 30).</figcaption></figure>

## 7.3 Performance on representative workload, with bursty arrival

Figure 4 shows the same experiment as Figures 2 and 3 but with only 50 tasks. By submitting 50 tasks with heavy load (up to 200%) in a short timeframe, we emulate a bursty workload with very short inter-arrival times, followed by a time interval without any task submission that allows the platform to recover from the burst. We observe that GREEDY-SLACK-SHIFT is able to reach the lower bound for almost every load values, both in the offline and online cases. In contrast, EDF-SHIFT+FIFO degrades the maximum flow under higher load because it schedules the non-critical tasks exclusively after the critical tasks, and thus misses opportunities to exploit available slack. This is where our slack-aware strategy shines: it recognizes when critical tasks have distant deadlines and schedules them opportunistically, reducing the maximum flow time. At most, in the online setting, GREEDY-SLACK-SHIFT reduces maximum flow by 22% compared to SPLIT-OFFLINE and by 50% compared to EDF-SHIFT+FIFO, respectively.

## 7.4 Analysis of service quality metrics

We present here the result of the same experiments as above, but examine two quality of service metrics: the proportion of successful instances under varying parameters and the mean flow.

### 7.4.1 Proportion of successful instances under various workload constraints.
Figure 5 shows the proportion of workload instances where all tasks with deadlines were successfully scheduled, under different deadline slack and load configurations, in the online setting. The top right part of each figure corresponds to the more constrained scenario, where all tasks must be started immediately to complete before their deadlines (deadline slack=0), and where 90% of the processors must be used in parallel to schedule all tasks. As we move toward the lower left corner, the constraints become more relaxed. In order to maintain consistency along rows and columns, we consider the same basic set of scenarios, changing only the deadline slack or the inter-arrival times of tasks (by scaling the time axis).

SPLIT-OFFLINE achieves the highest proportion of successful instances. Indeed, choosing an offline allocation of processors for critical tasks is the best choice to solve the maximum number of instances, at the expense of higher flows, as shown in Figure 3. We observe that GREEDY-SLACK-SHIFT* achieves a slightly higher success rate than GREEDY-SLACK-SHIFT thanks to its fallback mechanism. Since it is only used in an online setting, this fallback mechanism only applies to a subset of otherwise unschedulable tasks. As a result, it improves the success rate without degrading performance compared to GREEDY-SLACK-SHIFT, since it is only used when the original algorithm fails to produce a solution.

Comparing EDF-SHIFT+FIFO with GREEDY-SLACK-SHIFT*, we observe that for the three largest deadline slack values, GREEDY-SLACK-SHIFT* produces results similar to the state-of-the-art method. This suggests that GREEDY-SLACK-SHIFT* is particularly relevant when the deadline slack is above 4, as it not only finds a solution in most cases, but also achieves the best max flow results. For smaller deadline slack, EDF-SHIFT+FIFO has a higher success rate compared to GREEDY-SLACK-SHIFT*, although the difference remains small.

### 7.4.2 Mean flow.
For completeness, we now explore the mean flow (rather than max flow), a goal for which our methods were not designed. Mean flow represents the average delay for a given set of tasks, making it a metric that resource managers are interested in reducing. However, optimizing only for mean flow benefits scheduling strategies that prioritize short tasks at the expense of longer ones, leading to potential increases in total makespan. Figure 6 shows the mean flow for GREEDY-SLACK-SHIFT, EDF-SHIFT+FIFO and SPLIT-OFFLINE as we increase load in both offline and online settings.

Figure 6-a shows that GREEDY-SLACK-SHIFT exhibits a higher mean flow compared to the two state-of-the-art algorithms in the offline setting. Our strategy assigns deadlines to all tasks and then schedules them. When many tasks are available at once, as is the case in an offline scenario, the binary search tends to converge to a higher value of maximum flow because a larger number of tasks must meet their deadlines. In contrast, the other two algorithms have fewer tasks competing for their deadlines and can therefore achieve a better mean flow.
<figure><img src="image_6.png" /><figcaption>Figure 5: Proportion of successful instances (out of 30) under various workload constraints. Online setting: tasks are disclosed when they are released to all heuristics except SPLIT-OFFLINE, which has full knowledge of the instance from the beginning.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6: Absolute values of mean flow for the representative workload, averaged over 30 random instances, using 8 processors. These are the same experiments as Figures 2 and 3.</figcaption></figure>

Figure 6-b shows results for an online setting where only a limited number of tasks are available at any given time. Because GREEDY-SLACK-SHIFT does not differentiate between critical and non-critical tasks, it occasionally schedules non-critical tasks earlier than critical ones. This behavior benefits the mean flow. On the other hand, both EDF-SHIFT+FIFO and SPLIT-OFFLINE always schedule critical tasks first and treat non-critical tasks as a secondary priority, thus increasing the mean flow.

## 7.5 Production workload traces

Table 1 and Figure 7 present results obtained using real cluster occupation traces [14]. Each of the 10 traces consists of two months of real-world task submissions from 10 Microsoft ITP clusters: data that has been previously used in simulation studies with deadlines [11, 30].

The traces have different task submission profiles, so in order to have a fixed load for all schedulers, we run the simulation for each trace using the minimum number of processors required for the three algorithms to complete all tasks before their deadlines.

Criticality is randomly assigned to tasks over 10 different instances for each trace, and only the first 1000 tasks of each trace are processed for computational reasons. Table 1 summarizes the number of instances where our algorithm outperforms the other two, as well as the amount of improvement. Overall, GREEDY-SLACK-SHIFT* brings improvement for most traces.

Trace 9 exhibits the most degradation. Figures 7-a and 7-b show the performance when varying the number of processors of two instances from trace 9. We see in Figure 7-a that with 30 processors, GREEDY-SLACK-SHIFT* performs the worst. Since in Table 1 we choose the minimal number of processors for which all algorithms produce a valid schedule, GREEDY-SLACK-SHIFT* will exhibit degradations in cases like Figure 7-a. However, as the number of processors increases, it achieves the lowest maximum flow, showing that once the load constraint is relaxed, it finds the best solutions. In other instances, however, like shown in Figure 7-b, GREEDY-SLACK-SHIFT* already attains the smallest maximum flow with the minimal number of processors.

<table><caption>Table 1: Fraction of cases where GREEDY-SLACK-SHIFT* shows improvement (resp. degradation) compared to EDF-SHIFT+FIFO and SPLIT-OFFLINE. Values in parentheses are the average improvement (resp. degradation) percentage, computed as the geometric means over the improved (resp. degraded) instances. Traces with no change (2, 5, and 6) are omitted. Mean deadline slack of 6.</caption><thead><tr><th rowspan="2">Trace</th><th colspan="2">Cases with improvement over</th><th colspan="2">Cases with degradation over</th></tr><tr><th>EDF-SHIFT+FIFO</th><th>SPLIT-OFFLINE</th><th>EDF-SHIFT+FIFO</th><th>SPLIT-OFFLINE</th></tr></thead><tbody><tr><td>1</td><td>7/10 (22%)</td><td>7/10 (26%)</td><td>2/10 (1%)</td><td>1/10 (2%)</td></tr><tr><td>3</td><td>5/10 (4%)</td><td>9/10 (37%)</td><td>3/10 (18%)</td><td>1/10 (32%)</td></tr><tr><td>4</td><td>1/10 (51%)</td><td>1/10 (39%)</td><td>0/10</td><td>0/10</td></tr><tr><td>7</td><td>4/10 (9%)</td><td>0/10</td><td>0/10</td><td>0/10</td></tr><tr><td>8</td><td>3/10 (1%)</td><td>0/10</td><td>0/10</td><td>0/10</td></tr><tr><td>9</td><td>2/10 (11%)</td><td>9/10 (7%)</td><td>6/10 (11%)</td><td>1/10 (12%)</td></tr><tr><td>10</td><td>2/10 (18%)</td><td>2/10 (71%)</td><td>0/10</td><td>0/10</td></tr></tbody></table>

## 8 Conclusion

Shared compute platforms, whether HPC clusters or cloud environments, must handle workloads with widely varying deadline requirements. Since existing approaches based on static reservation or preemption often lead to inefficient resource utilization, we tackle the problem of mixed-criticality scheduling of non-preemptive
<figure><img src="image_8.png" /><figcaption>Figure 7: Evolution of maximum flow with different instances of trace 9. Mean deadline slack of 6.</figcaption></figure>

tasks. After formalizing this problem, we derived a 1/2-approximation algorithm for the maximization of tasks that meet their deadlines and extend it for mixed-criticality tasks. We derived a theoretical lower bound on the optimum maximum flow for non-critical tasks. Building on the approximation algorithm, we designed a heuristic focusing on deadline slack and enhanced it with an adapted temporal shifting strategy. Compared to state-of-the-art approaches commonly used for deadline-scheduling, this heuristic reduces maximum flow online by up to 14% compared to SPLIT-OFFLINE and by up to 13% compared to EDF-SHIFT+FIFO and consistently attains values at or near the theoretical lower bound. When evaluated on real cluster traces, this approach also outperforms existing state-of-the-art methods in most scenarios.

Our work is an important contribution with implications for cloud and HPC resource managers, where users with different priorities contend for the same resources. We show that it is possible to balance tasks of varying criticality without completely prioritizing one type over the other. In future work, we will extend our model to heterogeneous processors, where varying compute capabilities introduce new trade-offs in deadline and flow minimization. We also aim to evaluate our heuristics under real operation conditions by deploying them in an actual HPC center and enabling users to define their task's criticality.

## Acknowledgments

This material is based upon work supported by the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research, under Contract DE-AC02-06CH11357.

## References

[1] Mainak Adhikari, Tarachand Amgoth, and Satish Narayana Srirama. 2019. A Survey on Scheduling Strategies for Workflows in Cloud Environment and Emerging Trends. *ACM Comput. Surv.* (2019). doi:10.1145/3325097

[2] Vahid Arabnejad, Kris Bubendorfer, and Bryan Ng. 2019. Budget and Deadline Aware e-Science Workflow Scheduling in Clouds. *IEEE Transactions on Parallel and Distributed Systems* 30, 1 (2019), 29–44. doi:10.1109/TPDS.2018.2849396

[3] L. Bautista-Gomez, A. Benoit, S. Di, Th. Herault, Y. Robert, and H. Sun. 2024. A survey on checkpointing strategies: Should we always checkpoint à la Young/Daly? *Future Generation Computer Systems* 161 (2024).

[4] M. A. Bender, S. Chakrabarti, and S. Muthukrishnan. 1998. Flow and Stretch Metrics for Scheduling Continuous Job Streams. In *ACM-SIAM SoDA*.

[5] Nick Brown, Gordon Gibb, Evgenij Belikov, and Rupert Nash. 2022. Predicting batch queue job wait times for informed scheduling of urgent HPC workloads. https://arxiv.org/abs/2204.13543

[6] Alan Burns and Robert Ian Davis. 2022. *Mixed Criticality Systems - A Review* (13th ed.). White Rose Research Online. https://eprints.whiterose.ac.uk/183619.

[7] Maria Carla Calzarossa, Marco L. Della Vedova, Luisa Massari, Giuseppe Nebione, and Daniele Tessera. 2021. Multi-Objective Optimization of Deadline and Budget-Aware Workflow Scheduling in Uncertain Clouds. *IEEE Access* 9 (2021).

[8] Leah Epstein and Rob van Stee. 2003. Lower bounds for on-line single-machine scheduling. *Theoretical Computer Science* 299, 1 (2003), 439–450.

[9] M. E. Fenstermacher, J. Abbate, S. Abe, T. Abrams, M. Adams, B. Adamson, N. Aiba, Akiyama, et al. 2022. DIII-D research advancing the physics basis for optimizing the tokamak approach to fusion energy. *Nuclear Fusion* 62, 4 (2022).

[10] Nathan W. Fisher. 2007. *The multiprocessor real-time scheduling of general task systems*. Ph. D. Dissertation. The University of North Carolina at Chapel Hill.

[11] Wei Gao, Zhisheng Ye, Peng Sun, Yonggang Wen, and Tianwei Zhang. 2021. *Chronus: A Novel Deadline-aware Scheduler for Deep Learning Training Jobs*. In *Proceedings of ACM SoCC* '21. 15 pages.

[12] M. R. Garey and D. S. Johnson. 1979. *Computers and Intractability, A Guide to the Theory of NP-Completeness*. W.H. Freeman and Co, London (UK).

[13] Ronald Lewis Graham, Eugene Leighton Lawler, Jan Karel Lenstra, and AHG Rinnooy Kan. 1979. Optimization and approximation in deterministic sequencing and scheduling: a survey. In *Annals of discrete mathematics*. Elsevier.

[14] D. Gu, Y. Zhao, Y. Zhong, Y. Xiong, Z. Han, P. Cheng, F. Yang, G. Huang, X. Jin, and X. Liu. 2023. ElasticFlow: An Elastic Serverless Training Platform for Distributed Deep Learning. In *Proceedings of ASPLOS 2023*.

[15] Graham Holt. 2005. Time-Critical Scheduling on a Well Utilised HPC System at ECMWF Using Loadleveler with Resource Reservation. In *Job Scheduling Strategies for Parallel Processing*. Springer Berlin Heidelberg, Berlin, Heidelberg.

[16] M. Hussain, M.-X. Luo, A. Hussain, M. Hafeez Javed, Z. Abbas, and L.-F. Wei. 2023. Deadline-constrained cost-aware workflow scheduling in hybrid cloud. *Simulation Modelling Practice and Theory* 129 (2023).

[17] David Jackson, Quinn Snell, and Mark Clement. 2001. Core Algorithms of the Maui Scheduler. In *Job Scheduling Strategies for Parallel Processing*.

[18] Jon Kleinberg and Eva Tardos. 2006. *Algorithm design*. Pearson Education India.

[19] Arnaud Legrand, Alan Su, and Frédéric Vivien. 2008. Minimizing the Stretch When Scheduling Flows of Divisible Requests. *Journal of Scheduling* (2008).

[20] C. L. Liu and James W. Layland. 1973. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. *J. ACM* (1973).

[21] J Michael Moore. 1968. An n job, one machine sequencing algorithm for minimizing the number of late jobs. *Management science* 15, 1 (1968), 102–109.

[22] B. Moseley, K. Pruhs, C. Stein, and R. Zhou. 2024. A Competitive Algorithm for Throughput Maximization on Identical Machines. *arXiv:2111.06564*

[23] C. A. Phillips, C. Stein, E. Torng, and J. Wein. 1997. Optimal time-critical scheduling via resource augmentation (extended abstract). In *Proceedings of ACM STOC* '97.

[24] PuLP 2025. Optimization with PuLP. https://coin-or.github.io/pulp/.

[25] A. Reuther, N. Brown, W. Arndt, J. Blaschke, C. Boehme, A. Chazapis, B. Enders, R. Henschel, J. Kunkel, and M. Martinasso. 2024. Interactive and urgent HPC: challenges and opportunities. *arXiv:2401.14550* (2024).

[26] Frits C. R. Spieksma. 1999. On the approximability of an interval scheduling problem. *Journal of Scheduling* 2, 5 (1999), 215–227.

[27] Adam K.L. Wong and Andrzej M. Goscinski. 2007. Evaluating the EASY-backfill job scheduling of static workloads on clusters. In *Proceedings of IEEE Cluster*.

[28] Fuhui Wu, Qingbo Wu, and Yusong Tan. 2015. Workflow scheduling in cloud: a survey. *The Journal of Supercomputing* 71 (2015), 3373–3418.

[29] J. Yu and R. Buyya. 2006. Scheduling Scientific Workflow Applications with Deadline and Budget Constraints Using Genetic Algorithms. *Scientific Programming* (2006).

[30] Yuchen Zhang, Long Luo, Gang Sun, Hongfang Yu, and Bo Li. 2025. Deadline-aware Online Job Scheduling for Distributed Training in Heterogeneous Clusters. *IEEE Transactions on Cloud Computing* (2025). doi:10.1109/TCC.2025.3548604