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

Abstract

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).

arXiv comment9 pages, 6 figures

References in corpus (11)

• Scikit-learn: Machine Learning in Python
• Addressing Function Approximation Error in Actor-Critic Methods
• Learning Combinatorial Optimization Algorithms over Graphs
• Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
• Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
• Averaging Weights Leads to Wider Optima and Better Generalization
• Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
• Learning Improvement Heuristics for Solving Routing Problems
• Dealing with Sparse Rewards in Reinforcement Learning
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• Learning What to Defer for Maximum Independent Sets