1 of 19

ADAPTING CLASSIC SCHEDULING HEURISTICS FOR ONLINE EXECUTION UNDER UNCERTAINTY

KUBISHI RESEARCH GROUP

November 17, 2025

Jason Chamorro Loyola Marymount University

Gabriel Twigg-Ho Swinburne University of Technology

Jared Coleman Loyola Marymount University

Tainã Coleman San Diego Supercomputer Center

Bhaskar Krishnamachari University of Southern California

Mohammadali Khodabandehlou University of Southern California

Loyola Marymount

University

2 of 19

Task Graph

Compute Network

Schedule

2

Loyola Marymount

University

The work that I’m going to talk about today revolves around a really well-known problem in distributed computing called task scheduling.

I want to first carefully introduce the problem

We have a task graph, This is everything we need to get done. Each task is represented as a node, and each task has a cost. Arrows between task nodes represent dependencies in the task structure. For example, task t5 cannot start until it receives data from t1. the cost of these connections reflects the data size of the information to be transferred

The second piece of the model is the compute network. Each node in the network represents a processor that can complete a task. The time a given task takes to complete is its cost divided by the speed of the network node it is running on

The edges between network nodes are NOT directed, as data can flow both directions. Each edge represents the communication strength between two compute nodes. In our example, we can see that t4 cannot start until it receives data from t2. Because we want to run t4 on a different network node, we need to transfer t2's data to that node. The time that it takes to send this data is represented by the gap between the end of t2, and the start of t4 in the table.

We attempt to minimize makespan which is the time from the first task starting, and the last task finishing

Now that we understand the problem, lets discuss how schedules are actually created.

3 of 19

COMPARING SCHEDULING ALGORITHMS

Scheduling is NP-Hard and not approximable, but what about for practical situations?

Scheduling an ML workflow
Running a scientific workflow on a supercomputing system
Collecting and processing data from an IoT system
Running analyses in a tactical edge environment

Many tasks scheduling heuristic algorithms have been proposed

HEFT, CPoP, BIL, ETF, FCP, FLB, GDL, MinMin, MaxMin, MCT, MET, OLB, SMT, WBA, …

Which algorithms works best in practice?

3

Loyola Marymount

University

4 of 19

COMPARING SCHEDULING ALGORITHMS

HEFT Schedule

CPoP Schedule

Task Graph

Network

4

Loyola Marymount

University

5 of 19

COMPARING SCHEDULING ALGORITHMS

HEFT Schedule

CPoP Schedule

Task Graph

Network

0.5

5

Loyola Marymount

University

6 of 19

Task Graph - Online

Compute Network

stochastic task costs

stochastic data sizes

stochastic compute speeds

stochastic communication strengths

t₇

unforeseen tasks

estimate task cost

actual task cost

6

Loyola Marymount

University

Thus brings us to the online problem

There has been a lot of work done on developing these heuristic algorithms for systems with perfect information, but in practice, this often not always the case.

Real-world situations are often riddled with uncertainty. Networks go down or preform sub-optimally, new tasks are added to workflows, and task durations are often unknown before runtime. This means we need to re-examine how we look at the problem. Lets return to our problem definition.

Starting again with our tasks, instead of assuming a set value, we are now considering stochastic task costs based on some distribution. So looking at the example normal distribution in the bottom right, we might have an estimate of our task size being around 5, but in actuality it could be much higher or lower. This can also be true for our data sizes, compute speeds, and communication strengths.

There is also the situation where we do not know all of our tasks at the start of runtime. Returning to our task graph, you can see I have added a seventh task that we might only become aware of halfway through runtime, and we want to be able to account for it in our schedule. All of these factors combine into what I like to call the online problem.

7 of 19

THE ONLINE PROBLEM

Hypothetical Schedule

Realized Schedule

Deterministic approach

Replace unknowns with estimates
Use classic scheduling heuristic
Commit entire schedule

Estimate task graph

7

Loyola Marymount

University

Let's take a look at an example to help illustrate why this key distinction is important. Here we have a task graph with 5 nodes, and their respective estimated sizes and weights. In this case, our network is two nodes with equal speed.

�

The first approach, called the Deterministic method, replaces any unknown information with estimations so a classic deterministic scheduling algorithm can build a complete start-to-finish schedule.

Deterministic strategies allow us to run tried and true scheduling algorithms, like HEFT or CPoP, and can be successful with a strong estimation approach, but it is lacking in runtime adaptability.

�

Let's take a look at the hypothetical vs realized schedule. We assume that task B is going to take a lot more time to run than it actually does, and the inverse for D, it runs a lot longer than expected. Because we commit to a full schedule and are unable to reallocate resources during runtime, we have a poor result, finishing at time 12, and there's a lot of empty space on node two we could take advantage of.

8 of 19

THE ONLINE PROBLEM

Perfect Information

Online

Fully online approach

Only consider tasks as they become available to schedule
Does not consider estimates of future costs

Actual task graph

8

Loyola Marymount

University

