# Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning

arXiv: https://arxiv.org/abs/2308.14647 · HTML: https://mlsanity.com/paper/2308.14647/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 62 references that are in the map.
- First posted on arXiv 28 Aug 2023.

## Builds on (most cited first, 8 of 8)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling](https://mlsanity.com/paper/2011.04333/) (2020)
- [Bounding the Response Time of DAG Tasks Using Long Paths](https://mlsanity.com/paper/2211.08800/) (2022)
- [Response Time Bounds for Typed DAG Parallel Tasks on Heterogeneous Multi-cores](https://mlsanity.com/paper/1809.07689/) (2018)
- [Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG Tasks](https://mlsanity.com/paper/2101.11053/) (2021)

## Built on by (most cited first, 1 of 1)

- [A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling](https://mlsanity.com/paper/2603.23249/) (2026)

## Abstract (arXiv)

Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications from the automotive, avionics, and industrial domains that implement their functionalities through chains of intercommunicating tasks. This paper studies the problem of scheduling real-time DAG tasks by presenting a novel schedulability test based on the concept of trivial schedulability. Using this schedulability test, we propose a new DAG scheduling framework (edge generation scheduling -- EGS) that attempts to minimize the DAG width by iteratively generating edges while guaranteeing the deadline constraint. We study how to efficiently solve the problem of generating edges by developing a deep reinforcement learning algorithm combined with a graph representation neural network to learn an efficient edge generation policy for EGS. We evaluate the effectiveness of the proposed algorithm by comparing it with state-of-the-art DAG scheduling heuristics and an optimal mixed-integer linear programming baseline. Experimental results show that the proposed algorithm outperforms the state-of-the-art by requiring fewer processors to schedule the same DAG tasks. The code is available at https://github.com/binqi-sun/egs.