1
Cloud Workflow Scheduling Based on Graph Attention-Driven Hierarchical Reinforcement Learning
arXiv:2609.14952v1 [cs.LG] 14 Sep 2026
Zongjin Li, Shaohan Feng Member, IEEE, Chunxi Yang Member, IEEE and Wenbo Wang Senior Member, IEEE,
Abstract—Dynamic cloud workflow scheduling must balance deadline satisfaction, container utilization, and energy consumption while dealing with stochastic task-execution speeds, placement-dependent communication, and coupled task and container decisions. Workflows are naturally modeled as directed acyclic graphs (DAGs), but conventional vector- or matrixbased states do not fully capture their dependency topology. To better represent task urgency and structural relationships, we assign predicted sub-deadlines to tasks and use a multihead graph attention network (GAT) to extract dependency information from the evolving DAGs. Based on these representations, we develop a Graph Attention-Driven Hierarchical Reinforcement Learning (GA-HRL) framework and model the scheduling process as an event-driven hierarchical semi-Markov decision process (SMDP). Workflow arrivals and task completions trigger scheduling events. At each scheduling event, the Task Scheduling (TS) agent first processes the currently ready tasks by assigning them to admissible existing containers or requesting new ones. The requested containers are then processed by the Container Scheduling (CS) agent for host placement before the environment advances. The two agents are trained alternately using separate Proximal Policy Optimization (PPO). Experiments on the 2018 Alibaba cluster trace show that GA-HRL maintains competitive workflow success rate and, in settings where success is comparable, generally achieves higher container utilization and lower energy consumption. Under the largest speed variation, it trades a small success-rate margin for substantially lower energy. Simulation code is available at: https://github.com/zongjin130/ GA-HRL. Index Terms—Graph attention network, hierarchical reinforcement learning, dynamic workflow scheduling, multi-objective optimization, container placement.
I. I NTRODUCTION
I
N cloud computing environments, users submit their computational demands as workflows to the cloud platform, and the provider must allocate computing resources according to each workflow’s task structure and dependencies [1]. The scheduler therefore has to balance multiple objectives simultaneously [2]. From the user perspective, workflows should finish before their deadlines to maintain quality of service [3]. From the provider perspective, allocated resources should be utilized effectively, because unnecessary provisioning and poor utilization keep additional hosts and containers active and increase energy consumption. Consequently, dynamic workflow scheduling must jointly consider task timeliness, resource Zongjin Li, Chunxi Yang and Wenbo Wang are with the Faculty of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China (e-mails: zongjin [email protected]; [email protected]; wenbo [email protected]). Shaohan Feng is with the School of Information and Electronic Engineering (Sussex Artificial Intelligence Institute), Zhejiang Gongshang University, Hangzhou 310018, China (e-mail: feng [email protected]).
utilization, and energy efficiency rather than optimizing them separately. Cloud workflows are becoming larger and more complex, and cloud platforms usually operate online, so multiple workflows with different structures, arrival times, and deadlines may coexist [2]. Scheduling such workflows is difficult for two related reasons. First, a workflow is successful only after all its constituent tasks are coordinated, so task decisions are coupled. Second, precedence constraints restrict the order of execution, and treating tasks independently discards useful dependency information. Workflows are therefore commonly represented as Directed Acyclic Graphs (DAGs), where nodes denote tasks and directed edges represent both precedence constraints and data transfers [4]. From the resource-management perspective, containers are widely used because they are lightweight, start quickly, and support high resource density [5]. The platform may also need to create additional containers on suitable hosts when current resources are insufficient to meet workflow deadlines [6]. In practice, however, container performance is not fully predictable: the execution speed of a task can vary with host load and placement-dependent interference [2]. Communication is likewise placement-dependent, because intrahost and inter-host transfers use different bandwidths and transfer time cannot be known until containers are placed [3]. These uncertainties interact with workflow dependencies and can cause waiting time, reduce container reuse, and increase energy consumption. Dynamic workflow scheduling therefore requires a model that captures both runtime uncertainty and placement-dependent communication. Cloud workflow scheduling requires trade-offs both among tasks of the same workflow and among workflows competing for shared resources, and the problem is NP-hard [7, 8]. Traditional heuristics depend on problem-specific rules, whereas optimization-based methods often rely on repeated search or expensive solving procedures. As the numbers of tasks and candidate resources grow, such methods become difficult to deploy in an online scheduler. Reinforcement Learning (RL) has therefore attracted attention as a way to learn scheduling policies from interaction with the environment [9]. However, many RL-based schedulers still represent tasks by ordinary vectors or matrices, which retain local attributes but do not explicitly capture the non-Euclidean dependency structure of a DAG [10]. How to preserve and exploit this structure under changing resource conditions remains an open problem. This paper studies dynamic cloud workflow scheduling with stochastic task-execution speeds and placement-dependent communication. Each active workflow is kept as a DAG, and a predicted sub-deadline is assigned to every task to
2
represent its temporal urgency. A multi-head GAT then aggregates dependency information so that tasks with similar local attributes can still be distinguished by their structural context. The resulting representation is used in an eventdriven hierarchical semi-Markov Decision Process (SMDP), where a Task Scheduling (TS) agent first assigns ready tasks to admissible existing containers or requests new ones. All new-container requests generated during the TS phase are then processed by a Container Scheduling (CS) agent for host placement before physical time advances. The two policies are trained alternately using separate PPO actor-critic networks while sharing the same scheduling environment. GA-HRL is designed to meet workflow deadlines while also improving container utilization and reducing total energy consumption. The main contributions are as follows: 1) We develop a dependency-aware task representation for dynamically arriving DAG workflows. Predicted subdeadlines express task urgency, while a multi-head GAT aggregates topological information that conventional vector or matrix states do not retain explicitly. 2) We formulate the coupled task-to-container and container-to-host decisions as an event-driven hierarchical SMDP. At each scheduling event, the TS agent first processes the ready-task assignments, after which the CS agent processes the host-placement decisions generated by new-container requests before physical time advances. 3) We train the two agent-specific policies with PPO over their event-driven decision sequences. Trace-driven experiments show that GA-HRL maintains competitive workflow success and, in settings where success is comparable, achieves higher container utilization and lower energy consumption. Under the largest speed variation, it trades a small success-rate margin for substantially lower energy. The remainder of this paper is organized as follows. Section II reviews related work. Section III introduces the system model and problem statement. Section IV presents the proposed GA-HRL scheduling algorithm. Section V reports the experimental results, and Section VI concludes the paper.
In containerized cloud environments, the scheduler must make two coupled decisions: task scheduling, which determines the execution order and start time of tasks, and container placement, which determines the host on which each container is deployed [6]. These two decisions jointly affect execution efficiency and resource consumption. In practice, container execution speed fluctuates with host load, and communication delay depends on whether containers are co-located. These uncertainties interact with workflow dependencies, which can waste resources and increase energy consumption.
B. Mathematical Optimization based Methods Optimization-based methods formulate cloud resource allocation or workflow scheduling as mathematical programs. Chen et al. [3] reconstructed the request sequence by priority and minimized matching distance and the number of active physical machines. Jiao et al. [12] formulated joint resource placement and allocation as an integer linear program and designed a dynamic-programming-based algorithm. Hahnel et al. [13] extended the cutting-stock model to consolidate heterogeneous service requests, reducing overload probability and energy consumption. Liu et al. [14] proposed an approximate function placement algorithm for edge-cloud job completion time minimization, and Das et al. [15] studied dynamic function placement under cost and deadline constraints. Deng et al. [16] later embedded dependent functions into distributed serverless edge computing to obtain the optimal function placement and start time. These methods provide clear formulations and, in some cases, approximation guarantees. However, they generally assume deterministic inputs or require repeated optimization as the system state changes. This limits algorithm scalability because the computational burden grows quickly with the decision space. In our setting, workflows arrive online, execution speeds are stochastic, and each task assignment affects subsequent container placement, making direct online application of such methods difficult.
C. Heuristic Optimization based Methods II. R ELATED W ORKS This section reviews representative studies on cloud workflow scheduling from four perspectives: containerized workflow scheduling, mathematical optimization methods, heuristic optimization methods, and machine-learning-based methods. The discussion focuses on how these approaches represent workflow dependencies, handle resource allocation, and respond to dynamic or uncertain execution conditions. A. Containerized Workflow Scheduling Workflows are commonly represented by Petri nets [11], UML diagrams, or DAGs [4]. DAGs are widely used because they naturally express task parallelism, precedence constraints, and data dependencies. Each workflow DAG has its own arrival time, structure, and deadline [2].
Heuristic methods can be broadly divided into rule-based scheduling and iterative swarm-intelligence methods [2]. Rodriguez et al. [17] used particle swarm optimization to maximize the scheduling success rate and minimize cost in static cloud workflows. Arabnejad et al. [18] proposed deadlinebased heuristics for dynamic cloud workflows. Chen et al. [2] developed an uncertainty-aware online scheduler for realtime workflows with multiple objectives, while Fan et al. [6] proposed an energy-efficient heuristic for deadline-constrained workflows with container placement. These heuristics are generally computationally efficient and often work well under fixed assumptions. However, their performance depends heavily on hand-crafted rules or tuned parameters. When the arrival process, execution-speed distribution, or resource configuration changes, the same rules may not adapt as effectively as a learned policy.
3
D. Machine Learning based Methods Machine-learning-based schedulers can be divided into methods that use learning as a predictor/evaluator and methods that use RL to generate policies [19, 20]. Yang et al. [19] combined machine-learning prediction with relaxed linear programming to schedule tasks with unknown execution times. Yu et al. [8] applied RL with custom reward functions to optimize dynamic workflow scheduling. Ding et al. [20] proposed a Transformer-enhanced Deep Q-Network for largescale workflow scheduling, but the approach does not fully exploit inter-task dependency structure. Xie et al. [21] used graph neural networks to extract features of workflows and resources, improving scheduling success and energy efficiency. Despite these advances, many existing schedulers use dependency information mainly to determine eligible tasks, rather than embedding the DAG topology directly into the policy state. As a result, the structural information carried by the DAG is only partially exploited when resources are selected. Moreover, several methods assume that workflows are available at the beginning of scheduling or use pre-execution attributes, which does not fully capture the continual changes caused by online arrivals, fluctuating execution speeds, and dynamic container availability. GA-HRL addresses these gaps by combining DAGpreserving GAT representations, predicted sub-deadlines, and a hierarchical TS/CS policy in an event-driven scheduling framework. It differs from prior cloud workflow schedulers at three connected levels: • it explicitly models random workflow arrivals, taskspecific execution-speed realizations, and placementdependent communication; • at the TS level, the task state combines a predicted urgency indicator with a GAT representation of the DAG topology; and • for policy derivation, the state drives an event-triggered hierarchical policy that coordinates task assignment and container placement at separate decision epochs. III. M ODEL AND P ROBLEM S TATEMENT This section focuses on three key aspects: cloud resource modeling, workflow modeling, and the problem statement. A. Cloud Resource Model We consider a cloud service center in which physical hosts are activated on demand. Let H = {H1 , H2 , · · · , HN } denote the set of host instances activated during a scheduling episode, where N is the total number of activated host instances. Each host Hn is characterized by a resource tuple Hn = (Cn , Mn , Q̄n , P̄n ), where Cn represents the number of CPU cores, Mn is the memory size, Q̄n is the mean computational capacity measured in Million Instructions Per Second (MIPS), and P̄n is the mean power under full utilization. Let C all denote the set of all containers created during the scheduling horizon, and let Cn (t) denote the set of containers that are currently alive on host Hn at time t. We further define Cnall = {cm ∈ C all : ηm = n} as the set of all containers
deployed on Hn during the scheduling horizon. Then, at any time, a container cm ∈ Cn (t) is characterized by the resources allocated to it: cm = (Cm , Mm ), where Cm and Mm are respectively the number of CPU cores and memory required for container cm . The mean computational capacity and mean power of the container are determined by the number of CPU cores. The mean computational capacity of container cm is expressed as Q̄m =
Q̄ηm Cm , C ηm
(1)
where ηm = n means that container cm is deployed on host Hn . The nominal capacity Q̄m is known to the scheduler, whereas the capacity realized during execution is task specific. (m) Let Qk,j denote the computational capacity experienced by task tk,j when it executes on container cm . At the start of every task execution, a new realization is sampled independently as (m) (m) Qk,j ∼ N Q̄m , (v Q̄m )2 , 0 < Qk,j < 2Q̄m , (2) where v is the variance coefficient. Thus, two tasks executed successively on the same container may experience different realized capacities, while scheduling decisions made before execution use the nominal value Q̄m . We assume that the data transmission speed between containers is different [6]: the communication speed within the same host shares the internal network bandwidth of the host, usually with lower latency and not limited by physical networks. The communication speed in this scenario is denoted as B in . B in represents the effective intra-host bandwidth under the adopted sharing assumption. When the container is deployed on different hosts, all data transmission must pass through a shared physical network link, and its bus bandwidth, denoted as B cr , is strictly limited by the physical bandwidth of the cross-host link. B. Workflow Model We consider a set of W = {W1 , . . . , WK } of K workflows. Each workflow is characterized by the tuple Wk = (Ak , Dk , Gk ), where Ak is its arrival time, Dk is its deadline, and Gk = (Tk , Ek ) is the DAG representing its task structure. In particular, Tk = {tk,1 , . . . , tk,Nk } is the task set of Wk , with Nk = |Tk |, and Ek ⊆ {ek,ij | i, j ∈ {1, . . . , Nk }, i ̸= j} is the edge set representing the data dependency between tasks. An edge ek,ij indicates that tk,i is an immediate predecessor of tk,j , equivalently, tk,j is an immediate successor of tk,i . We denote the immediate predecessor and successor sets of tk,j by pred(tk,j ) and succ(tk,j ), respectively. A task with no immediate predecessor is called an entry task, and a task with no immediate successor is called an exit task. Each task tk,j has a required computation size pk,j , measured in Million Instructions, and each edge ek,ij carries a data volume dk,ij that must be transmitted from tk,i to tk,j . We assume that the workflow structure, task computation sizes, and inter-task data volumes are known when Wk arrives (see also [1]). An illustrative example is shown in Fig 1, where tasks t1,1 and t1,10 are respectively the entry task and the exit task. Tasks t1,4 , t1,5 , and t1,6 are the immediate predecessors of task t1,7 . Tasks t1,8 and t1,9 are the immediate successors of task t1,7 .
4
𝑡1,3
𝑒1,13
𝑡1,1 𝑒1,12
𝑒1,25 𝑒1,16
𝑒1,47 𝑡1,5
𝑡1,9
𝑒1,910
𝑒1,79
𝑒1,57
𝑒1,67
𝑡1,7
Pred（ 𝑡1,7 ）
𝑡1,7
𝑡1,6
Entry
𝑒1,310
𝑡1,4
𝑒1,24
𝑡1,2
𝑡1,8
𝑒1,78
𝑒1,810
Succ（ 𝑡1,7 ）
𝑡1,10
Exit
Fig. 1: Workflow diagram. TABLE I: Main notation used in the scheduling model. Symbol
Meaning
H, Hn Cn , Mn Q̄n , P̄n
set of host instances and host instance n CPU-core capacity and memory capacity of host Hn mean computational capacity and mean full-utilization power of host Hn set of workflows and workflow k arrival time and deadline of workflow Wk DAG of workflow Wk , consisting of task and edge sets number of tasks in workflow Wk task j of workflow Wk and dependency edge from tk,i to tk,j immediate predecessor and successor sets of task tk,j computational workload of task tk,j and data volume transmitted from tk,i to tk,j set of all containers created during the scheduling horizon and globally indexed container m set of containers currently alive on host Hn at time t set of all containers deployed on host Hn during the scheduling horizon CPU-core and memory requirements of container cm nominal capacity of container cm and capacity realized by task tk,j on cm nominal container power and task-specific power during execution index of the container assigned to task tk,j all host index of container cm ; ηm = n iff cm ∈ Cn intra-host and cross-host data transmission bandwidths number of containers on host Hn simultaneously receiving data at time t startup time required to deploy a new container execution time of task tk,j data transmission time from task tk,i to task tk,j container-ready, task-start, task-finish, and workflowfinish times scheduled finish time of the task currently executing on container cm total powered-on duration of host Hn active execution time and total lifetime of container cm host static-power ratio and container idle-power ratio static energy consumption of host Hn active and idle energy consumption of container cm total energy consumption of host Hn
W, Wk Ak , Dk Gk = (Tk , Ek ) Nk tk,j , ek,ij pred(tk,j ), succ(tk,j ) pk,j , dk,ij C all , cm Cn (t) all Cn Cm , Mm (m) Q̄m , Qk,j (m)
P̄m , Pk,j
µk,j ηm B in , B cr nn act (t) STc ex τk,j tx τk,ij Rm , Sk,j , Fk,j , Fk cur Fm
Tnon act life Tm , Tm rh , rc sta En act idle Em , Em En
We introduce two mappings for notational convenience: µk,j = m (task tk,j assigned to container cm ) and ηm = n (container cm deployed on host Hn ). These are merely index simplifications and leave the scheduling model unchanged. The main notations are summarized in Table I. C. Execution Model We first describe the event-driven execution lifecycle and defines the timing quantities used in the model. When work-
flow Wk arrives at time Ak , the scheduler first identifies the tasks that are ready according to the DAG. The TS agent then sequentially assigns these ready tasks to admissible existing containers or requests new containers. All new-container requests generated during the current TS phase are added to a deployment queue. After the TS phase is completed, the CS agent places the corresponding undeployed containers on hosts, and each newly created container becomes operational only after the startup delay STc . Because task durations are stochastic, a long predicted queue can accumulate considerable timing error. We therefore restrict each container to at most two unfinished tasks: one task in execution and at most one waiting task. A container whose execution and waiting positions are both occupied is removed from the feasible TS action set. When the executing task finishes, the waiting task may start only after all required predecessor data have arrived. Otherwise, the container remains idle until the start-time condition in (6) is satisfied. Workflow Wk is successful only if all of its tasks finish no later than Dk . The timing model distinguishes between quantities available when a scheduling action is chosen and quantities realized later during actual execution. Candidate actions are evaluated from nominal information, whereas the simulator advances according to sampled execution. Candidate actions are evaluated from nominal information, whereas the actual system evolution follows sampled execution capacities. The startup time STc , ex tx execution time τk,j , transmission time τk,ij , container-ready time Rµk,j , task start time Sk,j , task finish time Fk,j , and workflow finish time Fk together define the event timeline. 1) Execution time of tasks: When task tk,j starts on its (µ ) assigned container cµk,j , the task-specific capacity Qk,jk,j is sampled according to (2). The realized execution time is then pk,j ex (3) τk,j = (µ ) , Qk,jk,j whereas the scheduler evaluates a candidate container cm ex using the predicted execution time τbk,j,m = pk,j /Q̄m . The prediction is available at the decision epoch; the realized capacity is sampled only when execution begins. 2) Data transmission time of tasks: After a predecessor task tk,i finishes, its output data of volume dk,ij must be transmitted to the container hosting its successor task tk,j before tk,j can start. The transmission time depends on the relative placement of the two tasks’ containers, and three cases are considered: • Same container: If tk,i and tk,j are assigned to the same container, the output data already resides in local memory, so no data transfer is required and the transmission time is zero. • Different containers on the same host: If tk,i and tk,j are assigned to different containers co-located on the same host, the data is transferred through the intra-host network (e.g., shared memory bus or virtual bridge) at bandwidth B in . The transmission time is dk,ij /B in . • Containers on different hosts: If the containers hosting tk,i and tk,j are deployed on different physical hosts, the data must traverse the inter-host network link with
5
total bandwidth B cr . Because this link is shared among all containers concurrently receiving data on the destination host Hηµk,j , each container receives an equal share ηµ
of the bandwidth. Let nactk,j (t) denote the number of such receiving containers at transmission start time t. ηµ The effective bandwidth per container is B cr /nactk,j (t), ηµk,j yielding a transmission time of dk,ij nact (t)/B cr . Formally, the transmission time from tk,i to tk,j is 0, dk,ij tx τk,ij = B in , ηµk,j dk,ij nact (t) , B cr
µk,i = µk,j , µk,i ̸= µk,j , ηµk,i = ηµk,j , (4)
D. Energy Model This subsection formulates the energy consumption model for the cloud service center, where the total energy of a host is decomposed into host static energy, container active energy, and container idle energy. To that end, we first define the power parameters of hosts and containers, then compute each energy component accordingly. 1) Power parameters: The mean power of host Hn under full utilization is denoted by P̄n . Following the widely adopted linear server power model [22], a host that is powered on but not fully loaded still consumes a static power proportional to P̄n : Pnsta = rh P̄n ,
ηµk,i ̸= ηµk,j .
3) Ready time of containers: Only a container with no waiting task can be selected for another assignment. For such a candidate, the ready time is the earliest instant at which the newly assigned task can occupy the execution position: T0 + STc , if cµk,j is newly deployed, Rµk,j = Fµcur , if it is executing one task, k,j tnow , if it is idle.
tk,i ∈pred(tk,j )
tk,j = tk,entry , (6) otherwise.
(7)
6) Finish time of workflows: A workflow is completed when all of its tasks have finished. Therefore, the completion time of workflow Wk is Fk = max Fk,j . tk,j ∈Tk
P̄ηm (1 − rh )Cm . C ηm
(10)
(5)
For an entry task, the workflow arrival time Ak acts as its dataready time, which avoids taking a maximum over an empty predecessor set. 5) Finish time of tasks: The finish time of task tk,j on container cµk,j is obtained by adding its realized execution time to its start time: ex Fk,j = Sk,j + τk,j .
where rh ∈ (0, 1) is the host static-power ratio, representing the fraction of peak power consumed when the host is idle. Similarly, the mean power of container cm is proportional to its share of CPU cores on the hosting host: P̄m =
Here, T0 is the time at which the deployment of cµk,j is requested, Fµcur is the already scheduled finish time of the task k,j currently executing on cµk,j , and tnow is the current decision time. The newly assigned task may still start later than Rµk,j if its predecessor data have not yet arrived. 4) Start time of tasks: When task tk,j is assigned to container cµk,j , its start time is jointly determined by the container ready time Rµk,j and the data-ready times of all its predecessors: max{Ak , Rµk,j }, Sk,j = max{Rµk,j , tx max (Fk,i + τk,ij )},
(9)
(8)
Workflow Wk is considered successfully completed if and only if Fk ≤ Dk .
Here, (1 − rh ) represents the dynamic portion of the host power that is allocated to containers according to their CPUcore shares. Under the linear power-performance model based on dynamic voltage and frequency scaling [1, 22], the dynamic power consumed while task tk,j executes on container cm scales with the task-specific capacity realization: (m)
(m)
Pk,j = P̄m
Qk,j
Q̄m
.
(11)
Consequently, the power consumption can differ between successive tasks on the same container because a new capacity realization is drawn for each execution. 2) Host static energy: A host is considered active while at least one container is deployed on it. During its active period, the host incurs static energy consumption proportional to its powered-on duration: Ensta = Pnsta Tnon = rh P̄n Tnon ,
(12)
where Tnon denotes the continuous powered-on duration of host Hn , from its activation until it is shut down after its last container is terminated. 3) Container active energy: The active energy of container cm is the sum of the energy consumed by all tasks executed on it: act Em =
X (k,j):µk,j =m
(m)
ex Pk,j τk,j =
P̄m Q̄m
X
pk,j , (13)
(k,j):µk,j =m
where the second equality follows from (3) and (11). Under the adopted linear model, the sampled speed changes power and duration in opposite directions, so their effects cancel for a fixed workload.
6
4) Container idle energy: Between consecutive task executions, a container remains alive but idle and still consumes a reduced level of power. The idle energy of container cm is idle life act Em = rc P̄m Tm − Tm , (14) life where rc ∈ (0, 1) is the container idle-power ratio, Tm is the total lifetime of container cm from creation to termination, and act Tm is its cumulative active execution time. 5) Total energy consumption: The total energy consumption of host Hn aggregates the host static energy and the energy consumed by all containers deployed on it: X act idle En = Ensta + Em + Em . (15) all cm ∈Cn
(m)
Although Qk,j does not alter the active energy of a fixed workload under the linear model, it changes the execution (µ ) ex timeline through τk,j = pk,j /Qk,jk,j . The resulting shifts in task completion, data readiness, and container reuse affect container idle durations and host powered-on durations. Therefore, energy differences mainly arise from these timeline effects, the selected container and host types, and the degree of resource reuse, rather than from a direct speed multiplier on active energy. E. Problem Formulation Let π denote a scheduling policy that determines both taskto-container assignments and container-to-host placements. Given a workflow set W = {W1 , . . . , WK } arriving over a finite scheduling horizon and a cloud infrastructure H = {H1 , . . . , HN }, we aim to find a policy π that jointly optimizes three objectives subject to resource-capacity, task-dependency, and assignment constraints. 1) Optimization objectives: The goal is to maximize the workflow scheduling success rate and the container utilization while minimizing the total energy consumption. The three objectives are defined as follows: Nsucc Jsuc (π) = K X T act m J (π) = 1 uti all life |C | T (16) cm ∈C all m |H| X J (π) = En ene n=1
where Nsucc = |{k : Fk ≤ Dk }| is the number of workflows completed before their deadlines. The policy aims to maximize Jsuc (π) and Juti (π) while minimizing Jene (π). 2) Problem constraints: The scheduling solution must satisfy the following constraints. C1 (CPU capacity): for each host Hn and each time t, X Cm ≤ Cn (17) cm ∈Cn (t)
ensures that the aggregate CPU-core demand of all currently alive containers does not exceed the host capacity.
C2 (memory capacity): for each host Hn and each time instance t, X Mm ≤ Mn (18) cm ∈Cn (t)
ensures that the aggregate memory demand of all currently alive containers does not exceed the host capacity. C3 (dependency relationship): tx Sk,j ≥ Fk,i + τk,ij , ∀ tk,i ∈ pred(tk,j ),
(19)
requires that the output of every immediate predecessor arrives before task tk,j starts. For an entry task, the predecessor set is empty, so C3 is vacuously satisfied and its start time follows the first branch of (6). C4 (unique assignment): |C all |
X
xk,j,m ≤ 1,
(20)
m=1
where xk,j,m ∈ {0, 1} is a binary assignment variable such that xk,j,m = 1 if task tk,j is assigned to container cm , and P xk,j,m = 0 otherwise. The inequality allows m xk,j,m = 0 when a task is discarded after its workflow deadline, while a scheduled task is assigned to at most one container. The global objectives in (16) can only be evaluated after all workflows have been processed. In practice, however, the policy π makes decisions at the granularity of individual tasks and containers: for each ready task, a container is selected; for each new container, a host is selected. The global objectives therefore emerge from the accumulation of these per-step decisions over all scheduling intervals. Since the scheduling decisions at each interval depend only on the currently observed system state and cannot anticipate future workflow arrivals or container-speed realizations, this problem is a dynamic stochastic optimization that is NPhard even in its static deterministic variant [8]. Moreover, because scheduling decisions are triggered by workflow-arrival and task-completion events rather than by fixed-duration time slots, the process is modeled as an SMDP. The TS and CS agents have separate decision sequences: TS decisions are generated for the currently ready tasks, whereas CS decisions are generated for undeployed containers produced by newcontainer requests. After the current TS phase is completed, the corresponding CS placement decisions are processed before physical time advances. Consequently, successive decisions of each agent may be separated by different amounts of physical time. IV. S CHEDULING A LGORITHMS The GA-HRL scheduler follows a four-stage procedure that mirrors the scheduling model introduced above. First, the currently active workflows are kept in DAG form and preprocessed to obtain task-level timing indicators from their predicted execution time. Second, a multi-head GAT updates each task representation using information from its dependency neighborhood. Third, the TS agent combines the resulting task representation with the current container state and decides whether a ready task should reuse an admissible
7
existing container or request a new container. Fourth, if a new container is requested, the CS agent selects a feasible host for it. This ordering connects the graph representation directly to the two coupled resource-allocation decisions, rather than treating GAT, hierarchical control, and policy generation as independent components. The two decision layers operate in the same event-driven environment and can be described as two interacting SMDPs. Workflow arrivals and task completions trigger scheduling events. At each event, the TS agent first processes all currently ready tasks sequentially. New-container requests generated during the TS phase are added to a deployment queue. After the TS phase is completed, the CS agent processes all undeployed containers in the queue and places them on hosts. Physical epochs advances only after both the TS and CS decision phases associated with the current scheduling event have been completed. Because TS and CS are invoked at different frequencies, each agent has its own sequence of decision epochs and its own holding times between successive invocations. Specifically, the TS Agent operates at its own decision epochs: it observes the dependency-aware representation of the selected ready task and the admissible containers, then either reuses an existing container with available capacity or requests a new one. Its reward combines predicted deadline margin, uncertainty-sensitive energy proxies, and container availability. The CS Agent, in contrast, is activated only after the TS phase is completed, and each undeployed container from a new-container request triggers a CS decision. The CS agent observes container requirements, feasible host capacities, and predecessor locality, then places the container on an existing or newly activated host. If the TS phase produces no new-container request, no CS decision occurs for that event. For each agent g ∈ {TS, CS}, the induced process is represented as Mg = (S g , Ag , P g , Rg , ∆g ). Here, S g , Ag , P g , and Rg denote the state space, action space, transition map, and reward function of agent g, respectively. Let Tqg denote the starting time of the q-th decision epoch of agent g − Tqg denote the corresponding holding g, and let ∆gq = Tq+1 time between two consecutive decisions of the same agent. The holding time characterizes the irregular physical-time spacing between successive decisions and affects the subsequent state through task execution, data transmission, workflow arrivals, task completions, and resource-state evolution. For policy optimization, the successive invocations of each agent form its decision-epoch trajectory. Fig. 2 summarizes this complete path from workflow representation to hierarchical decision making and training. A. Workflow Embedding for State Construction The state representation used by the TS policy is constructed in two complementary steps. The first step computes a reference timing profile for each workflow before task assignment, providing an estimate of task urgency. The second step applies a GAT to the active workflow DAGs, producing task embeddings that combine local task attributes with dependency information. The reference timing profile is
not intended to guarantee feasibility under every stochastic execution realization, and the GAT itself does not make resource decisions. Instead, the two parts jointly define the task-level state consumed by the TS policy. 1) Sub-deadline calculation: Following the timing procedure adopted in the Stochastic Hybrid Workflows Scheduling (SHWS) system [1], we construct a reference timing profile using execution time that is available before task assignment. Let Q̄ref denote the nominal capacity of a high-capacity reference container. The reference execution time of task tk,j is defined as pk,j ex,ref . (21) τbk,j = Q̄ref Based on this reference profile, the forward pass computes the Earliest Start Time (EST) of each task: ESTk,j = Ak , if tk,j = tk,entry , ex,ref max {ESTk,i + τbk,i + dk,ij /B cr }, otherwise. tk,i ∈pred(tk,j )
(22) The Earliest Completion Time (ECT) is then ex,ref ECTk,j = ESTk,j + τbk,j .
(23)
Similarly, the backward pass computes the Latest Completion Time (LCT) of each task: LCTk,j = Dk , if tk,j = tk,exit , ex,ref min {LCTk,r − τbk,r − dk,jr /B cr }, otherwise. tk,r ∈succ(tk,j )
(24) Using the partial critical path-based deadlinedistribution [23] form adopted in SHWS, and taking the workflow entry and exit tasks as global anchors, the sub-deadline of task tk,j is ECTk,j − ESTk,entry ECTk,exit − ESTk,entry × (LCTk,exit − ESTk,entry ) .
sub Dk,j =ESTk,entry +
(25)
These timing quantities are heuristic urgency indicators used in task features and reward shaping, rather than hard guarantees under every stochastic capacity realization. The actual success of a workflow is determined only by the realized completion condition Fk ≤ Dk . 2) Graph embedding with GAT: The sub-deadline calculation provides each task with an urgency indicator, but it does not yet encode the dependency structure of the workflow. To capture this structural information, we apply a multi-head GAT to the active workflow DAGs following the attention mechanism in [24]. Because multiple workflows may coexist at a decision epoch, we merge all active workflows into a single DAG. Let It denote the current event-driven decision epoch. At epoch It , a pseudo-entry task tpsd-enter is prepended to all entry tasks, and a pseudo-exit task tpsd-exit is appended after all exit tasks. Both pseudo tasks have zero execution and transfer cost, and
8
It k , jr
e
(
CS agent
TS agent
Graph attention neural network ( , z ) = LeakyReLU a ( , z ) W ( , z ) h ( − 1)
W ( , z )hkIt,r ( − 1)
)
It k, j
Z 1 hkIt, j ( ) = kIt, jr ( , z )W ( , z ) hkIt,r ( − 1) Z z =1 t It + k ,r k,j
Tasks schedule cm ……
Containers generation
……
c2
Hosts generation Containers placement
c1
Time Action:𝑎𝑞𝑇𝑆
State𝑆𝑞𝑇𝑆
Action:𝑎𝑞𝑐𝑠 Environment
Workflows that are not fully scheduled
State:𝑆𝑞𝑐𝑠
Sub-deadline Calculate and Workflow Aggregation
Dksub , j = ESTk , j +
Newly arrived workflows
ECTk , j − ESTk ,entry
Unscheduled workflows
Ectk ,exit − Estk ,entry
( LCTk ,exit − ESTk ,entry )
Resource pool
……
Fig. 2: Schematic diagram of the GA-HRL scheduling algorithm.
their initial feature vectors are set to zero because they do not correspond to real computational tasks. These auxiliary nodes are used only to connect multiple active workflows into one graph and are never scheduled as real tasks. Through the above processing, we can use GAT on multiple workflows, and the detailed information is shown in Fig. 2. For each original task tk,j in the merged graph, we denote t its node by tIk,j . To characterize the communication demand from its immediate predecessors, we define the maximum predecessor data volume as max dk,ij , pred(tk,j ) ̸= ∅, tk,i ∈pred(tk,j ) dpred,max = (26) k,j 0, otherwise. t The initial feature vector of task tIk,j is then
h i sub t t hIk,j (0) = Dk,j , ESTk,j , dpred,max , pk,j , succ(tIk,j ) , k,j (27) sub where Dk,j is the sub-deadline obtained by assuming that t tIk,j is scheduled to a newly created container with the best t computational capacity, and | succ(tIk,j )| is the number of It immediate successors of tk,j . The GAT encoder consists of several stacked graph attention layers. Let N It = |T It | denote the number of nodes in the merged DAG at epoch It . The first-layer input feature is h i⊤ H gat (0) = hI1t (0), hI2t (0), . . . , hINt It (0) , (28) where d0 is the initial feature dimension. At layer ℓ, the GAT layer updates each node representation by attending over its neighbors, producing the refined feature matrix h i⊤ It H gat (ℓ) = hI1t (ℓ), . . . , hINt It (ℓ) ∈ RN ×dh . (29) where dh denotes the embedding dimension at the output of layer ℓ. To retain the node’s own information during aggregation and to avoid an empty neighborhood for exit nodes, we define the augmented successor neighborhood n o + t t Nk,j = succ(tIk,j ) ∪ tIk,j . (30)
t For head z of layer ℓ, the attention coefficient between tIk,j It + and a node tk,r ∈ Nk,j is t exp eIk,jr (ℓ, z) It . (31) αk,jr (ℓ, z) = X It exp e (ℓ, z) ′ It + k,jr
tk,r′ ∈Nk,j
The scalar attention score is computed as t t eIk,jr (ℓ, z) = LeakyReLU a⊤ (ℓ, z) W (ℓ, z)hIk,j (ℓ − 1) t ∥ W (ℓ, z)hIk,r (ℓ − 1) , (32) where W (ℓ, z) is the learnable feature-transformation matrix and a(ℓ, z) is the learnable attention vector of head z in layer ℓ. The node representation is then updated by multi-head + aggregation over Nk,j : ! Z 1 X X It It It hk,j (ℓ) = σ αk,jr (ℓ, z)W (ℓ, z)hk,r (ℓ − 1) , Z z=1 I + t ∈N tk,r k,j
(33) where Z is the number of attention heads and σ(·) is the activation function. We denote the resulting stacked GAT encoder by fψGAT , where ψ collects all learnable parameters {W (ℓ, z), a(ℓ, z)}ℓ,z . B. Task Scheduling (TS) Agent The TS agent determines the container assignment for each ready task according to both the task characteristics and the current container state. This subsection defines its state representation, action space, and reward function. 1) State representation: At a TS decision epoch, the TS agent sequentially processes all currently ready tasks before physical time advances. For task tk,j scheduled at step q, the state sTS q contains the following information: • the embedding vector of the selected task tk,j ;
9
for each existing candidate container cm , its hosting host ηm , CPU-core allocation Cm , memory allocation Mm , mean computational capacity Q̄m , execution-speed variation coefficient v, current ready time or workload, and the estimated predecessor-to-container data-transfer delays under the current placement; • for each candidate new-container type, its CPU-core allocation, memory allocation, nominal computational capacity, and execution-speed variation coefficient v. The hostdependent transmission information of a new container is determined only after the CS agent selects its host. 2) Action space: At TS decision step q, the agent chooses either to assign the selected task to an admissible existing container or to request a new container of a specified type. Let Cqfeas denote the set of existing containers that are feasible under the current scheduling rules, Nctype the number of available container types, and ιi the action of creating a new TS container of type i. The TS action space (aTS q ∈ Aq ) is feas ATS ∪ ιi | i = 1, . . . , Nctype . (34) q = Cq •
An existing container belongs to Cqfeas only if it has no waiting task; hence it contains either one executing task or is idle. A container that already has one executing task and one waiting task is masked out before policy sampling. If aTS q = cm , the selected task occupies the sole waiting position when cm is busy, or the execution position when cm is idle. If aTS q = ιi , a new container of type i is requested and added to the deployment queue. After the current TS phase is completed, the corresponding undeployed container is subsequently placed by the CS agent. 3) Reward function: For task tk,j and candidate container cm , the TS reward evaluates the expected scheduling quality of each feasible action: sub − ESTk,j (1 + v) Dk,j rqTS = w1TS ex τbk,j,m idle act + Ēm Ēm ESTk,j − Rm TS + w2 1− + w3TS , Tnorm Ēact,sub + Ēidle,sub (35) ex where τbk,j,m = pk,j /Q̄m is the predicted execution time. (m) The realized time pk,j /Qk,j is sampled only when the task actually starts and is not used to rank actions. The containeravailability term is positive when cm is expected to be ready before ESTk,j and becomes negative when the task would wait beyond that reference time. For an existing container, Q̄m and P̄m are evaluated using its actual hosting host. For a newly requested container whose placement has not yet been determined, the TS agent evaluates the reward by assuming that the container is deployed on the feasible host that yields the minimum estimated energy consumption. This assumption is used only to evaluate the new-container action; the actual host is subsequently selected by the CS agent. The factor (1 + v) is introduced as an uncertainty-sensitive term for reward shaping. It should not be interpreted as a probabilistic upper bound or as a physical correction applied to
the execution-time or energy model. Its purpose is to give more weight to preserving sub-deadline margin when the executionact idle speed variation becomes larger. Similarly, Ēm and Ēm are energy proxies used to rank candidate actions rather than realized energy values. We define act Ēm =
P̄m pk,j (1 + v) , Q̄m
(36)
solely to introduce an uncertainty-sensitive penalty into the reward. This proxy does not contradict the system energy model, in which the realized active energy of a fixed workload is independent of the sampled speed under the linear powerperformance assumption. Using the maximum predecessor data volume dpred,max k,j idle cr defined in (26), we set Ēm = P̄m rc dpred,max /B . The k,j corresponding values for the fastest reference container are Ēact,sub and Ēidle,sub . The coefficients w1TS , w2TS , and w3TS control the three terms, and Tnorm is a constant used to normalize the container-availability term.
C. Container Scheduling (CS) Agent When the TS agent requests a new container, the request is added to the deployment queue. After the current TS phase is completed, the CS agent selects an appropriate host for each undeployed container according to the container requirements and the current host states. If no existing host satisfies the deployment requirements, the CS agent activates a new host. This subsection defines the CS state representation, action space, and reward function. 1) State representation: After the TS agent completes the current ready-task assignment phase, each undeployed container waiting for host placement triggers one CS decision. Thus, a TS phase may be followed by zero, one, or multiple CS decisions, depending on the number of new-container requests generated during task scheduling. The CS agent therefore maintains its own event-driven decision sequence. For container cm scheduled at step q, the state sCS q includes the following information: the resource requirements of the selected container, including its CPU-core requirement, memory requirement, nominal computational capacity, and the data-transfer speeds achievable on different hosts; • the current workload of each host, including the number of occupied CPU cores, occupied memory, available CPU percentage, available memory percentage, CPU utilization, and mean energy consumption; • the host and container IDs of the critical predecessor task. For each predecessor tk,i ∈ pred(tk,j ), its data-ready time for the current task is estimated from its start time, the execution time pk,i /Q̄µk,i on its assigned container, and the corresponding data-transfer time to tk,j . The predecessor with the largest estimated data-ready time is regarded as the critical predecessor, because the current task cannot start until the outputs of all its predecessors have arrived. •
10
2) Action space: Let Cnused (q) and Mnused (q) denote the number of occupied CPU cores and the occupied memory on host Hn at CS decision step q. The feasible existing-host set for container cm is Hqfeas = ‘ Hn ∈ H : Cn − Cnused (q) ≥ Cm , Mn − Mnused (q) ≥ Mm . (37) Let Nhtype denote the number of available host types, and let ξi denote the action of activating a new host of type i. The CS action space is feas CS ACS ∪ ξi | i = 1, . . . , Nhtype , aCS q = Hq q ∈ Aq . (38) Before policy sampling, an action mask removes all existing hosts that violate either the CPU-core or memory requirement of the selected container. Therefore, infeasible host-placement actions cannot be selected by the CS policy. 3) Reward function: Among feasible host-placement actions, the CS agent aims to improve data locality and resource crit consolidation. Let Hk,j denote the host on which the critical predecessor of task tk,j is deployed, and define the locality indicator ( crit , 1, if container cm is deployed on Hk,j loc (39) xq = 0, otherwise. For an entry task with no predecessor, no critical predecessor exists, and xloc q is set to zero. The CS reward is then CS rqmathrmCS = w1CS xloc q + w2
(q) + Cm Cηused m , Cηm
(40)
where w1CS , and w2CS are the reward coefficients of the CS agent. Cηm and Cηused (q) are the total and used CPU cores m of the host selected by the action, respectively, and Cm is the CPU-core requirement of container cm . The first term rewards data locality with the critical predecessor, while the second term promotes resource consolidation among feasible hosts. The complete online scheduling procedure of GA-HRL is summarized in Algorithm 1. The algorithm combines the workflow representation, TS decisions, CS decisions, and the subsequent timing and energy updates into one event-driven procedure. D. Policy Derivation with PPO Both the TS and CS agents are trained with PPO [25]. Although the underlying scheduling environment is eventdriven and successive decision epochs may be separated by nonuniform physical holding times, each invocation of an agent is treated as one step in that agent’s decision-epoch trajectory. Accordingly, we optimize the decision-indexed discounted return: Qg −1 X J g (πg ) = Eπg γ q rqg , (41) q=0
where Qg is the number of decisions made by agent g in an episode, and γ ∈ (0, 1) discounts successive decisions rather
Algorithm 1 GA-HRL Online Scheduling. Require: Trained TS policy πθTS , trained CS policy πθCS , and trained GAT encoder fψGAT ; workflow stream W; resource pool H. Ensure: Task-to-container assignments and container-to-host placements. 1: Initialize the scheduling environment and resource states; 2: while the scheduling episode is not terminated do 3: Process workflow arrivals and task completions; for newly arrived workflows, compute timing indicators using (22)-(25) and update ready set R; 4: Construct the merged DAG and update task embeddings using the trained GAT encoder fψGAT according to (27)(33); 5: while R ̸= ∅ do 6: Select tk,j , construct sTS from (34), and sample q TS aTS q ∼ πθTS (·|sq ); 7: Execute aTS by reusing a feasible container or req questing a new one; enqueue the new container if requested; 8: end while 9: while the deployment queue is not empty do 10: Select cm ; construct sCS q using (37)-(38), and sample CS aCS q ∼ πθCS (·|sq ); 11: Deploy cm to the selected feasible host or activate a new host; 12: end while 13: Advance to the next scheduling event; update execution, transmission, and task timing using (2), (3), (4), and (5)-(8), and update energy using (12)-(15); 14: end while 15: return the final scheduling decisions;
than elapsed physical time. The holding time ∆gq affects the transition to the next decision state through the physical system evolution, but is not used as an additional time-dependent discount. 1) TD residual and GAE: In the following, g ∈ {TS, CS} denotes the agent, and q indexes its consecutive decisions. The Temporal-Difference (TD) residual of agent g is δqg = rqg + mgq γVϕg (sgq+1 ) − Vϕg (sgq ),
(42)
where rqg is the reward after decision q, Vϕg (·) is the critic, and mgq is a non-terminal mask with mgq = 0 for terminal transitions and mgq = 1 otherwise. γ ∈ (0, 1) is the perdecision discount factor. The generalized advantage estimate (GAE) is then Âgq = δqg + mgq γλGAE Âgq+1 ,
(43)
where λGAE controls the bias-variance tradeoff. 2) PPO objective: For both agents, the actor maximizes the clipped surrogate objective h i Lgπ (θg ) = Ê min ugq (θg )Âgq , clip(ugq (θg ), 1 − ε, 1 + ε)Âgq , (44)
11
where
Algorithm 2 Alternating PPO Training of TS and CS Agents. πθg (agq |sgq ) ugq (θg ) = πθgold (agq |sgq )
Require: GAT encoder fψGAT ; TS policy-value pair (πθTS , VϕTS ); CS policy-value pair (πθCS , VϕCS ); γ, λGAE , ε; number of alternating epochs E; rollout lengths is the probability ratio between the current and previous LTS and LCS ; PPO optimization epochs S. policies, and clip(·) constrains this ratio to [1 − ε, 1 + ε]. Ensure: Trained GAT encoder fψGAT , TS policy πθTS , and CS 3) Critic and combined objective: The target used to train policy πθCS . the critic is 1: Initialize the GAT encoder, the two actor-critic networks, Ĝgq = Âgq + Vϕg (sgq ), (46) and rollout buffers DTS and DCS ; 2: for e = 1 to E do and the critic minimizes the mean-squared value loss 3: Fix πθCS and reset the environment; 2 4: for q = 1 to LTS do g g g LV (ϕg ) = Ê Vϕg (sq ) − Ĝq . (47) 5: Compute the current task embedding with fψGAT old and TS construct s ; q The actor-critic parameters are updated by maximizing the TS TS 6: Sample a from πθTS old (·|sq ) and execute the action; q combined PPO objective: 7: Use fixed π for intervening CS decisions; θCS g g g g b 8: Store the TS transition in D ; JPPO (θg , ϕg ) = Lπ (θg ) − c1 LV (ϕg ) + c2 E Ent πθg (· | sq ) , TS 9: end for (48) TS 10: Calculate ÂTS q and Ĝq ; where c1 is the value-loss coefficient, Ent(·) is policy entropy, 11: for i = 1 to S do and c2 (set to 0.01) is the entropy coefficient used in the 12: Jointly update ψ, VϕTS , and πθTS using the TS PPO implementation. objective; 4) Alternating training: The two agents are trained alter- 13: end for nately using separate actor-critic networks and rollout buffers. 14: Fix the updated f GAT and TS actor-critic network, and ψ The alternating PPO training procedure is summarized in reset the environment; Algorithm 2. 15: for q = 1 to LCS do In implementation, scheduling one task or deploying one 16: Use the fixed TS policy and encoder until a CS container constitutes one decision step in the corresponding decision is triggered; agent-specific trajectory. During the TS training phase, the 17: Construct sCS q ; CS current CS policy is kept fixed and is used to process the 18: Sample aCS old (·|sq ) and execute the action; q from πθCS intervening CS decisions required to advance the shared en- 19: Store the CS transition in DCS ; vironment. After the TS rollout is collected, the TS agent 20: end for computes its GAE advantages and updates its actor-critic 21: Calculate ÂCS and ĜCS ; q q network using the TS rollout buffer. The updated TS policy 22: for i = 1 to S do is then kept fixed during the subsequent CS training phase, in 23: Update VϕCS and πθCS using the CS PPO objective; which it processes the intervening task-scheduling decisions. 24: end for After the CS rollout is collected, the CS agent computes its 25: Update policy/encoder parameters, clear both buffers, GAE advantages and updates its actor-critic network using the and evaluate the joint policy; CS rollout buffer. 26: end for For the finite-horizon scheduling episodes considered here, the number of workflows, tasks, and corresponding TS/CS decisions is finite. With bounded rewards and 0 < γ < 1, the decision-indexed return in (41) is well defined. For a A. Experimental Setup fixed policy, standard policy evaluation under the per-decision 1) Environment Configuration: All experiments were imdiscount retains the usual contraction property, so the nonuniplemented in Python 3.11.13 with PyTorch 2.6.1 and form physical holding times do not alter the policy-evaluation sb3-contrib 2.7. Each reported metric is averaged over formulation adopted here. Since PPO uses nonlinear function 50 independent evaluation runs with different random seeds, approximation and the two policies are coupled through the covering random workflow arrivals, container execution-speed scheduling environment, however, we do not claim global variations, and learning-based scheduling decisions. convergence to an optimal joint policy. Instead, the training At the beginning of each scheduling episode, no host is curves in our experiments (e.g., Fig. 3) are used to evaluate active. Hosts are activated on demand by the CS agent. A empirical convergence. container is terminated when it has neither an executing task nor a waiting task, and a host is shut down when no container V. P ERFORMANCE E VALUATION remains on it. If the same physical resource is activated again We evaluate GA-HRL using three metrics: workflow later, it is treated as a new host instance with a new host ID scheduling success rate, average container resource utilization, for scheduling and energy accounting. Accordingly, N denotes the total number of host instances activated during an episode. and total system energy consumption. (45)
12
TABLE II: Parameters of host types
1 2
96 192
264000 528000
Memory (GB) 384 768
795 1600
0.5
2) Parameter Settings: We construct a trace-driven environment from the 2018 Alibaba cluster trace [26]. Eight container types are considered, with CPU allocations {1, 2, 4, 6, 8, 16, 24, 32} cores and memory allocations {4, 8, 16, 24, 32, 64, 96, 128} GB. The mean capacity and power of each container are derived from its hosting host and CPU-core share. The host configurations are summarized in Table II. Following [27], we use 5,200 workflow DAGs from the trace, each containing at least 10 tasks. The output data volume of each task is uniformly distributed over [500, 5000] MB, the cross-host bandwidth is 200 MB/s, and the intra-host bandwidth is 500 MB/s. (m) For each task execution, the capacity Qk,j is sampled from the rejection-sampled model in (2). The execution-speed variation coefficient is v ∈ {0, . . . , 0.45} with a step size of 0.05. The number of workflows is K ∈ {100, . . . , 1000} with a step size of 100, and workflow arrivals follow a Poisson process with rate λ = 0.5. The TS and CS agents use the same PPO hyperparameters: learning rate 1 × 10−5 , discount factor γ = 0.99, GAE parameter λGAE = 0.95, clipping range ε = 0.2, valueloss coefficient c1 = 0.5, entropy coefficient c2 = 0.01, and maximum gradient norm 0.5. Each PPO rollout contains 2,048 decision steps, with a minibatch size of 32 and two optimization epochs per update. The reward coefficients are w1TS = 0.4, w2TS = 0.3, w3TS = 0.3, w1CS = 0.7, and w2CS = 0.3. Training is performed for 1,000 alternating epochs, with 2,048 TS and 2,048 CS training steps per epoch. Following [1], the deadline of workflow Wk is Dk = Ak + α
df
Skfast ,
0.4 0.3 0.2
GA-HRL M/A2C M/DDQN M/f-GAT M/f-CS
0.1 0 -0.1 0
50
ek,ij ∈E(P)
ex,min where τk,i is the execution time of tk,i on the fastest container type. Thus, a larger αdf relaxes the deadline.
B. Ablation Study We construct four ablated versions to examine the contribution of each main component. M/A2C and M/DDQN replace PPO with A2C and DDQN, respectively. M/f-GAT removes the GAT encoder and uses the original task features directly as policy input. M/f-CS retains the learned TS policy but replaces the CS policy with a random feasible host-placement rule.
100
150
200
250
300
Number of episode
(b) 0.4 0.35 0.3 0.25 0.2
GA-HRL M/A2C M/DDQN M/f-GAT M/f-CS
0.15 0.1 0.05 0
50
100
150
200
250
300
Number of episode Fig. 3: Training convergence of different methods: (a) average reward of the TS agent and (b) average reward of the CS agent. TABLE III: Ablation study results of GA-HRL Method
Workflow success (%)
Container resource utilization (%)
Energy consumption (J)
GA-HRL M/A2C M/DDQN M/f-GAT M/f-CS
100 97 95 100 92
65 64 66 65 70
1.84×107 1.98×107 2.02×107 2.03×107 2.19×107
(49)
where αdf ∈ {2.0, . . . , 2.9} (with a step size of 0.1) is the deadline factor, and Skfast is the critical-path length under the fastest-resource assumption. Let Pk denote the set of entryto-exit paths of Wk , and let T (P) and E(P) denote the task and edge sets on path P. Then X X dk,ij ex,min , (50) τk,i + Skfast = max P∈Pk B cr tk,i ∈T (P)
Average reward of TS agent
CPU cores
(a) Mean power (W)
Average reward of CS agent
Type
Mean capacity (MIPS)
Fig. 3 compares training rewards, and Table III reports the final scheduling metrics. The training curves in Fig. 3 show that GA-HRL and M/A2C converge to relatively high TS rewards, whereas M/DDQN exhibits larger fluctuations. On the CS side, M/fCS remains substantially lower and more volatile because its host decisions are random. Table III further shows that removing GAT preserves workflow success but increases energy consumption, while removing the learned CS policy reduces success to 92% and increases energy to 2.19 × 107 J. These results indicate that the dependency-aware representation and learned host placement contribute in complementary ways: the former improves task-decision quality, and the latter coordinates locality and resource consolidation.
13
Scheduling success (%)
GA-HRL SMWDSA
DTODRL DS-CSP
(a)
100 80 60 40
Resource utilization (%)
2.0
Energy consumption (J)
OHDS HACPPO
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9 (b)
70 65 60 55 50 45 2.0
3.5
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
107
2.9 (c)
3 2.5 2 2.0
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
Fig. 4: Effect of the deadline factor αdf with K = 100 workflows, λ = 0.5, and v = 0.1: (a) workflow scheduling success rate, (b) average container resource utilization, and (c) total system energy consumption.
C. Performance Comparison 1) Benchmark Settings: We compare GA-HRL with five baselines representing the approaches of learning, heuristic, and optimization: DTODRL [10], OHDS [6], SMWDSA [1], HACPPO [28], and DS-CSP [13]. OHDS includes its own container-placement strategy, which is retained. For baselines that do not define host placement, we keep their original task policy and select the second-level placement randomly from feasible hosts. Within each run, all methods receive the same workflow instances, arrival process, and random seed. 2) Effect of the deadline factor: We first evaluate the effect of the deadline factor αdf with K = 100 workflows, Poisson arrival rate λ = 0.5, and execution-speed variation coefficient v = 0.1. The results are shown in Fig. 4. As shown in Fig. 4(a), relaxing the deadline generally enhances workflow scheduling success. GA-HRL and DTODRL maintain a 100% success rate across the entire tested range. HACPPO also exhibits steady improvement with increasing αdf and consistently outperforms the heuristic and determin-
istic baselines, though it falls short of the two top-performing learning-based methods. In contrast, OHDS, SMWDSA, and especially DS-CSP yield lower success rates, as their policies are less responsive to the combined effects of dynamic arrivals, precedence constraints, and execution-speed variations. The utilization and energy metrics in Fig. 4(b)–(c) offer a clearer distinction among the learning-based approaches. GAHRL achieves the highest and most stable container utilization, ranging from 66% to 68%, at an energy cost of only 1.76×107 1.88 × 107 J. DTODRL attains the same workflow success rate but utilizes only 61%-64% of container capacity and consumes 2.14 × 107 -2.32 × 107 J. HACPPO shows utilization close to that of GA-HRL yet incurs consistently higher energy consumption, indicating that similar container occupancy does not necessarily imply equivalent placement efficiency. Among the major baselines, SMWDSA remains the least resourceefficient, with utilization below 50% and energy consumption around 3.09 × 107 J. Overall, these results suggest that GAHRL can satisfy both loose and stringent deadlines without resorting to indiscriminate resource over-provisioning. 3) The influence of execution-speed variation: We next evaluate robustness to execution-speed variation by changing v from 0 to 0.45 while fixing K = 100, λ = 0.5, and αdf = 2.1. The results are shown in Fig. 5. Figure 5(a) shows that higher execution-speed variation lowers success for all methods, though at markedly different rates. At v = 0.45, DTODRL leads with 86%, followed by GA-HRL at 82%. HACPPO exhibits intermediate robustness, degrading more slowly than heuristic baselines yet faster than the top two. In contrast, SMWDSA and DS-CSP drop to 47% and 5%, respectively, highlighting the fragility of reactive or deterministic policies under high variability. The resource costs (Fig. 5(b)-(c)) reveal that GA-HRL maintains utilization at 63%-67% and energy at 2.32×107 J at v = 0.45. DTODRL achieves 4% higher success but consumes 3.27 × 107 J, while SMWDSA costs 4.98 × 107 J. HACPPO’s utilization stays stable, yet its energy exceeds GA-HRL’s with increasing volatility. Thus, at maximum variation, GA-HRL sacrifices a modest success margin (4%) for roughly 29% energy savings over DTODRL, which is consistent with its uncertainty-aware design that favors preserving deadline slack over aggressive scale-out. 4) The influence of the number of workflows: Finally, we evaluate scalability by varying the number of workflows K from 100 to 1000 with λ = 0.5, v = 0.1, and αdf = 2.1. The results are shown in Fig. 6. Fig. 6(a) shows that GA-HRL and DTODRL maintain workflow scheduling success close to 100% as the workload increases. HACPPO remains comparatively stable in the highsuccess region but below GA-HRL and DTODRL, whereas OHDS and SMWDSA level off at lower success rates and DSCSP degrades further. These results indicate that the learningbased schedulers are better able to absorb the denser arrival stream, but their resource efficiency differs. As shown in Fig. 6(b), the average container utilization of GA-HRL rises gradually from about 66% to 70%, indicating that the scheduler increasingly reuses existing containers as more workflows overlap. HACPPO also maintains relatively
14
GA-HRL SMWDSA
DTODRL DS-CSP
(a)
80 60 40 20
60
40
100
55 50
0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 10 7
Resource utilization (%)
60
Energy consumption (J)
(a)
200
300
400
500
600
700
800
900
(b)
65
4 3 2 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45
Fig. 5: Effect of the execution-speed variation coefficient v with K = 100 workflows, λ = 0.5, and αdf = 2.1: (a) workflow scheduling success rate, (b) average container resource utilization, and (c) total system energy consumption.
high utilization, while DTODRL remains slightly lower than GA-HRL over most of the tested range. Fig. 6(c) shows that total energy consumption increases steadily with workflow volume for all methods. GA-HRL remains the most energyefficient across the tested range and exhibits a more gradual increase than the competing schedulers. At K = 1000, GAHRL consumes 15.35 × 107 J, compared with 17.07 × 107 J for DTODRL and 22.53×107 J for SMWDSA; HACPPO also remains above GA-HRL in total energy. The results therefore support the conclusion that GA-HRL scales to denser workflow loads mainly through container reuse and coordinated placement rather than indiscriminate scale-out provisioning. VI. C ONCLUSION AND F UTURE W ORK This paper presented GA-HRL, an event-driven hierarchical reinforcement learning scheduler for dynamic cloud workflows with stochastic execution speeds and placement-dependent communication. It represents workflows as DAGs, uses predicted sub-deadlines to capture task urgency, and applies a
1000
(b)
70 65 60 55 50 45 100
(c)
5
0.0
DTODRL DS-CSP
80
0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45
70
45 0.0
OHDS HACPPO
100
200
300
400
500
600
700
800
900
10 8
Energy consumption (J)
0 0.0
Scheduling success (%)
OHDS HACPPO
100
Resource utilization (%)
Scheduling success (%)
GA-HRL SMWDSA
1000
(c)
3
2
1
0 200
300
400
500
600
700
800
900
1000
Fig. 6: Effect of the number of workflows K with λ = 0.5, v = 0.1, and αdf = 2.1: (a) workflow scheduling success rate, (b) average container resource utilization, and (c) total system energy consumption.
multi-head GAT to encode dependency information. A taskscheduling agent then assigns ready tasks to containers, and a container-scheduling agent places newly requested containers, with both agents trained alternately using separate PPO actorcritic networks. Trace-driven experiments on the 2018 Alibaba cluster trace showed that GA-HRL maintains competitive workflow success while generally achieving higher container utilization and lower energy consumption, and at the largest speed variation it trades a small success-rate gap relative to DTODRL for substantially lower energy. Ablation results further confirmed that the dependency-aware task representation and learned container placement improve scheduling efficiency in complementary ways. The current model represents runtime interference through execution-speed variation and does not explicitly consider resource failures or online estimation errors; future work will evaluate GA-HRL on a physical testbed and incorporate measured interference, failures, and online performance estimation.
15
R EFERENCES [1] L. Ye, Y. Xia, L. Yang, and C. Yan, “Shws: Stochastic hybrid workflows dynamic scheduling in cloud container services,” IEEE Transactions on Automation Science and Engineering, vol. 19, no. 3, pp. 2620–2636, 2022. [2] H. Chen, X. Zhu, G. Liu, and W. Pedrycz, “Uncertainty-aware online scheduling for real-time workflows in cloud service environment,” IEEE Transactions on Services Computing, vol. 14, no. 4, pp. 1167–1178, 2021. [3] C. Cheng, J. Li, and Y. Wang, “An energy-saving task scheduling strategy based on vacation queuing theory in cloud computing,” Tsinghua Science and Technology, vol. 20, no. 1, pp. 28–39, 2015. [4] Z. Liu, L. Huang, Z. Gao, M. Luo, S. Hosseinalipour, and H. Dai, “Gadrl: Graph neural network-augmented deep reinforcement learning for dag task scheduling over dynamic vehicular clouds,” IEEE Transactions on Network and Service Management, vol. 21, no. 4, pp. 4226–4242, 2024. [5] L. M. Al Qassem, T. Stouraitis, E. Damiani, and I. M. Elfadel, “Containerized microservices: A survey of resource management frameworks,” IEEE Transactions on Network and Service Management, vol. 21, no. 4, pp. 3775–3796, 2024. [6] G. Fan, X. Chen, Z. Li, H. Yu, and Y. Zhang, “An energy-efficient dynamic scheduling method of deadline-constrained workflows in a cloud environment,” IEEE Transactions on Network and Service Management, vol. 20, no. 3, pp. 3089–3103, 2023. [7] H. Topcuoglu, S. Hariri, and M.-Y. Wu, “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE transactions on parallel and distributed systems, vol. 13, no. 3, pp. 260– 274, 2002. [8] X. Yu, W. Wu, and Y. Wang, “Integrating cognition cost with reliability qos for dynamic workflow scheduling using reinforcement learning,” IEEE Transactions on Services Computing, vol. 16, no. 4, pp. 2713– 2726, 2023. [9] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski et al., “Human-level control through deep reinforcement learning,” nature, vol. 518, no. 7540, pp. 529–533, 2015. [10] Z. Cao, X. Deng, S. Yue, P. Jiang, J. Ren, and J. Gui, “Dependent task offloading in edge computing using gnn and deep reinforcement learning,” IEEE Internet of Things Journal, vol. 11, no. 12, pp. 21 632– 21 646, 2024. [11] A. Kheldoun, K. Barkaoui, and M. Ioualalen, “Formal verification of complex business processes based on high-level petri nets,” Information Sciences, vol. 385, pp. 39–54, 2017. [12] S. Jiao, X. Zhang, S. Yu, X. Song, and Z. Xu, “Joint virtual network function selection and traffic steering in telecom networks,” in GLOBECOM 2017-2017 IEEE Global Communications Conference. IEEE, 2017, pp. 1–7. [13] M. Hähnel, J. Martinovic, G. Scheithauer, A. Fischer, A. Schill, and W. Dargie, “Extending the cutting stock problem for consolidating services with stochastic workloads,” IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 11, pp. 2478–2488, 2018. [14] L. Liu, H. Tan, S. H.-C. Jiang, Z. Han, X.-Y. Li, and H. Huang, “Dependent task placement and scheduling with function configuration in edge computing,” in Proceedings of the International Symposium on Quality of Service, 2019, pp. 1–10. [15] A. Das, S. Imai, S. Patterson, and M. P. Wittie, “Performance optimization for edge-cloud serverless platforms via dynamic task placement,” in 2020 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID). IEEE, 2020, pp. 41–50. [16] S. Deng, H. Zhao, Z. Xiang, C. Zhang, R. Jiang, Y. Li, J. Yin, S. Dustdar, and A. Y. Zomaya, “Dependent function embedding for distributed serverless edge computing,” IEEE Transactions on Parallel and Distributed Systems, vol. 33, no. 10, pp. 2346–2357, 2021. [17] M. A. Rodriguez and R. Buyya, “Deadline based resource provisioningand scheduling algorithm for scientific workflows on clouds,” IEEE transactions on cloud computing, vol. 2, no. 2, pp. 222–235, 2014. [18] V. Arabnejad, K. Bubendorfer, and B. Ng, “Scheduling deadline constrained scientific workflows on dynamically provisioned cloud resources,” Future Generation Computer Systems, vol. 75, pp. 348–364, 2017. [19] Y. Yang, H. Shen, and H. Tian, “Scheduling workflow tasks with unknown task execution time by combining machine-learning and greedyoptimization,” IEEE Transactions on Services Computing, vol. 17, no. 3, pp. 1181–1195, 2024. [20] F. Ding, Y. Yuan, L. Lv, R. Zhang, and W. Zhou, “Transformer-enhanced
dqn approach for energy and cost-efficient large-scale dynamic workflow scheduling in heterogeneous environment,” IEEE Internet of Things Journal, vol. 11, no. 22, pp. 37 351–37 367, 2024. [21] Y. Xie, L. Huang, Y. Kong, S. Wang, S. Xu, X. Wang, and J. Ren, “Virtualized network function forwarding graph placing in sdn and nfvenabled iot networks: A graph neural network assisted deep reinforcement learning method,” IEEE Transactions on Network and Service Management, vol. 19, no. 1, pp. 524–537, 2022. [22] C. Jin, X. Bai, C. Yang, W. Mao, and X. Xu, “A review of power consumption models of servers in data centers,” applied energy, vol. 265, p. 114806, 2020. [23] Q. Wu, F. Ishikawa, Q. Zhu, Y. Xia, and J. Wen, “Deadline-constrained cost optimization approaches for workflow scheduling in clouds,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 12, pp. 3401–3412, 2017. [24] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” arXiv preprint arXiv:1710.10903, 2017. [25] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347, 2017. [26] Website. Alibaba Inc. (2018), [Online]. Alibaba Production Cluster Data v2018. Available: https://github.com/alibaba/clusterdata/tree/v2018. [27] Z. Sun, Y. Mei, F. Zhang, H. Huang, C. Gu, and M. Zhang, “Multitree genetic programming hyper-heuristic for dynamic flexible workflow scheduling in multi-clouds,” IEEE Transactions on Services Computing, vol. 17, no. 5, pp. 2687–2703, 2024. [28] A. Jayanetti, S. Halgamuge, and R. Buyya, “Deep reinforcement learning for energy and time optimized scheduling of precedence-constrained tasks in edge–cloud computing environments,” Future Generation Computer Systems, vol. 137, pp. 14–30, 2022.