The second main proposed strategy is called the Online approach. This only considers tasks as they become available to schedule. So in our example here, the scheduler would first only consider task A, and once it has finished, it would then ONLY consider tasks B,C and D. This approach allows us to adapt to changes in runtime, including introducing new tasks to the system, but it doesn't build off our well explored offline algorithms. Furthermore, it can struggle in larger systems to make long-term scheduling decisions, often prioritizing short-term immediate successes.

In this example, this approach works really well! I have included the *best* schedule, created using HEFT with perfect information, and we can see that the online approach creates a schedule that finishes at the same time, despite a different order.

Both online and deterministic have usecases where they can be successful, but also have some pretty significant downsides. What if we could combine the two approaches?

9 of 19

OUR APPROACH

Online Rescheduling - HEFT

First task finished.

Once a task finishes, it cannot be rescheduled.

HEFT runs again scheduling around completed task.

Second task finished.

Online Rescheduling - HEFT

First task finished.

Once a task finishes, it cannot be rescheduled.

HEFT runs again scheduling around completed task.

Second task finished.

Online Rescheduling - HEFT

HEFT runs again scheduling around completed task.

Second task finished.

est. t₁

est. t₄

est. t₂

est. t₃

Compute node v₁

Compute node v₂

t₁

est. t₂

Compute node v₁

Compute node v₂

t₁

est. t₃

est. t₂

est. t₄

Compute node v₁

Compute node v₂

Estimated Schedule

Realized Schedule

t₁

est. t₃

t₂

Compute node v₁

Compute node v₂

Realized Schedule

t₂

Generate an estimate schedule, reschedule as tasks complete based on observed information
Running tasks locked
Modular

9

Loyola Marymount

University

At a high level, our approach for online scheduling is a simple repeated two-step process that is a mix of both methods. First, we generate a complete start-to-finish estimate schedule, the deterministic aspect. Once a task finishes, regardless if it was the task we expected to finish first, we generate a new schedule around the observed completion time. This rescheduling is the online aspect.

Importantly, any tasks that have started cannot be rescheduled or prematurely terminated. In this example, we can see that t1 finishes much earlier than we expected. Because t2 is still running, we can only reschedule t3 and t4. We estimate that t3 is going to take longer than t4, so we reschedule it to accommodate all the free space in the schedule. We then repeat this process until we are done!

One of the benefits of this approach is that it is general. Most research in the field is primarily concerned with just task uncertainty. Our approach can support uncertainty anywhere in the system, in the network or the tasks themselves, including adding new tasks to the queue during runtime. It also doesn't focus on perfecting a single estimate method, but rather provides the framework to apply any estimator, allowing for further scenario-dependent customization.

Using this method, we get the benefits of runtime adjustments, without having to sacrifice offline heuristics or future planning capabilities.

10 of 19

WORKFLOWS

Montage Workflow

WFCommons

Suite of 9 scientific applications
Tasks and edges fitted to common probability distributions
Computed nodes fitted to empirical distributions from execution traces

Applicable and large-scale

10

Loyola Marymount

University

11 of 19

EXPERIMENTAL SETUP

Computation-to-communication(CCR)

Varied from 0.2 to 5 to simulate compute-bound and communication-bound

Network Speed Estimate

Task Size Estimate

Estimator Method

Mean: E[X] of each task's cost or network speed distribution
SHEFT-inspired:

11

Loyola Marymount

University

The last piece of constructing our environment is our network bandwidth. Rather than sample from a distribution, we assume homogeneous bandwidth across the system. We do this so we can control computation-to-communication ratios. This allows us to observe and compare how rescheduling impacts compute-bound systems and communication-bound setups. A low CCR value means data movement dominates execution time, while a high value means a more computationally intensive system.
moving to our estimator, we have selected two methods for estimating from our distributions. The first is to simply take the mean of the distribution. The second, inspired by SHEFT, takes the mean and adjusts it based on the variance. Previously, SHEFT was meant only to handle task uncertainty, so we extended it for networks. The basic intuition here is pretty simple; when variance increases, we bake in a buffer by assuming worse performance. For network speeds, SHEFT adjusts down as variance increases, and for task costs, it adjusts them up.

12 of 19

COMPARING ALGORITHMS

Heuristics: HEFT and CPoP
Schedulers

Online: Our proposed strategy. Reschedules as task durations are revealed
Naïve Online: One-shot estimation schedule
Offline: Assumes full knowledge of actual network and tasks weights

Evaluation – Normalized Makespan Ratio

Ratio closer 1 indicates performance closer to ideal scheduler

12

Loyola Marymount

University

Before we can talk about some results, we have to go over how we compare schedulers. We test our method on two scheduling heuristics, HEFT and CPoP. These representt two of the most popular offline methods

For simplicity, we call our approach, where we reschedule as tasks finish, online. Then we have a naïve baseline, which schedules once based on estimates and deterministically commits everything. Finally, we have our target for achievable performance, which is the offline scheduler, which is the heuristic with perfect information about the network and tasks.

