Cloud providers must assign heterogeneous compute resources to workflow DAGs while balancing competing objectives such as completion time, cost, and energy consumption. In this work, we study a single-workflow, queue-free scheduling setting and consider a graph neural network (GNN)-based deep reinforcement learning scheduler designed to minimize workflow completion time and energy usage. We identify specific out-of-distribution (OOD) conditions under which GNN-based deep reinforcement learning schedulers fail and provide a principled explanation of why these failures occur. Through controlled OOD evaluations, we demonstrate that performance degradation stems from structural mismatches between training and deployment environments, which disrupt message passing and undermine policy generalization. Our analysis exposes fundamental limitations of current GNN-based schedulers and highlights the need for more robust representations to ensure reliable scheduling performance under distribution shifts.
Figures & tables
Figure 1. Overview of the workflow scheduling problem in a heterogeneous cloud . The scheduler receives a DAG with ready tasks and a set of machines with different speed and power. It must decide which task runs on which machine, and each choice changes both completion time and energy.
Figure 2. Schematic comparison of a wide DAG (left, shallow with many parallel branches) and a Long - CP DAG (right, deep dependency chain with limited side - branch concurrency).
Figure 3. Fitness landscape of the scheduling search space. We exhaustively enumerate all feasible action sequences for a small scenario and project them onto a 2D plane using a Hilbert curve. The Z-axis shows energy consumption (lower is better). Left: LongCP DAG. Right: wide DAG . A pair of side‑by‑side 3D landscapes compares scheduling fitness for two small task graphs. In each panel, every feasible scheduling action sequence is plotted as a point on a 2D plane generated by a Hilbert space‑filling curve; nearby coordinates represent similar sequences, and axis units are indices without physical meaning. The vertical axis is energy consumption, with lower height indicating a more efficient schedule. \parThe surface forms peaks, valleys, and plateaus. Valleys and basins mark clusters of low‑energy schedules. Peaks and ridges indicate schedules or neighborhoods with higher energy. Sharp drops or cliffs reflect cases where small changes in the action sequence cause large changes in energy, while smooth regions indicate insensitivity to local perturbations. \parThe left panel corresponds to a graph with a long critical path; the right panel corresponds to a graph with many parallel branches. The two surfaces differ in the location, size, and apparent density of low‑energy regions, illustrating how graph topology affects the distribution of good schedules and the ruggedness of the search space. Readers can use these landscapes to judge whether efficient schedules are concentrated in a few basins or dispersed across many regions, and whether exploring locally similar schedules is likely to yield gradual improvement or encounter abrupt changes. \parBoth panels were produced with the same enumeration and projection procedure, and the vertical scale represents energy in the same units, enabling qualitative comparison of landscape shape and the relative prevalence of low‑energy areas across the two task graphs.
Figure 4. Speed–power host regimes. Illustration of the four queue-free host regimes studied in this paper. Homogeneous-Speed: all VMs share the same processing speed but differ in power, isolating energy trade-offs at fixed makespan. Homogeneous-Power: all VMs share the same active power but differ in speed, isolating time trade-offs. Heterogeneous Aligned: speed and power are monotonically aligned, inducing an intuitive Pareto frontier between makespan and active energy. Heterogeneous Non-Aligned: speed and power are not aligned, creating counter-intuitive trade-offs and stronger generalization challenges for learned schedulers. A four quadrant schematic compares queue free host regimes by how virtual machines differ in processing speed and active power. Each quadrant shows a small set of VM markers that illustrate the relation between speed and power. \parHomogeneous Speed: all VMs have the same speed and different power. For a fixed workload the makespan is the same regardless of which VM is chosen, while total active energy changes with the selected power levels. \parHomogeneous Power: all VMs have the same active power and different speeds. Power per unit time is constant. Faster VMs shorten runtime and reduce active energy, slower VMs lengthen runtime and increase energy. \parHeterogeneous Aligned: speed and power increase together. Faster VMs always draw more power. This yields a clear trade off between time and energy, forming an intuitive Pareto frontier from slow low power to fast high power choices. \parHeterogeneous Non Aligned: speed and power have no consistent order. Some VMs are fast and low power, others are slow and high power. Dominance is unclear and the Pareto set can be irregular, creating counterintuitive trade offs and tougher generalization for learned schedulers.
Figure 5. Overview of the proposed GIN-based actor–critic scheduler architecture. Block diagram of a scheduler that uses an actor and a critic with a shared graph neural network. Inputs are two sets of nodes and two edge types. Task nodes carry status flags, remaining work, completion time, and resource needs. VM nodes carry current load, completion times, speed, core counts, available cores, memory capacity, free memory, and idle and peak power. Dependency edges connect parent and child tasks. Compatibility edges connect tasks to VMs that can run them. \parTwo small multilayer perceptrons encode tasks and VMs into a common latent space. Encoded nodes pass through several Graph Isomorphism Network layers that aggregate over both edge families. A global pooling produces a single graph embedding shared by both heads. \parThe actor head builds an embedding for each feasible task and VM pair by combining the task node, the VM node, and the graph embedding. A small scorer maps each pair to a scalar. Invalid pairs are masked. The remaining scores form a task by VM matrix, flattened and passed through softmax to produce a probability distribution over actions. \parThe critic head takes only the graph embedding and uses a small multilayer perceptron to output a single value that estimates expected return from the current state. Arrows indicate shared parameters between encoders and backbone, and separate outputs for policy and value.
Host cfg
Method
Eval Domain
Makespan
Active Energy
HS host configuration
HS
LongCP
LongCP
2.08
52.87
HS
wide
LongCP
2.08
51.00
HS
LongCP
wide
0.70
58.92
HS
wide
wide
0.70
57.11
HP host configuration
Table 1. Cross-domain evaluation of heterogeneous agents across host configurations. Best results for each evaluation domain within a host configuration are in bold.
Figure 6. Empirical attainment functions (EAFs) over 100 test jobs for the wide and LongCP specialists on the wide configuration (top) and the LongCP configuration (bottom). Each panel shows the distribution of the trade-off between normalized makespan (x-axis) and normalized active energy (y-axis), with color indicating the attainment level α and black contours marking α∈{0.5,0.75,0.9} . Two stacked panels summarize empirical attainment over 100 test jobs for two schedulers: a LongCP specialist and a wide specialist. Axes show normalized makespan on the horizontal axis and normalized active energy on the vertical axis. Each panel depicts the empirical attainment function as filled levels with overlaid contours at attainment levels 0.5, 0.75, and 0.9. The top panel uses the wide host configuration; the bottom panel uses the LongCP configuration. In each panel, the shapes of the attainment regions indicate how often a scheduler reaches points in the time–energy plane. Regions shifted left indicate shorter makespan, regions shifted down indicate lower energy. The side by side attainment patterns allow comparison of which scheduler more frequently reaches low time versus low energy regions, and how the full distribution of outcomes spreads across the trade off frontier.
Figure 7. Correlation between makespan and active energy across Pareto checkpoints for AL (top row) and NA (bottom row), with LongCP and wide specialists. Grid of subplots reporting the correlation between makespan and active energy across saved Pareto checkpoints. The top row corresponds to an aligned regime and the bottom row to a non aligned regime. Columns compare LongCP and wide specialists. Each subplot summarizes, for a sequence of model checkpoints along the Pareto front, how strongly time and energy move together. Positive correlation means runs with longer time also tend to use more energy; negative correlation means improvements in time often come with higher energy or vice versa, indicating a stronger trade off. Near zero indicates weak or inconsistent relationship. The layout lets the reader see how regime and specialization affect the sign and magnitude of the objective correlation across training checkpoints.
Figure 8. Panels: a) Active energy, case NA; b) Active energy, case AL; c) Makespan, case NA; d) Makespan, case AL. A 2 by 2 layout shows objective landscapes in a 2D projection of the actor’s parameter space, with the same axes across panels labeled First Principal Direction and Second Principal Direction. Each panel displays a background field representing the objective value over this plane and a single training trajectory drawn as a curve with a start marker (filled circle) and an end marker (X). Lower values are better for both objectives. \parPanel a (active energy, non aligned regime): the trajectory starts near the upper left and moves downhill toward a broad low energy basin near the center left, then continues to the right, ending slightly above the basin’s minimum. \parPanel b (active energy, aligned regime): the path again descends toward a central low energy region but finishes to the right of the minimum, indicating a modest rise relative to the best area. \parPanel c (makespan, non aligned regime): the trajectory begins left of center, ascends mildly, then turns and descends toward the lower right, finishing close to a region with low makespan. \parPanel d (makespan, aligned regime): the path starts near the upper left, curves toward a low basin near the lower center, and ends mid right, not at the lowest area. \parAcross panels, the same projected coordinates allow comparison of how training moves through different landscapes under two regimes (aligned and non aligned) and two objectives (active energy and makespan). A colorbar is present to indicate objective magnitude, while the curve and markers highlight the progression from initialization to the final checkpoint.
Figure 9. State visitation under a fixed mixed objective and non-aligned speed–power. (a) Conceptual state-space diagram with anti-aligned red (makespan) and blue (energy) descent directions, plus an inset showing non-aligned host speed–power. (b) Long Critical Path (LongCP) training: KDE contours and rollouts concentrate in high-parallelism regions. (c) wide DAG training: visitation shifts toward lower-parallelism states. A 2 by 2 layout shows objective landscapes in a 2D projection of the actor’s parameter space, with the same axes across panels labeled First Principal Direction and Second Principal Direction. Each panel displays a background field representing the objective value over this plane and a single training trajectory drawn as a curve with a start marker (filled circle) and an end marker (X). Lower values are better for both objectives. \parPanel a (active energy, non aligned regime): the trajectory starts near the upper left and moves downhill toward a broad low energy basin near the center left, then continues to the right, ending slightly above the basin’s minimum. \parPanel b (active energy, aligned regime): the path again descends toward a central low energy region but finishes to the right of the minimum, indicating a modest rise relative to the best area. \parPanel c (makespan, non aligned regime): the trajectory begins left of center, ascends mildly, then turns and descends toward the lower right, finishing close to a region with low makespan. \parPanel d (makespan, aligned regime): the path starts near the upper left, curves toward a low basin near the lower center, and ends mid right, not at the lowest area. \parAcross panels, the same projected coordinates allow comparison of how training moves through different landscapes under two regimes (aligned and non aligned) and two objectives (active energy and makespan). A colorbar is present to indicate objective magnitude, while the curve and markers highlight the progression from initialization to the final checkpoint.
Dynamic cloud workflow scheduling must balance deadline satisfaction, container utilization, and energy consumption while dealing with stochastic task-execution speeds, placement-dependent communication, and coupled task and container decisions. Workflows are naturally modeled as directed acyclic graphs (DAGs), but conventional vector- or matrix-based states do not fully capture their dependency topology. To better represent task urgency and structural relationships, we assign predicted sub-deadlines to tasks and use a multi-head graph attention network (GAT) to extract dependency information from the evolving DAGs. Based on these representations, we develop a Graph Attention-Driven Hierarchical Reinforcement Learning (GA-HRL) framework and model the scheduling process as an event-driven hierarchical semi-Markov decision process (SMDP). Workflow arrivals and task completions trigger scheduling events. At each scheduling event, the Task Scheduling (TS) agent first processes the currently ready tasks by assigning them to admissible existing containers or requesting new ones. The requested containers are then processed by the Container Scheduling (CS) agent for host placement before the environment advances. The two agents are trained alternately using separate Proximal Policy Optimization (PPO). Experiments on the 2018 Alibaba cluster trace show that GA-HRL maintains competitive workflow success rate and, in settings where success is comparable, generally achieves higher container utilization and lower energy consumption. Under the largest speed variation, it trades a small success-rate margin for substantially lower energy. Simulation code is available at: https://github.com/zongjin130/GA-HRL.
Zongjin Li, Shaohan Feng, Chunxi Yang +1
Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China · School of Information and Electronic Engineering (Sussex Artificial Intelligence Institute), Zhejiang Gongshang University, Hangzhou 310018, China
With the rapid development of the Internet of Things, computation intensive directed acyclic graph (DAG) tasks have become increasingly common in cloud-edge-end collaborative environments. However, cloud, edge, and end nodes are highly heterogeneous in computing capacity, network bandwidth, and energy consumption, which makes the efficient scheduling of tasks with complex dependencies an NP-hard problem. Traditional heuristic algorithms and conventional reinforcement-learning methods often fail to capture the spatio-temporal dynamics of system resources. This paper proposes PPO-STGNN, a DAG task-scheduling algorithm that integrates proximal policy optimization (PPO) with spatio-temporal graph neural networks (STGNNs). The method uses an STGNN to extract features from both the DAG task topology and the physical cloud-edge-end resource graph, and then optimizes the scheduling policy through PPO to minimize makespan and schedule length ratio (SLR) while improving CPU and memory load balancing. To accelerate convergence, a multi-teacher behavior-cloning mechanism is introduced for pretraining. Experimental results show that PPO-STGNN significantly improves load balancing while maintaining a low completion time, making it suitable for dynamic and heterogeneous cloud-edge- end DAG scheduling scenarios.
Yangshuo Qi, Chenwei Wang, Zihan Shen +1
Beijing University of Posts and Telecommunications, Beijing, China · Google, Mountain View, USA · NanJing University, NanJing, China
Workflow scheduling in cloud computing demands the intelligent allocation of dynamically arriving, graph-structured workflows with varying deadlines onto ever-changing virtual machine resources. However, existing deep reinforcement learning (DRL) schedulers remain limited by rigid, single-path inference architectures that struggle to handle diverse scheduling scenarios. We introduce DEFT (Deadline-pErceptive Mixture-oF-Experts), an innovative DRL policy architecture that leverages a specialized mixture of experts, each trained to manage different levels of deadline tightness. To our knowledge, DEFT is the first to introduce and validate a Mixture-of-Experts architecture for dynamic cloud workflow scheduling. By adaptively routing decisions through the most appropriate experts, DEFT is capable of meeting a broad spectrum of deadline requirements that no single expert can achieve. Central to DEFT is a graph-adaptive gating mechanism that encodes workflow DAGs, task states, and VM conditions, using cross-attention to guide expert activation in a fine-grained, deadline-sensitive manner. Experiments on dynamic cloud workflow benchmarks demonstrate that DEFT significantly reduces execution cost and deadline violations, outperforming multiple state-of-the-art DRL baselines.
Ya Shen, Gang Chen, Hui Ma +1
School of Engineering and Computer Science, Victoria University of Wellington, Wellington, New Zealand