Graph Assisted Offline-Online Deep Reinforcement Learning for Dynamic Workflow Scheduling
Authors: Yifan Yang
Gang Chen
Hui Ma
Cong Zhang
Zhiguang Cao
Mengjie Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: workflow scheduling
graph attention neural network
reinforcement learning
online learning
Primary area: optimization
TL;DR: This paper proposes an offline-online DRL framework that uses novel graph representations to effectively and efficiently schedule dynamic workflows across heterogeneous machines, significantly improving flowtime compared to state-of-the-art methods.

Abstract: Dynamic workflow scheduling (DWS) in cloud computing presents substantial challenges due to heterogeneous machine configurations, unpredictable workflow arrivals/patterns, and constantly evolving environments. However, existing research often assumes homogeneous setups and static conditions, limiting flexibility and adaptability in real-world scenarios. In this paper, we propose a novel *Graph assisted Offline-Online Deep Reinforcement Learning* (GOODRL) approach to building an effective and efficient scheduling agent for DWS. Our approach features three key innovations: (1) a *task-specific* graph representation and a *Graph Attention Actor Network* that enable the agent to dynamically assign focused tasks to heterogeneous machines while explicitly considering the future impact of each machine on these tasks; (2) a *system-oriented* graph representation and a *Graph Attention Critic Network* that facilitate efficient processing of new information and understanding its impact on the current state, crucial for managing unpredictable workflow arrivals/patterns in real-time; and (3) an *offline-online* method that utilizes imitation learning for effective offline training and applies gradient control and decoupled high-frequency critic training techniques during online learning to sustain the agent’s robust performance in rapidly changing environments. Experimental results demonstrate that GOODRL significantly outperforms several state-of-the-art algorithms, achieving substantially lower mean flowtime and high adaptability in various online and offline scenarios.

