# ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 45 references that are in the map.
- First posted on arXiv 6 Jun 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Averaging Weights Leads to Wider Optima and Better Generalization](https://mlsanity.com/paper/1803.05407/) (2018)
- [HyperNetworks](https://mlsanity.com/paper/1609.09106/) (2016)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning to Perform Local Rewriting for Combinatorial Optimization](https://mlsanity.com/paper/1810.00337/) (2018)
- [Learning by Playing - Solving Sparse Reward Tasks from Scratch](https://mlsanity.com/paper/1802.10567/) (2018)
- [Learning Improvement Heuristics for Solving Routing Problems](https://mlsanity.com/paper/1912.05784/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Deep Policy Dynamic Programming for Vehicle Routing Problems](https://mlsanity.com/paper/2102.11756/) (2021)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [Dealing with Sparse Rewards in Reinforcement Learning](https://mlsanity.com/paper/1910.09281/) (2019)
- [Learning to Search with MCTSnets](https://mlsanity.com/paper/1802.04697/) (2018)
- [Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks](https://mlsanity.com/paper/1803.09621/) (2018)
- [SOM-Guided Evolutionary Search for Solving MinMax Multiple-TSP](https://mlsanity.com/paper/1907.11910/) (2019)

## Built on by (most cited first, 30 of 31)

- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)
- [Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling](https://mlsanity.com/paper/2211.10936/) (2022)
- [Learning to Control Local Search for Combinatorial Optimization](https://mlsanity.com/paper/2206.13181/) (2022)
- [DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems](https://mlsanity.com/paper/2405.17272/) (2024)
- [Imperative Learning: A Self-supervised Neuro-Symbolic Learning Framework for Robot Autonomy](https://mlsanity.com/paper/2406.16087/) (2024)
- [Graph Neural Networks for Job Shop Scheduling Problems: A Survey](https://mlsanity.com/paper/2406.14096/) (2024)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem](https://mlsanity.com/paper/2309.15517/) (2023)
- [Learning context-aware adaptive solvers to accelerate quadratic programming](https://mlsanity.com/paper/2211.12443/) (2022)
- [DAN: Decentralized Attention-based Neural Network for the MinMax Multiple Traveling Salesman Problem](https://mlsanity.com/paper/2109.04205/) (2021)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem](https://mlsanity.com/paper/2402.17606/) (2024)
- [A Neural Separation Algorithm for the Rounded Capacity Inequalities](https://mlsanity.com/paper/2306.17283/) (2023)
- [iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning](https://mlsanity.com/paper/2405.00285/) (2024)
- [Policy-Based Self-Competition for Planning Problems](https://mlsanity.com/paper/2306.04403/) (2023)
- [Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.16580/) (2024)
- [Neuro CROSS exchange: Learning to CROSS exchange to solve realistic vehicle routing problems](https://mlsanity.com/paper/2206.02771/) (2022)
- [Offline reinforcement learning for job-shop scheduling problems](https://mlsanity.com/paper/2410.15714/) (2024)
- [Graph Q-Learning for Combinatorial Optimization](https://mlsanity.com/paper/2401.05610/) (2024)
- [Optimizing Job Allocation using Reinforcement Learning with Graph Neural Networks](https://mlsanity.com/paper/2501.19063/) (2025)
- [Generalizing Beyond Suboptimality: Offline Reinforcement Learning Learns Effective Scheduling through Random Solutions](https://mlsanity.com/paper/2509.10303/) (2025)
- [Variational Approach for Job Shop Scheduling](https://mlsanity.com/paper/2602.00408/) (2026)
- [Mamba Meets Scheduling: Learning to Solve Flexible Job Shop Scheduling with Efficient Sequence Modeling](https://mlsanity.com/paper/2602.21546/) (2026)
- [Construct, Merge, Solve & Adapt with Reinforcement Learning for the min-max Multiple Traveling Salesman Problem](https://mlsanity.com/paper/2602.23579/) (2026)
- [Agentic-Kube: A Graph-Enhanced Multi-Agent Reinforcement Learning Framework for Multi-Objective Kubernetes Scheduling](https://mlsanity.com/paper/2603.12031/) (2026)
- [GOAL: Graph-based Objective-Aligned Diffusion Solvers for Dynamic Multi-Objective Optimization](https://mlsanity.com/paper/2605.19119/) (2026)
- [Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling](https://mlsanity.com/paper/2605.23957/) (2026)

## Abstract (arXiv)

We propose ScheduleNet, a RL-based real-time scheduler, that can solve various types of multi-agent scheduling problems. We formulate these problems as a semi-MDP with episodic reward (makespan) and learn ScheduleNet, a decentralized decision-making policy that can effectively coordinate multiple agents to complete tasks. The decision making procedure of ScheduleNet includes: (1) representing the state of a scheduling problem with the agent-task graph, (2) extracting node embeddings for agent and tasks nodes, the important relational information among agents and tasks, by employing the type-aware graph attention (TGA), and (3) computing the assignment probability with the computed node embeddings. We validate the effectiveness of ScheduleNet as a general learning-based scheduler for solving various types of multi-agent scheduling tasks, including multiple salesman traveling problem (mTSP) and job shop scheduling problem (JSP).