Learning to Solve Resource-Constrained Project Scheduling Problems with Duration Uncertainty using Graph Neural Networks

Guillaume Infantes, Stéphanie Roussel, Antoine Jacquet, Emmanuel BénazéraarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces "Wheatley," a novel framework that uses Graph Neural Networks (GNNs) and Deep Reinforcement Learning (DRL) to tackle the Resource-Constrained Project Scheduling Problem (RCPSP) with uncertain task durations. Wheatley learns a proactive scheduling policy that outperforms traditional methods, offering more resilient and generalizable schedules for real-world industrial applications.

What Problem Does This Paper Address?

Project scheduling is crucial in many industries, but real-world tasks rarely have fixed durations. Factors like equipment failures or supply chain issues introduce uncertainty, making it challenging to create schedules that are both efficient and robust. Traditional proactive scheduling methods often produce fixed schedules that can become inefficient when actual task durations deviate from predictions. Reactive scheduling, while flexible, can lead to unstable and unpredictable outcomes. This paper addresses the need for a proactive scheduling approach that can effectively handle duration uncertainty, aiming to minimize the expected project duration and produce schedules that are reusable across various scenarios.

Methods

The core of Wheatley lies in its innovative application of Graph Neural Networks (GNNs) combined with Deep Reinforcement Learning (DRL). The RCPSP with uncertain durations is framed as a Markov Decision Process (MDP). A GNN-based agent is trained using DRL (specifically, Proximal Policy Optimization - PPO) to learn an optimal "priority dispatch rule." This rule guides a Serial Schedule Generation Scheme (SGS) to construct a schedule.

Key methodological innovations include:

  • MDP Formulation: The problem is modeled as an MDP where states represent partial schedules encoded as AON-flow graphs. The agent learns to transition between states by selecting tasks to schedule.
  • GNN Architecture: A sophisticated GNN architecture is employed to process the complex graph representation of the scheduling problem. This includes:
  • Graph Rewiring: To improve message passing and information flow, the graph is augmented with reverse edges, resource nodes, and a virtual pooling node.
  • Heterogeneous Graph Processing: The GNN uses a message-passing mechanism with attention to handle diverse node and edge types (task nodes, resource nodes, precedence edges, flow edges, etc.).
  • Handling Uncertainty: Duration uncertainty is managed by maintaining three distinct flow graphs (for minimum, maximum, and mode durations) within the state representation.
  • Proactive Policy Learning: The DRL agent learns a policy that aims to minimize the expected makespan, allowing for a single, reusable schedule that is resilient to duration variations.

Datasets

The paper uses benchmarks from the PSPLib [16] for training and evaluation. These instances are categorized by the number of tasks (30, 60, 90, and 120). For evaluation in the uncertain case, 100 duration scenarios were generated for each benchmark instance. The authors also note that their framework, Wheatley, is made publicly available for future research.

Key Insights and Ideas

  • GNNs as a Powerful Tool for Scheduling: The paper demonstrates that GNNs are highly effective at capturing the complex dependencies and resource constraints inherent in scheduling problems, especially when dealing with uncertainty.
  • Proactive Scheduling for Resilience: Learning a single, robust policy that generalizes across different duration scenarios is more practical for industrial settings than purely reactive approaches.
  • MDP Formulation for DRL: Framing the scheduling problem as an MDP provides a clear structure for applying DRL algorithms to learn optimal decision-making policies.
  • Graph Rewiring Enhances Information Flow: The proposed graph rewiring techniques are crucial for enabling the GNN to effectively propagate information across the complex scheduling graph, leading to better decision-making.

Key Results

Wheatley demonstrates superior performance compared to baseline methods:

  • Deterministic Case: Wheatley achieves competitive results, with an average gap of less than 5% for smaller datasets (30, 60, 90 tasks) and a slightly larger gap for 120-task datasets.
  • Uncertain Case: In scenarios with uncertain task durations, Wheatley significantly outperforms traditional Priority Dispatch Rules (PDRs) and adapted deterministic approaches (CP-50, CP-50-ws).
  • Wheatley achieves the best average makespan across most benchmark subsets.
  • While CP-based approaches can be effective on smaller datasets, they struggle with larger instances, often timing out or solving fewer scenarios. Wheatley, in contrast, shows strong performance and generalization on larger and unseen datasets. For instance, on the ukn 120 dataset, Wheatley's gap is still less than 12%, while CP-50-ws has a gap greater than 12%.

Limitations and Future Work

  • Limitations:
    • The paper focuses on minimizing the expected makespan. Other objectives (e.g., minimizing tardiness, maximizing resource utilization) are not explored.
  • The current uncertainty model assumes known probability distributions for durations. Real-world scenarios might involve more complex or unknown distributions.
  • Future Work:
    • Extending the approach to handle alternative scheduling objectives.
  • Investigating more complex uncertainty models, including multimodal distributions.
  • Validating the approach on non-public industrial datasets and exploring its scalability for very large problems.
  • Adapting the framework to other RCPSP variants and constraints.

Summary updated

Abstract

The Resource-Constrained Project Scheduling Problem (RCPSP) is a classical scheduling problem that has received significant attention due to of its numerous applications in industry. However, in practice, task durations are subject to uncertainty that must be considered in order to propose resilient scheduling. In this paper, we address the RCPSP variant with uncertain tasks duration (modeled using known probabilities) and aim to minimize the overall expected project duration. Our objective is to produce a baseline schedule that can be reused multiple times in an industrial setting regardless of the actual duration scenario. We leverage Graph Neural Networks in conjunction with Deep Reinforcement Learning (DRL) to develop an effective policy for task scheduling. This policy operates similarly to a priority dispatch rule and is paired with a Serial Schedule Generation Scheme to produce a schedule. Our empirical evaluation on standard benchmarks demonstrates the approach's superiority in terms of performance and its ability to generalize. The developed framework, Wheatley, is made publicly available online to facilitate further research and reproducibility.
BibTeX
@misc{infantes2025learning,
  author = {Guillaume Infantes and Stéphanie Roussel and Antoine Jacquet and Emmanuel Bénazéra},
  title = {{Learning to Solve Resource-Constrained Project Scheduling Problems with Duration Uncertainty using Graph Neural Networks}},
  year = {2025},
  eprint = {2511.13214},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.13214},
}
Figure