# Schedulable Job-Level Dependencies for Cause-Effect Chains via Graph Neural Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 43 references that are in the map.
- First posted on arXiv 2 Jul 2026.

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

- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness](https://mlsanity.com/paper/2402.14847/) (2024)
- [Reinforcement Learning for Search Tree Size Minimization in Constraint Programming: New Results on Scheduling Benchmarks](https://mlsanity.com/paper/2508.20056/) (2025)
- [Packing-Inspired Algorithms for Periodic Scheduling Problems with Harmonic Periods](https://mlsanity.com/paper/2410.14756/) (2024)
- [Periodic Chains Scheduling on Dedicated Resources -- A Crucial Problem in Time-Sensitive Networks](https://mlsanity.com/paper/2503.19003/) (2025)

## Abstract (arXiv)

Modern automotive software architectures comprise large sets of mixed-criticality functions executing on shared multi-core platforms with strict real-time and end-to-end timing requirements. Sensor-to-actuator data propagation in such systems is typically expressed via cause-effect chains with worst-case data-age budgets. Job-level dependencies (JLDs) have been introduced to provide a schedule-agnostic mechanism for bounding the data age independently of the underlying scheduler. The state-of-the-art methods for synthesizing JLDs, however, do not check whether the produced JLDs are enforceable under a concrete scheduling policy or jointly schedulable at the system level. In this paper we propose the first machine-learning-based JLD synthesis method, built around a two-level Graph Neural Network with temperature-controlled sampling that learns the structural patterns connecting cause-effect chain configurations to their JLD solutions. Since learned outputs may not be correct by construction, we embed the GNN in a novel Generate-and-Verify architecture in which a safe DP data-age checker, together with a per-chain EDF feasibility checker and a system-level demand-bound test, accept or reject each candidate. We show that the ML-based generator substantially outperforms the original greedy heuristic while achieving orders-of-magnitude lower synthesis time, demonstrating that learned structural priors can effectively replace exponential propagation-tree enumeration on this class of real-time scheduling problems.