Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling

Bulent Soykan, Sean Mondesire, Ghaith Rabadi, Grace Bochenek
2/8/2026
cs.AIcs.ET

No official code found. Best implementation: bulentsoykan/GNN-DRL4UPMSP (6 stars, MIT, last commit 2026-02-12).

Abstract

The Unrelated Parallel Machine Scheduling Problem (UPMSP) with release dates, setups, and eligibility constraints presents a significant multi-objective challenge. Traditional methods struggle to balance minimizing Total Weighted Tardiness (TWT) and Total Setup Time (TST). This paper proposes a Deep Reinforcement Learning framework using Proximal Policy Optimization (PPO) and a Graph Neural Network (GNN). The GNN effectively represents the complex state of jobs, machines, and setups, allowing the PPO agent to learn a direct scheduling policy. Guided by a multi-objective reward function, the agent simultaneously minimizes TWT and TST. Experimental results on benchmark instances demonstrate that our PPO-GNN agent significantly outperforms a standard dispatching rule and a metaheuristic, achieving a superior trade-off between both objectives. This provides a robust and scalable solution for complex manufacturing scheduling.

View on arXivView PDF

Code Implementations(1)

bulentsoykan/GNN-DRL4UPMSPCommunity62%
MIT

Paper "Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling"

61PythonFeb 8, 20268 months agoMIT

Similar Papers

Exploring Multi-Agent Reinforcement Learning for Unrelated Parallel Machine Scheduling

91% match2024

Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions

89% match2023

Solving Integrated Process Planning and Scheduling Problem via Graph Neural Network Based Deep Reinforcement Learning

88% match1 repo172024

Deep Learning for Unrelated-Machines Scheduling: Handling Variable Dimensions

86% match2025

Solving the flexible job-shop scheduling problem through an enhanced deep reinforcement learning approach

85% match2023

Partitioning Distributed Compute Jobs with Reinforcement Learning and Graph Neural Networks

84% match2023

Cite this paper

@article{soykan2026graphenhanced,
  title  = {Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling},
  author = {Bulent Soykan and Sean Mondesire and Ghaith Rabadi and Grace Bochenek},
  year   = {2026},
  eprint = {2602.08052},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2602.08052v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2602.08052.svg)](https://codeofpaper.com/paper/2602.08052)

Discussion