A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling

• URL: http://arxiv.org/abs/2603.23249v1
• Date: Tue, 24 Mar 2026 14:16:08 GMT
• Title: A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling
• Abstract summary: We propose an end-to-end reinforcement learning framework for heterogeneous directed acyclic graphs (DAGs)<n>WeCAN addresses task--pool compatibility coefficients and generation-induced optimality gaps.<n>Experiments on graphs and real-world TPC-H DAGs demonstrate improved makespan over strong baselines, with inference time comparable to classicals.
• Score: 6.655206888698601
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient scheduling of directed acyclic graphs (DAGs) in heterogeneous environments is challenging due to resource capacities and dependencies. In practice, the need for adaptability across environments with varying resource pools and task types, alongside rapid schedule generation, complicates these challenges. We propose WeCAN, an end-to-end reinforcement learning framework for heterogeneous DAG scheduling that addresses task--pool compatibility coefficients and generation-induced optimality gaps. It adopts a two-stage single-pass design: a single forward pass produces task--pool scores and global parameters, followed by a generation map that constructs schedules without repeated network calls. Its weighted cross-attention encoder models task--pool interactions gated by compatibility coefficients, and is size-agnostic to environment fluctuations. Moreover, widely used list-scheduling maps can incur generation-induced optimality gaps from restricted reachability. We introduce an order-space analysis that characterizes the reachable set of generation maps via feasible schedule orders, explains the mechanism behind generation-induced gaps, and yields sufficient conditions for gap elimination. Guided by these conditions, we design a skip-extended realization with an analytically parameterized decreasing skip rule, which enlarges the reachable order set while preserving single-pass efficiency. Experiments on computation graphs and real-world TPC-H DAGs demonstrate improved makespan over strong baselines, with inference time comparable to classical heuristics and faster than multi-round neural schedulers.

Related papers

• Complexity-Balanced Diffusion Splitting [20.558008394592097]
  Complexity-Balanced Splitting (CBS) is a principled framework for temporal capacity allocation.<n>CBS partitions the diffusion timeline into segments of equal approximation burden.<n>CBS consistently improves quality without increasing per-step inference cost.
  arXiv  Detail & Related papers  (2026-06-04T17:57:15Z)
• Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Scheduling [26.97705087364345]
  Graph-RHO is a novel critical-path-aware graph-based RHO framework.<n>We introduce a topology-aware heterogeneous graph network that encodes subproblems as operation-machine graphs with multi-relational edges.<n>We incorporate a critical-path-aware mechanism that injects inductive biases during training to distinguish highly sensitive bottleneck operations from robust ones.
  arXiv  Detail & Related papers  (2026-04-11T07:35:09Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Adaptive Linear Path Model-Based Diffusion [52.84663832658799]
  We introduce Linear Path Model-Based Diffusion (LP-MBD), which replaces the variance-preserving schedule with a flow-matching linear probability path.<n>We also propose Adaptive LP-MBD (ALP-MBD), which leverages reinforcement learning to adjust diffusion steps and noise levels according to task complexity and environmental conditions.
  arXiv  Detail & Related papers  (2026-02-02T21:33:03Z)
• Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models [99.85131798240808]
  We introduce a novel generative framework called textitGuided Topology Diffusion (GTD)<n>Inspired by conditional discrete graph diffusion models, GTD formulates topology synthesis as an iterative construction process.<n>At each step, the generation is steered by a lightweight proxy model that predicts multi-objective rewards.<n>Experiments show that GTD can generate highly task-adaptive, sparse, and efficient communication topologies.
  arXiv  Detail & Related papers  (2025-10-09T05:28:28Z)
• HedraRAG: Coordinating LLM Generation and Database Retrieval in Heterogeneous RAG Serving [10.130938079844121]
  HedraRAG is a runtime system built on a graph-based abstraction that exposes optimization opportunities across stage-level parallelism, intra-request similarity, and inter-request skewness.<n>The resulting execution plans are mapped onto hybrid CPU-GPU pipelines to improve resource utilization and reduce latency.
  arXiv  Detail & Related papers  (2025-07-12T04:42:43Z)
• Adaptive Inference-Time Scaling via Cyclic Diffusion Search [61.42700671176343]
  We introduce the challenge of adaptive inference-time scaling-dynamically adjusting computational effort during inference.<n>We propose Adaptive Bi-directional Cyclic Diffusion (ABCD), a flexible, search-based inference framework.<n>ABCD refines outputs through bi-directional diffusion cycles while adaptively controlling exploration depth and termination.
  arXiv  Detail & Related papers  (2025-05-20T07:31:38Z)
• STRGCN: Capturing Asynchronous Spatio-Temporal Dependencies for Irregular Multivariate Time Series Forecasting [14.156419219696252]
  STRGCN captures the complex interdependencies in IMTS by representing them as a fully connected graph.<n>Experiments on four public datasets demonstrate that STRGCN achieves state-of-the-art accuracy, competitive memory usage and training speed.
  arXiv  Detail & Related papers  (2025-05-07T06:41:33Z)
• Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning [2.365237699556817]
  Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications. We propose a new DAG scheduling framework that attempts to minimize the DAG width by iteratively generating edges. We evaluate the effectiveness of the proposed algorithm by comparing it with state-of-the-art DAG schedulings and an optimal mixed-integer linear programming baseline.
  arXiv  Detail & Related papers  (2023-08-28T15:19:18Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  This paper proposes a novel spatial-spectral HSI classification method via multiple random anchor graphs ensemble learning (RAGE) Firstly, the local binary pattern is adopted to extract the more descriptive features on each selected band, which preserves local structures and subtle changes of a region. Secondly, the adaptive neighbors assignment is introduced in the construction of anchor graph, to reduce the computational complexity.
  arXiv  Detail & Related papers  (2021-03-25T09:31:41Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.