Published as a conference paper at ICLR 2025
GRAPH ASSISTED - DEEP REINFORCEMENT LEARNING FOR DYNAMIC WORKFLOW SCHEDULING
Yifan Yang', Gang Chen', Hui Ma', Cong Zhang Zhiguang Cao*, Mengjie Zhang' Victoria University of Wellington, #Nayyang Technological University, SSinaapore Management University (yifan. yang, gang .nng.chi. chen, hui.ma, mengjie. (aang)eecs. vuw ac cong0300e ntu. ettu.edu.sg, zgcao@sma. edu.sg
ABSTRACT
Dynamic workflow scheduling (DWS) in cloud computing presents substantial challenges due to heterogeneous machine configurations, unpredictable work- flow arrivals/patterns, and constantly evolving environments. However, exist- ing research often assumes homogeneous setups and static conditions, limiting flexibility and adaptability in real-world scenarios. In this paper, we propose a novel Graph assisted Offiine- Online Deep Reinforcement Learning (GOODRL) approach to building an effective and efficient scheduling agent for DWS. Our approach features three key innovations: (1) task-specific graph representation and a Graph Attention Actor Network that enable the agent to dynamically assign focused tasks to heterogeneous machines while explicitly considering the future impact of each machine on these tasks; (2) a system-oriented graph representation and Graph Attention Critic Network that facilitate efficient processing of new information and understanding its impact on the current state, crucial for manag- ing unpredictable workflow arrivals/patterns in real-time; and (3) an offline-online method that utilizes imitation learning for effective offline training and applies gradient control and decoupled high-frequency critic training techniques during online learning to sustain the agent's robust performance in rapidly changing vironments. Experimental results demonstrate that GOODRL significantly out- performs several state-of-the-arr algorithms, achieving substantially lower mean flowtime and high adaptability in various online and offline scenarios.
INTRODUCTION
The advent of cloud computing has revolutionized the way computational resources are utilized and managed, enabling organizations to execute complex workflows efficiently (Jadeja & Modi, 2012; Marinescu, 2022). Each workflow typically represented Appendix A), where nodes correspond to tasks and edges represent task dependencies (Deelman al., 2015). The goal of Dynamic Workflow Scheduling (DWS) assign tasks to heterogeneous machines to minimize the mean flowlime across long operating duration (Huang et al., 2022).
Directed Acyclic Graph (DAG) (see
DWS is characterized by flexible task assignment across heterogeneous machines, unpredictable workflow arrivals and patterns, and rapidly changing environments, making it one of the most chal- lenging scheduling problems studied in the literature (Jayanetti et al., 2024). Despite its practical importance, DWS has received comparatively less attention previously. In fact, existing methods often oversimplify or fail to effectively address all these dynamic aspects.
Current approaches to DWS mainly rely static scheduling heuristics that ignore the complexity of real-time cloud environments. Hand-crafted heuristics, such as priority dispatching rules (PDRs) (Topcuoglu et al., 2002; Pham & Fahringer, 2020), are valued for their speed, intuitiveness, and ease of implementation, but require extensive expertise and time-consuming adjustments. In contrast,
"corresponding author

---

Published as a conference paper at ICLR 2025
Genetic Programming-based Hyper- Heuristic (GPHH) can automatically design PDRs through it- erative -ntuuatiion-nddeeluutioonn making it a state-of-the-ar approach for DWS (Xu et al., 2023; Chen et al., 2024). However, GPHH can be highly sensitive in performance to specific problem configurations (see Appendix K) and is unsuitable for online applications due to high instability.
Recent advancements in Learning to Optimize (L20) research (Kool et al., 2019; Wu et al., 2022) have successfully demonstrated the potential of using reinforcement learning (RL) algorithms to train neural network-based PDRs (a.k.a., scheduling agents) to tackle static scheduling problems (Zhang et al., 2020; Song et al., 2022; Zhang et al., 2024). Relevant studies clearly indicate that proper state representations are crucial for DRL (deep RL) algorithms to learn effectively (Zhang et al., 2024). However, existing vector- or matrix- -based state representations (Huang et al., 2022; Jayanetti et al., 2024; Zhu et al., 2024) cannot accurately capture sophisticated interactions between tasks and machines in the cloud (verified in Table 1). Although Graph Neural Networks (GNNs) can effectively process complex graph-
states (Sun & Yang. 2023; Grinsztajn et al., 2023; Zhang et al., 2024), their fixed graph structures, shared feature embeddings, and unmodified RL methods limit scalability for tackling large and highly dynamic cloud workflow scheduling problems. This calls for developing novel graph representations and neural network architectures that can properly manage and process the ever- werrchhagging state information, along with advanced learning methods to boost the adaptability and stability of the scheduling agents in both offline and online scenarios.
In this paper, we propose a novel Graph assisted Offline-Onling Deep Reinforcement Learning (GOODRL) approach for learning a scheduling agent to tackle DWS, featuring three innovations: (I) We develop task-specific graph and a Graph Attention Actor Network to facilitate flexible task assignment across heterogeneous machines. They together explicitly capture the future impact of each machine on the focused task at both topological and feature levels, significantly enhancing the agent's 's ability to precisely differentiate all eligible actions. (2) We design a system-oriented graph and a Graph Attention Critic Network to seamlessly integrate newly arriving workflows with ex- isting ones. By enabling bi-directional information flow and self-attention across all task nodes in the graph, the scheduling agent can accurately respond to real-time changes in the system state. (3) We propose an offline-online RL method that combines offfine imitation learning with online gra- dient control and decoupled high-frequency critic training techniques to sustain the agent's robust performance in rapidly changing environments. Experiments across diverse scenarios demonstrate the effectiveness and reliability of GOODRL. Our method tackles significantly larger and more dy- namic scheduling problems, which have been under-explored in prior works, consistently reducing the mean flowtime compared to multiple state-of-the-ar algorithms.
2 RELATED WORK
To motivate our research on learning-based approaches for DWS, we review prominent research works on relevant scheduling problems from recent years, focusing on graph representations, neural network architecture designs, and training methods. (See Appendix S for more details)
Graph Representations. Scheduling research typically uses disjunctive graphs (Song et al., 2022; Su et al., 2023; Corsini et al., 2024; Zhang et al., 2024) or Directed Acyelic Graphs (DAGs) (Mao et al., 2019; Luo et al., 2021; Sun et al., 2021; Zhu et al., 2024) to represent system states, capturing various information related workflowssjobs and machines. While disjunctive graphs model static job shop scheduling (JSS) through single static graphs of all known jobs on homogeneous machines (Zhang et al., 2020; Song al., 2022: Su et al., 2023), they fail handle the dynamic nature of unpredictable workflows and heterogeneous machines in DWS. In cloud computing, each workflow typically represented as a separate DAG, which captures task-relate information only, ignoring machine-related information. Current research processes each static DAG individually (Mao et al., 2019; Zhu et al., 2024), failing to model the real-time interactions across multiple dynamically arriving workflows and preventing them from being used to solve DWS problems effectively.
To address this, we propose a novel real-time graph representation to comprehensively model the state of multiple workflows and heterogeneous machines. Unlike prior works where actor and critic networks rely on the same graph representation (Zhang et al., 2020; Song et al., 2022; Zhu et al., 2024), we design two distinctive graph representations: one for the actor (for action selection), and another for the critic (for value estimation). This allows the actor to focus on ussk-specific information while ensuring the critic has access to the overall operating status of the DWS system.
2

---

Published as a conference paper at ICLR 2025
Architecture Design. Graph Neural Networks such Graph Convolutional Network (GCN) (Kipf & Welling, 2017; Mao et al., 2019; Ni et al.. 2021; Zhu et al., 2024), Graph Isomorphism Network (GIN) (Xu et al., 2018; Su et al., 2023), Heterogeneous GNN (Song et al., 2022: Wang & Gombolay, 2022), and Graph Attention Network (GAT) (Veličković et al., 2018; Song et al., 2022; Wang et al., 2023) are commonly used to process graph-based state representations. For example, Ni et al.
(2021) used GCN for extracting node embedding followed by self-attention layers to jointly process multiple sub-graph wub-graphs associated with different process stages. Zhang et al. (2020) utilized GIN to obtain node embeddings, which are concatenated through mean pooling and are further processed by the actor network. While effective, this approach can make it more challenging for the actor to distinguish between different actions, particularly in large graphs with many nodes. In view of this, Zhang et al. (2024) introduced two separate GAT networks in the actor to extract topological embedding and context-aware embedding individually.
To better capture workflow dynamics and accurately evaluate the current policy, we design separate architectures for the actor and critic networks respectively, allowing each to specialize in different aspects of the scheduling process.
Training Methods. Current bearning-based methods for scheduling problems include RL (Su et al., 2023; Lei et al., 2023; Zhang et al., 2023), as well as supervised (Pan et al., 2023; Luo et al., 2023), unsupervised, and self--spervvsed learning techniques (Corsini et al., 2024; Pirnay & Grimm, 2024). Supervised learning relies on expensive labeled solutions (Corsini et al., 2024). Self-supervised learning is highly sensitive to sample quality (Pirnay& & Grimm, 2024). RL-based methods are more suitable for dynamic scheduling in online settings, thanks to their ability to continuously learn and make real-time decisions in a changing environment. Existing RL methods include value-based (e.g., DDQN (Liu et al., 2022; Lei et al., 2023)), policy-based (e.g.. REINFORCE (Mao et al., 2019; Zhang et al., 2024), ES-RL (Su et al., 2023)). and Actor Aetto-Critic-een Crittc-based (e.g.. PPO (Lei et al., 2023; Zhang et al., 2023)) algorithms.
Different from existing studies that focus mainly on offline learning with limited adaptability, we propose a two-stage RI. approach for effective offline learning and stable online adaptation in DWS.
PROBLEM FORMULATION
DWS problem instance consists of a set W of dynamically arriving workflows and a collection M of heterogeneous machines. A workflow W; E W is modelled as DAG (see Appendix A), denoted by W; = (Ow:, Cw.). with a node set Ow, = {Ou,.... ........ Osm;) representing tasks and an edge set Cw: {(Oij, Ou OOi) Osk Ow, Each edge (Oij, O.k) indicates that task Oi, must be completed before Oik starts. Let O = Ow, U Ow, U... Ow be the set of all tasks to be executed to accomplish all workflows in W. Each task O. with a workload twa E R can be assigned to any machine Mg E M. Its execution time et(g) twrs of the assigned machine Mg. Each workflow W; arrives at a specific time at,, and is finished at ft; max; (ft,)) when all its tasks Oij Ow; are completed. The flowtime of workflow W; is determined by F, = ft: at,,
depends on the speed mss may
At each decision step t., single focused task O is identified. O2 is unassigned task that becomes ready for execution at time based on the current state of the DWS system. It will be assigned to a specific machine according to policy æ. Once assigned, Oº will be added to the machine's 's waiting queue. All pending tasks in the waiting queue are executed in the FIFO order (Senapati et al., 2021). The objective of DWS is to find a policy æ M, ~ (O M) to minimize the mean flowtime [W] I! F; across all workflows received within an operating duration, while obeying task precedence constraints. Appendix B explains the workflow scheduling process in details.
F = 1
METHODOLOGY
In this section, we introduce the proposed GOODRL approach. We first formulate DWS as a RL problem where novel task-specific and orieendd graph representations are introduced. Then, we detail the architecture designs of the baseb actor network and the GaT-based critic network. Finally, we outline the offline-onlime RL. method.
3

---

Published as a conference paper at ICLR 2025
Offine Learning
Online Learning
Iniliiized Intiiaizad Crilie
Inttalized
Information:
Olseevation
System of
Butter sampled By HEFT
Iniladio Leaming
Standard PPO
Onina PPO
Online Schedules
Repescntation:
Task-spectto GGrpp (*(sf.
System nted Gmeh 9"
Intated Actor
Pre-traned Astor
End
Model:
Actor Network
Cracc Networe V/
(a) The two-stage offline-online learning process.
(b) Information processed by the tor and critic.
Figure I: The overall framework of GOODRL for DWS.
Figure 1 illustrates the overall framework of our GOODRL approach. In Figure (()), the offline stage begins by pre-training the actor network with imitation learning to follow expert-designed PDRs (e.g., HEFT (Topcuoglu et al., 2002; Senapati et al., 2021)). This prevents the accumulation of uncompleted tasks, which would otherwise occur if training started with a randomly initialized actor. Such accumulation can lead to memory issues and significantly increase computation time required for training the actor network. Standard PPO (Schulman et al., 2017) is subsequently employed to train the actor and critic networks. In the online stage, the pre-trained actor network is continuously fine-tuned by the newly developed online PPO algorithm. This is achieved by using gradient control and decoupled high-frequency critic training techniques introduced in Section 4.3.2. The information processed respectively by the actor and critic networks is shown in Figure 1(b).
Scheduling Agent
4.1 REINFOR LEARNING PROBLEM FORMULATION
RL Algorithm
upisic:
We model the scheduling process in the DWS system an RL problem, as shown in Figure 2. The Scheduling Agent an intelligent entity composed of an Actor, a Critic, and an RL Algorithm. As model of policy म, the actor selects an action/machine ae to execute the focused task O at any decision step L. The critic evaluates the actor's expected fu- ture return. The RL Algorithm continuously improves the performance of the actor under the guidance of the critic. The Cloud Environment employs a Workflow Pool to keep track of all workflows being executed on all available Ma- chine Resources, providing system state st agent observa- tion st. and reward rt to the scheduling agent. The key components (S A P, R, V) of this RL problem are explained as follows.
Reward
Action
Crilic
Pz
System State
Agent
Observation
Cloud Environment
Workflow
Machine
Pool
Resources
Figure 2: The RL based formulation of the DWS systems.
System State. Each system state of E S is a snapshot of the current status of the whole DWS system at decision step including (1) the focused task Oj; (2) details of all workflows under processing, including information of their constituent tasks, task dependencies modeled by DAGs, as well as workflow arrival times; and (3) the current processing status of each machine. We design novel system-oriented graph (s{) = (Oi, Cw U CM U Ca) to represent sf as the input of the critic V, as shown Figure 3(a). Only uncompleted tasks are included in (*(sf) for efficient memory usage.
Moreover, the edge set in (s{)) covers three types of information: (1) task precedence constraints Cw (e.g.. edge (012, 014) E Cw in Figure 3(a) indicates that task O14 cannot be executed before completing task 012): (2) machine processing order constraints CM (e.g., edge (O13, O23) CM in Figure 3(a) indicates that machine M1 must execute O13 first before executing Oza); and (3) the
eligible actions/machines for executing Of represented by C. {(O)a:) Oî) aa E A}. Each edge in CA connects the last task node Olae). denoting the most recent task assigned to an eligible machine, to O; (e.g., task O23 connected by edge (O23, O31) E C. in Figure 3(a) is the last task assigned to machine M1). In summary, gOss models the evolving interactions across all workflows at each system state sf. providing the critic with a comprehensive view of the DWS system.
Agent Observation. The agent observation of at decision step l is partial observation of the system state sf. To accurately capture subtle differences among all candidate actions for executing Oj, we propose novel task-specific graph (" ax) (O,, Cw U CM U Ca.) to represent observation- action pair (sf, a,) as the input of the actor æ,, as shown in Figure 3(b). The new graph representation explicitly captures the future impact of each specific action/machine Ma, O from two levels:
4

---

Published as a conference paper at ICLR 2025
Task Execution Status
unsnasigned
focused
asosigned
complite Qi
Machine Processing Oder
Ma
(*((f)
(e 0i)
Examples
of Oui
aqumup
Wi O
Ou
Ow: Oue = Osi
last task on
O₂ (0 Ons,0..00 On,,010 OrL, Ost.
machine
Oa On. Oaa Out)
Ow (00s Os4), (Ou, Ord,
W2
(On, Omd) (Os Ord,
O0. Osa), (Os, Osllis
focused task
(10,, Oia,, (Ou, Osa)]:
newly
odges
Cu (10z. On), (Osa. On)hi
anived
W3
worldlow
c. O(On,
C. ((0,..
(a) System-oriented Graph Representation
(b) specffe Graph Representation
Figure 3: Examples of two novel graph representations. The DWS system at the current decision step includes workflows and 2 machines, requiring the assignment of the focused task O31 to either machine M1 or M2-
(1) At the topology level, an edge Ca, = [((0 0,)} is inserted in (s{ a+) to capture the interaction between Oü and the selected machine Ma, (e.g., edge (O23, Os1 in Figure 3(b), since O2g is the last task assigned to machine M,, which is Ma, in this example). (2) At the feature level, the raw feature vector of Of is updated in real-time to predict the consequence of processing
Of using Mo.. The real-time updated feature vector E. E R² includes seven important features defined in Appendix C, including task execution status eSij, task workload twij. remaining workload of associated workflow rwaj, task execution time et!y) task completion time at (g) machine speed m8g. and machine utilization millg
Actions. Any action d₁ E A assigns the focused task Oj to the waiting queue of an eligible machine Mg. The size of the action space is |A|| [M].
Transition. The system transits from state 8; to state 8 after taking action de, which assigns the focused task at decision step to a specific machine for execution. See Figure 8 in Appendix B.
Rewards. A reward iz provides scalar feedback signal for taking action a, at system state sf. In line with the objective to minimize the mean flowtime F, we define r. = Σ Wweew F,, where We refers to the set of workflows completed in between decision steps and t 1. If no workflows are completed during the two steps, Vr = 0.
Learning Objective. The scheduling agent aims to learn an optimal policy (modeled by the actor) maximize the expected total rewards (estimated by the critic) from the long-term operation of the DWS system in both offline and online scenarios.
4.2 GRAPH ATTENTION ACTOR AND CRITIC NETWORKS
In the following, introduce the architecture designs of the Graph Attention Actor Network (s at) and the Graph Attention Critic Network (o(s)), respectively.
4.2.1
ACTOR NETWORK ARCHITECTURE DESIGN
Tadk-peeelfe Graph Representation
Task-specfic Embedding Modul
Selection
Agant
GAT
MUP
Somo ed Action
Layers
Embodding
Layers
Peir
Figure 4: Schematic design of the graph attention actor network.
Figure depicts the architecture design of the actor network To(of, at) with trainable parameter 0, aiming to accurately differentiate all eligible machines for processing the focused task. The actor network takes each observation-action pair represented by the task-specific graph G" (f. az) as its input, and transforms (s) a,) into the node embedding of the focused task O through GAT layers. By concentrating on the focused task/node, the subsequent Multi-Layer Perceptron (MLP) layers easily produce discriminative scores for different (s8, at) pairs. These scores are further
5

---

Published as a conference paper at ICLR 2025
processed by the softmax function to generate the probability distribution over the action space for reliable action selections by the actor.
Task-specific Embedding Module. In Figure 4, K GAT layers (Veličković et al., 2018) are utilized to extract the node embedding of the focused task Of from (s), 0z). Appendix D presents the detailed mathematical modelling of the GAT layers. The node embedding hog , (K) E Rd with respect to the focused task OF at the K-th GAT layer is extracted from the task-specific graph (sf: az) and is further processed by an MLP for action selection.
Action Selection. To determine the probability of performing any action de A according to wa. our actor network uses MLP layers to process the focused node embedding har extracted from G" (sf. ae). A score z z(5" ax) = M L (h.g, .a.) is hence calculated. After obtaining the scores of all eligible actions, the action selection probability is determined using the popular softmax function: T (sf. 0+) softmax( {=(s).a))/az E A)). An action 0₂ is then chosen following these probabilities
Remark. Our actor network design introduces two advantages for flexible task assignment across heterogeneous machines. (1) Pairwise processing: Instead of processing all tasks and machines in a single static graph as in previous studies (Song et al., 2022: Su et al., 2023), we calculate each (sf, ut) pair separately. This design explicitly considers the immediate and future impact of assigning any machine to the focused task at both the topology and feature levels, allowing the actor to accurately differentiate all eligible actions and make informed scheduling decisions. (2) Focused embedding: Our design learns the embedding of the focused task directly, rather than using mean pooling combine embeddings of all nodes, in many existing studies (Zhang al., 2020; Corsini et al., 2024). This design can effectively prevent the learned embedding from being diluted by irrelevant information from non-focused tasks/nodes. Relevant ablation experiments on the actor network architecture design are reported in Appendix F.
4.2.2 CRITIC NETWORK ARCHITECTURE DESIGN
-oriete- Graph Represeatation
System- eeitt-eriented Embedding Modale
State Valuee
Syswm f
GAT Layers
Local Topological
Self- Albention on Layers
Global col Embeddiinge
obal Graph Ersowdiing
Kglet)
Embeedding
Figure 5: Schematic design of the graph attention critic network.
Figure 5 depicts the architecture design of the critic network (s() with trainable parameter ø aiming capture the full information of the system state required for effective cemporalddiffernnce learning (Sutton, 2018). The critic network takes system-oriented graph representation (*()) as its state input. GAT layers are employed first by the critic compute all node embeddings based on the local topological structure of (sf).. Subsequently. Self-Attention layers are utilized to handle the relationship among all task nodes of (s(s) at the global scale. The resulting node embeddings are then aggregated via mean pooling and processed by MLP layers to predict the expected future return of the DWS system.
Embedding Module. Unlike previous approaches where the actor and critic net- works share a common feature extractor (Ni et al., 2021; Song al., 2022: Wang et al., 2023), our critic network uses its own GAT layers and self-attention layers (Vaswani, 2017; Ni et al., 2021) to extract node embeddings from (sf).. Specifically, K GAT layers are used to obtain the em- beddings of all nodes in (s))). The corresponding mathematical modelling of these layers can be found in Appendix E.
After obtaining all node embeddings, employ L layers of self-attention to integrate information from all nodes in (s)). The update rule for the I-th self-attention layer is:
(n (
(ue-
(u (WC-DW!)
u = softmax
(1)
Vd
where (0) = -ee (K)
IEO, E Rolxd is the collection of node embeddings produced by the GAT
layers, n()) [e( (K+))
IZEO, RllOIxdd is the collection of node embeddings produced by the I-th

---

Published as a conference paper at ICLR 2025
self-attention layer, and w w K. w E Rdxdd are the learnable weight matrices of the 1-th self-attention layer. Finally, all node embeddings aggregated using the common mean pooling technique to construct the high-level global embedding of (*{) as follows:
cxS- = Oil
1
Σ
(K+L)
(2)
DEO:
where e (K+L) E 12 is the embedding of node x, corresponding to a row of u((
State Value. The state value is computed by passing the aggregated global embedding e5g through an MLP, yielding (=f+ = (Leg( This scalar output from the critic network estimates the expected future return from system state of upon following the actor.
Remark, Our critic network design brings two key benefits for handling unpredictable workflow (1) Comprehensive context awareness: The GAT layers process each edge of (sf) in both directions. We further add additional edges between the focused task and all eligible machines in (sE), enabling the critic directly assess the influence of both past and future tasks on the focused task, providing comprehensive contextual understanding of task-mechine interactions. (2) song-range interaction modeling: It is well-established the scheduling literature that distant task nodes in complex graph such as (s()) can strongly influence each other (Ni et al., 2021). We employ a self-attention mechanism to capture long-range dependencies across all task nodes, including those belonging to newly arrived workflows, empowering the critic with a holistic view of the system's 's dynamics. Relevant ablation experiments on the critic network architecture design are reported in Appendix G.
arrivals and patterns.
4.3 OFFLINE-ONLING REINFORCEMENT LEARNING
Two learning stages are involved in training the scheduling agent. In the offline stage, we pre-train the agent's actor and critic networks establish effective initial policies for the DWS system. In the online stage, pre-trained networks are fine-tuned in real-time to adapt to the changing environment.
4.3.1 OFFLINE LEARNING
We employ both the imitation learning method (Barde et al., 2020) and the PPO algorithm (Schul- man et al., 2017) to train the actor and critic networks. Initially, the actor network is trained through imitation learning, with the widely used HEFT heuristic serving as the teacher. (Topcuoglu et al., 2002). This approach avoids the unnecessary trial-and-error required for training randomly ini- tialized actor, which can cause unprocessed tasks to accumulate in the DWS system, increasing memory demands and risking program interruption. Therefore, the actor network can be quickly and effectively trained to achieve comparable performance as HEFT with high sample efficiency.
Afterwards, the PPO algorithm is utilized to train both the actor and critic networks. Iteratively, PPO samples N independent trajectories to update both networks, further enhancing the effectiveness of the actor while keeping the critic accurate. See Appendix H.1 for the pseudo-code of offline learning.
4.3.2 ONLINE LEARNING
We develop online version of the PPO algorithm that simultaneously uses the actor to sched- ule newly arriving workflows while continuously improving its performance during the day-to-day operation of the DWS system.
The standard PPO algorithm, which relies on multiple short trajectories for robust policy updates, is not suitable for online learning, where stable actor updates must be performed on single long- lasting trajectory. We improve PPO with two techniques for online learning, enabling the actor to be reliably and quickly fine-tuned to meet changing scheduling demands.
First, we implement Gradient Control to stabilize actor training by regulating the gradient magni- tude. Specifically, adopt the following threshold to bound the L2 norm of the policy gradient vector used for training the actor network:
VoJ, if [|VoJ]1a S Pprey + Opee and [ TO.
V
0,
otherwise,
7

---

Published as a conference paper at ICLR 2025
where Vg. stands for the policy gradient. Merey and Opeev the mean L2 norm of VaJ and the corresponding standard deviation from the previous training epoch. To bounds the maximum allowed L2 norm of VJJ. Whenever the L2 norm of VoJ J is too large, we avoid using it to train the actor network (i.e., VoJ is set to the zero vector). This prevents abrupt change of the actor network, ensuring stable learning in dynamic environments.
Second, we train the critic network independently and at a higher frequency than the actor, fully decoupling their training processes. This separation prevents interference between the networks during training, providing the actor with more stable guidance from the critic's accurate value esti- mates. The pseudo-code of our online PPO algorithm is presented in Appendix H.2.
EXPERIMENTS
This section evaluates GOODRL's performance, starting with the experimental setup and baselines, followed by offline and online comparisons, and ablation studies to assess some key components.
5.1 EXPERIMENTAL SETUP
Environment Settings. We follow the framework of Huang et al. (2022) to perform training and testing on distinct offline and online scenarios listed in Table and Table 2. Each scenario involves multiple machines and a series of dynamically arriving workflows. A scenario contains either 5 x or 6 x 4 machines, representing the number of machine configurations and units per configuration respectively (see Appendix I.3 for details). Four popularly studied workflow patterns (Deelman et al., 2015) (see Figure 9 and Table 6 in Appendix A) are used to randomly create 30 workflows for offline training and 1 3k, 5k workflows for offline evaluation. In online testing, we further assess PDRs and scheduling agents real-time conditions. These workflows arrive dynamically following a Poisson distribution, with an arrival rate of (5.4,9) 9} workflows per hour.
large scenarios with 5k, 10k, and 20k workflows under demanding
Model Configurations. Detailed information regarding the network architecture, normalization method, offline imitation learning, offline PPO, online PPO, hardware/software platform, and al- gorithm implementation is presented in Appendix J. Our code and data are publicly available at https://gttub..oom cotieuuu.cooo/oaaaaaaaaaaaaaaaaa Yang 1950/GODL
Baselines. We compare GOODRL against three well-known PDRs designed manually by DWS experts: Earliest Start Time (EST), Predict Earliest Finish Time (PEFT), and Heterogeneous Earliest Finish Time (HEFT) (Topcuoglu et al., 2002; Senapati et al.. 2021). We also employ the state-of- the-art GPHH method for DWS as a baseline to evolve high-performing PDRs through extensive evolutionary search. For GPHH, we use standard parameter settings from previous studies (Xu et al., 2023), perform 30 independent runs with different random seeds and report the best results obtained (details in Appendix K). Given the limited research GNN-based state representations for DWS, we compare GOODRL with ERL-DWS (Shen et al., 2024), an advanced DRL method with an advanced transformer- baasdd neural network architecture. Their average performance is evaluated using five random seeds.
5.2 PERFORMANCE COMPARISON IN OFFLINE SCENARIOS
Table presents the mean flowtime achieved by GOODRL and competing algorithms across 12 of- fline scenarios. Each scenario contains 30 problem instances of 1k, 3k or 5k workflows each. Since the test performance of the best scheduling heuristic evolved by GPHH varies hugely across differ- ent scenarios, we report the best test results achieved by the top three heuristics obtained from 30 independent runs (see Appendix K for details). Despite our best efforts, including adding imitation learning, ERL-DW'S showed significant improvement in test performance. We hence report its best available results in Table 1. Appendix P further reports the inference time of these methods.
GOODRL achieves consistently low mean flowtime in Table 1, with average rank of 1.17 across all scenarios, outperforming all baselines. Compared to expert-designed PDRs (EST, PEFT, HEFT), GOODRL significantly reduces the mean flowtime, with Gap differences up to 289.98%. Although GPHH slightly outperforms Oofs--Offiin" (i.e., trained offline with GOODRL) on scenarios (5 x 5.4, 1k) and (5 x 5, 5.4, 3k), the Gap differences merely 1. 1.24% and 0. 15%. However, GPHH
8

---

Published as a conference paper at ICLR 2025
Table 1: Performance comparison in offline scenarios. "(6 x 4, 9, 1k)) each instance in this scenario contains 1000 workflows arriving rate of 9 workflows per hour, which need to be assigned to machines with 6 different configurations, with 4 units per configuration. "Obj.": the mean slowtime over 30 instances. "Gap": the gap the best "Obj" in each row. "bold": the best
result in each scenario. "blue bold": the average ranking across all scenarios of the best approach.
EST
PEPT
HEFT
GPHH
ERL-DWS
Ours-Offline
Scenarios
Obj. Gap
Obj.
Gap
Obj-
Gap
Obj.
Gap
Obj.
Gup
Obj-
Gap
(5 x 5,5,4 1R)
1243.15 15
204.51%
551.30
35.04%
509.95
24.91
408.24
0.00%
1889.47
362.83%
413.29
1.24%
(5 x 5,9,1k 18)
1152.40
177.94%
510.55
23.14%
478.44
15.39%
430.28
3.78%
2180.41
425.89%
414.61
0.00%
(6 x 4,544 18)
1083.02
290.07%
438.40
57.90%
391.61
41.05%
322.52
16.16%
713.87
157.11%
277.65
0.00%
4,9,
990.20
248.92%
391.17
37.84%
357.95
26.13%)
300,20
5.78%
1523,83
436.95%
283.79
0.00%
5,6,,
1235. 14 202.87%
551.33
35.19%
508.10
24.59%
407.81
0.00%
2670.81
554.91%
408.41
0.15%
5,
1153.02
179.00%
510.22
23.46%
477.07
15.44%
427.04
3.33%
3582.70
766.91%
413.27
0.00%
4,54,44)
1081,28
289.98%
438.62
58.19%
390.64
40.89%
386.77 77 39.49%
1108.95
299.961%
277.27
0.00%
3,9,
992.46
250.72%
389.94
37.80%
356.08
25,88 25.83%
358.40
26.65%
2748.28
871.19%
282.98
0.00%
5,5,, 5k)
1231.70
202.34%
550.53
33.13%
507.91
24.67%
408.38
0.24%
2944.35
622.73%
407.39
0.00%
5,9,
1146.62
177. 17%
509.61
23.19%
477.12
15.33%
427.88
3,43%
4299,75
939.38%
413.68
0.00%
(6 5k).
1076. 75 288. %
437.53
57.71%
389.24 24
40.30%
386,95
39.47%
1281.00
361.73%
277.44
0.00%
6
x 4.9.5)
992.92 250.55%
388.68
37.22%
356.47 25.85%
297.40
5.00%
3480.87
1 1128.92%
283.25 0.00%
5.08
2.92
5.92
1.17
exhibits extensive performance variability, with Gaps reaching 39.49% and 39.47% to GOODRL in other scenarios. ERL-DWS performs significantly worse than GOODRL as high as 128.92%% Additionally, both expert-designed PDRs and GOODRL exhibit robust performance the number of workflows increase, while GPHH and ERL-DWS deteriorate significantly. Overall, our offline results demonstrate the impressive performance of GOODRL on DWS problems.
5.3 PERFORMANCE COMPARISON IN ONLINE SCENARIOS
Table 2 presents the mean flowtime obtained by all algorithms in online scenarios. "Ours-Offline" refers to the online performance of the scheduling agent only trained offline by GOODRL. "Ours- Online" indicates the online performance of the scheduling agent that is trained both offline and online by GOODRL. "Ours-Online" achieves the highest rank of 1.17 across all compared algo- rithms. Both "Ours-Online" and "Ours-Offline" significantly outperform expert-designed PDRs (EST, PEFT, HEFT) and ERL-DWS. While GPHH ranks third, it relies on the best result of 30 runs, requiring approximately 200 CPU hours for training. Additionally, GPHH's performance de- grades as the number of workflows increases. In contrast, "Ours-Online" consistently improves upon "Ours-Offinee.. with performance gains of up to 1.24% in the (6 x 4, 9, 20k) scenario. This highlights GOODRL's ability to adapt pre-trained agents to dynamic demands (see Appendix Q for more robustness experiments), owing to its dynamic graph representation and offline-online training scheme. Note that even small improvement in mean flowtime can yield substantial practical benefits, including significant cost savings in large-scale dynamic environments (see Appendix R).
Figure 6 shows the mean flowtime achieved by "Ours-offline" and "Ours-online" in three online scenarios, comparing their performance over 5000 consecutive workflows. To ensure fair and reli- able comparison, we begin tracking mean flowtime after the first 2000 workflows, by which point the DWS system has reached stable dynamics. "Ours-onling consistently achieves lower mean flowtime than "Ours-offline" throughout the entire evaluation, as clearly evidenced in Figure 6. These results highlight the effectiveness of online learning in GOODRL for continuously improving scheduling performance.
5.4 ABLATION STUDIES
(1) Actor Network: Table 4 (Appendix F) validates the task-specifi embedding module (TSEM) in our actor network. Our-TSEM, with pairwise processing and focused task embedding, achieved the lowest cross-entropy loss compared to TSEM w/o pair (removing pairwise processing) and TSEM w. mean (adding mean pooling). These results confirm that separating task-machine pairs and avoiding mean pooling greatly enhance the ability to differentiate actions by focusing on critical task-specific information. (2) Critic Network: Table 5 (Appendix G) validates the system-orient -riieted embedding module (SOEM) in our critic network. Ours-SOEM, incorporating bi-directional edges, additional connections, and self-attentio mechanism, significantly outperforms SOEM w/o. edge

---

Published as a conference paper at ICLR 2025
Table 2: Performance comparison in online scenarios. "Scenarios": the scenarios for evaluating
the online performance of the scheduling agent previously trained offline in (5 x 5, 5.4). "bold": the best result in each scenario. "blue bold": the average ranking across all scenarios of the best approach.
EST
PEFT
HEFT
GPHH
ERL-DWS
Ours-Oflling
Ours-Online
Scenarios
Obj
Gap
Obj.
Gap
Obj-
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
Obj.
Gap
(6 5,4, 5R)
1076.01
277.05%
439.28
53.93%
391.63
37.23%
303.70
6.42%
1349.12
372.74%
286.43
0.37%
285.38 0.00%
x
4,5.4,10k)
1077.09
279.13%
439.64
54.75%
390.26
37.37%
305.31
7.47%
1778.26
525,94%
284.09
0.00%
285.12 0.36%
[6 x 4,54, 20k)
1072.90
276.97%
54.55% 439.88
391.18
37.44%
309.12
8.61%
2257.78
693.29%
286, 08 0.52%
284.61 0.00%
[6 5k)
994.00
233.40%
84 30.09%
355.51
19.24%
303.57
1.82%
1246,91
318.24%
301.00
0.96%
298.14 0.00%
x 1.9,
993,97
03%
387. 64
31 85%
355,21
20.82%
307.27
4.52%
1838,20
525.24%
297.19
1.09%
294.00
0.00%
(6 x
2,9,
997.53
231 28%
388,
79
29. 12%
3.56.39
18.36%
312.56 5.08%
2783,78
835.93%
301.11 1.24%
297.44 0.00%
1.83
1.17
(a) (6 4, 9, 5k)
(b) (6 x 10K)
(c) 16 20k)
Objective
306
Ours Offine
Ours Onlie
300
Ours-OHtine
Oure Online
298
300
295
296
Oura-Oltin
Orne
2300
3000
4000
5000
5000
6000
7300
8000
9000
7030
8000
9000
10000
11000
12000
Cumulative Workflow Number
Figure 6: Performance comparison between "Ours-Offiine" (trained only offline with GOODRL) and "Ours-Online" (trained both offline and online with GOODRL) in three online scenarios.
(removing bi-directional and additional edges) and SOEM w/o. self (removing the self-attention layers) in value loss. The results highlight the importance of comprehensive context awareness and modeling long-range interactions for effectively managing dynamic workflows. (3) Online Learning: Table 13 (Appendix L) validates two key techniques proposed for online training. Ours- Online achieved superior online performance improvement compared to Online w/o. grad. (remove gradient control) and Online w/o. freq. (remove independent frequecyy critic updates). These results demonstrate the effectiveness of both techniques in stabilizing and enhancing online learning.
5.5 SCALABILITY, TRANSFERABILITY AND EXTENSIBILITY OF GOODRL
(1) Scalability to significant changes: Experiments in Appendix M demonstrate that our model can effectively handle significant changes in workflow patterns, arrival rates, and machine configurations without retraining. (2) Transferability to FJSS: We applied GOODRL to FJSS problems studied in Song al. (2022), a representative research work on FISS, to validate its transferability. Results in Appendix N demonstrate that GOODRL, designed for complex large-scale DWS problems, can also performs competitively on other scheduling problems such as FISS. (3) Extensibility to multi- objective problems: In Appendix O, we demonstrate empirically that GOODRL. can support other practical objectives such as cost, beyond flowtime reduction, by modifying the reward function. In particular, the actor trained with the modified reward can achieve desirable trade-off between flowtime and cost, with a slight increase in flowtime but substantial cost savings of up to 41 %.
6 CONCLUSION AND FUTURE WORK
This paper proposes GOODRL, an offline-online DRL approach for DWS. GOODRL features three key technical innovations. First, it introduces new task-specific graph representation and Graph Attention Actor Network to assess the immediate and future impacts of assigning any machine to process focused tasks, enabling the scheduling agent to dynamically and effectively manage work- flow execution. Second, GOODRL adopts a novel restem-oriented graph representation and a Graph Attention Critic Network to model complex interactions across multiple workflows and machines, providing accurate value estimates from a holistic system-wid perspective. Third, GOODRL lever- ages offline imitation learning for efficient actor pre-training and an enhanced online PPO algorithm with gradient control and decoupled high-frequency critic training techniques for robust real-time adaptation. Experimental results confirm that GOODRL significantly outperforms sate-of-the-an art baselines in minimizing mean flowtime. In future work, we could explore unlimited machine con- figurations, constraint handling and multi objett- learning techniques to tackle constrained multi- objective scheduling problems in cloud computing and other complex computing paradigms.
10

---

Published as a conference paper at ICLR 2025
7 ACKNOWLEDGMENT
The authors thank Zaixing Sun, Zhengxin Fang, and Jian Liang for valuable discussions. We wish acknowledge the use New Zealand eScience Infrastructure (NeSI) high performance com- puting (HPC) facilities https://www.nesi.com computing.githut www.gub...o/rapoiooooooooooooo
and the Räpoi HPC cluster (https:/vuwwrrsearcch This research partially supported by Grant VUW-FSRG- 10114, administered by Victoria University of Wellington. This research is also supported by the National Research Foundation, Singapore under Al Singapore Programme (AISG Award No. AISG3-RP-2022-031))
REFERENCES
Batuhan Altundas, Zheyuan Wang. Joshua Bishop, and Matthew Gombolay. Learning coordination policies over heterogeneous graphs for human-robot teams via recurrent neural schedule propa- gation. In International Conference Intelligent Robots and Systems, pp. 11679-11686. IEEE, 2022.
Paul Barde, Julien Roy, Wonseok Jeon, Joelle Pineau, Chris Pal, and Derek Nowrouzezahrai, Ad- versarial soft advantage fitting: Imitation learning without policy optimization. In Advances in Neural Information Processing Systems, volume 33, pp. 12334-12344, 2020.
Nikhil Barhate. Minimal pytorch implementation of proximal policy optimization. https://
github. wwm/ http://whhiaaaaateeeeeeeeee Pyroch,, 2021.
Jieyi Bi, Yining Ma, Jianan Zhou, Wen Song, Zhiguang Cao, Yaoxin Wu, and Jie Zhang. Learning to handle complex constraints for vehicle routing problems. In Advances in Neural Information Processing Systems, 2024.
Xinan Chen, Ruibin Bai, Rong Qu, Jing Dong, and Yaochu Jin. Deep reinforcement learning assisted genetic programming ensemble hyper-heuristics for dynamic scheduling of container port trucks. IEEE Transactions Evolutionary Computation, 2024.
Andrea Corsini, Angelo Porrello, Simone Calderara, and Mauro Dell' Amico. Self-labeling the job shop scheduling problem. In Advances in Neural Information Processing Systems, 2024.
Ewa Deelman, Karan Vahi, Gideon Juve, Mats Rynge, Scott Callaghan, Philip J Maechling, Rajiv Mayani, Weiwei Chen, Rafael Ferreira Da Silva, Miron Livny, al. Pegasus, a workflow man- agement system for science automation. Future Generation Computer Systems, 46:17-35 2015. URL https:t//////. ppq.aus.ssssssa isi. edu/.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Nathan Grinsztajn, Daniel Furelos-Blance Shikha Surana, Clément Bonnet, and Tom Barrett. Win- ner takes it all: Training performant rl populations for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 48485-48509, 2023.
Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
Jiang-Ping Huang, Liang Gao, and Xin-Yo Li. An end-to-end deep reinforcement learning method based graph neural network for distributed job-shop scheduling problem. Expert Systems with Applications, 238: 121756, 2024.
Victoria Huang. Chen Wang, Hui Ma, Gang Chen, and Kameron Christopher. Cost-aware dynamic multi-workflow scheduling in cloud data center using evolutionary reinforcement learning. In International Conference Service-Orientel Computing, pp. 449-464. Springer, 2022.
Yashpalsinh Jadeja and Kirit Modi. Cloud computing conceptss architecture and challenges. In International Conference on Computing, Electronics and Electrical Technologies, pp. 877-880. IEEE, 2012.
11

---

Published as a conference paper at ICLR 2025
Amanda Jayanetti, Saman Halgamuge, and Rajkumar Buyya. Reinforcement learning based work- flow scheduling in cloud and edge computing environments: A taxonomy, review and future directions. arXiv preprint arXiv:2408.02938, 2024.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Kun Lei, Peng Guo, Wang, Jian Zhang, Xiangyin Meng, and Linmao Qian. Large-scale dynamic scheduling for flexible job-shop with random arrivals of new jobs by hierarchical reinforcement learning. JEEE Transactions on Industrial Informatics, 1001)1000--1018, 2023.
Renke Liu, Rajesh Piplani, and Carlos Toro. Deep reinforcement learning for dynamic scheduling of flexible job shop. International Journal of Production Research, 60(13):4049-4060 2022.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Information Processing Systems, volume 36, pp. 8845-8864, 2023.
Jinhong Luo, Yunfan Zhou, Xijun Li, Mingxuan Yuan, Jianguo Yao, and Jía Zeng. Learning to optimize dag scheduling in heterogeneous environment. arXiv preprint arXiv:2103.0663 2021.
Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh. Learning scheduling algorithms for data processing clusters. In Proceedings of the ACM Special Interest Group Data Communication, pp. 270 288, 2019.
Dan C Marinescu. Cloud computing: theory and practice. Morgan Kaufmann, 2022.
Fei Ni. Jianye Hao, Jiawen Lu, Xialiang Tong, Mingxuan Yuan, Jiahui Duan, Yi Ma, and Kun He. A multi cillt--graphhh attributed reinforcement learning based optimization algorithm for large-scale hybrid flow shop scheduling problem. Proceedings of the ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 3441-3451, 2021.
Zixiao Pan, Ling Wang, ChenXin Dong, and Jing-Fang Chen. A knowledge-guides end-to-end optimization framework based on reinforcement learning for flow shop scheduling. IEEE Trans- actions Industrial Informatics, 20(2): 1853):88333333 1853-1861, 2023.
Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learning schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11):3360-337) 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances Neural Information Processing Systems, volume 32, 2019.
Thanh-Phuong Pham and Thomas Fahringer. Evolutionary multi-objectio workflow scheduling for volatile resources in the cloud. IEEE Transactions on Cloud Computing, 10(3):1780-179,, 2020.
Jonathan Pirnay and Dominik G Grimm. Take a step and reconsider: Sequence decoding for self- improved neural combinatorial optimization. arXiv preprint vrXiv:2407.17206 2024.
Shuo Qin, Dechang Pi, Zhongshi Shao, Yue Xu, and Yang Chen. Reliability-wware multi-objective memetic algorithm for workflow scheduling problem in multi-cloud system. IEEE Transactions on Parallel and Distributed Systems, 34(4):1343 1361, 2023.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint 17770:1707 2017.
Debabrata Senapati, Arab Sarkar, and Chandan Karfa. Hmds: A makespan minimizing dag sched- uler for heterogeneous distributed systems. ACM Transactions on Embedded Computing Systems, 20(5s): 2021.
12

---

Published as a conference paper at ICLR 2025
Ya Shen, Gang Chen, Hui Ma, and Mengjie Zhang. Cost-aware dynamic cloud workflow scheduling using self-attention and evolutionary reinforcement learning. In International Conference on Service- Service-Oriented Oriented Computing, pp- 3-18, 2024.
Wen Song, Xinyang Chen, Qiqiang Li, and Zhiguang Cao. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 19(2):600-1610,, 2022.
Chupeng Su, Cong Zhang, Dan Xia, Baoan Han, Chuang Wang, Gang Chen, and Longhan Xie. Evolution strategies-based optimized graph reinforcement learning for solving dynamic job shop scheduling problem. Applied Soft Computing, 145: 10596, 2023.
Penghao Sun, Zehua Guo, Junchao Wang, Junfei Li, Julong Lan, and Yuxiang Hu. Deepweave: Accelerating job completion time with deep reinforcement learning- basedd coflow scheduling. In International Conference on International Joint Conferences on Artificial Intelligence, pp. 3314 3320, 2021.
Zaixing Sun, Yi Mei, Fangfang Zhang, Hejiao Huang, Chonglin Gu, and Mengjie Zhang. Multi-uree genetic programming hyper-heuristic for dynamic flexible workflow scheduling in multi-clouds. IEEE Transactions on Services Computing, 2024.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, volume 36, pp. 3706-3731, 2023.
Richard S Sutton. Reinforcement learning: An introduction. A Bradford Book, 2018.
Haluk Topcuoglu, Salim Hariri, and Min- You Wu. Performance-effectt and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):260-274, 2002.
A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Runqing Wang, Gang Wang, Jian Sun, Fang Deng, and Jie Chen. Flexible job shop scheduling via dual attention network-based reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Shuang Wang, Xiaoping Li, and Ruben Ruiz. Performance analysis for heterogeneous cloud servers using queueing theory. IEEE Transactions on Computers, 69(4):563-57) 576, 2019.
Zheyuan Wang and Matthew Gombolay. Learning scheduling policies for multi- coordination with graph attention networks. IEEE Robotics and Automation Letters, 5(3):4509 4516, 2020.
Zheyuan Wang and Matthew Gombolay. Stochastic resource optimization over heterogeneous graph neural networks for failure-predictive maintenance scheduling. Proceedings of the Interna- tional Conference on Automated Planning and Scheduling. volume 32, pp. 527-536, 2022.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning scenario representation for solving two-stage stochastic integer programs. In International Conference on Learning Representations, 2022.
Keyulu Xu. Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
Meng Xu, Yi Mei, Shiqiang Zhu, Beibei Zhang, Tian Xiang, Fangfang Zhang, and Mengjie Zhang- Genetic programming for dynamic workflow scheduling in fog computing. IEFE Transactions Services Computing. 16(4):2657-2671. 2023.
Cong Zhang, Wen Song, Zhiguang Cao. Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances Neural Information Processing Systems, volume 33, pp. 1621-1632, 2020.
13

---

Published as a conference paper at ICLR 2025
Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling. In Interaational Conference on Learning Representations, 2024.
Lu Zhang, Yi Feng, Qinge Xiao, Yunlang Xu, Di Li, Dongsheng Yang, and Zhile Yang. Deep reinforcement learning for dynamic flexible job shop scheduling problem considering variable processing times. Journal of Manufacturing Systems, 71:257-273. 2023.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Chi Xu. Mv- moe: Multi-task vehicle routing solver with mixture-of-experts. In International Conference Machine Learning, 2024.
Kaige Zhu, Zhenjiang Zhang, Sherali Zeadally, and Feng Sun. Learning to optimize workflow scheduling for edge-cloud computing environment. IEEE Transactions Cloud Computing, 2024.
14

---

Published as a conference paper at ICLR 2025
A DIRECTED ACYCLIC GRAPH
A workflow W3 can be represented as a Directed Acyclic Graph (DAG), denoted by W; (Ow. Cw,), ). as shown in Figure 7. Here, Ow, {On, O12, Oin,) } is the set of nodes, where each node Oij represents a specific task of W; that needs to be executed. The edge set C, represents the directed edges between tasks, where each edge (Oij, Oas) indicates precedence constraint such that task Oi must be completed before task Oi can start. The execution of tasks in the workflow follows the topological order defined by the DAG. A task can be scheduled or executed only after all its predecessor tasks have been completed; such a task is referred as ready task.
workflow W1
workflow W22
workflow W3
Ost
33
(Ow, Cuj)
W₂ (Ow,,
W₂ Cws)
(On, Ora, Ozs, Ore)
Ow, (On, On, Oz, Onl)
Ow, (On, Ozn On, Ozt, On)
Ow, - ((On, Ora), (On, Ota), (On, O0), Ow))
On, (OO,. Ozs), (Osz, Owa) (On. Ozd)
Cns (OO,. Oz)) (Ozz. Osi). (Os, (Os,, On))
Figure 7: Three workflows in DAG form
B DYNAMIC WORKFLOW SCHEDULING PROCESS
Workflow scheduling involves assigning interdependent tasks to heterogeneous virtual machines to optimize specific objectives such as mean flowtime across workflows. In the scheduling process, certain constraints or assumptions must be taken into account:
The pattern of each workflow (i.e., DAG structure) is unknown until it reaches the system.
Tasks within workflow can be allocated any machine, with processing times varying cording to machine speeds.
Each machine can process only one task at time.
Only tasks with all predecessors completed are eligible for scheduling.
Figure 8 depicts the scheduling process in a DWS system. The process begins with the dynamic arrival of workflows into the Workflow Pool. At each decision step f. the system automatically iden- tifies unique task that needs to be assigned state St. called the focused task O For example, O43 is chosen as the focused task at the current state. The scheduling agent then assigns the focused task to one of the available machine queues according to a policy æ. For example, O43 assigned to the queue of machine Mj following M1 = x x(043, (M1, M,,.... M MM)) The assigned tasks waiting in each machine queue will be executed according to the First- In- First-Out (FIFO) principle (Deelman et al., 2015; Huang et al., 2022), and their execution time depends on the machine's pro- cessing speed. The task execution status in the workflow pool is updated step-by-step. transitioning from unassigned to focused, then to assigned, and finally to completed. Meanwhile, the schedul- ing agent iteratively updates the system, identifies new focused tasks, and manages task execution in line with machine queues until all tasks are completed.
Workfllow Pool
Update -
Machine Resource
Start
C
Machina Queues
Machines
Tire
als
& O
c utassigned O feeased task
① Jesignod mak compleedd
End
Any tasks?
Scheduler
facused
Eviend
Policy
and
Figure 8: Scheduling process in the dynamic workflow scheduling system.
15

---

Published as a conference paper at ICLR 2025
C RAW NODE FEATURES IN GRAPH REPRESENTATION
Detailed definitions of raw node features and their respective value ranges are reported Table In particular, for the four machine-related features (i.e., et, ct, ms, mu), if ((O E UCM U.a. or 3(., Ozy) E Cw UCM Ca., the feature values f(1) node 0 are calculated using the status of the specific machine My; otherwise, the feature value is estimated using the average information across all machines, denoted by ( on Mg-
p(()
Table 3: Meaning and value range of raw features within each node,
Symbol
Meaning
Explanation
Range
Represents four possible status of task Ozy:
Task exccution status
0,1,2,3
unassigned. focused, assigned, and completed.
workflow related
tway
Tisk worklead
workload lask Ozy-
39185.28
Remaining worklonds
The sum of the workloods of all unassigned tasks
associated workflow
workflow W; to which Ozg belongs.
29.41
The exccution time task Oey machine My. with @ indicating the average across all machines.
et or et
Task Exccution time
<4898.16s
(9)
or ct
(2)
Task completion time
expecied completion lame machine M, or Mg.
O.y
29.41 h
machine related
The procssiing speed machine M,, with y represcating the average processing speed
mse v
Machine speed
8.16.32.48.644.6
acrosa machines.
the rallo ils working time the total
may or may
Machine utilization
time, with q representing the system average.
[0,1]
D
EMBEDDING MODULE
We use K GAT layers (Veličković et al., 2018) to extract the node embedding of the focused task Of from G"(5), a.). Specifically, the update rule the k-th layer defined as follows:
(k) =a
Σ (EV(2)
w (k-1) Day
(k)
e
where h r.g RR is the raw feature vector of node in (" az) the input layer, and h Rd is the d-dimensional embeddings of node x at the k-th layer. Additionally, N(xx) (ulV(y,)) 2) or v(I,3) y) CwUCMUCa, } is the neighboring set containing all incoming and outgoing neighbors of node x in (st, (s)) Furthermore, (k) azz the attention coefficient between nodes and y at the k-th layer; w-(h) is the learnable weight matrix of the k-th layer; and a is non-linear activation function (e.g., ReLUU). The node embedding hizg. h E Rdd with respect to the focused task Of at the K-th layer is extracted from the task-specific graph (*(s,, a.) and is further processed by an MLP for action selection.
E SYSTEM-ORIENTED EMBEDDING MODULE
Unlike previous approaches where the actor and critic networks share a common feature extractor (Ni et al., 2021: Song et al., 2022; Wang et al., 2023), our critic network uses its own GAT layers and self-attention layers (Vaswani, 2017; Ni et al., 2021) to extract node embeddings from (x)). Specifically,, GAT layers are used to obtain the embeddings of all nodes (*()), with the update rule at the k-th layer defined as:
Σ (k) (h (k-1)
e =
(EN(2)
where e Rd is the d-dimensional embedding of node obtained at the k-th layer, (kk) is the
(k) layer's learnable weight matrix, a2y is the attention coefficient between nodes and y. and a is non-linear activation function (c.g., ReLU). The neighborhood set ((x) = (y/3(y x)) or (æ, y) e
UCUC UCAA) contains all predecessor and successor nodes connected directly node a in (xf))
16

---

Published as a conference paper at ICLR 2025
Table 4: Cross-entropy loss different iterations. "Ours-TSEM": our task-specific embedding module proposed in Section 4.2.1. "TSEM w/o. pair": an architecture that does not handle (s, a)
pairs; instead, it directly calculates all action selection probabilities based on a state. "TSEM w. mean": an architecture that additionally concatenates the mean pooling of all nodes from the task- specific graph input to the MLP.
Actor Architecture
100-th
200-th
300-th
400-th
500-th
600-th
701-th
800-th
900-th
Ours- Ours-TSEN TSEM 2.7486
2.7106
2.6881
2.6647
2.6498
2.6038
2.5726
2.5297
2.5091
TSEM w/o. pair
3.1707
3.1597
3.1538
3.1468
3.1435
3.1394
3.1365
3.1333
3.1302
TSEM w. mean
2.7099
2.7209
2.7152
2.6659
2.7109
2.6172
2.5989
2.5334
2.5243
F ABLATION STUDY OF ACTOR NETWORK ARCHITECTURE DESIGN
In Table 4, compare three alternative actor network architectures based their cross-entropy loss defined below averaged over five random seeds. This comparison provides insights into how well each architecture expected to achieve the lowest cross-entropy loss and hence is more capable of modelling effective scheduling policies.
learn from HEFT through imitation learning. The best architecture is
LCE
Σ ..EED
CrossEntropy(<oo($) .),
(5)
where DD is a repository of state-transition data obtained by using HEFT to schedule workflow tasks, (o( represents the probability distribution over eligible actions determined by the actor network with parameters 0,
We compare Ours-TSEM which incorporates the advantages of pairwise processing and focused embedding mentioned in Section 4.2.1, against two baselines: TSEM w/o pair (removing pairwise processing) and TSEM w. mean (adding mean pooling over all nodes).
Our-TSEM achieves the lowest cross-entropp loss in most cases, as its architecture precisely considers the impacts of each machine on the focused task, enabling the actor network to ef- fectively differentiate all candidate actions.
TSEM w/o pair demonstrates smaller reduction in loss than Our- TSEM. indicating that pairwise processing can accurately capture the task-machine interactions, facilitating effective scheduling.
TSEM w. mean leads to inferior loss, since it dilutes the information the focused task as a result of mixing the embeddings of all tasks, making it hard to distinguish eligible actions.
Overall, Our design of TSEM allows precise differentiation of actions, facilitating precise task signment across heterogeneous machines.
G ABLATION STUDY OF CRITIC NETWORK ARCHITECTURE DESIGN
In Table 5, we analyze the effectiveness of our critic network design based on the value loss, which measures the mean squared error between predicted state values and sampled returns:
LMSE
1 [D]
Σ (Vo(s)) RR)
SGED
where Vsf) represents the predicted value for state of with network parameters 6, and R2 the corresponding sampled return.
To validate the advantages of comprehensive context awareness and long-range interaction model- ing in our critic network design proposed in Section 4.2.2, we compare Ours-SOEM against two variants: SOEM w/o edge (removing bi-directional and additional edges) and SOEM w/o self (re- moving the self-attention mechanism).
Ours-SOEM achieves the lowest value loss in most cases, demonstrating the effectiveness of its design in capturing the full influence of fask-maching interactions, enabling the critic to make accurate value estimations.
17

---

Published as a conference paper at ICLR 2025
Table S: Mean relative error between return and state value at different iterations. "Ours-
SOEM": our system-oriented embedding module proposed in Section 4.2.2. "SOEM w/o edge":
only one-directional edges and no extra edges are used in Ours-SOEM. "SOEM w/o. self" Ours-
SOEM architecture removes the self-attention layer.
Critic Architecture
100-th
200-th
300-th
400-th
500-th
600-th
700-th
800-th
900-th
Ours-SOEM
16.3971
14.0938
10.4907
9,5811
7.8581
7.5675
7.1238
6.0035
6.2547
SOEM w/o. edge
17.3012
13.4737
11.6626
9.8066
8.8853
7.5266
7.5607
7,593
7.1468
SOEM wlo. self
20.6114
16.1826
14.6813
12.6997
12.0733
10.7019
10.1497
8.5121
8.5645
SOEM w/o edge shows higher value loss than on unidirectional edges limits the critic's ability capture the context of task-machine teractions. Without additional connections, it is challenging for SOEM w/o edge to capture comprehensive contextual relationships in the graph.
indicating that relying solely
SOEM w/o self exhibits a noticeable increase in value loss due to the lack of the self-attention layer, which is essential for modeling long-range interactions among task nodes. This capability is crucial for DWS, tasks from newly arriving workflows can have a long-range impact on existing tasks.
Overall, our design of SOEM enhances contextual understanding and effectively captures long- range dependencies. For example, in Figure 3(a), the newly arrived workflow W3s can be effectively incorporated into the current system state by using bi-directional and additional edges and the self- attention mechanism. Our design of SOEM enables the critic provide accurate value estimations and adapt to the complexities of unpredictable workflow arrivals and patterns.
H DETAILS OF OFFLINE AND ONLINE LEARNING ALGORIHTMM
H.1 DETAILS OF OFFLINE LEARNING ALGORITHM
For offline learning. we propose a two-step training process that combines Imitation Learning and Proximal Policy Optimization (PPO) for offline training, shown in Algorithm 1. In the first step, the actor leverages Imitation Learning to efficiently mimic the behavior of HEFT (Topcuoglu al., 2002), an expert-designed heuristic policy denoted by â, aiming to minimize the correspond- ing cross-entropy loss (line 7). This method allows the actor to quickly learn an effective policy, preventing the buildup of uncompleted tasks in the graph representation, which often occurs with randomly initialized policies.
The actor trained via imitation learning provides stable starting point for the second step. In the second step, ==4 independent trajectories are collected per training iteration. The scheduling agent jointly updates both the actor and critic networks in the direction of minimizing the clipped policy loss and the value function loss (line 24). This combination of imitation learning followed by PPO ensures robust performance while mitigating the risk memory overload.
H.2 DETAILS OF ONLINE LEARNING ALGORITHM
For online learning, we propose an enhanced version of the Proximal Policy Optimization (PPO) algorithm, as outlined in Algorithm 2. It enables the actor to dynamically schedule incoming work- flows while simultaneously refining its parameters during the operations of the Dynamic Workflow Scheduling (DWS) system. Traditional PPO relies on multiple short trajectories for effective policy updates, making less suitable for online scenarios where stable updates are necessary based on single long-lasting trajectory.
The algorithm alternates between real-time scheduling decisions (line 3-6) and network updates (line 8-24). The transition data by the interaction between the actor and the dynamic environment during real-time scheduling efficiently managed and stored through a fixed-size experience buffer B (line 6). For dynamically arriving workflows, at each step, the system needs to sample action/machine for the focused task based on the actor's 's policy. After every Tw steps (after an initial warm-up period of Tww). the most recent transitions in buffer B are used to update the actor and critic networks separately. The updated actor then resumes real-time decision decision-making making, gathering new transition data for the next network update cycle.
18

---

Published as a conference paper at ICLR 2025
Algorithm 1:
Offline Learning with Imitation Learning and PPO
Input: Initial actor network тp, initial critic network Vg, environment env; heuristic policy म, actor learning rate Ox, critic learning rate ov, value loss coefficient entropy loss coefficient Ce. clipping parameter 6, number of trajectories N, update epochs Eg and Eg. number of training steps U
Output: Pre-trained actor network Te, pre-trained critic network V
// Step 1: Imi tat Learning Initialize environment env and buffer D; while env is nol terminated do
Execute action a; = (8{) and observe next state 8141;
Store transition ( in buffer D;
- St+1i
for update = to E1 do
Compute cross-entropy loss: [CE 1o Eg Layaar aLED CrossEntropy(mo((f) a:);
Perform gradient descent on LCE to update 9 to mimic heuristic policy f:;
// Step 2: PPO Training
for each iteration = U do Initial buffer B; Ootd <- 0;
10
11
for π = to N do Initialize environment env, and buffer Br
13
while env, not terminated do
Sample action a₃ Teer Execute action a₂ and observe reward ra and next state 8141; Store transition (sf (t, rt; 81+1) in buffer Bai
15
17
- 81+1;
18
for each transition buffer B, do
Calculate Return: Rs > k=0
-1,11-1 -t
Caleulate Advantage: A, Rr Vo(s));
20
B BUB.:
22
for update = to E2 do for each minibatch B from buffer B do Compute aggregated loss:
24
CCLIP-
Σ min 1s))
Noaia (,, A, clip
Moord 185) - +5) Aj).
malayla;)
CVF
[8 プド (Va(s))
1
R2)
-= - + CVF
25
Perform gradient descent on to update 0 and Φ:
One technique of our approach involves monitoring the gradient changes of the actor (line 21-23). This is performed by controlling the mean L2 norm of the gradients ///l22 within a dynamically ad- justed threshold (line 2/). Actor updates permitted only when the gradient norm remains below this threshold, facilitating stable online learning. Additionally, the upper bound on gradient changes adaptively adjusted maintain controlled updates, ensuring stability in policy improvement and mitigating abrupt changes in actor behavior. This stabilization is crucial in dynamic environments, where sudden shifts in actor's policy could lead to catastrophic scheduling decisions, resulting in severe backlogging of subsequent workflow tasks.
Another technique is the independent, higher-frequnne training of the critic network (line 11-14). This decoupling from the actor's updates allows the critic to improve its accuracy of estimating fu- ture returns. Meanwhile, frequent critic update stabilizes online learning by providing more precise value estimations. Subsequently, the algorithm actor's parameter. Accurate critic predictions provide more reliable feedback for the actor, leading more effective policy improvement.
the updated critic guide the training of the
19

---

Published as a conference paper at ICLR 2025
Algorithm 2: Online Learning with Enhanced PPO
Input:
Pre-trained actor network TT. pre-trained critic network Va, environment env, discounting factor y, actor learning rate O'z, critic learning rate av,, entropy loss coefficient Ce, clipping parameter c, environment warm-up steps Tew: critic warm-up steps Tow. time window steps Tw. actor update epochs Es, critic update epochs E Output: Scheduling decision arrival workflows with |O) tasks
Initialize online environment env, and experience buffer B with fixed size 2i
for to |O] do
// Online Decision Making
Ondd <- 0;
Sample action at (8));
Execute action and observe reward r2 and next state st+1; Store transition (s ag rt, 8(++) in buffer B; if (t Tnw) )% = 0 and 2 T.w then for each transition buffer B do
Calculate Return using Tw steps of rewards: R₃ = 2
10
for update
Eg do // Update Critic Network for update = Fee/ Fig do for each minibatch B from buffer B do
12
Compute value loss: Lv | Σ
(Va(s)) R
Perform gradient descent on Lv to update d;
// Update Actor Network if (t /Tww//TT. 2 Tew then for each transition buffer B do Calculate Advantage: A, Rg Vo(+;;;
16
17
for each minibatch B from buffer B do Compute policy loss:
L E min (r, -c, c, A,,)
where (0) To (ayles)'
su(a;ls;)
Calculate the mean L2 norm of the actor's gradients [.]l2; |[ S μlprer + prey and || J S To then
Perform gradient ascent L. to update 0;
U Update the parameters of the gradient control Mkprev prev's
24
8z St+15
I SIMULATION SETTINGS
I.1 REAL-WORLD TRACES
Regarding real-world traces, previous studies explored three different aspects, as summarized below:
Workflow characteristics: Past studies considered different task dependency graphs, num- ber of tasks, and task execution time. They focused mainly on scientific workflows such as CyberShake and Montage (Deelman et al., 2015; Qin et al., 2023; Sun et al., 2024). For detailed introduction to these real-world scientifie workflows, please refer to (Deelman et al., 2015). These datasets are available in the workflow repository the Pegasus web- site (htps://downloud.poggaal wwwpppw..ii....uueaaeeap www.:///mmiii//ytteeeeeeeee wwtthheiewwofllwssstt....... tar.g).. In line with existing works, experiments were also conducted these scientific workflows.
Resource configurations: Past studies considered various resource configurations, including virtual or physical machine configurations, quantities, and prices. They mainly followed
20

---

Published as a conference paper at ICLR 2025
source configurations supported by major cloud providers, such as Amazon EC2', Google Cloud', and Microsoft Azure'. Our experiments adopted the resource configurations supported by Amazon BC2.
Existing studies primarily relied on workflow arrivals simulated by a Pois- son distribution, such as (Huang et al., 2022; Xu al., 2023; Wang et 2019). Please refer to (Wang et al., 2019) for theoretical analysis of such arrival patterns. Wang al. (2019) specif- ically pointed out that "the distributions of the time interval each request are exponential which implies that the arrival rates are Poisson distributed.".
Arrival patterns:
I.2 WORKFLOW INFORMATION
We adopt the common experimental setup used in the cloud computing domain (Huang et al., 2022;
Xu al., 2023), utillizing four widely-studied workflow patterns (Deelman et al., 2015), as shown in Figure 9. Each workflow pattern contains detailed information such as task workloads twy and the dependeney relationships between tasks, summarized in Table For more information, please refer to hups://pegasus. isi. wtt.ee//oooueeeattooo//o/ooo httpr//mnniiiooieeeiiiiiinnnnnno guide/introduccion..in htmll In the simulated exper- iments, these workflow patterns arrive dynamically according a Poisson distribution consistent with the default settings of existing studies (Wang et al., 2019; Xu al., 2023; Shen et al., 2024).
Montage
CyberShake
SIPHT
Inspiral
Figure 9: Four widely studied workflow patterns in dynamic workflow scheduling.
Table 6: Information of four widely used workflow patterns. "Total workload": the sum of all task workload twy in a workflow.
Pattern name Number of tasks
Number of edges
Average task workload
Total workload
Montage
25
45
145.76
1.01 h
CyberShake
30
52
405.6 (05.622
3.38 h
SIPHT
33
3060.12
24.65
Inspiral
30
35
3529.10
29.41 h
Figure 10 depicts the 95%-99% quantile of workflow arrivals different arrival rates. Specifically, the 95% and 99% quantiles at À 5.4 are 9.3 (approx. 280 tasks) and 11.7 (approx. 350 tasks) workflows per hour, and that are (approx. 420 tasks) and 16 (approx. 480 tasks) workflows hour.
I.3 MACHINE CONFIGURATIONS
The cloud system in our experiments supports six types of virtual machines. Each type follows strictly the latest machine configurations of Amazon EC2 instances, listed in Table 7. Here, the "vCPU" parameter indicates the processing speed ms of each machine. For example, task Oiş machine
with task workload twiy 402.3 will require an execution time of et; 402.3/8 M, equipped with 8 vCPUs. The number of machines for each configuration is determined by the specific scenario. For example, scenario denoted as in Table 7, with three machines of each type, resulting in a total of 12 machines.
9) comprises of the first four VM types
htttp:///wss.amazoo www./ooww..mmcc//pppionoo/oeaaeo
"https//cloou. miccrosof..com/eenng/iiiiiii http:://wwreemmmroofo..oo
21

---

Published as a conference paper at ICLR 2025
Work Low Courds
20
WORT Counts
Number Workllows
12.5
Quartla
Number of Workflows
50% Guentile
99% Quartile
10.0
1.5
7.5
10-
5.0
2.5
0.0
200
800
800
100
200
300
400
500
Arrival Time
Arrival Time
(a) = 5.4
(b)
9.0
Figure 10: New arrival counts of 95%-99% Quantiles at different arrival rates.
Table 7: Configurations of six machines based on Amazon EC2. "vCPU": used as the processing speed of the machine.
Instance Name vCPU
Memory On-Demand hourly rate
m5. 2xlarge
8
32 GiB
S0.344
m5. 4xlarge
16
64 GiB
S0.688
m5, 8xlarge
32
128 GiB
$1.376
m5. 1xxlage
48
192 GiB
$2.064
m5a. 6xllage
256 GiB
$2.752
m5a.24x
96
384 GiB
S4.128
MODEL CONFIGURATIONS
Network Architecture. The actor network consists of Graph Attention Network (GAT) layers with one attention head, followed by 4 MLP layers. The critic network V has 2 GAT layers with one attention head, self-attention layer with two attention heads, and MLP layers. Each of these layers has 128 hidden dimensions.
Normalization. All raw feature values are normalized by dividing by constants to maintain a con- sistent scale across the network inputs. The reward is normalized by dividing it by 1000 to ensure stability during training.
Imitation Learning. The actor network is pre-trained with 7680 state-transition samples obtained by using HEFT heuristic. The mini-batch size set to 64. The actor updated 10 epochs using the Adam optimizer with constant learning rate of 1 10-1 The choice of 10 epochs for pre- pre-training the actor network was based on experimental observations. After 10 epochs, the actor surpass the performance of the HEFT heuristic.
was able to match
Table 8: Imitation learning hyperparameters.
Hyperparamettrr
Value
Data size ((D)
7680
Num. epochs
10
Minibatch size
64
Actor learning rate 1 10-4
Offline PPO. We warm up the critic network for 200 iterations before running 1000 training itera- tions. Each iteration collects 4 independent episodes of transition data for actor and critic training. Following the implementation (Barhate, 2021). use a clipping parameter of 0.2 for PPO. The coefficients for the clipped policy loss and the value function loss are set to and 0.5, respectively. The discount factor 7 0.99. We use the Adam optimizer with fixed learning rates: 3 x 10-4 for the actor and x 10-3 for the critic. In each iteration, both the actor and critic networks updated for epoch.
Online PPO. For online learning, we update the pre-trained actor network over single long tra- jectory with approximately 30x 5000, 30 10000, or 60x20000 steps. After a system warm-up phase of 15000 30000 steps, begin running the online PPO algorithm. We first train the critic network for 50 iterations. Subsequently, both the actor and critic networks are trained for additional 250, 500, or 1000 training iterations. In each iteration, 512 steps of transition data collected to
22

---

Published as a conference paper at ICLR 2025
Table 9; Offline PPO hyperparameters.
Hyperparameter
Value
Critic warm-up iterations
200
Max training iterations
1000
Num. independent episodes
4
Num. epochs
Minibatch size
64
Clipping parameter
0.2
Policy coefficient
1
Value function coefficient
0.5
Discount factor (x)
0.99
Actor learning rate
3 x 10 10-4
Critic learning rate
1 1 10-3
alternately train the actor and critic networks, with mini-batch size of 64. The actor and critic are updated for 5 and 20 epochs per iteration, respectively. We use the Adam optimizer with learning rates of 5 x 10-5 for the actor and 10-4 for the critie. gradient control mechanism ensures that the gradient magnitude for each mini-batch stays within the range of the mean plus one standard deviation, based on the previous iteration's values, and does not exceed 0.075.
Table 10: Online PPO hyperparameters.
Hyperparameter
Value
Critic warm-up iterations
50
Max training iterations
250, 500, 1000
Windows stepsize
512
Num. epochs for actor
5
Num. epochs for critic
20
Minibatch size
64
Clipping parameter
0.2
Discount factor (r))
0.99
Actor learning
5 10-5
Critic learning rate
1 10-4
Maximum available gradient change (76)
0.075
Hardware platform and Algorithm Implementation. We implement the GAT networks using PyTorch-GGemmeric (Fey & Lenssen, 2019), and the rest of the components are built using Py (Paszke et al., 2019). Our experiments are conducted in a cloud computing environment to parallel the exccution of numerous experiments. Due to the predominance of CPU resources in the cloud environment, all experiments were conducted on CPU. The averaged offline training time was ap- proximately 150 CPU hours, while the averaged online training times were 30 CPU hours, 60 CPU hours, and 22 CPU hours, respectively. Our code and simulator will be made publicly available. Table 1:: Software and hardware version information.
Software and hardware
Version
Python
3.11.5
PyTorch
2.4.1
PyTorch-Geometric
2.5.3
rl-zo03
2.3.0
deap
1.4.1
Nodes
56
CPUs/Node
256
Available Mem/CPU
1850 MB
K OFFLINE PERFORMANCE OF GENETIC PROGRAMMING
Table 12 presents the mean and standard deviation results of the top three GPHH heuristics across various offline scenarios. For each scenario, the corresponding result averaged over 30 problem
23

---

Published as a conference paper at ICLR 2025
instances with each having 1000, 3000 5000 workflows. We select the best results in each sce- nario (summarized in the right column) and present them in Table 1. As evidenced in this table, the performance of GPHH varies significantly across different scenarios, indicating that the schedul- ing heuristic evolved by GPHH cannot reliably handle large-scale problems. Previous research on GPHH for DWS has typically focused small-scale problems (Xu al., 2023), often with around 30 workflows, where GPHH performed well. However, these small-scale problems are not popular in many cloud computing applications (Huang al., 2022: Zhu et al., 2024). Our results suggest that GPHH, when applied to large and more complex scenarios, can suffer from significant instability.
Mean and standard deviation objective of GPHH in offline scenarios. The mean performance of the top three GPHH heuristics on the validation set, evaluated across 30 instances.
Table 12:
Scenarios
GPHiII-top
GPHill-top GPHill-top
minimum
(5 x 5.4, 1k)
435.56
607.30
408.24
408.24
(5 x 5,9, 11)
430.28
267913.55
52435.90
430.28
(6 1,5
726.23
380.29
322.52
322.52
4,9,
5314.90
300.20
352.45
300.20
(5 5,54,3)
435.27
622.15
407.81
407.81
5,9,3))
427.04
1503503.96
21490.23
427.04
4,5.,333
759.19
386.77
484.37
386.77
(6 4,9,
7277.48
7277.48
358.40
358.40
(5 x 5,54,
437.32
622.01
408.38
408.38
(5 x 5k)
427.88
2650402.61
13750.89
427.88
(6 5.4,
728.35
386.95
590.84
386.95
(6 x 4, 9, 5k)
7504.89
297.40
360.58
297.40
L ABLATION STUDY OF ONLINE LEARNING METHOD
In Table 13, we validate two key techniques proposed for online training: gradient control and independent high-frequency critic updates, as described in Subsection 4.3.2. We compare Ours- Online against two baselines: Online w/o grad. (removing gradient control) and Online w/o freq. (removing high-frequency critic updates).
Ours-Online achieves consistent improvements in mean flowtime, demonstrating the stability and effectiveness of both techniques enhancing online learning performance.
Online w/o grad. shows slight deterioration, highlighting the importance of gradient control for stabilizing actor updates during online training.
Online w/o freq. performs significantly worse, with drastic negative impacts, indicating that frequent critic updates are crucial for providing accurate value estimates and guiding effective policy updates.
Overall, the inclusion of both techniques in Ours-Onling ensures stable and improved performance in online learning.
Table 13: Improvement in mean flowtime compared to Ours-Offline at different iterations. "Ours-Online": our online learning method proposed in Section 4.3.2. "Online w/o. grad.": our online learning method removes the gradient control technique. OOnine w/o. freq.": actor and critic are updated together using an aggregation loss.
Training Method
150-th
175-th
200-th
225-th
250-th
Ours-Online 1.62%
1.50%
1.57 %
1.52%
1.52%
Online w/o. grad.
-1.18%
-1.08%
-1.24%
-1.66%
-1.64%
Online w/o. freq. -184.80%
-261.27%
-283.93%
-336.86%
-382.54%
M SCALABILITY TO SIGNIFICANT CHANGES
We conduct additional experiments to test the generalization ability of our scheduling policy (i.c., actor network) without retraining, focusing scenario changes in workflow patterns, workflow
24

---

Published as a conference paper at ICLR 2025
arrival rates, and cloud configurations. The results demonstrate that our model can effectively handle variations in workflow patterns, arrival rates, and machine combinations.
As shown in Table 14, evaluated scenarios with significant differences from the training environ- ment. Here, the "-" symbol indicates that the setting remains the same as the original scenario, while "V" denotes change. The original training scenario involved mixed workflow patterns, À = 9.0, and set x 5 machines. Scenarios and 2 involve only compute-intensine workflow patterns (20 times larger in workload than normal ones), showing that our model maintains strong performance under significant changes in workflow patterns, Scenarios 3 to 6 involve variations in the combina- tion of machines (i.e., configurations each quantity), demonstrating our model's ability to adapt to changes in cloud configurations.
Table 14: Varied scenarios in workflow patterns, arrival rates, and machine numbers.
Workflow Arrival Machine Pattern
Scenarios
EST
PEFT
HEFT
GP
ERL-DWS
Ours
Rate
Number
1954.59
961.26
881.55
962.35
14103.84
862.59
2
V
2114.21
1005.76
904.06
832.37
6403.65
791.86
3
15
1793.76
927.33
872.71
1015.96
3208.32
761.24
x 10
1512.44
684.15
643.34
517.05
2696.69
509.17
5
5 5 7
1317.28
561.51
513.70
396.07
2534,30
385.44
6
6 6 5
1190.84
450.93
404.47
286.00
2420.63
282.07
N TRANSFERABILITY TO OTHER SCHEDULING PROBLEMS
To demonstrate the transferability of our method, we applied our graph representation and neural network architecture to the FJSS problems studied in Song et al. (2022), chosen for its strong rep- resentativeness. our experiments, all sequence-structures jobs of an FISS problem instance are represented jointly workflow, enabling pipeline to handle the FJSS problem effectively special case of our workflow scheduling problem.
As summarized in Table 15, GOODRL achieved highly competitive performance compared to DRL- and DRL-S proposed in Song et al. (2022) on the same FJSS test instances with different sizes. Results confirms that GOODRL can be transferred to solve related scheduling problems, including FISS problems. It is important to note that GOODRL is purposefully designed to address dynamic scheduling problems, leveraging key innovations such as task-specific and system-oriented graph representations, which are tailored to handle unpredictable workflow arrivals and evolving system states. Existing research such as (Zhang et al., 2020: Song et al., 2022: Zhang al., 2024; Huang et al., 2024) mainly considered static problems.
Table 15: Results on FJSS instance with different sizes. "DRL-G" and "DRL-G" are methods proposed in (Song et al., 2022).
FISS Size
MOR
SPT
FIFO
MWKR
DRL-G DRL-S
Ours
10x5
116.69
129.06
119.62
115.29
111.67
105.61
112.57
20x5
217.17
229.89
216.13
216.98
211.22
207.50
202.38
30x 10
320.18
347,40
328.50
319.89
313.04
312.20
304.63
40x 10
425.19
443.30
427.22
425.70
416.18
415.15
395.70
O EXPANDABILITY TO MULTI-OBBEECIVVE PROBLEMS
We conduct experiments to demonstrate our method can support other practical objectives beyond flowtime reduction, typically by modifying the reward function. By directly incorporating cost term into the reward function, we can re- re-train the actor to optimize for both VM cost (calculated based the hourly rental fees of each VM type) and flowtime. The results in the table below indi- cate that, when explicitly considering the cost of using VMs, the mean flowtime experiences a slight increase of up 8%, but substantial cost savings of up to 41 % achieved in some scenarios.
25

---

Published as a conference paper at ICLR 2025
Hence, with modified reward function, GOODRL can achieve desirable trade-off between flow- time and cost, showcasing its flexibility and practical utility. These results differ from our original focus reducing the mean flowtime alone and demonstrate the potential of GOODRL to support wide range of objectives.
Table 16: Performance comparison of policies trained with single and multi-ohjective.
Scenarios
Objectives Single-Ohj.
Multi-Obj.
Diff.
flowtime cost
401.77
420.29
+4.61%
(5 504,30)
139.82
82.28
-41.15%
flowtime cost
408.49
413.02
+1.1
(5 5.9,30) 30)
116.32
97.51
-16.17%
flowtime 277.57
286.73
+3.30%
(6 4, 5.4,
cost
192.24
143.47
-25.37%
flowtime 285.93
306,90
+7.33%
(6 4, 30)
cost
135.58
91.18
-32.75%
Extending our approach to incorporate multi-objective optimization is both feasible and valuable. Below, outline how this be achieved in general and the specific challenges that need to be addressed:
Reward design: A weighted reward combining flowtime and energy efficiency (or cost as proxy) can be used. Weights could be static or adaptively tuned.
Graph representation: Additional features like machine prices, scheduling overhead, and other Quality of Service (QoS) requirements can incorporated to provide the necessary con- text for optimizing both objectives.
Learning challenges: Conflicting objectives require strategies like Pareto-optimal training multi-critic designs to balance trade-offs effectively.
P INFERENCE TIME COMPARISON
At inference time, our model (i.e., the task-specific actor network) requires very short time to make a decision, as reported Table 17. Across various test scenarios, our model takes 6-7 ms to allocate a VM to process the target task. While prior approaches such ERL-DWS and GPHH faster, it is important to emphasize that our model's inference time is sufficiently short to meet the requirements of real-worid DWS problems. In fact, the inference time significantly less than the typical communication latency and data transfer time in a cloud environment.
Table 17: The average inference time to make decision.
Scenarios
GPHH ERL-DWS Ours
(5 x 5, 5.4, 1k)
0.7 ms
2.6 ms
6.1 ms
(5 X 5, 9, 1k)
1.0 ms
2.7 ms
7.6 ms
4, 5.4, 14)
0.6 ms
2.7 ms
6.0 ms
(6 4, 9, 1k)
0.7 ms
2.5 ms
6.8 ms
Q ROBUSTNESS ANALYSIS IN ONLINE SCENARIOS
(1) Fluctuation of Workflow Arrivals: We conducted additional experiments where we introduced significant changes to the arrival rate, ranging from decrease of 50% to an increase of 100% relative to the arrival rates used to train the actor network. As evidenced by the experiment results reported in Table 18, GOODRL can achieve consistently the best performance, outperforming all competing approaches by large margin. These results demonstrate that GOODRL is robust to substantial fluctuations arrival patterns and can effectively adapt to dynamic changes over time.
We have conducted additional experiments to investigate whether our online algorithm can quickly adapt to such performance deterioration. our experi- ments, we introduced artificial noise various levels the affline-trained actor to intentionally
(2) Fluctuation of Offline-trained Actor:
26

---

Published as a conference paper at ICLR 2025
Table 18: Performance comparison under changed arrival rates.
Arrival Rates
EST
PEFT
HEFT
GP
ERL-DWS
Ours
-50%
1288.59
626.37
567.55
403.99
2328.24
398.01
+50%
1165.15
516.60
481.70
413.99
4076,43
409.66
+ +100%
1112.05
498.06
469.46
424.92
$255.60
423.02
degrade its performance. We then trained this noise-infused actor online over series of iterations. As shown in Table 19, the initial performance dropped by approximately 3.7-3.8% compared to the actor without noise. However, after 150 online training iterations, this gap was significantly reduced to around 1-2%. These results clearly demonstrate that our online learning method in GOODRL can quickly adapt to distribution shifts and effectively recover performance, even when starting with suboptimal frfline-rraieed actor.
Table 19: Performance gap with the no-nosie actor across online training iterations.
Noise
0-th
25-th
50-th
75-th
100-th
125-th
150-th
c=0.05
3.71%
3.61%
3.49%
3.20%
2.21%
1.94%
1.95%
e=0.1
3.87%
3.66%
2.92%
2.42%
1.46%
1.10%
1.06%
R ADVANTAGES OF ONLINE RL COMPONENT
The adoption the Online RL component is important for ensuring long-term stability and practical utility in large-scale DWS problems:
Maintain high long-term utility: The online RL component enhances long-term utility of GOODRL by constantly learning from new experiences collected from the daily operation of the cloud system. Unlike offline learning, online RL avoids costly and unnecessary retraining of the actor from scratch. It is highly sample efficient and responsive, offering strong adaptability in practice.
The small improvement in mean flowtime can translate to a sig- nificant improvement scheduling efficiency and resource utilization for large-scale prob- lems. As shown in Table 20, even small improvements in flowtime (e.g., 0.84% reduction in average flowtime) can result substantial cost savings (e.g.. 16%1 reduction in ma- chine rental fees). We will include quantitative examples in the revised paper to clearly highlight the practical significance of this improvement.
Practical significance:
Table 20: Comparison of two scheduling plans in flowtime and cost.
Scenarios
Objectives
Scheduling Plan-1 Scheduling Plan-2
Diff.
flowtime 421.94
420.29
0.39% +
(5 x 5, 5.4,30)
102.44
82.28
19.68% |
flowtime
416.53
413.02
0.84% 4
(5 x 5, 9,9,300 30)
152.63
97.51
36.11% $
flowtime
292.81
286.73
2.08% 4
(6 x 4, 5.5,4,30 30)
188.43
143.47
23.86% 1
flowtime
309.70
306.90
0.90%
(6 x 4, 4, 30)
137.43
91.18
33.65% 4
S RELATED WORDS ON LEARN-TO-OPTIMIZE
The Learn-to-Optimizz (L20) field extensively uses Graph Neural Networks (GNNs) and Rein- forcement Learning (RL) to solve combinatorial optimization problems, including Vehicle Routing Problems (VRP) (Bi et al., 2024; Hou et al., 2023; Zhou al., 2024), Job Shop Scheduling (JSS) (Zhang et al., 2020; 2024; Park et al., 2021: Su et al., 2023; Huang et al., 2024), and Multi-Agent Task Allocation (MATA) (Altundas al., 2022; Wang & Gombolay, 2020). However, the specific
27

---

Published as a conference paper at ICLR 2025
graph representations and network architectures used in L20 approaches must be tailored to the unique characteristics and challenges of each problem domain.
These domain-specifte adaptations often constitute the core contributions of L20 research. In this context, our research introduces novel graph representations and network architectures specifically designed to tackle the unique challenges of dynamic workflow scheduling (DWS) problems, clearly differentiating it from existing L.20 approaches. For example, while encoder-decoder models are commonly used for VRPs, scheduling problems must handle complex operation-job-machiee con- straints, making such models less effective, as noted in Zhang et al. (2020).
In 1.00 research for scheduling:
Studies in (Zhang et al., 2020; Park et al., 2021; Zhang et al., 2024) tackled static JSS, where Zhang al. (2020) used topological graph representation directly trained with PPO, and Zhang et al. (2024) enhanced this with an additional context-aware embedding module to im- prove the actor's ability distinguish actions. Park al. (2021) incorporated raw features for static JSS to improve representation.
The work you mentioned in Song et al. (2022) addressed flexible JSS (FISS), which introduced heterogeneous graph representation and the corresponding network architecture design, di- rectly trained with PPO.
For dynamic Su et al. (2023) proposed new graph representations by considering stochastic processing times in raw features, and machine failures in action selection, and directly used the ESRL method. However, still focuses on small-scale problems, with unchangeable graph, i.e., the number of nodes on the graph is fixed over time.
The work in Huang et al. (2024) focused on distributed JSS, which also used PPO and claimed their contributions on graph representations for solving challenges in distributed JSS but with small-scale.
Thus, while these methods all leverage GNNs and RL, addressing the challenges in different problem variants still requires unique designs and careful considerations, making each approach valuable to the research community. As Zhang et al. (2024) highlights, "Unlike routing problems that are vastly studied, JSS has received relatively less attention, and the performance of existing learning- based solvers still far from optimal due to the lack of an effective learning framework and neural representation scheme".
Our work focuses on Dynamic Workflow Scheduling (DWS), which not only presents a more complex setting but also better aligns with real-world applications. It has great potential to push the boundary of using DRL to solve real-world COPs, especially scheduling problems, in several key aspects:
Dynamic and evolving states: Workflow arrivals and patterns are unpredictable. Conse- quently, the number of active workflows varies significantly across time, unlike the fixed setup in previously studied scheduling problems. This fluctuation in active workflows introduces unpredictable state transitions, requiring new methods to effectively handle their impact on learning stability and performance.
Large problem size: Our approach can handle problem instances involving to 600,000 workflow tasks, which is more than 100 times larger than previously studied ISS problems (Zhang et al., 2020; 2024; Park et al., 2021; Su et al., 2023; Huang et al., 2024) and MATA prob- lems (Altundas et al., 2022: Wang & Gombolay, 2020). Furthermore, Cloud service providers require scheduling policies that can continuously adapt to new operating conditions, necessi- tating online updates to policy network parameters.
Workflow-specific constraints and heterogeneous machines: Unlike JSS, DWS involves in- tricate inter-task dependencies, flexible machine choices, and highly heterogeneous processing time. These challenges demand for a novel design of the graph representations that can properly capture intricate relationship among tasks, workflows, and machines.
In view of the above challenges, existing graph representations and network designs for small-scal static JSS and MATA problems are insufficient for DWS.
28

---

Published as a conference paper at ICLR 2025
A recent survey (Jayanetti et al., 2024) from world-leading cloud computing research group vealed that existing RL-based methods for workflow scheduling often relied on vector or matrix representations, lacking effective GNN- based methods for this domain. Additionally, solving large- scale dynamic problems with PPO requires novel algorithmic designs to significantly enhance learn- ing stability, which is often overlooked in prior studies.
Building on the above discussion, our paper makes significant contributions to the existing literature on scheduling problems in:
Designing problem-specific graph representations and network architectures to tackle the unique challenges large-scale DWS problems, which have been largely overlooked in prior research; and
Proposing a novel offline-online learning framework to ensure high stability and adaptability in dynamic DWS environments.
29


Reviews:
[{"review_id": "ympmkDlrwe", "reviewer": "Reviewer_jCq6", "summary": "This paper proposes a novel Graph-assisted Offline-Online Deep Reinforcement Learning (GOODRL) approach for Dynamic Workflow Scheduling (DWS) in cloud environments. The authors introduces three main innovations: a task-specific graph representation with a Graph Attention Actor Network for focused task assignments, a system-oriented graph representation with a Graph Attention Critic Network for real-time state evaluation, and a hybrid offline-online RL method to improve adaptability. The offline stage uses imitation learning for stable initial policy development, while the online stage applies advanced PPO techniques for continuous adaptation. Experiments demonstrate GOODRL’s superiority over state-of-the-art methods in minimizing mean flowtime and enhancing performance in several offline and online settings.", "questions": "Besides the concerns raised in the weakness part, I have the following additional questions:\n\n1. PPO has also been applied to solve other combinatorial optimization problems like routing problems, where the horizons are also very large. Could you give some intuitions why PPO is particularly unstable for this problem?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow\n2. Special designs on the actor and critic network to have more efficient embeddings and long-range interaction modeling\n3. customized gradient for stabilizing the PPO training for the online settings\n4. Experiments are conducted on many online and offline settings", "weaknesses": "This paper presents a comprehensive learning pipeline for addressing the dynamic workflow scheduling (DWS) problem. I appreciate the authors for their efforts in adapting various components to suit the unique challenges of DWS.\n\nThe primary concern with this paper is the applicability of the proposed pipeline. Many of the modifications and design choices appear closely tailored to DWS, leaving it unclear how generalizable this approach might be to other scheduling problems, such as flexible job shop scheduling. Can these designs be readily adapted for other problem domains? The paper would be significantly strengthened by demonstrating the pipeline’s transferability to other scheduling scenarios.\n\nSeveral techniques are introduced throughout the pipeline, though not all are rigorously validated in the ablation study. A more thorough investigation into the contributions of each component would enhance our understanding of their individual benefits.\n\nOverall, I appreciate the contributions of this work and currently lean toward a borderline acceptance.\n\n---\nI increase my score to 8 in response to the author's rebuttal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jx2i1tamfO", "reviewer": "Reviewer_Eeze", "summary": "Prior works often consider homogeneous setups and static conditions, and fails to consider the dynamic nature of the workflow scheduling problem. To this end, the paper proposes a GNN-based DRL approach with an offline stage as well as an online stage.", "questions": "1. In a real-world data cluster, how does the arrival pattern change over time? Consider plotting the 95%-99% quantile of the number of simultaneous arrivals. Please also consider adding other more background information.\n2. How long does the model take to make a decision at inference time, compared to prior approaches?\n3. It seems that in Table 1 and 2, the arrival rates during training and testing are always the same for each scenario. However, in a real-world data center, the arrival pattern might fluctuate over time, especially in the case of extreme events (e.g., holidays or deadlines). How robust is your approach to such distribution shifts?\n4. In Table 1 and 2, \"Ours-Offline\" already achieves a very good performance. If due to distribution shifts, the offline version gets a much lower performance, can the online algorithm quickly adapt to such changes?\n5. Many real-world scenarios involve some type of resource contention or performance interference. For example, two tasks are both memory intensive, so maybe we should allocate them on different machines. How does GOODRL address this issue?\n\nMinor:\n- Line 45, \"In fact existing\" --> \"In fact, existing\"", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper has many diagrams, which help the readers to understand.\n- GOODRL shows strong performance against other baselines.", "weaknesses": "- My main concern is that the paper seems to be applying some existing algorithms to a scheduling problem. There are some simple modifications at different parts of the overall method, and ended up giving us good performance. However, what are the broader insights of this work?\n- Consider adding more background on the DWS problem and studies on real traces.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X2VqPwVDu3", "reviewer": "Reviewer_8vKM", "summary": "The paper presents Graph assisted Offline-Online Deep Reinforcement Learning (GOODRL) for Dynamic Workflow Scheduling for Cloud Computing. The presence of heterogenous configurations, dynamic arrival of workflows, and constant evolving environment makes this a challenging problem for State of the Art Models.\n\nThe Contributions presented in the paper are:\n\n1) A Task-Specific Graph Representation and Graph Attention Actor Model that dynamically assign focused tasks to heterogenous machines.\n2) Explicit Consideration of the future impact of the crucial state.\n3) A combination of Offline Imitation Learning followed by Online PPO.", "questions": "- How does this model differ from the model presented in Wang et al 2022 [7]?\n\n- How does the heterogeneity of the agent-task is accounted for in the graph representation?\n\n- It is unclear what the novelty of this work is compared to similar works published in Multi-Agent Coordination, and Task Allocation and Scheduling Domains.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 1, "strengths": "- Clear and detailed explanation of the approach being used.\n- Easy to understand figures.\n- Compared against Multiple Benchmarks and show that the model outperforms the baselines in most instances", "weaknesses": "- The topic of Resource Opimization using Graph Neural Networks is an open problem that has applications not limited to Cloud Computing. The problem itself is also explored under Multiple Travelling Salesman Problems [1, 2], Vehicle Routing Problem [3], Job Shop Scheduling [4] and Task Allocation and Scheduling in Multi-Agent Systems [5, 6]. While the application of the problem into Cloud Computing is novel, the use of Reinforcement Learning and Graph Attention Networks to similar optimization problems exists.\n\n- It is unclear how the proposed method differs from Online Predictive Scheduling using Heterogenous Graph Attention presented in Wang et al 2022 [7]:\n\n- The enhancement provided by the Online RL part of the model is unclear. The experimental results show that the Offline Learning allows for the model to be within 2% of the Online Training results. The significance of this improvement is unclear and needs to be discussed clearly.\n \n[1] Yujiao Hu, Yuan Yao, and Wee Sun Lee. 2020. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs. Knowledge-Based Systems 204 (Sept. 2020), 106244. https://doi.org/10.1016/j.knosys.2020. 106244\n\n[2] Yujiao Hu, Zhen Zhang, Yuan Yao, Xingpeng Huyan, Xingshe Zhou, and Wee Sun Lee. 2021. A bidirectional graph neural network for traveling salesman problems on arbitrary symmetric graphs. Engineering Applications of Artificial Intelligence 97 (Jan. 2021), 104061. https://doi.org/10.1016/j.engappai.2020.104061\n\n[3] Steve Paul and Souma Chowdhury. 2022. A scalable graph learning approach to capacitated vehicle routing problem using capsule networks and attention mechanism, Vol. 86236. American Society of Mechanical Engineers, V03BT03A045\n\n[4] Song, Wen, et al. \"Flexible job-shop scheduling via graph neural network and deep reinforcement learning.\" _IEEE Transactions on Industrial Informatics_ 19.2 (2022): 1600-1610.\n\n[5] Z. Wang and M. Gombolay, \"Learning Scheduling Policies for Multi-Robot Coordination With Graph Attention Networks,\" in IEEE Robotics and Automation Letters, vol. 5, no. 3, pp. 4509-4516, July 2020, doi: 10.1109/LRA.2020.3002198.\n\n[6] B. Altundas, Z. Wang, J. Bishop and M. Gombolay, \"Learning Coordination Policies over Heterogeneous Graphs for Human-Robot Teams via Recurrent Neural Schedule Propagation,\" _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_, Kyoto, Japan, 2022, pp. 11679-11686, doi: 10.1109/IROS47612.2022.9981748.\n\n[7] Wang, Z., & Gombolay, M. (2022). Stochastic Resource Optimization over Heterogeneous Graph Neural Networks for Failure-Predictive Maintenance Scheduling. _Proceedings of the International Conference on Automated Planning and Scheduling_, _32_(1), 527-536. https://doi.org/10.1609/icaps.v32i1.19839", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sPtrU9kQZ9", "reviewer": "Reviewer_RdYS", "summary": "The paper introduces an innovative approach, GOODRL, for handling dynamic workflow scheduling in cloud computing environments. This method integrates a task-specific graph representation with Graph Attention Networks (GATs) for actor-critic networks and incorporates offline imitation learning alongside online reinforcement learning to adapt to changing conditions. The proposed system is evaluated in various online and offline scenarios and is shown to outperform existing state-of-the-art methods in terms of mean flowtime and adaptability.", "questions": "- Could the authors elaborate on how their model adapts to significant changes in workflow patterns or cloud configurations without extensive retraining? How does the method maintain robust performance under dynamic conditions that differ from the training data?\n- What are the practical deployment requirements for GOODRL in terms of computational resources, and how do they compare with simpler heuristic-based solutions in large-scale, real-time applications?\n- Can the authors provide more insights into how the method handles noisy or incomplete data, which is a common challenge in real-world cloud scheduling environments?\n- How might the proposed approach be extended or adapted to incorporate multi-objective optimization, such as balancing energy efficiency with flowtime reduction, and what specific challenges would need to be addressed to achieve this?\n- Could the authors comment on potential scalability issues when deploying GOODRL in larger cloud infrastructures or in environments with highly heterogeneous machine configurations, and how these challenges could be mitigated?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper proposes a unique combination of graph representations tailored for actor and critic networks, enhancing action differentiation and value estimation.\n- GOODRL demonstrates improvements in mean flowtime over established baseline algorithms, showcasing robust performance in both offline and online settings.\n- The offline-online learning approach with imitation learning and gradient control addresses challenges in adapting to dynamic environments, adding practical value.\n- The ablation studies and performance comparisons are thorough, providing strong evidence for the contributions and architectural decisions.", "weaknesses": "- The paper's reliance on simulations limits its generalizability to real-world cloud environments. Practical tests in real cloud data centers would bolster the validity of the results.\n- The experiments primarily focus on a specific set of workflow types and machine configurations, potentially limiting the applicability of findings to other types of DWS problems.\n- The computational overhead associated with the proposed GAT-based architectures is not discussed in detail, raising questions about deployment feasibility in large-scale, real-time applications.\n- While the method performs well in flowtime reduction, other practical objectives, such as energy efficiency and cost, are not explored, which would be valuable for broader applicability.\n- The paper lacks discussion on how the model generalizes to varied workloads, impacting its robustness in dynamic cloud environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)