Reinforcement learning for one-shot DAG scheduling with comparability identification and dense reward
Authors: Xumai Qi
Dongdong Zhang
Taotao Liu
Hongcheng Wang
Venue: NeurIPS 2025 poster ()
Keywords: DAG scheduling
graph theory
combinatorial optimization problem
reinforcement learning
Primary area: reinforcement_learning

Abstract: In recent years, many studies proposed to generate solutions for Directed Acyclic Graph (DAG) scheduling problem in one shot by combining reinforcement learning and list scheduling heuristic. However, these existing methods suffer from biased estimation of sampling probabilities and inefficient guidance in training, due to redundant comparisons among node priorities and the sparse reward challenge. To address these issues, we analyze of the limitations of these existing methods, and propose a novel one-shot DAG scheduling method with comparability identification and dense reward signal, based on the policy gradient framework. In our method, a comparable antichain identification mechanism is proposed to eliminate the problem of redundant nodewise priority comparison. We also propose a dense reward signal for node level decision-making optimization in training, effectively addressing the sparse reward challenge. The experimental results show that the proposed method can yield superior results of scheduling objectives compared to other learning-based DAG scheduling methods.

Reinforcement learning for one-shot DAG scheduling with comparability identification and dense reward
Xumai Qi!
Dongdong Zhang"
Taotao Liu'
Hongcheng Wang'
School of Computer Science and Technology, Tongji University
Shanghai Key Laboratory of Urban Renewal and Spatial Optimization Technology, CAUP, Tongji University
Abstract
In recent years, many studies proposed to generate solutions for Directed Acyclic Graph (DAG) scheduling problem in one shot by combining reinforcement learning and list scheduling heuristic. However, these existing methods suffer from biased estimation of sampling probabilities and inefficient guidance in training, due redundant comparisons among node priorities and the sparse reward challenge. To address these issues, analyze of the limitations of these existing methods, and propose novel one-shot DAG scheduling method with comparability identification and dense reward signal, based the policy gradient framework. In our method, a comparable antichain identification mechanism is proposed to eliminate the problem of redundant nodewise priority comparison. We also propose dense reward signal for node level decision-makee making optimization in training, effectively addressing the sparse reward challenge. The experimental results show that the proposed method can yield superior results of scheduling objectives compared to other learning-baid brased DAG scheduling methods.
Introduction
The Directed Acyclic Graph (DAG) scheduling problem is a class of NP-hard [Kan 2012] Com- binatorial Optimization Problems (COP). DAG scheduling problem arises in the emerging cloud manufacturing and distributed computing, involving production and computation workflow schedul- ing. The jobs, operations, tasks modeled into nodes of DAG, and the directed edges represent the precedence constraints among them. The goal to achieve the best possible performance by determining an optimal node execution order and allocating resources accordingly.
DAG scheduling has attracted extensive research attention, with many heuristic, metaheuristic and Reinforcement Learning (RL) methods proposed to solve it. Among them, RL has already shown promise in solving generic COPs [woon et al. 2020 Hottung et al., 2022 Choo et al. 2022 Zhang
al. 2023 Wang et al. 2025 Specifically for DAG scheduling, early studies tended construct the solution (i.c., the order of node execution) incrementally [Mao et al. 2019 Zhou et al.) 2022 Song
al. 2023 They utilized graph neural networks (GNN) guide the policy network to select the optimal schedulable node at each step, until the complete solution is constructed.
Considering that the incremental solution construction methods computationally consuming and less efficient in training, some studies proposed RL-based one-shot DAG scheduling, which is motivated by list scheduling [Lee et al. 2020 202 Jeon et al. 2023 They attempted to enable network to infer the entire solution through a single forward propagation process. List scheduling is classic and effective heuristic rule for DAG scheduling. As shown in Fig Ia| they generate full schedule of the DAG by leveraging GNN to assign a fixed priority list for all task nodes in one single step, and iteratively learn to optimize the network according to the objective cost the feedback
"Corresponding Author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Simulation Evalustion
Estimating dense reward
Simulation & Fxaibati
Node level reward (dense)
Global reward (sperse)
Exceation order
Priorit rakk solution
solution
Comparable antichain idlentification
Pairwise priority comperrison
Joint makk sampling probability
Nodewise sampling probubility
Prorrties
Policy Network
Polley Network
Policy gradient calculation
Policy gradient calculation
GNN Encoder
DAG Schedaling problem
DAG Schedalinng problem
(a) Existing method.
(b) Our proposed method.
Figure 1: The comparison of existing one-shot DAG scheduling method and ours.
reward. Compared to the incremental solution construction methods, such one-shot scheduling approaches generally yields better results and requires less computation.
However, we will analyze in detail in section 3, the existing RL-based one-shot scheduling approaches involve excessive node priority comparisons and sparse reward signal challenge, leading to unstable training and suboptimal results. They unnecessarily compare node priorities in pairwise, rather than accurately representing the distribution of execution order, leading to biased policy sampling probability and high variance in policy gradient estimation. Moreover, the sparse reward problem remains challenge in the one-shot approaches. The agent has optimize the entire priority list with a limited amount of global reward signal.
To address these issues, as shown in Fig. 1b based on our analysis, we propose a novel RL-based one-shot DAG scheduling method with comparability identification and dense reward signal. (We define comparable to distinguish the task pairs that would influence the priority-induced execution orders.) For the redundant node priority comparison problem the existing RL-based one-shot scheduling approaches, we propose comparable antichain identification mechanism to eliminate the problem of redundant nodewise priority comparison. In this way, we can derive the accurate formulation of the nodewise sampling probability corresponding to the generated solution, thereby avoiding inaccurate probability estimation and improving training stability. Besides, compared to the existing methods suffering from sparse reward challenge, we design dense reward for one-shot RL-based DAG scheduling methods to guide node-level optimization, enabling the scheduling results to closely converge the optimum. We modify the key components in the existing RL-based one-shot DAG scheduling method, while retaining the list- based scheduling components that have proven effective. The key contributions of this study are follows:
We analyze the limitations of existing RL-based one-shot methods in DAG scheduling, including the redundant nodewise priority comparison problem and the sparse reward challenge.
Based on the analysis, we propose novel RL-based one-shot solution generation method for DAG scheduling. In our method, a comparable antichain identification mechanism is proposed to eliminate the problem of redundant nodewise priority comparison. We also propose dense reward signal for node level decision- decision-making optimization in training, effectively addressing the sparse reward challenge.
Comprehensive comparative and ablation experiments conducted on various DAG scheduling tasks demonstrate the superiority of our method in terms of solution quality.
2 Preliminaries
DAG scheduling. We define a DAG = (V,E). where the node set V = {wi 02 ... Un
represents the tasks in the real-world DAG scheduling problem, and the directed edge set E C V denotes the precedence constraints among the tasks. If (v,, vy)) E F, task uy cannot start until vs completed. That is, task node can be ready only after all its predecessors is finished. Each task ię is

---

typically associated with a processing time d,, and d; might be related to the processor where the task allocated. The scheduler needs to determine feasible task node execution order, and processor allocation if in proti-pro environments. The goal is to optimize the target cost metric evaluated after completing the DAG execution, such as makespan.
List scheduling heuristic for DAG scheduling. In list scheduling, according to certain ranking rule : {1, 2, .... n} + {1. ..., n,,, list of priority rank Rank(V) [vo(1)) Vo(2):... .... (n(n)) for each node in V is generated. At each step, the ready task that has the highest priority rank is selected to be scheduled.
Policy gradient. In a typical policy gradient framework, the gradient to update the network parame- ters is formulated as Equation (L) Po (a (8)) is the probability for the RL network with parameters 0 to sample according to the current st. R, is the cumulative single-step reward r starting from t.
T
VoJ(0) Epo
Volog po(arlst) Rs
(1)
One-shot DAG scheduling. The existing approaches (e.g. J.oo et al. 2023 follow the paradigm of list scheduling and policy gradient. Instead of making stepwise decisions, they define the action space as the priority rank of all task nodes in the DAG. As shown in Fig. Ta the DAG scheduling problem instance is fed into the RL network 6 which consists a GNN encoder and a policy network, outputting logits for each node. The logits are treated as the priority values of each task node. The corresponding ranking rule og is to perform a descending sort on the logits of each task node. In this way, the priority rank Ran descending sort can essentially be interpreted as iteratively selecting the maximum element from the remaining unselected ones, which involves pairwise priority comparison of all task nodes. At each selection step, the sampling probability can be calculated by performing softmax operation over the current candidates V (1)a(1)) ...; (t)(t- as shown in Equation (2). The probability of the entire rank can be calculated as Equation (3) In one-shot DAG scheduling, Equation (T) can be modified to
[1))(1)) (2a(22) (n)(n) can be sampled. Sampling such
Equation (4). where C(G, Rank(V V)) ) is the value of optimization goal when applying the sampled
priority rank Rank(V (V 0) on G.
exp(logits, (Voott))
po po(Voncelllooo()> un (-))
(2)
LEV (VV exp(logits, (v)
exp(logits, (1a)
P(Rank(V:0)) vVV (V exp(logits,(v))
(3)
VoJ(O) = (p((ann(VVe)) Volog P(Rank(V:O)) C(G. Ran
(4)
3 Analysis of the one-shot schedule approaches
3.1 Redundant priority comparison and biased sampling probability estimation
We observe that the current methods' action space is inconsistent with the actual scheduling solutions. The existing methods directly regard the output priority rank Rank(V; ()) as the action of RI.. However, multiple priority ranks may correspond to same node execution sequence. Some heuristic- based priority generating approaches, such as Topcuoglu et al. [2002]. Djigal et al. [202]], are designed to ensure that the obtained node priority rank is also the node execution order, but the logits output by a neural network cannot inherently guarantee such consistency. (For example, in Fig. 2, both Rank(V; 01) and Rank(VV (2) result in the same node execution order for the graph on the left.) If multiple priority ranks Rank1, Ranky,... correspond to a same node execution sequence Solution (G) [Mz(T), Un(2): ..., (x(n)). the total probability of sampling that solution should be Equation
5). So, if only single rank list's probability P P(Rank)) ) is used to approximate
3

---

Sampled ranks
Solutions
Rank (V; (P), 21. Pa. 12]
((G;
[1 P2. V4. Vzl
Rank (V; (v,, P2, v3. vyl
((;
[u, 22, U4 23]
Rank (V, P2. 24 v1]
S (G))
[vg, Pz. Vg.
The examples of different priority rank that which can be mapped to same node execution order, and the impact of inaccurate probability estimation on training.
Figure 2:
P(Solution( G)), this introduces underestimation in probability. This increases entropy and the variance of the policy gradient.
P(Solution((]) = P(Rankı U Rankz U...)
(5)
Such inconsistency causes redundant comparison. Given a one-shot RL network the solution Solution( G; 0) is priority topological sort of G based on Rank(V;0) 0). This sort is constrained by both the priority ranks and the directed edges F. E are hard constraints, while the priority ranks only serve soft constraints. If there exists a path from u to v. then is guaranteed to precede v in any valid Solution G),, regardless of their priority. The priority comparison of nodes located on the same path is unnecessary. But when constructing priority rank, existing methods iteratively select the node with the maximum priority by comparing it with all unselected nodes, including the nodes that on the same path of the selected node. These comparisons are thus redundant or invalid, as they do not affect the resulting topological order. Treating them as candidate actions introduces irrelevant logits into the softmax distribution, distorting the sampling probability.
Redundant priority comparison and biased sampling probability estimation may lead to unstable training and suboptimal results. Under pairwise priority comparison, the model may tend to equally optimize the pairwise ordering of all node pairs, rather than focusing on those node pairs that actually influence the final schedule. The model might spend unnecessary effort optimizing the rank of nodes on the same paths. As a result, the training can become less efficient. Taking Fig. 2 for example, the final node execution order is solely determined by the relative priorities between Vs and 04. If the optimization objective cost C(G, Rank(V; 02)) obtained from Rank(V (V; (2) achieves better than C(G, Ronk(V: (s)), the model might mistakenly attribute the improvement 2/2 's being higher-ranker than U1. However, since in and 1/2 lie on the same path, their relative priorities have no influence on the result. Similarly, the model may spend unnecessary effort optimizing other node pairs that are irrelevant to the outcome, such as < 01, G3 >, < U1 04 >.
3.2 Sparse reward challenge
In addition to the redundant priority comparison, also need to address the sparse reward challenge in the one-shot solution generation methods. Specifically, the global reward is generated only once in the whole decision-making process, which cannot effectively reflect the specific contribution of each local decision (the priority assignment of each task node) to the final result, thus seriously limiting the effective guidance of policy gradient algorithm for network parameters. This sparsity not only makes the training, but also may cause the model to get trapped in local optimum. Therefore, key
designing a denser and more decomposable reward signal guide local pecision-makinn issue to improve the training efficiency and stability of one-shot method.
In conclusion, the biased sampling probability estimation caused by redundant priority comparison, together with the sparse reward challenge, would constraint the performance of RL-based one-shot DAG scheduling. We will address these two issues in the next section.
4 Proposed method
4.1 Motivation
To address the issue of redundant priority comparison, according to the analysis in the previous section, we need to distinguish the nodes that has necessity to compare. Removing those invalid nodes in each step aligns the actual sampling distribution closer to the true P(Solution(G)) It can produce lower-entropy distributions and reduced policy gradient variance, which is beneficial to the

---

convergence for RL model [uuang and Ontañón 2020]. Clearly, there is no need to compare the priorities of node pairs lying on the same path. Only mutually unreachable node pairs (i.e., those belonging to the same antichain) require comparisons. However, since a node may appear in multiple different antichains, it is necessary to determine which antichain comparisons are relevant. For example, assume that {u, " and {v, u2) are respectively two antichains in graph, with a path between in and u2. If v is prior to i1 in Rank(V), V is guaranteed to precede u2 in Solution (G), no matter which one in 2 and 02 is prior. This makes the priority comparison between u1 and v2 unnecessary. But if My is prior to v, the comparison between ii and 12 remains essential to determine the final order of and Ug in Solution(G).
It is challenging to define a meaningful stepwise reward for DAG scheduling problems. However, is still practical to estimate the cumulative return R, in one-shot scheduling. The cumulative reward at each step reflects the difference between the contribution of the current/local decision and the global objective. Since the objective value associated with each task node can be obtained during the simulation-base based evaluation of the overall scheduling result, the cumulative reward can be estimated accordingly.
In this section, we propose a one-shot solution generation method for DAG scheduling based on policy gradient algorithm framework that can address the above-mentioned problems. Specifically, we first propose a comparable antichain identification method for each node during the process of priority topological sorting. This enables us to compute nodewise sampling probabilities and obtain an execution sequence as the solution. The simulated or evaluated cost of each node in the resulting schedule is then compared with heuristic-deriver advantage baseline to generate node level dense reward signals. These dense rewards, along with the sampling prohabílities, are used to calculated the policy gradient. The overview figure of the proposed method is illustrated in Appendix A
Our framework adopts a GNN-based encoder and a multi-layer perceptron policy (MLP) policy network to handle the DAG scheduling problem instance to produce priority logits list for all nodes, following the common setup in prior work. The encoder implemented using the Graphormer (Ying) et al. [021]] whose effectiveness in encoding directed graph data has been widely validated. Check Appendix C for more details about the implementation about our method.
4.2 Comparable antichain identification
We define pair of nodes as comparable if their relative priorities affect the resulting execution order, as formally stated in Definition Based on this definition, we further define the comparable antichain of node in Definition 2.
Definition 1 (Comparable node pair): Given task nodes and in DAG scheduling problem, a priority rank Rank(V), and the node execution sequence Solution (G) derived from Rank(V) Without loss of generality, assume that u is higher-ranked than (i.c., u is before & in Rank(V)). Remove and reinsert both u and into any position in Rank(V) while guaranteeing is now after v, obtaining& a Rank' (V). If, for any Rank' (V), the relative ordering of u and in Solution'(C) (G) derived from Rank' (V) ()))))))) is always the reserve of that in Solution( G), we say that < u > is comparable in (V).(V).
Definition 2 (Comparable antichain): The set that contains v and the comparable nodes of v in (Vn
We propose a straightforward comparable antichain identification method based on the priority topological sorting process, which aims to eliminate redundant priority comparisons between incom- parable nodes and accurately reflect the nodewise sampling probability corresponding to the sampled specific node execution sequence. Recalling the process of priority topological sorting: given DAG G, iteratively remove the already sorted nodes from G in each step f, obtaining subgraph Gt- Then in Ge, identify the set of nodes with 0 in-degree Vrin=0, and select the node Uz(+) with hightest priority rank from the O-in-degree set V/i==0 and append it to (G)
Clearly, the O-in-degree set V:i==0 in each step forms an antichain of G, since the node removal operations do not remove edges between the remaining nodes and the nodes with 0 in-degree is guaranteed to be mutually unreachable. According to lemma and lemma 2, we can track the comparable antichain of each ((())) by merely using Vin=0
Lemma 1: V=m==0 is comparable antichain of (c)
5

---

Proof: By construction, (x(() is higher-ranked than any E Vi" so Un(() appears before each such in the resulting Solution(G). Now suppose to re-insert the priority rank so that u is higher-ranked to Uz(()- Then either u selected before step t, or select instead of (z(() In both cases, would now be before (x()) in the resulting Solution' (G). Therefore, Vin forms comparable antichain of (n))))
Lemma 2: For any u E Vi none of its successors is comparable antichain with Ux(+)-
By construction, (x(1) is higher-ranked than any u E Vi=== and (a(()) appears before each u in Solution(G) u', a successor of u, is guaranteed to appear after u in Solution(G) due to the precedence constraints, must also appear after Uv(() in any valid Solution' (G) by re-inserting (w(() and u' in the priority rank. Thus, regardless of how the relative priorities between (x(() and u' are changed, their positions in Solution' (G) remain fixed.
Proof:
In this way, the nodewise sampling probability corresponding Solution(G). together with the probability of Solution (G) can be precisely obtained. The procedure of "selecting Uat(s) from vćin=0" can be interpreted as performing an argmax operation in V V:i== Similar with Jeon et al. (2023 iinttedd of performing argmax on the original logits of Vii==0 we use the gumbel-perture logits Kool et al., [2019) of V, Therefore, the sampled rank sequence becomes more aligned with the underlying probability distribution. Given the logits generated by the policy network in one shot, the softmax-based nodewise sampling probability can be calculated in Equation (6).
" on
xxp(logits,(Mma(t)
po(C:oco(S5-1(G:0) [Uxo(1), 11)(
(6)
Σ EEViin= exp(logits,
4.3
Dense reward
We further propose dense reward signal for RL-based one-shot DAG scheduling, providing nodewise reward signal to guide the optimization of local decisions. For each scheduled node, we define its dense reward signal based on its distance the final objective, thus approximating the node's value estimation. Such design also makes one-shot DAG scheduling more interpretable. Specifically, the nodewise decisions, sampling probabilities and dense reward signals can be regarded as an entire sampling trajectory in RL (like the trajectory by Monte Carlo sampling). This makes the interpretability of our methods closer to MDP-based incremental approaches than those one-shot methods with sparse reward signal signal C(G, SoluSoon G;; 0)) or C(G, Ronk(G;0)) (G))).
Considering Equation (I), we regard the selection of the hightest priority node from V:i==0 each step as the "action". instead of treating the generation of the whole priority rank or execution order the single action. The sampling probability of each step be calculated in Equation (6). Therefore, Equation (I can be modified into Equation
VaJ(O)
Volog pa (T R.
We estimate R₂ by Equation g Here, (() the objective cost function value corresponding to the current subsequence (G: For instance if the optimization goal is to minimizing the DAG's makespan, then C'S, 0)) indicates the latest completion time among all scheduled nodes when (1) is finished. The value of C(S.(G;)) can be obtained during the simulation process when computing C( C(Solution G; 0)).
R4 C(Solution - C(S((G:))
(8)
We further consider introducing advantage baseline to RG in order to stabilize the training. The advantage baseline is computed by a heuristic algorithm (c.g., critical path method). Specifically, before training on DAG scheduling problem G. we schedule G using the heuristic bascline, and record the objective cost value upon the completion of each node e; denoted as (1,).. Based on this, we can define the advantage function A, as shown in Equation (9). Ar can be further normalized
in batch-wieg wise into A nommlizod()). In this way, Equation can be modified into Equation (00) where

---

B is the batch size. The detailed procedure of calculating dense reward signal is demonstrated in Appendix
A = R. baseline = Ch. -C(S((())
(9)
B
VoJ(O) = B
11
V olog Po Po (e),
A mormalized(
(10)
In practice, compared sparse reward settings (where only the final cost is used), our dense reward reduces the variance of policy gradient estimates, because each node's policy update receives a targeted reward signal rather than sharing a single scalar. Also, it helps the model differentiate good and bad actions early in training.
5 Related work
RL has demonstrated significant potential in solving DAG scheduling problems in an end-to-end manner. typical RL DAG scheduler consists of a GNN encoder extracting graph features, and
a policy network making scheduling decisions [Mao et al. 2019 Zhou et al. 2022 Song et al.
2023). There are already some GNN variants for general DAG-structured applications YYu al.
2019 Thost and Chen [021 Luo et al. 2023]. Some focused on modifying GNNs specially for DAG scheduling [Gagrani al. 2022 Zhang et al.] [024]. The other studies paid attention to improving the decision-makinn
including modifying the policy network or action space. From the RL-based DAG scheduling, existing literature can be categorized into incremental solution construction, one-shot schedule generation, and adge-generation approaches.
viewpoint decision-maker
Incremental solution construction. The agents follow Markov Decision Process (MDP) to select a candidate task node at each step, constructing the whole solution incrementally (Yang et al. 2019
Yu et al. 2023 Dong al. 2023 Qi et al. 2024]. These methods faces two major limitations, which cause inefficient exploration and training. The first is the sparse reward challenge. Some works [Chen al. 2023 Wang et al. 2025 Nasuta et al.) [2044] tried overcome this challenge only in specific application domains, rather than providing general solutions. Second, these methods require re-encode the entire graph instance in each step, leading to excessive computation.
One-shot schedule generation. Inspired by the list scheduling heuristic, some studies learn to generate DAG schedules in one shot. Lee et al. [2200] 2021] proposed to use sequence learning technique to generate global fixed priority list for all task nodes in single step. Jeon et al. 2023 proposed a node prioritization method based on the Gumbel-man -maueel-mxxkk trick Kooo et al. 2019]] which enables efficient sampling of node priority values. One-shot scheduling avoids repeatedly extracting graph features and reduces the exploration space. However, the one-shot methods exhibit lower interpretability compared to incremental construction methods for not following MDP (Darvariu et al.] (2024) Moreover, when applied to large-scale instances, one-shot methods still limited by sparse reward challenge.
Edge generation. Some studies attempt to prioritize task nodes indirectly by modifying the DAG's topological structure, rather than directly generating solutions. Wang al. (202T) and EGS proposed by Sun et al. (2024) leverages the property of DAG scheduling problem that solution to remains valid after adding new edges. They iteratively generate edges using RL, aiming to improve the solution obtained by traditional heuristics. However, as we will later demonstrate, these approaches often suffer from an excessively large search space.
Experiments
In this section, we report the experimental results to evaluate both the individual contributions of proposed modules and the overall performance of our method compared with existing basclines.
7

---

Most of the training, simulation and evaluation of the experiments are conducted on machine with an Intel Gold 6226R CPU, 256 GB of RAM and NVIDIA RTX 3090 (24G) GPU.
Benchmarks setup. In order emphasize that our method is general method for DAG scheduling rather than being tied to a specific problem, we evaluate our method on three henchmarks with unique environment settings, reflecting the method's adaptability to diverse scenarios. These benchmarks Pegasus, TPC-H, and a job shop scheduling problem (JSSP) benchmark generated by ZZhng et al. [2020] Pegasus is scientifie workflow scheduling tracing dataset with heterogeneous multiprocessor greedy rule to allocate processors. The classic Heterogeneous Earliest Finish Time (HEFT) [Topcuoglu et al. 2002] algorithm is adopted as the advantage baseline for Pegasus benchmark in our experiments when estimating the dense reward. TPC-H represents the DAG workflow scheduling task under homogeneous resource environment. We use the TPC-H benchmark generated by [aag et al. [2021] in the experiments, Shortest First Time (SFT) is adopted as the heuristic baseline for TPC-H. JSSP is a special case of DAG scheduling under multi-machine settings. Shortest Processing Time (SPT) is adopted as the heuristic baseline for ISSP. Check Appendix [ for more details about thees benchmarks. Evaluation metrics include the optimization objective, gap to heuristic baseline, and run time of the algorithm.
setting [Dellman et al.) 2015). We use
Baselines. Our approach is compared against the following baselines: (1) The heuristic algorithms used as advantage baselines in our method; (2) Jeon al. [2023], state-of-the-art RL-based one-shot DAG scheduling method; (3) EGS [Sun et al.) [0024] a DAG scheduling approach based on edge generation; (4) POMO-DAG, our adapted implementation of the POMO (Kwon et al., 2020 for DAG scheduling, serving as a incremental solution construction method. See Appendix C for more details about these baselines. Additionally, we conduct ablation studies assess the contribution of each proposed component in section 4, including: (5) Ours without CAI, our method without conducting comparable antichain identification (CAI); (6) Ours without DR, our method without estimating gradient with dense reward (DR), but sparse reward. The results are presented in Tab. and More results on other workflows in the Pegasus benchmark is presented Appendix
Ablation studies. From the perspective of scheduling performance in optimization objective, observe that removing the comparable antichain identification module generally results a larger degradation compared to removing the dense reward module. This suggests that redundant pairwise node priority comparisons are more detrimental to solution quality, while the dense reward acts more like a "fine-tuning". Note that the results of our full method on the TPC-H in Tab. 2 do not always outperform either the variant without comparable antichain identification or Jeon et al. 2023) s one-shot approach. A possible explanation is that the DAGs in each problem of TPC-H less interconnected. In this situation, the network may have difficulty learning the node priorities across the DAG, and since CAI has masked out many nom-comparable nodes, this further increases the difficulty of learning in such cases. In terms of runtime, incorporating comparable antichain identification, which is based on the priority topological sorting process, slightly increases the overall run time. This is because priority topological sorting introduces additional computation with a time complexity of (nlog n + El), which higher than ranking via argsort operation (O(nlog n)). Furthermore, priority topological sorting involves loops that, unlike argsort, cannot be parallelized using GPU-accelerated libraries. Nevertheless, the additional runtime overhead remains within an acceptable range. In summary, both comparable antichain identification and dense reward make contributions to the overall performance, with comparable antichain identification playing a more critical role.
small and
8

---

Table 1: Experimental results on SIPHT dataset in Pegasus, with different problem instance sizes (100, 200, 300, 400, and 1000 task nodes). The evaluation metrics include the optimization objective (Makespan), the gap relative to the heuristic baseline (HEFT), and the run time.
SIPHT-100
SIPHT-200
SIPHT-300
SIPHT-400
SIPHT-1000
Method
MS
Gap/%
Timel]
MS
Gap%
Time's
MS
Gap/%
Timel
MS
Gap/%
Time's]
MS
Gap/%
Time's
HEFT (huseline)
|27.00
0.005
357.8
0.018
543.0
0.024
714.8
0.044
1821.4
0.196
Jeon et
2023
218.5
-3.74
0.07
-1.57
0.15
550.6
1.40
0.26
712.7
-0.29
0.43
1898.1
2.44
POMO-DAG
214.0
-5.74
13,4
367.5
2.72
20.8
575.8
6,05
27.5
741.9
3,80
34,3
1875,1
2.95
50.6
BGS
200.6
-11.63
1.02
346.3
-3.21
2.35
542.8
-0.04
4.04
710.2
-0.64
10.2
1821.0
-0.02
64.5
Ours
196.9
-13.3
0.61
338.4
-5.42
0.97
541.6
-0.25
1.17
708.3
-0.91
1.22
1819.2
-0.13
2.59
DR
213.2
-6.07
0.67
542.2
-0.14
710,3
1.88
1818.9
40.13
2.83
Ours w/o CAT
214.4
-5.55
0.11
345.8
-3.07
0.21
542.5
-0.09
0.34
710.4
-0.62
0.46
1867.7
2.54
2.22
Table 2: Experimental results on TPC-H benchmark, with 3 different problem instance sizes (50, 100
and 150 sub-DAGs). The evaluation metrics include the optimization objective makespan (MS), the gap relative the heuristic baseline (STF), and the run time.
TPC-H
TPC-H 100
TPC-H 150
Method
MS
Gap/%
Timels
MS
Gap/%
Timels
MS
Gap/%
Timo's
STF (baseline)
24.97
0,010
42,85
0.027
69.76
0.038
Jcon al.
2023
23.73
-4.95
0.23
41.22
-3.81
0.44
74.02
6.11
0.76
POMO-DAG
46.90
87.8
24.3
90.30
110.74
27.4
141.90
103.43
33.2
24.58
10.8
42.18
68.99
-1.10
Ours
20.49
-17.73
0.51
39.22
-8.47
0.82
73.47
5.32
1.49
Ours w/o DR
24.10
-3.47
0.59
39.68
-7.40
0.86
70.14
0.54
1.19
Ours w/o CA1
22.47
-10.00
0.23
42.96
0.16
0.43
67.91
-2.65
0.78
Table 3: Experimental results on JSSP.
JSSP 20
JSSP 20*20
JSSP 30-10
JSSP 30"20
Method
MS
Gap/%
Timels
Gap/%
Time's
MS
Gap/%
Time's
MS
Gap!%
Time's
SPT (Baseline)
516.7
<0.001
1096.2
<0.001
845.9
<0.001
1692.0
<0.002
Joon al 2023
445.2
-13,84
0.12
964.0
-12.06
0.15
735.6
-13.04
0.24
1548.6
-8.48
0.15
POMO-DAG
341.6
-33,88
3,0
936.3
-14.59
5.3
971.3
-6.45
4.2
1458.0
-13.83
6.7
EGS
465.9
-9.83
1034.5
-5.63
3.5
837.5
-0.99
1604.1
-5.20
17.0
Ours
-23.11
-25.76
0.41
571.3
.15.72
0.45
Ours w/o DR
394.7
-23.61
0.36
928.6
-15.29
0.41
661.1
-21.85
0.32
1481.9
-12.42
0.44
Ours w/o CA1
436.8
-15.46
0.12
939.2
-14.32
0.16
718.2
-15.10
0.12
1505.3
-11.03
0.14
Comparison experiments. Our method achieves better performance than Jeon et al. 2023 in most cases. But it incurs slightly longer runtime, explained in the ablation study. When compared with POMO-DAG, our method consistently yields better results in most scenarios. In a few small- scale cases such JSSP-20-10 10 in Tab. 3, our method performs slightly worse. We attribute this to the simple disjunctive DAG structure of JSSP, where the advantage of comparability identification becomes less significant. Nonetheless, our approach demonstrates a substantial advantage in run time, because POMO is an incremental solution generation method that relies on repeatedly re-encode the entire instance across multiple sampling rounds, making more computation consuming. Compared to EGS, our method achieves similar or even better solution quality. EGS leverages a heuristic algorithm to solve subgraphs induced by edge generation, which provides a strong upper bound in optimization. However, EGS cannot guarantee superior performance, because the search space is significantly large, making it prone to local optima. Furthermore, EGS exhibits longer runtime due to its iterative edge resampling and repeated graph encoding. In summary, our method demonstrates consistent advantages over existing approaches in both solution quality and runtime efficiency across various DAG scheduling tasks.

---

7 Conclusion
In this paper, we present novel one-shot solution generation method for DAG scheduling based on the policy gradient algorithm. We propose to identify the comparable antichain for each node during the topological sorting process, eliminating redundant comparisons and sampling computations, enabling more accurate gradient estimation. Furthermore, we design dense reward that significantly improves training efficiency by mitigating the reward sparsity problem commonly observed in dearning-basee DAG scheduling. Experimental results across diverse scenarios demonstrate that our method achieves superior scheduling quality compared existing DAG scheduling approaches. This suggest that our method have potential for further extension and optimization in large-scale or dynamic environments, like scientific workflow management. As future work, we will expand this foundational study to more specific applications by considering domain knowledge and optimization objectives.
Limitations. Although the experiment results present effectiveness of our method across various DAG scheduling tasks, the proposed comparable antichain identification approach is primarily designed to handle precedence constraints. Since our study is continuation of prior foundational researches, we primarily focus on optimizing makespan objective. Extending our study to specific application by considering domain-specine objectives would be promising direction. Moreover, for the scheduling problems involving domain-specific constraints, such as the deadline constraints in real-time systems, adaptations would be necessary. Additionally, our approach remains within the list scheduling paradigm. Exploring sequence-agnostic alternatives, such as one-shot edge generation for node prioritization, may be promising direction.
Acknowledgments and Disclosure of Funding
This research is supported in part by the project of National Natural Science Foundation of China (No. 52478030), the project of Shanghai Municipal Commission of Economy and Informatization (No. k20023020251762). and the project of the Fundamental Research Funds for the Central Universities (No. 22120250610).
References
Genxin Chen, Jin Qi, Ying Sun, Xiaoxuan Hu, Zhenjiang Dong, and Yanfei Sun. A collahorative scheduling method for cloud computing hcterogeneous workflows based on deep reinforcement learning. Future Generation Computer Systems, 141:284-29) 2023. ISSN 0167-739X. doi: 10.1016/j future. 202...1.022.... future URL http:///wwwwsceeeeereeeecccc com/ wwwp///i/////aeo/cccccceeeee/eaa http:///aaaaaaaaaaaaaaaaa///////
Jinho Choo, Ycong-Dac Kwon, Jihoon Kim, Jeongwoo Jac, André Hottung, Kevin Tiemney and Youngjune Gwon. Simulation seuuulationguudedd beam search for neural combinatorial optimization. In S. Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho. and A. Oh, editors,Advaneeee Advances in Neural Information Processing Systems, volume 35, pages 8760-877 8772. Curran Associates, Inc.. 2022. URL http:///pceeeeen..ecee www.eediiiinnnnnnpss..eee. neurips cc/ Paper Conference, .df sateerffleeepppppee httpp//////////e/e////eeeee httpee///bbbbbbbeeee/// ffw.a444ffaaefffee//////aaa /tt.://///9000000000oo0oaaaaaa11
Victor-Alexandru Darvariu, Stephen Hailes, and Mirco Musolesi. Graph ceaatoo for combinatorial optimization: survey and unifying perspective. arXiv preprint arXiv:2404.06499 2024. URL https:
//arxivv.o org/ aaaaaaaeeaaa 2404. 06492
Fwa Deelman, Karan Vahi, Gideon Juve, Mats Rynge, Scott Callaghan, Philip J. Maechling, Rajiv Mayani, Weiwei Chen, Rafael Ferreira da Silva, Miron Livny, and Kent Wenger. Pegasus, a workflow management system for science automation. Future Generation Computer Systems, 46:17-35 2015. ISSN 0167-739X. doi: https://doi 101 101.0/..............ooooeeeeeee. f0w.. htw.p///........pp//////....e.ee asticle/pi//S01s77391100000
URI htttpp://ww.scceaeeeeieeeee wttppett..ooo/ccccccceeccc
Hamza Djigal, Jun Feng, Jiamin Lu, and Jidong Ge. Ippts: An efficient algorithm for scientific workflow scheduling in heterogeneous computing systems. IEEE Transactions on Parallel and Distributed Systems, 32
(5):1057-1071, 2021. doi: 10. 10.1109/TPDS 202........0.0.....
Tingting Dong. Fei Xue, Hengliang Tang, and Chuangbai Xiao. Deep reinforcement learning for toul--tolerant workflow scheduling in cloud environment. Applied Intelligence, 53(9):9916 9932,999222222 2023. ISSN 0924- 669X. doi: 10. 1007/ 022-999022-00-3--- S10489- 022-
03963-w. w. URL | /tstps://linkk http:///innn.ssinorrr...e com/ wwwm///rtccee/.../ 1007
10

---

Mukul Gagrani, Corrado Rainone. Yang Yang, Harris Teague, Wonseok Jeon, Roberto Bondesan, Herke Hoof, Christopher Lott, Weiliang Zeng. and Piero Zappi. Neural topological ordering for com-- putation graphs. In Koyejo. S. Mohamed, A. Agarwal, D. Belgrave, K. Cho. and Oh, edi- tors, Advances in Neural Information Processing Systems, volume 35, pages 17327 17339. Curran As- sociates, Inc., 2022. URL https: http::://proceedinggs neur httppcccppppe_eiiiee wttp:e/iillls/pppe//a/a/ file/// 0at.bbbaf.0110000061100303666333
Paper- Conference... pdf
André Hottung, Ycong-Dae Kwon, and Kevin Tierney Efficient active scarch for combinatorial optimization problems. In The Tenth International Conference on Learning Representations, 2022.
Shengyi Huang and Santiago Ontañón. A closer look at invalid action masking in policy gradient algorithms. arXiv preprint arXiv:2006, 2020..
Wonseok Jeon, Mukul Gagrani, Burak Bartan, Weiliang Will Zeng, Harris Teague, Piero Zappi, and Christopher Lott. Neural dag scheduling via one-shot priority sampling. In The Eleventh International Conference on Learning Representations, 2023.
AHG Rinnooy Kan. Machine scheduling problems: classification, complexity and computations. Springer Science& & Business Media, 2012.
Wouter Kool, Herke Van Hoof, and Max Welling, Stochastic beams and where to find them: The Gumbel-top -oo-kk trick for sampling sequences without replacement. In Kamalika Chaudhuri and Ruslan Salakhutdinov. editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 3499-3508. PMIR, 09-15 Jun 2019. URL htt.tta://pooceeeiiinieeoo mlr ppres//
v97 v97/kool13t www.oo.......................... html html
Yeong- Dae Kwon, Jinho Choo, Byoungiip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21188-21198. Curran Associates. Inc., 2020. URL httpps ptstts://prrceett http://rccoooon..uurr...ee.ee/ep wwtpripp...pppppe.e...... ffles/ htt.://///...0.....2220000000...
Paw.peaa pdf
Hyunsung Lee, Jinkyu Lee, Ikjun Yeom, and Honguk Woo. Panda: Reinforcement learning- priority assignment for nulti-processor real-time scheduling. IEEE Access, 8:185570-185583, 2020. doi: 10.1 109/ ACCESS.2000 200ISSS.222..3000 2020.3029040.
Hyunsung Lee, Sangwoo Cho, Yeongjae Jang, Jinkyu Lee, and Honguk Woo. A global dag task scheduler using deep reinforcement learning and graph convolution network. IEEE Access, 9:158548-158561, 2021, doi: 10. 10.1109/ACCESS.o 2021 1021..3 3130477.
Yuankai Luo, Veronika Thost, and Lei Shi. Transformers over directed acyclic graphs. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Ad- vances in Neural Information Processing Systems, volume 36, pages 47764-47782 Curran Asso- ciates, Inc., 2023. URL httpp::/ httpp://proceedingg. www.:nnww.....ceeoo cc/paper.fflee/pappeeeeepeeeeeep wwwpss/ppppe//223///// Conferencec.eecc.ec.o pdf
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 on Data Communication, SIGCOMM '19, page 270-288, New York, NY, USA, 2019. Association for doi: 10. 00.1145/3341300.332220 URL https: acm
Computing Machinery. ISBN 9781450359 doi/ abs/ 1145//3411330 33013333333322333 3342080
org/doi/abs/100
Alexander Nasuta, Marco Kemmerling, Daniel Lütticke, and Robert H Schmitt. Reward shaping for job shop scheduling. In International Conference on Machine Learning, Optimization, and Data Science, pages 197-211. Springer, 2024. ISBN 978-3-031--5366955
Xumai Qi, Dongdong Zhang, Taotao Liu, and Hongeheng Wang. Deep reinforcement learning for large-scale scientific workflow scheduling with improved structure feature extraction and sampling. In IFIP International Conference on Network and Parallel Computing, pages 310-323. Springer, 2024.
Yutao Song, Chen Li, Lihua Tian, and Hui Song. reinforcement learning based job scheduling algorithm heterogeneous computing environment. Computers and Electrical Engineering, 107:108653, 2023. ISSN 0045-7906. doi: 10. cot.0//o...oopeeeeneg.0000000 108653, URL htllhhtps://// http:://wwww..cieeeeeeeeeee com/ science/ http:///aaaaaeeaaaa/////////////
2023.00.
Binqi Sun, Mirco Theile, Ziyuan Qin, Daniele Bernardini, Debayan Roy, Andrea Bastoni, and Marco Caccamo. Edge generation scheduling for dag tasks using deep reinforcement learning. IEEE Transactions on Computers. 73(4):0034 1047, 2024. doi: 10. 10.1109922222223355244...

---

Veronika Thost and Jie Chen. Directed acyclic graph neural networks. In The Ninth International Conference on Learning Representations, 2021.
H. Topcuoglu, S. Hariri, and Yon Wu. Performance-effectiee and low-complexity task scheduling for heterogeneous computing. IEEE Transactions Parallel and Distributed Systems, 13(3):260-22 274, 2002. doi: 10.1109/71.993226.
Runzhong Wang. Zhigang Hua, Gan Liu, Jiayi Zhang, Junchi Yan, Feng Qi, Shuang Yang. Jun Zhou, and Xiaokang Yang. bi-level framework for learning solve combinatorial optimization on graphs. 34:21453 21466, 2021. URL htt httpttttppppppp//oeeeeeeoooe
Xiaohan Wang. Yuanjun Laili, Lin Zhang, and Yongkui Liu. Hybrid task scheduling in cloud manufacturing with sparse-reward deep reinforcement learning. /EEE Transactions on Automation Science and Engineering, 22: 02167711119944444465444440022212 httpp//ocoaaaaaooorcoooooooooooa
neurips. cwwr.ps.cc/pppprrrreeoo http///appppetteeeeee///////////
Paper pdf
2025, doi: 10. (10//AAEE.224.3371225
Zhe Yang. Phuong Nguyen, Haiming Jin, and Klara Nahrstedt. Miras: Model-based reinforcement learning for microservice resource allocation over scientific workflows. In 2019 JEFE 39th International Conference on Distributed Computing Systems (ICDCS), pages 122-132, 2019. doi: 10.1 90.109//CDCSS.211...M 9.0021...
Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tic- Yan Liu. transformers really perform badly for graph representation? M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Procexsing Systems, volume 34, pages 28877-28888. Curran Associates, Inc., 2021. TRR.https:: hattps://prooeedings neuripa. ht.pa.cc/pppp ca/paper. Paper .df
Xiaoming Yu, Wenjun Wu, and Yangzhou Wang. Integrating cognition cost with reliability qos for dynamic workflow scheduling using reinforcement learning. IEEE Transactions on Services Computing, 16(4):
2713-2726, 2023. doi: 10. 109//TSC.022333533138
Yue Yu, Jie Chen, Tian Gao, and Mo Yu. DAG-GNN: DAG structure lcarning with graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedingy of the 36th International Conference on Machine Learning, volume 97 Proceedings of Muchine Learning Research, pages 7154-7163. PMLR. 09-15 Jun 2019. URL http:::tttttsseeeeeeeee
mlr, Sieess/99/yy193 html
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 H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1621-1632. Curran Associates. Inc., 2020. URL https: h http://eeccceess..////////
11958dfee29bol 0222299677994888 097777999889903888 22433 hwwpiiiinnnnuurrs.s.comom www.:eur.....pppppee htt.:/pp.cc/appprr..aa////ppp//p
pdf
Cong Zhang, Yaoxin Wu, Yining Ma, Wen Song. Zhang Le, Zhiguang Cao, and Jie Zhang, review on learning to solve combinatorial optimisation problems in manufacturing. IET Collaborative Intelligent Manufacturing 5(1):e12072) 2023.
Cong Zhang, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jing Sun. Learning topological representations with bidirectional graph attention network for solving job shop scheduling problem. In Negar Kiyavash and Joris M. Mooij, editors, Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence, volume 244 of Proceedings of Machine Learning Research, pages 4192-4208. PMLR, 15-19 Jul 2024. URL httpp:://proceeding: mlr. prw.s/eeaaaaaa. v244/ 220444/2hag224... .html
Yunfan Zhou, Xijun Li, Jinhong Luo, Mingxuan Yuan, Jia Zeng, and Jianguo Yao. Learning to optimize dag scheduling in heterogeneous environment. In 2022 23rd IEEE International Conference on Mobile Data Management (MDM), pages 137-146, 2022. doi: 10.1 109/DD55031 20022.00040.
12

---

A Illustration of our method
Our proposed framework is illustrated in Figure 3a comprising two key components: comparable antichain identification (top-right) and dense reward estimation (bottom-left). The comparable antichain identification module constructs a complete global solution in the form of a node execution order, and estimates the sampling probability for each node. This solution is then simulated and evaluated to obtain nodewise cost values. By subtracting these with the cost values from a heuristic baseline solution and conducting normalization operation, obtain nodewise reward signals. Figure 3b further provides a detailed illustration the comparable antichain identification and sampling probability estimation process. At each step of the priority topological sorting, the of zero in- degree nodes in the current subgraph is identified as comparable antichain. Within this antichain, the node with the highest perturbed logits is selected for scheduling. The original logits are then passed through a softmax operation to compute sampling probabilities. This process continues iteratively to construct the full execution order along with the sampling probabilities for all nodes.
Note that the entire procedure requires only a single forward pass of the reinforcement learning network the DAG scheduling problem instance, from which all logits are obtained in shot.
Priority list (logits)
The DAG scheduling problem
Encoder layer (GNN)
Policy Network (MLP)
Comparable antichain Identification and sampling probability estimation
Simulation and evaluation
Heuristic baseline
Global solution Solution 0)
Nodewise baseline Cn
Nodewise C
C
Cp.
Nodewise sampling probabilities
Normalization
Nodewise dense rewards
Policy gradient
(a) Illustration the overall framework.
The (t- 1-th in priority topological sorting
The 0-in-degroe set identified as comporable antichain of #zp(c-1)
The E-th step in priority topological sorting
The 0 in-deee set identified comparable antichain of Pxy())
organex priotity (gunbel-perturbed kogits)
argmax priority logits)
on logits
softmax: logits
P(P P(9nse-n[Sotution., SSolution.
(Ty((-1)
((Pra(t)) (G:
(b) Illustration of comparable antichain identification and sampling probability estimation.
Figure 3: Illustration of the proposed method.
13

---

B
More information about the benchmarks
B.1
Pegasus
Pegasus (Deelman et al. 2015 provides an open-source workflow trace data generated from various scientific computing applications. We adopt it the benchmark for DAG workflow scheduling under the heterogeneous multiprocessor setting. Under such setting, the attributes of task node is include the computational workload c; and the output data size b; For each processor m, the key attribute is its computational capacity fm. Assuming that task node o; is assigned to processor m, the processing time d, (as described in section 2) can be calculated as Equation (IT).
C2
d:
(11)
fm
Besides, Pegasus benchmark requires to consider the transmission time z; between processors: a task node cannot begin execution until all of its predecessor nodes have completed both their computation, and the transmission of their output data to the processor on which it is scheduled. Specifically, if a task node 2 and its successor by are assigned to different processors, then a transmission time is related to the output data size of u; and the bandwidth of computing environment. If both ey and dj are assigned to the same processor, the transmission time is considered negligible. This definition of 2; is formalized in Equation
by bandwidili
if U2 and 2y are on different processors
(12)
if U2 and My are on the same processor
Our proposed method outputs only the execution order of the nodes, while the assignment of each node to a processor is determined using the Earliest Finish Time (EFT)-greddy rulc. Specifically, for given node be scheduled, which is determined by the RL network, the EFT-greedy rule dispatches it to the processor that results in the earliest possible finish time. We adopt HEFT (Topcuoglu et al. 2002] as the advantage baseline for scheduling workflows in the Pegasus benchmark, as a part of the dense reward estimation. HEFT is a classic list-based heuristic algorithm for DAG scheduling on heterogeneous processors. computes the priority (rank-up) of each node based on the average finish time of its successor nodes, and then assigns each node to processor using the EFT-greedy rule.
B.2 TPC-H
We adopt TPC-H as the benchmark for DAG workflow scheduling under the homogeneous single- processor setting. There is no need to dispatch tasks to specific processors in such setting. Each task node v; has a fixed processing time d, and computation resource requirement q. The total resource consumption of concurrently running tasks must not exceed the system's 's maximum resource capacity, We use the open source code P immpleeented by Wang et al. [2021) to generate TPC-H instances. Shortest Time First (STF) heuristic is adopted as the advantage baseline for TPC-H in our research. At each decision point, the STF rule selects the task with the shortest processing time.
B.3 JSSP
The JSSP is a typical COP where each job consists of a sequence of operations. The operations within a job must follow predefined order, forming precedence constraints, which can be modeled into DAG. Different from the above-mentioned problem setting, each operation in JSSP must be processed on specific machine for a specified duration. The scheduler needs determine the execution order of operations that require the same machine but belong to different jobs. Consequently, JSSP is a special case of DAG scheduling problem. JSSP is often used as standardized benchmark scenario for evaluating the performance of DAG scheduling methods. serving to validate their effectiveness on structurally constrained tasks. We use the code by Zhang et al. 2020
generate JSSP instances.
Similar with other DAG scheduling tasks, list scheduling can be applied to JSSP. By assigning each operation priority value (or priority rank), the execution order of operations that require the same
14

---

machine can be determined. That is. if multiple operations compete for the same machine, the one with higher priority selected be executed first.
Shortest Processing Time (SPT) heuristic is adopted as the advantage baseline for JSSP. At each decision point, the SPT rule selects the operation with the shortest processing duration, and it would start on its designated machine at the earliest feasible time.
C Implementation details
C.1 Input of network
DAG scheduling problem instance consists of a DAG G E) and a set node attributes. These attributes typically include processing time d,, resource machine requirements, in-degree and out-degree, among others. Specifically, for DAG workflow scheduling under heterogeneous multiprocessors environments(as in the Pegasus benchmark), additional attributes include the required computation workload c, output data size b; of each node, and the computational capacity of each processor. For each task node Vi, pack and normalize all these attributes into vector 25 the raw feature of U; which is then fed into the GNN encoder.
C.2 Neural network and hyper parameter settings
We used Graphormer| Ying et al. 2021 with 4 layers and 4 attention heads. It outputs 64-dimension node embeddings for each task nodes. The policy network is 64*64* MLP with ReLU activation function. We train each benchmark for at most 1000 epochs, and the batch size is 16. The logits regularization rate is 0.001. The Adam optimizer is employed with learning rate 5 x 10-4
C.3 Perturbed logits
We follow Jeon al. [2023] to introduce Gumbel trick (Kool et al. 2019) when sampling the node execution order. Instead treating the original logits output by the policy network as the priority values of the task nodes, the argmax sampling operation is performed over the comparable antichain Vii=D on perturbed logits (formulated in Equation (3)). which follows on Gumbel distribution (formulated in Equation (14).. Therefore, the sampling becomes more aligned with the underlying probability distribution formulated in Equation (6).
perturbed (o = logits(r;) + ((:)
(13)
7(v) = log(( llo p), Uniform(0, 1)
(14)
C.4 Simulation and evaluation environment
To evaluate the generated scheduling solutions and obtain both the overall optimization objective and node-level dense rewards, we implemented a DAG workflow simulation environment based on the open-source SimPy F platform based on Python language. This simulator is further wrapped into an OpenAl Gyn environment to integrate with reinforcement learning frameworks. capable to simulate all three aforementioned benchmarks, and can be extended to support other scheduling scenarios if necessary.
D Dense reward signal calculation procedure
Our dense reward is constructed by simulating the entire one-shot generated schedule, and evaluating the global cost (e.g., makespan). Then, compute node-level reward for each scheduled node, based on its distance to the final cost. Specifically:
httpe://simg.rrrathhebooss
httt::://gituub..com/opeepet
15

---

1. Given DAG scheduling problem G, we conduct the heuristic advantage baseline algorithm on G, obtaining each task node's individual baseline cost C₂2 (v:).
2. For a sampled solution Solution 0) (i.e., an execution order), we simulate it using SimPy- based simulator. and obtain the overall makespan ((Solution(G; in practice. For each task node (x(+), we obtain its individual cost (G; 0) (e.g., its finish time) through simulation.
3. We obtain the return-like dense reward signal Rg of each task node Ur(() by comparing the global objective C(Solution( (G; 0)) with individual cost C(S,(G; 0)), according to Equation (8)
4. To derive the advantage-like feedback A,, further substract each baseline from R2 according
to Equation
E Baseline algorithms
Jeon et al. [2023]. Although the original authors did not fully release their source code, the idea described in their paper is sufficiently clear and straightforward to reproduce. So we implemented their approach accordingly.
POMO-DAG. We build POMO-DAG upon the POMO R proposed by Kwon al. 2220), adapting its problem instance encoder to Graphormer-based GNN (ing et al. 2021] so that can process DAG scheduling problems. The model generates a ranked list of nodes as the scheduling solution.
EGS. For EGS [Sun et al. 2024). the basic framework of the original code is publicly available We retained the original structure and implemented the missing policy network and training procedure that were not released.
Additional results on Pegasus benchmark
Due to page limits, additional experimental results on the Pegasus benchmark presented here in the appendix, specifically for the LIGO and GENOME datasets (see Table{]and Table(5) respectively). Similar the results SIPHT presented in section of each dataset (100, 200, 300, 400, and 1000 task nodes). The evaluation metrics include the optimization objective (makespan, MS in short), the gap relative to the heuristic baseline (HEFT), and the run time.
selected 5 different problem instances
In the LIGO-1000 case, neither our method the neural baselines outperformed the heuristic algorithm. We attribute this to the fact that the result (2373.5) obtained by the heuristic method is already close the lower bound of the optimization objective, leaving little room for improvement.
G The impact of heuristic advantage baseline selection
Considering that the selection of heuristic algorithm for advantage baseline might influence the effec- tiveness of dense reward signal, we conducted experiments comparing multiple heuristic advantage baselines, including the previously used HEFT, and Critical Path on Processor (CPOP), Shortest Finish Time (SFT). The results of the gap related HEFT in percentage shown in the following Table 6 as a complement to Table T The results show that our method with different advantage baseline still outperforms existing methods, and the performance of our method with different heuris- tie advantage baseline is comparable. We believe this is because the heuristic algorithm provide constant estimates for each DAG scheduling problem instance, ensuring the advantage estimation is unbiased. Additionally, these heuristics are near-optimal in many cases, leading to similar schedules. As result, the variance reduction benefit is preserved, while introducing little bias.
htapp:://gittuub.com//---laae https://github.com sun/egs
16

---

Table 4: Experimental results on LIGO dataset in Pegasus.
Method
LIGO-100
LIGO-200
LJGO-300
LIGO-400
LIGO-1000
MS
Gapfi
Timel]
MS
Gupe'
Time's
MS
Gap/%
Timel]
MS
Cap/s:
Timels]
MS
Gap/S:
Timees
HEPT (huseline)
2217.5
0.005
462.9
0.014
670.3
0.026
959.3
0.043
2373.5
0.221
et
217.0
670.8
0.26
962.8
0.36
2376.7
2.39
POMO
216.7
-0.37
11.43
473.8
2.35
17.50
675.3
0.75
23.04
969.1
1.02
28.48
2382.0
0.36
50.56
BGS
214.2
-1.52
0.98
462.5
-0.09
3.07
669.9
-0.06
5.34
956.9
-0.25
8.75
2373.5
55.14
Ours
214.0
-1.61
0.62
462.1
-0.17
0.99
668.8
-0.22
1.20
956.6
-0.28
1.26
2373.5
2.59
214.0
-1.56
2375.5
Ours w/o CAT
215.9
0.94
0.10
462.7
0.04
0.25
672.1
0.13
0.32
960.4
0.11
0.48
2377.6
0.17
2.12
Table 5: Experimental results on GENOME dataset in Pegasus.
GENOME-100
GENOME-200
GENOME-300
GENOME-400
GENOME-1000
Melhod
MS
Gap/%
Timess|
MS
Gapt%
Time's]
MS
Gap!%
Timels
MS
Gap*
Timels]
MS
Gapt%
Timels
HEFT (baseline)
2553.1
0.005
|297344
0.013
(47519
0.028
345332
0.043
15016.88
0.239
Jcon ot al
2023
25114
-1.63
0.08
2369.9
-0.15
0.15
4755.3 3
0.07
0.27
3483.2
0.87
0.46
15001.9
-0.10
2.58
PUMO-DAG
2472.0
40.26
4783.2
22.83
2.16
50.55
BGS
2475.6
-3.04
0.94
2356.2
-0.72
4.05
4730.0
-0.46
6.43
3453.0
-0.01
9.08
14970.4
-0.31
71.90
Ours
2468.2
-3.32
0.61
2350.5
-0.96
1.00
4728.4
40.49
1.20
3453.
-0.01
1.29
14955.8
-0.41
2.79
Ours w/o DR
2507.6
-1.78
0.36
2350.5
-0.96
0.70
4744.1
-0.16
1.45
3453.2
0
1.93
14978.3
-0.26
2.96
Ours CAl
0.11
0.34
3453.2
14984.2
2.37
Table Experimental results on relative gap about the selection of heuristic advantage baseline.
Heuristic Method
SIPHT-100
SIPHT-200
SIPHT-300
SIPHT-400
ours HEFT
-13.3
-5.42
-0.25
-0.62
CPOP
-12.2
-5.42
-0.20
-0.62
SFT
-12.8
.4.83
-0.22
-0.62
H
Convergence guarantee analysis
Since the optimization of our approach is based on policy gradient, it inherits the theoretical conver- gence properties of the classical policy gradient framework. Although the convergence performance actual usage might be as perfectly good that of the classic policy gradient under ideal conditions, several designs in our method could enhance the stability and convergence behavior in practice:
1. Nodewise dense rewards signal provides a closer approximation of value/advantage estimation each decision step.
2. The CAI module improves the quality of nodewise decision probability estimation, obtaining more accurate gradients and hence improved convergence behavior.
3. For given DAG scheduling instance, the results generated by the heuristic advantage baseline algorithm is fixed across training epochs. This ensures that the advantage estimation is unbiased.
While these designs do not provide formal theoretical bounds, they provide empirical support for training stability and convergence, as reflected in the performance across diverse testbenches.
I Interpretability analysis
Darvariu al. 2024 pointed out that one-shot RL methods for combinatorial optimization problems tend to be less interpretable than incremental solution construction approaches, as they do not strictly follow the Markov decision process and do not satisfy the Bellman equation value evaluation. However, by introducing the dense reward signal, our method improves the interpretability of one-shot approaches to some extent. Specifically, the nodewise decisions, sampling probabilities and dense reward signals can be regarded as entire MDP sampling trajectory in RL (like trajectory by
17

---

Monte Carlo sampling). This makes the interpretability of one-shot learning closer to MDP-based incremental approaches than those one-shot methods with sparse rewards.
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The contributions of the paper can be found in sections 1, 3 and 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of the proposed method Appendix G.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
19

---

Justification:
The theoretical proofs are provided in section 4 "proposed method".
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the experiment details in section 6 and the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
20

---

Answer: [Yes]
Justification:
We provide the code and how to use it in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
wowoooooooyylllooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//guiii wwwiicccguie///eeeeeeeeis CoodeSubeiiieeee ssi wswinnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We describe the experimental settings and details in section and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We report the experimental results in the tables in section 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
21

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the compute resources in section 6. More details in appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:p////ourrr...cccpaaa///aaaa
Answer: [Yes]
Justification:
We have read and followed the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Potential positive impacts include improved efficiency in computing systems, discussed in section 1 and 7. No known negative socictal impacts are anticipated this stage.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
22

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
No high-risk dataset, code or model is used in this paper.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Original papers and codes are cited in this paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
23

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This paper used LLM only for editing and formatting purpose.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur/e 220p:////....ccoeeeeeee///22///0 for what should or should not be described.
25


Reviews:
[{"review_id": "w8cUtZtDIJ", "reviewer": "Reviewer_ebqq", "summary": "The paper introduces a new one-shot method for solving the Directed Acyclic Graph (DAG) scheduling problem using reinforcement learning (RL). The paper identifies two primary weaknesses in existing one-shot scheduling approaches: the redundant priority comparisons among nodes, which leads to biased estimates of sampling probabilities, and sparse reward signals, which provide inefficient guidance for the learning agent.\n\nThe paper introduces Comparable Antichain Identification (CAI) mechanism, which eliminates unnecessary comparisons by only considering nodes whose relative priority actually impacts the final execution order.\n\nThe paper further presents a dense reward signal for RL with node-level feedback during training. using Policy Gradient for training the GNN encoder.\n\nThe model is benchmarked using three existing datasets (Pegasus, TPC-H, and JSSP) and compared against heuristic and learning based models. The experimental results show that the proposed method generally outperforms other learning-based approaches in terms of solution quality and is more computationally efficient than incremental methods.", "questions": "- What are the disadvantages of relying on Q-Learning for the generation of a dense reward? Could a simple feedback per scheduled task performacne be used to make the reward dense for each scheduling step?\n- How sensitive is the method’s performance to the choice of the heuristic used for advantage baseline estimation?\n- Are there theoretical guarantees (e.g., bounds) on performance improvements or convergence properties?", "limitations": "- The method assumes access to a decent heuristic for baseline reward estimation.\n- CAI's benefit is less pronounced on shallow or disjoint DAGs.\n- Despite improved training efficiency, the GNN-based architecture and sorting overhead may still limit real-time or very large-scale applications.\n- The method does not directly model dynamic environments or online scheduling, restricting its scope to static DAG instances.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- Carefully analyzes limitations in prior work and supports its approach with formal definitions, lemmas, and justification.\n- Empirical Results include Ablation study to show the impact of each component of the proposed method.\n- The experiments are done on a broad range of problems.\n\nWeaknesses\n- The method underperforms or matches baselines on simpler DAG structures (e.g., TPC-H). While mentioned, this is not deeply analyzed.\n- Like most one-shot methods, it sacrifices interpretability compared to MDP-based incremental approaches.\n- Dense reward requires a strong heuristic baseline to be effective, which could limit portability across problem domains without such heuristics.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful evaluation of our manuscript and the valuable feedback. We are glad that the strengths of our paper were recognized. In this rebuttal, we respond to your concerns and clarify several aspects of our work.\n\n#### Weakness 1:\n>The method underperforms or matches baselines on simpler DAG structures (e.g., TPC-H). While mentioned, this is not deeply analyzed.\n\nWe analyze this issue as follows: \nOur proposed CAI intends to remove the redundant priority comparison among DAG nodes that has dependency relationship, thus obtaining more accurate sampling probability. So, CAI is particularly useful in DAGs with more complex dependency structures, in which multiple nodes often lie along a longer path. For simpler DAG structures (e.g., TPC-H benchmark), they typically consist of many small-size DAGs with much shorter paths. In this situation, the number of dependent nodes located on the same path is small, and the existing dependencies are weak. The redundant comparisons among dependent nodes are significantly reduced, so the further improvement from applying CAI is limited. We thank the reviewer for pointing out this to improve our analysis about the experiment.\n\n\n#### Weakness 2:\n>Like most one-shot methods, it sacrifices interpretability compared to MDP-based incremental approaches.\n\nMost one-shot DAG scheduling methods are generally less interpretable than MDP-based incremental approaches. This is because there is no intermediate feedback to help these methods establish the connection between each decision step and the final outcome. However, by introducing the dense reward signal, our method improves the interpretability of one-shot approaches to some extent. Specifically, the nodewise decisions, sampling probabilities and dense reward signals can be regarded as an entire MDP sampling trajectory in RL (like a trajectory by Monte Carlo sampling). This makes the interpretability of one-shot learning closer to MDP-based incremental approaches than those one-shot methods with sparse rewards. \n\n#### Weakness 3:\n>Dense reward requires a strong heuristic baseline to be effective, which could limit portability across problem domains without such heuristics.\n\nWe conducted experiments comparing multiple heuristic advantage baselines, including the previously used HEFT, and Critical Path on a Processor (CPOP), Shortest Finish Time (SFT). The results of the gap related to HEFT in percentage is shown in the following table, as a complement to Table 1. The results show that our method with different advantage baseline still outperforms existing methods, and the performance of our method with different heuristic advantage baseline is comparable.\n|Method|SIPHT100|SIPHT200|SIPHT300|SIPHT400|\n|----| --| ----|----|---|\n|ours+HEFT|-13.3|-5.42|-0.25|-0.62|\n|ours+CPOP|-12.2|-5.42|-0.20|-0.62|\n|ours+SFT |-12.8|-4.83|-0.22|-0.62|\n\n\n#### Question 1:\n> What are the disadvantages of relying on Q-Learning for the generation of a dense reward? Could a simple feedback per scheduled task performance be used to make the reward dense for each scheduling step?\n\nWe’d like to clarify that our method is based on policy gradient, rather than Q-learning. This design is motivated by the nature of the RL-based one-shot scheduling, which relies on differentiable probabilistic modeling of nodewise scheduling decisions. Such probabilistic modeling can be achieved in policy gradient. However, standard Q-learning typically does not explicitly model the action probability.\n\nWe think the reviewer might suggest that we could fit a Q-function network to estimate per-node scheduling values (or rewards) to provide dense feedback signal. However, in practice, in each DAG scheduling problem instance, we only obtain a single global performance metric, making the per-node value fitting process inherently sparse. As a result, introducing such additional fitting is unlikely to be very effective.\n\nIn contrast, our designed dense reward signal reflects the accumulated impact of the scheduling trajectory from the beginning up to the current step. The reward approximates the overall performance of the current schedule. In this sense, our dense reward signal can make a close advantage function estimation over the current execution state of the DAG. So, fitting a Q-function network is unnecessary.\n\n\n#### Question 2:\n>How sensitive is the method’s performance to the choice of the heuristic used for advantage baseline estimation?\n\nAs we clarified in the response to Weakness 3, the performance our our method with different heuristic advantage baseline is comparable.\n\n#### Question 3:\n>Are there theoretical guarantees (e.g., bounds) on performance improvements or convergence properties?\n\nSince the optimization of our approach is based on policy gradient, it inherits the theoretical convergence properties of the classical policy gradient framework. Although the convergence performance in actual usage might be not as perfectly good as that of the classic policy gradient under ideal conditions, several designs in our method could enhance the stability and convergence behavior in practice:\n1. Nodewise dense rewards signal provides a closer approximation of value/advantage estimation at each decision step.\n2. The CAI module improves the quality of nodewise decision probability estimation, obtaining more accurate gradients and hence improved convergence behavior.\n3. For a given DAG scheduling instance, the results generated by the heuristic advantage baseline algorithm is fixed across training epochs. This ensures that the advantage estimation is unbiased.\nWhile these designs do not provide formal theoretical bounds, they provide empirical support for training stability and convergence, as reflected in the performance across diverse testbenches. \n\n\n#### Limitation 1\n>The method assumes access to a decent heuristic for baseline reward estimation.\n\nPlease check our Response to Weakness 3.\n\n#### Limitation 2\n>CAI's benefit is less pronounced on shallow or disjoint DAGs.\n\nPlease check our response to Weakness 1.\n\n#### Limitation 3\n>Despite improved training efficiency, the GNN-based architecture and sorting overhead may still limit real-time or very large-scale applications.\n\nWe would like to highlight that our method inherits the runtime advantages of one-shot scheduling compared to some other RL-based approaches, as demonstrated in the results. This is because one-shot scheduling avoids repeated encoding of the entire workflow, which offer runtime advantages in certain large-scale scenarios. This suggest that our method have potential for further extension and optimization in large-scale environments, like scientific workflow management, which we consider a valuable future extension direction.\n\n\n#### Limitation 4\n>The method does not directly model dynamic environments or online scheduling, restricting its scope to static DAG instances.\n\nWhile our proposed one-shot policy is evaluated in relatively static settings, it can be applied to dynamic environments. For example, when new tasks are revealed, or a new DAG job instance is submitted, re-scheduling can be performed by re-running the network. The objective and dense reward signal calculation should be adjusted accordingly. In cases where DAG job structures and arrival time is known in advance, we can perform pre-processing by adding pseudo predecessor nodes with fixed execution times.\n\nNevertheless, real-world dynamic scheduling scenarios often involve domain-specific constraints, which might require more dedicated modeling. Therefore, we agree this is a promising future work.\n\n\n#### Paper Formatting Concerns\n>Limitations section discussing the model limitations is not clearly stated. Having a distinct paragraph or subsection would improve the quality of the paper.\n\nDue to the page limitation, we only discussed limitations in Appendix G in the supplementary material. However, in order to improve the paper quality, we fully agree the viewer’s valuable suggestion to use a distinct subsection in the main text to state the limitations in the camera-ready version. Moreover, we will improve the limitations discussion based on the points that the viewer has raised."}, {"review_id": "uQ1HMDfVJt", "reviewer": "Reviewer_ZH3U", "summary": "This paper addresses critical limitations in existing reinforcement learning (RL) approaches for one-shot Directed Acyclic Graph (DAG) scheduling. Current RL-based methods suffer from two fundamental issues: redundant node priority comparisons that lead to biased sampling probability estimation, and sparse reward signals that hinder effective policy optimization. To overcome these challenges, we introduce a novel framework featuring a comparable antichain identification mechanism and a dense reward design. The comparable antichain identification dynamically determines which node pairs actually influence scheduling outcomes during topological sorting, eliminating unnecessary priority comparisons and enabling accurate probability estimation for gradient computation. This is complemented by a dense reward signal that provides node-level optimization guidance by comparing each node's completion time against heuristic baselines (e.g., HEFT for Pegasus, SFT for TPC-H), effectively mitigating the sparse reward problem.", "questions": "1.  How does the comparable antichain identification mechanism specifically enhance the accuracy of nodewise sampling probabilities compared to existing methods?\n2. Can the authors provide more details on how the dense reward signal is calculated and how it improves training efficiency in practice?", "limitations": "While the proposed method demonstrates effectiveness on the tested benchmarks, the paper lacks a detailed discussion on its scalability for very large-scale DAG scheduling problems. As the scale of DAGs increases, the computational overhead of the comparable antichain identification mechanism may become significant. The authors could further explore strategies to enhance the method's scalability for large-scale scenarios.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1.The paper proposes a novel one-shot DAG scheduling method based on reinforcement learning, introducing a comparable antichain identification mechanism and a dense reward signal. This effectively addresses the issues of redundant node priority comparisons and sparse rewards in existing RL-based one-shot scheduling approaches. The comparable antichain identification mechanism eliminates unnecessary pairwise priority comparisons, improving the accuracy of sampling probability estimation and training stability. The dense reward signal provides node-level optimization guidance, alleviating the sparse reward challenge and enhancing training efficiency.\n2. The paper provides a detailed analysis of the limitations of existing methods, including redundant priority comparisons and biased sampling probability estimation, as well as the sparse reward challenge. It demonstrates through theoretical derivations and lemma proofs that the comparable antichain identification method can accurately reflect the nodewise sampling probability corresponding to the sampled node execution sequence. This offers a solid theoretical foundation for the proposed method.\n3. The experimental section is well-designed, with evaluations conducted on three different DAG scheduling benchmarks (Pegasus, TPC-H, and JSSP). The results demonstrate that the proposed method achieves superior scheduling quality compared to existing learning-based DAG scheduling approaches.Ablation studies further validate the effectiveness of the comparable antichain identification mechanism and dense reward signal, highlighting their respective contributions to the overall performance.\n4. The paper makes several important contributions to the field of DAG scheduling. It not only proposes an innovative RL-based one-shot scheduling method but also provides new insights and solutions for addressing the challenges of redundant priority comparisons and sparse rewards in RL-based scheduling. This advances the development of reinforcement learning in DAG scheduling applications.\n\nWeaknesses:\n1. Although the dense reward signal improves training efficiency, the paper does not provide a thorough theoretical analysis of its design principles and theoretical properties. For instance, the impact of the advantage baseline selection on the dense reward signal's performance and its adaptability across different scheduling scenarios could be explored in greater depth.\n2. The paper compares the proposed method with several existing approaches but lacks a comprehensive comparison with the latest state-of-the-art methods in different application domains. This makes it difficult to fully assess the proposed method's competitiveness and generalizability. Including comparisons with more advanced methods would better highlight the method's advantages and limitations.", "was_revised": true, "final_justification": "The problem is interesting, and I think some parts can be further clarified, like the importance of using onepass manner to determine a DAG. I still think high computational load is not so convincing since DAG may be data dependent and adjustable each round. Overall I would like to recommend borderline acc.", "rebuttal": "We thank the viewer for thoughtful and careful evaluation of our manuscript and the valuable feedback. In this rebuttal, we respond to the concerned issues and clarify several aspects of our work.\n\n#### Weakness 1:\n> Although the dense reward signal improves training efficiency, the paper does not provide a thorough theoretical analysis of its design principles and theoretical properties. For instance, the impact of the advantage baseline selection on the dense reward signal's performance and its adaptability across different scheduling scenarios could be explored in greater depth.\n\nWe appreciate the reviewer’s insightful comment regarding the design and theoretical properties of the dense reward signal. \n\nThe core motivation for using dense rewards is to improve training efficiency and convergence stability in one-shot policy gradient learning, where the traditional sparse final reward often results in poor credit assignment. To address this, we design a dense reward signal by decomposing the total objective into node-wise costs. It is computed through simulation. For each scheduled node, we define its dense reward signal based on its distance to the final objective, thus approximating the node's value estimation when it is executed. Such design also makes one-shot DAG scheduling more interpretable. Specifically, the nodewise decisions, sampling probabilities and dense reward signals can be regarded as an entire MDP sampling trajectory in RL (like a trajectory by Monte Carlo sampling). This makes the interpretability of one-shot learning closer to MDP-based incremental approaches than those one-shot methods with sparse rewards. \n\nAs for the impact of the advantage baseline selection, we conducted experiments comparing multiple heuristic advantage baselines, including the previously used HEFT, and Critical Path on a Processor (CPOP), Shortest Finish Time (SFT). The results of the gap related to HEFT in percentage is shown in the following table, as a complement to Table 1. The results show that our method with different advantage baseline still outperforms existing methods, and the performance of our method with different heuristic advantage baseline is comparable.\n\n|Method |SIPHT100|SIPHT200|SIPHT300|SIPHT400|\n|--------| -----| -------|--------|------|\n|ours+HEFT|-13.3 |-5.42  |  -0.25 |  -0.62|\n|ours+CPOP|-12.2 |-5.42  |  -0.20 | -0.62|\n|ours+SFT |-12.8 |-4.83  |  -0.22 | -0.62|\n\nWe believe this is because the heuristic algorithm provide constant estimates for each DAG scheduling problem instance, ensuring the advantage estimation is unbiased. Additionally, these heuristics are near-optimal in many cases, leading to similar schedules. As a result, the variance reduction benefit is preserved, while introducing little bias.\n\n#### Weakness 2:\n> The paper compares the proposed method with several existing approaches but lacks a comprehensive comparison with the latest state-of-the-art methods in different application domains. This makes it difficult to fully assess the proposed method's competitiveness and generalizability. Including comparisons with more advanced methods would better highlight the method's advantages and limitations.\n\nIn this work, our main goal is to propose a foundational scheduling framework, rather than a specialized model for a particular domain. Our approach can be viewed as an extension of prior foundational DAG scheduling studies (e.g., Jeon et al. [2023], Sun et al.[2024] referenced in the manuscript). We focus on comparisons with these recent and representative foundational studies.\n\nFor future work, we regard adapting the proposed one-shot scheduling method to specific domain as a promising direction. The proposed CAI mechanism and dense reward signal can be extended to real-world systems by considering domain knowledge (such as the highly real-time system model, edge computing, and quality-of-service objectives) to better suit in specific areas. We will accordingly enrich the \"Conclusion\" section to discuss these domain adaptations and other future extensions.\n\n#### Question 1:\n> How does the comparable antichain identification mechanism specifically enhance the accuracy of nodewise sampling probabilities compared to existing methods?\n\nExisting methods typically sample a ranking list over all nodes (i.e., a total order) and conduct a topological sort to get the the actual node execution order as the solution from the rank list. However, multiple distinct ranking lists $\\{Rank_1, Rank_2, \\dots\\}$ can lead to a same valid DAG schedule $Solution(G)$, and the total probability of sampling that solution should be:\n$$\nP(Solution(G)) = P(Rank_1 \\cup Rank_2 \\cup …)\n$$\n\nSo, if only a single rank list’s probability $P(Rank_j)$ is used to approximate $P(Solution(G))$, this introduces underestimation.\n\nWe believe the reason causing the above issue lies in the sampling process. Existing methods use Equation (2) in the manuscript in each ranking step, which involves choosing each node among all unranked nodes. This regards the nodes that cannot possibly be scheduled at that step (i.e., nodes that are on the same dependency path with the currently selected node) as candidate nodes. These comparisons are thus redundant or invalid, as they do not affect the resulting topological order. Treating them as candidate actions introduces irrelevant logits into the softmax distribution, distorting the sampling probability.\n\nOur CAI module first restricts comparisons to independent nodes. Then, among these mutually independent nodes, it further selects the subset that actually influences the final scheduling order — the comparable antichain. This masks those invalid nodes, making the actual sampling distribution closer to the true $P(Solution(G))$.  \n\n\n#### Question 2:\n> Can the authors provide more details on how the dense reward signal is calculated and how it improves training efficiency in practice?\n\nOur dense reward is constructed by simulating the entire one-shot generated schedule, and evaluating the global cost (e.g., makespan). Then, we compute a node-level reward for each scheduled node, based on its distance to the final cost. Specifically:\n\n1. Given a DAG scheduling problem $G$, we conduct the heuristic advatage baseline algorithm on $G$, obtaining each task node's individual baseline cost $C_h(v_i)$.\n2. For a sampled solution $Solution(G;\\theta)$ (i.e., an execution order), we simulate it using a SimPy-based simulator. and obtain the overall makespan $C(Solution(G;\\theta))$ in practice. For each task node $v_{\\pi(t)}$, we obtain its individual cost $C(S_t(G;\\theta)) $ (e.g., its finish time) through simulation.\n3. We obtain the return-like dense reward signal $R_t$ of each task node $v_{\\pi(t)}$ by comparing the global objective $C(Solution(G;\\theta))$ with individual cost $C(S_t(G;\\theta))$:\n$$ R_t = C(Solution(G;\\theta)) - C(S_t(G;\\theta))$$\n4. To derive the advantage-like feedback $A_t$, we further substract each baseline from $R_t$, obtaining:\n$$ \n\\begin{align*}\nA_t &= R_t - \\textbf{baseline} \\\\\n&= (C(Solution(G;\\theta)) - C(S_t(G;\\theta))) - (C(Solution(G;\\theta))-C_h(v_{\\pi_\\theta(t)})) \\\\\n&=C_h(v_{\\pi_\\theta(t)}) - C(S_t(G;\\theta)) \n\\end{align*}\n$$\n\nBy introducing heuristic baseline, we provide a meaningful reward signal for each action, rather than assigning the same reward to all nodes or only to the final outcome.\n\nAs for how it improves training efficiency in practice, compared to sparse reward settings (where only the final cost is used), our dense reward reduces the variance of policy gradient estimates, because each node's policy update receives a targeted reward signal rather than sharing a single scalar. Also, it helps the model differentiate good and bad actions early in training.\n\n#### Limitation:\n>While the proposed method demonstrates effectiveness on the tested benchmarks, the paper lacks a detailed discussion on its scalability for very large-scale DAG scheduling problems. As the scale of DAGs increases, the computational overhead of the comparable antichain identification mechanism may become significant. The authors could further explore strategies to enhance the method's scalability for large-scale scenarios.\n\nCAI demonstrates better performance especially on those testbenches with more complex node dependency relationship. Our method also inherits the runtime advantages of one-shot scheduling compared to some other RL-based approaches, as demonstrated in the results. This suggest that our method have potential for further extension and optimization in large-scale environments, like scientific workflow management. We thank the reviewer's valuable suggestion which we consider a promising future extension direction."}, {"review_id": "w6RwPgAdiO", "reviewer": "Reviewer_GVMe", "summary": "This paper proposes a method using comparable antichain identification to reduce redundant comparisons and a dense reward signal for node-level optimization, reporting improved scheduling objective results compared to other learning-based approaches.", "questions": "Please see the weaknesses.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1.The paper presents a structurally guided one-shot DAG scheduling framework that integrates node-level decision mechanisms into a policy gradient setup.\n\n2.It provides a clear analysis of the limitations of prior one-shot approaches, particularly their reliance on redundant node comparisons, and proposes targeted improvements to address them.\n\nWeaknesses\n\n1.The ablation results in Table 2 show that removing either CAI or the dense reward sometimes leads to better performance than using both modules together. This suggests potential negative interactions or lack of synergy between the components, raising questions about the robustness of the combined design, especially across different DAG structures such as shallow or disjoint graphs.\n\n2.The motivation for the CAI module is based on the assumption that redundant comparisons lead to inaccurate sampling probability. However, this claim is primarily supported by intuitive reasoning and illustrative examples (e.g., Fig. 2), lacking formal justification or empirical analysis. A more rigorous treatment of how CAI affects the sampling distribution or improves policy gradient estimation would enhance the technical depth and clarity of the contribution.", "was_revised": true, "final_justification": "The rebuttal resolves my major concerns.", "rebuttal": "We thank for the viewer for your careful reading and valuable suggestion of our manuscript. In this rebuttal, we would like to respond to the concerns raised by the reviewer.\n\n#### Weakness & Question 1:\n> The ablation results in Table 2 show that removing either CAI or the dense reward sometimes leads to better performance than using both modules together. This suggests potential negative interactions or lack of synergy between the components, raising questions about the robustness of the combined design, especially across different DAG structures such as shallow or disjoint graphs.\n\nIn these specific cases, the performance degradation caused by introducing CAI is more. We attribute this to two main reasons:\n\n1. The DAGs in a TPC-H scheduling problem instance exhibit imbalanced structures. Also, since these DAGs are not mutually interconnected, the entire scheduling instance is a highly sparse graph structure. Moreover, the number of DAGs in the TPC-H benchmark is relatively limited. As a result, GNN-based network may struggle to learn to capture the features of each node across all DAGs within the scheduling instance. In addition, since CAI masks out incomparable nodes at each step, it may further hinder the network from learning accurate global priority value (logits) for each node.\n\n2. Our proposed CAI intends to remove the redundant priority comparison among DAG nodes that has dependency relationship, thus obtaining more accurate sampling probability. So, CAI is particularly useful in DAGs with more complex dependency structures, in which multiple nodes often lie along a longer path. For simpler DAG structures (e.g., TPC-H benchmark), they typically consist of many small-size DAGs with much shorter paths. In this situation, the number of dependent nodes located on the same path is small, and the existing dependencies are weak. The redundant comparisons among dependent nodes are significantly reduced, so the further improvement from applying CAI is limited.\n\nIn future work, we plan to investigate strategies for better handling such cases, including more effective feature extraction or training schemes tailored for such multi-DAG instances.\n\n#### Weakness & Question 2:\n>The motivation for the CAI module is based on the assumption that redundant comparisons lead to inaccurate sampling probability. However, this claim is primarily supported by intuitive reasoning and illustrative examples (e.g., Fig. 2), lacking formal justification or empirical analysis. A more rigorous treatment of how CAI affects the sampling distribution or improves policy gradient estimation would enhance the technical depth and clarity of the contribution.\n\nWe appreciate the reviewer’s request for a more rigorous explanation of how CAI improves sampling probability estimation and policy gradient updates. We provide a clarification below.\n\nExisting methods typically sample a ranking list over all nodes (i.e., a total order) and conduct a topological sort to get the the actual node execution order as the solution from the rank list. However, multiple distinct ranking lists $\\{Rank_1, Rank_2, \\dots\\}$ can lead to a same valid DAG schedule $Solution(G)$, and the total probability of sampling that solution should be:\n$$\nP(Solution(G)) = P(Rank_1 \\cup Rank_2 \\cup …)\n$$\n\nSo, if only a single rank list’s probability $P(Rank_j)$ is used to approximate $P(Solution(G))$, this introduces underestimation. This increases entropy and the variance of the policy gradient.\n\nWe believe the reason causing the above issue lies in the sampling process. Existing methods use Equation (2) in the manuscript in each ranking step, which involves choosing each node among all unranked nodes. This regards the nodes that cannot possibly be scheduled at that step (i.e., nodes that are on the same dependency path with the currently selected node) as candidate nodes. These comparisons are thus redundant or invalid, as they do not affect the resulting topological order. Treating them as candidate actions introduces irrelevant logits into the softmax distribution, distorting the sampling probability.\n\nOur CAI module first restricts comparisons to independent nodes. Then, among these mutually independent nodes, it further selects the subset that actually influences the final scheduling order — the comparable antichain. This masks those invalid nodes, making the actual sampling distribution closer to the true $P(Solution(G))$.  As a result, it reduces entropy and variance of policy gradient.\n\nWe will revise Section 3 and 4 to include the above explanation. We thank the reviewer's suggestion for making this point clearer and more rigorous."}, {"review_id": "Xb3LJsyGjT", "reviewer": "Reviewer_WSCD", "summary": "This paper shows a one-shot reinforcement learning (RL) method for scheduling tasks represented as a Directed Acyclic Graph (DAG). The authors address two key issues in existing one-shot approaches: redundant priority comparisons among nodes on the same precedence path, leading to biased probability estimates and unstable training, and sparse global rewards that offer little guidance for individual node-level decisions. To overcome these challenges, they propose a CAI mechanism, which extracts only nodes whose relative ordering affects the final schedule, and a dense reward signal that decomposes global makespan cost into node-level contributions. Empirical evaluations across three benchmarks—Pegasus scientific workflows, TPC-H query DAGs, and job-shop scheduling instances—demonstrate that the proposed method outperforms state-of-the-art one-shot RL, edge-generation scheduling, and incremental baselines in training efficiency.", "questions": "A few questions that could improve the article:\n\nQ: Have you tested the method on objectives beyond makespan? example: cumulative flow time\nComparable improvements with alternative cost functions would support broader applicability and show that both CAI and DR are agnostic to objective design.\n\nQ: Can the method handle settings where the DAG is revealed incrementally or changes over time?\nIt would be interesting to know extensions in dynamic environments and outlining path for adaptation.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The strengths are:\n-The work demonstrates gains across heterogeneous benchmarks, which highlights robustness\n-The method applies node-level dense rewards based on heuristic advantage baselines in one-shot RL, that is an adaptation of reward-shaping concepts.\n\nThe weaknesses are:\n- The paper does not explore other objective metrics or multi-objective scenarios, which narrows its applicability.", "was_revised": true, "final_justification": "I would keep the score, since there aren't additional prelim results to address the weaknesses", "rebuttal": "We thank the viewer for careful evaluation of our manuscript and the valuable feedback. In this rebuttal, we respond to the concerned issues and clarify several aspects of our work.\n\n#### Weakness 1:\n>The paper does not explore other objective metrics or multi-objective scenarios, which narrows its applicability.\n\nIn this work, our main goal is to propose a foundational scheduling framework, rather than a specialized model for a particular domain. Our approach can be viewed as an extension of prior foundational DAG scheduling studies (e.g., Jeon et al. [2023], Sun et al.[2024] referenced in the manuscript) , where makespan is adopted for evaluating DAG scheduling algorithms. Therefore, adopting makespan as the metric enables us to demonstrate direct comparison with prior works.\n\nWe regard extending the proposed one-shot scheduling method to application-specific objectives as a promising future direction, by considering domain knowledge (such as the highly real-time system model, edge computing, and quality-of-service objectives). We will add the corresponding description in the Conclusion section.\n\n#### Question 1:\n>Have you tested the method on objectives beyond makespan? example: cumulative flow time. Comparable improvements with alternative cost functions would support broader applicability and show that both CAI and DR are agnostic to objective design.\n\nAs explained in the response to Weakness 1, we only tested performance on makespan. We appreciate the viewer's thoughtful suggestion to consider other objective metrics or multi-objective scenarios to support broader applicability of our proposed method. We agree that this would be a promising direction.\n\n#### Question 2:\n>Can the method handle settings where the DAG is revealed incrementally or changes over time? It would be interesting to know extensions in dynamic environments and outlining path for adaptation.\n\nWhile our proposed one-shot policy is evaluated in relatively static settings, it can be applied to dynamic environments. For example, when new task nodes are revealed, or a new DAG job instance is submitted, re-scheduling can be performed by re-running the network. The optimization objective and dense reward signal calculation should be adjusted accordingly. In cases where DAG job structures and arrival times are known in advance (i.e., containing earliest-start-time constraints), we can perform pre-processing by adding pseudo predecessor nodes with fixed execution times.\n\nConsidering that real-world dynamic scheduling scenarios often involve domain-specific constraints, it might require more dedicated modeling. Therefore, we think this is a highly promising future work, and we will accordingly add the discussion in the Conclusion section."}]

Author rebuttal:

Meta-review: The paper proposes a novel one-shot DAG scheduling method using reinforcement learning (RL), and also propose a dense reward signal for node level decision-making optimization in training, effectively addressing the sparse reward challenge. 

Based on comments from reviewers, the strengths of the paper include: (1) Strong empirical results: The proposed method outperforms existing learning-based DAG scheduling approaches across multiple heterogeneous benchmarks. The evaluation is thorough, including ablation studies that highlight the contribution of each component. (2) Clear theoretical foundation: The paper presents a well-structured analysis of limitations in prior work and supports the proposed method with formal definitions, lemmas, and sound justification.

Some minor concerns were raised, such as the high computational load due to data dependency and per-round adjustability, as well as the limited exploration of alternative or multi-objective metrics, which may affect general applicability. However, these are relatively minor and do not undermine the overall quality or contribution of the work.

Given the overall positive reviewer scores—one Accept and three Weak Accepts—and the paper’s solid technical merit, I recommend acceptance.
Decision: Accept (poster)