We evaluate based on makespan – the time from the first task starting and the last task ending. Because our workflows can have wildly different makespans, we have to normalize. We normalize over the makespan of the offline scheduler to get an idea of how close we get to the best possible performance possible by the heuristic. A ratio closer to 1 indicates the uncertainty approach, online or naïve, achieved results similar to the offline scheduler.

Lets take a look at some results.

13 of 19

RESULTS

13

Loyola Marymount

University

We will start off by looking at some general results about how online performs against naïve across CCR values. There are three key observations we can make

First of all, and most obvious, Online schedulers consistently outperform naïve. This confirms the benefit of rescheduling, and we typically see relative improvements of about 15%-20%. The online approach achieves results within 3-5% of the ideal offline scheduler, while the naïve is closer to ten

Secondly, Mean estimators slightly outperform SHEFT estimators. This one was definitely a bit surprising, because SHEFT is designed for conservation based on variance. This suggests conservative estimates do not always yield better results, and for some applications, simpler estimators will perform better.

Our final observation is that, in most cases, variance is substantially reduced by online schedulers. Tighter ranges for the online boxplots suggest that in addition to improving makespan, online rescheduling makes results more predictable.

14 of 19

WORKFLOW SPECIFIC RESULTS

14

Loyola Marymount

University

Those last results were taken across all nine of our workflows, but let's remind ourselves that the nature of scheduling algorithms is such that algorithms and approaches will perform differently depending on the setting they are applied to. To examine this phenomenon, let's look at CPoP with mean estimator, but this time split up our results based on workflow.

We still see that rescheduling improves makespan across *most* workflows, but not always. Most notably, montage actually has the online scheduler preforming WORSE than the naïve approach! We suspect this might be due to the high variance in some task costs in montage compared to other workflows. Examining the trace data, we see there are tasks with runtimes from 11 seconds, all the way up to 24 hours!

While reactivity improves variance and makespan across most cases, but it still cannot escape the limits imposed by the problem’s non-approximability and context dependence; different problems call for different solutions

15 of 19

CONCLUSION

Online Scheduling Framework: Enables classic offline heuristics to operate during runtime in heterogeneous distributed systems.
SHEFT adaptation: Extended estimator to networks.
Workflows: Proved the validity of online rescheduling on 9 applicable large-scale scientific workflows, improving mean makespan and variance in most cases.
Future Work:

Refined estimation methods that adapt to observations
Reinforcement learning integration
Multi-objective tradeoff
Computational overhead of rescheduling and time complexity

Selective rescheduling

ACKNOWLEDGEMENTS

This material is based upon work supported by the National Science Foundation under Award No. 2451267. This work was supported in part by Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196

15

Loyola Marymount

University

So to summarize, I:

Introduced our online scheduling framework for heterogeneous distributed systems, enabling classic offline heuristics to operate in the online environment with an emphasis on adaptability
Addressed adaptations made to the SHEFT estimator
Discussed results on proving the benefits of rescheduling on 9 applicable workflows

For future work we would like to:

Explore estimation methods that adapt during runtime

Integrate reinforcement learning to reconfigure parameters during runtime

Consider more objectives than makespan, such as fairness, energy efficiency, etc

Explore the computational overhead of rescheduling after every iteration, and with that explore selective rescheduling approaches that reduce unnecessary rescheduling calls.

And finally a more robust evaluation of our approach against other online approaches and realistic task-cost models

All in, we hope that this work will provide a baseline for further research in adaptive online scheduling approaches.

16 of 19

APPENDIX

16

Loyola Marymount

University

17 of 19

17

Loyola Marymount

University

18 of 19

PARAMETRIC SCHEDULING

Parametric scheduling framework.

36 offline list-scheduling algorithms and their online counterparts
4 modular components: Priority function, comparison function, insertion strategy, and critical path reservation

HEFT: Upward rank, earliest finish time, insertion-based, no critical path reservation
CPoP: CPoP rank, earliest finish time, insertion-based, critical path reservation

18

Loyola Marymount

University

We adapt a previously developed parametric scheduling framework for constructing our online algorithms. This framework breaks list scheduling algorithms into four main modular components. A choice of three priority functions, three comparison functions, append-only or insertion-based strategies, and finally, a true false critical path reservation setting.

Now I don't want to get too in the weeds on the details of the parametric scheduler, but this gives us immediate access to 36 list scheduling algorithms, and now their online counterparts. For this paper, we focus on two of the most popular algorithms, HEFT and CPoP. We can see that these two algorithms share a comparison function and insertion strategy, but differ in their priority function and whether or not they reserve a critical path.

We also need a baseline to compare our method against. We call this our *Naïve online baseline.* This uses stochastic duration estimates just like before, but commits ALL tasks on the first estimate and does not reschedule during runtime. This reflects many Deterministic-based current practices, which assume known runtimes but are usually based on collected data.

Performing better than this Naïve baseline can help us get an idea about how much better our online schedule is.

19 of 19

19

Loyola Marymount

University