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

• URL: http://arxiv.org/abs/2602.08052v1
• Date: Sun, 08 Feb 2026 16:54:47 GMT
• Title: Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling
• Abstract summary: This paper proposes a Deep Reinforcement Learning framework using Proximal Policy Optimization (PPO) and a Graph Neural Network (GNN)<n>The GNN effectively represents the complex state of jobs, machines, and setups, allowing the PPO agent to learn a direct scheduling policy.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• PPO-STGNN: A Proximal Policy Optimization Approach with Spatio-Temporal Graph Neural Networks for DAG Task Scheduling in Cloud-Edge-End Computing [3.11321804521525]
  This paper proposes PPO-STGNN, a task-schling algorithm that integrates atemporal graph neural networks (STGNNs)<n>Results show that PPO-STGNN significantly improves load balancing while maintaining a low completion time.<n>It is suitable for dynamic and heterogeneous cloud-edge-end DAG scheduling scenarios.
  arXiv  Detail & Related papers  (2026-09-03T08:04:30Z)
• HiDiffTIR: Hierarchical Difficulty-Aware Policy Optimization for Multi-Turn Tool-Integrated Reasoning [95.29291773706224]
  Tool-Integrated Reasoning is a capability for LLM agents to solve complex tasks by interacting with external tools iteratively.<n>Existing approaches typically assign uniform trajectory-level advantages and treat all correct tool calls equally.<n>This can lead to imprecise learning signals that do not adequately distinguish between trivial and challenging tool-use patterns.
  arXiv  Detail & Related papers  (2026-08-22T09:14:15Z)
• MagicAgent: Towards Generalized Agent Planning [73.21129030631421]
  We present textbfMagicAgent, a series of foundation models specifically designed for generalized agent planning.<n>We introduce a lightweight and scalable synthetic data framework that generates high-quality trajectories across diverse planning tasks.<n>We show that MagicAgent-32B and MagicAgent-30B-A3B achieve superior performance across diverse open-source benchmarks.
  arXiv  Detail & Related papers  (2026-02-22T01:39:16Z)
• Reason-Plan-ReAct: A Reasoner-Planner Supervising a ReAct Executor for Complex Enterprise Tasks [0.0]
  We introduce RP-ReAct, a novel multi-agent approach that decouples strategic planning from low-level execution to achieve superior reliability and efficiency.<n>RP-ReAct consists of a Reasoner Planner Agent (RPA), responsible for planning each sub-step, and one or multiple Proxy-Execution Agent (PEA) that translates sub-steps into concrete tool interactions.<n>We evaluate RP-ReAct, on the challenging, multi-domain ToolQA benchmark using a diverse set of six open-weight reasoning models.
  arXiv  Detail & Related papers  (2025-12-03T08:28:40Z)
• Dynamic Test-Time Compute Scaling in Control Policy: Difficulty-Aware Stochastic Interpolant Policy [40.173458986694584]
  We introduce Difficulty-Aware Interpolant Policy (DA-SIP), a framework that enables robotic controllers to adaptively adjust their integration horizon in real time based on task difficulty.<n>DA-SIP achieves 2.6-4.4x reduction in total time while maintaining task success rates comparable to fixed maximum-computation baselines.
  arXiv  Detail & Related papers  (2025-11-25T22:46:42Z)
• Cloud-Fog-Edge Collaborative Computing for Sequential MIoT Workflow: A Two-Tier DDPG-Based Scheduling Framework [2.5263430338308557]
  Medical Internet of Things (MIoT) demands stringent end-to-end latency guarantees for sequential healthcare deployed over heterogeneous cloud-fog-edge infrastructures.<n>We propose a Two-tier DDPG-based scheduling framework that decomposes the scheduling decision into a hierarchical process.<n> Experiments results validate our approach, demonstrating increasingly superior performance over baselines as complexity rises.
  arXiv  Detail & Related papers  (2025-10-24T03:58:31Z)
• Dependency-Aware Task Offloading in Multi-UAV Assisted Collaborative Mobile Edge Computing [53.88774113545582]
  This paper presents a novel multi-unmanned aerial vehicle (UAV) assisted collaborative mobile edge computing (MEC) framework.<n>It aims to minimize the system cost, and thus realize an improved trade-off between task consumption and energy consumption.<n>We show that the proposed scheme can significantly reduce the system cost, and thus realize an improved trade-off between task consumption and energy consumption.
  arXiv  Detail & Related papers  (2025-10-23T02:55:40Z)
• Dynamic Generation of Multi-LLM Agents Communication Topologies with Graph Diffusion Models [99.85131798240808]
  We introduce a novel generative framework called textitGuided Topology Diffusion (GTD)<n>Inspired by conditional discrete graph diffusion models, GTD formulates topology synthesis as an iterative construction process.<n>At each step, the generation is steered by a lightweight proxy model that predicts multi-objective rewards.<n>Experiments show that GTD can generate highly task-adaptive, sparse, and efficient communication topologies.
  arXiv  Detail & Related papers  (2025-10-09T05:28:28Z)
• PLAN-TUNING: Post-Training Language Models to Learn Step-by-Step Planning for Complex Problem Solving [66.42260489147617]
  We introduce PLAN-TUNING, a framework that distills synthetic task decompositions from large-scale language models.<n>Plan-TUNING fine-tunes smaller models via supervised and reinforcement-learning objectives to improve complex reasoning.<n>Our analysis demonstrates how planning trajectories improves complex reasoning capabilities.
  arXiv  Detail & Related papers  (2025-07-10T07:30:44Z)
• Evaluating the Efficacy of LLM-Based Reasoning for Multiobjective HPC Job Scheduling [6.375075345747834]
  Large Language Model (LLM)-based scheduler using ReAct-style framework (Reason + Act)<n>System incorporates a scratchpad memory to track scheduling history and refine decisions via natural language feedback.<n>We evaluate our approach using OpenAI's O4-Mini and Anthropic's Claude 3.7 across seven real-world HPC workload scenarios.
  arXiv  Detail & Related papers  (2025-05-29T14:25:29Z)
• Prediction-Assisted Online Distributed Deep Learning Workload Scheduling in GPU Clusters [24.845122459974466]
  This paper proposes an adaptive shortest-remaining-processing-time-first (A-SRPT) scheduling algorithm.<n>By modeling each job as a graph corresponding to heterogeneous Deep Neural Network (DNN) models, A-SRPT strategically assigns jobs to the available GPU.<n>A-SRPT maps the complex scheduling problem into a single-machine instance, which is addressed optimally by a preemptive "shortest-remaining-processing-time-first" strategy.
  arXiv  Detail & Related papers  (2025-01-09T20:19:01Z)
• VinePPO: Refining Credit Assignment in RL Training of LLMs [66.80143024475635]
  We propose VinePPO, a straightforward approach that leverages the flexibility of language environments to compute unbiased Monte Carlo-based estimates.<n>Our method consistently outperforms PPO and other baselines across MATH and GSM8K datasets in less wall-clock time.
  arXiv  Detail & Related papers  (2024-10-02T15:49:30Z)
• Controllable Dynamic Multi-Task Architectures [92.74372912009127]
  We propose a controllable multi-task network that dynamically adjusts its architecture and weights to match the desired task preference as well as the resource constraints. We propose a disentangled training of two hypernetworks, by exploiting task affinity and a novel branching regularized loss, to take input preferences and accordingly predict tree-structured models with adapted weights.
  arXiv  Detail & Related papers  (2022-03-28T17:56:40Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.