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

• URL: http://arxiv.org/abs/2511.13214v1
• Date: Mon, 17 Nov 2025 10:27:35 GMT
• Title: Learning to Solve Resource-Constrained Project Scheduling Problems with Duration Uncertainty using Graph Neural Networks
• Authors: Guillaume Infantes, Stéphanie Roussel, Antoine Jacquet, Emmanuel Benazera,
• Abstract summary: Resource-Constrained Project Scheduling Problem (RCPSP) is a classical scheduling problem that has received significant attention due to its numerous applications in industry.<n>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.<n>We leverage Graph Neural Networks in conjunction with Deep Reinforcement Learning (DRL) to develop an effective policy for task scheduling.
• Score: 0.15749416770494704
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Semantic Scheduling for LLM Inference [48.19648297172146]
  We introduce the concept of semantic scheduling in scheduling of requests from large language models (LLM)<n>We present a novel scheduling algorithm with optimal time complexity, designed to minimize the overall waiting time in LLM-based prompt scheduling.
  arXiv  Detail & Related papers  (2025-06-13T20:15:58Z)
• Causally Aligned Curriculum Learning [69.11672390876763]
  This paper studies the problem of curriculum RL through causal lenses.<n>We derive a sufficient graphical condition characterizing causally aligned source tasks.<n>We develop an efficient algorithm to generate a causally aligned curriculum.
  arXiv  Detail & Related papers  (2025-03-21T02:20:38Z)
• Haste Makes Waste: Evaluating Planning Abilities of LLMs for Efficient and Feasible Multitasking with Time Constraints Between Actions [56.88110850242265]
  We present Recipe2Plan, a novel benchmark framework based on real-world cooking scenarios.<n>Unlike conventional benchmarks, Recipe2Plan challenges agents to optimize cooking time through parallel task execution.
  arXiv  Detail & Related papers  (2025-03-04T03:27:02Z)
• Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags [3.723602673856398]
  This study investigates scheduling strategies for the resource-constrained project scheduling problem with maximal time lags (SRCPSP/max)<n>Recent advances in Constraint Programming (CP) and Temporal Networks have reinvoked interest in evaluating the advantages and drawbacks of various proactive and reactive scheduling methods.
  arXiv  Detail & Related papers  (2024-09-13T15:01:25Z)
• The Road Less Scheduled [45.01813613035411]
  Existing learning rate schedules that do not require specification of the optimization stopping step T are greatly out-performed by learning rate schedules that depend on T. We propose an approach that avoids the need for this stopping time by eschewing the use of schedules entirely. Our Schedule-Free approach introduces no additional hyper- parameters over standard schedules with momentum.
  arXiv  Detail & Related papers  (2024-05-24T16:20:46Z)
• Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
  Job-Shop Scheduling Problem (JSSP) is a optimization problem where tasks need to be scheduled on machines in order to minimize criteria such as makespan or delay. This paper introduces a new approach that leverages Deep Reinforcement Learning (DRL) techniques to search for robust solutions.
  arXiv  Detail & Related papers  (2024-03-04T08:38:55Z)
• Job Shop Scheduling via Deep Reinforcement Learning: a Sequence to Sequence approach [0.0]
  This paper presents an end-to-end Deep Reinforcement Learning approach to scheduling that automatically learns dispatching rules. We show that we outperform many classical approaches exploiting priority dispatching rules and show competitive results on state-of-the-art Deep Reinforcement Learning ones.
  arXiv  Detail & Related papers  (2023-08-03T14:52:17Z)
• Dynamic Scheduling for Federated Edge Learning with Streaming Data [56.91063444859008]
  We consider a Federated Edge Learning (FEEL) system where training data are randomly generated over time at a set of distributed edge devices with long-term energy constraints. Due to limited communication resources and latency requirements, only a subset of devices is scheduled for participating in the local training process in every iteration.
  arXiv  Detail & Related papers  (2023-05-02T07:41:16Z)
• Generating Dispatching Rules for the Interrupting Swap-Allowed Blocking Job Shop Problem Using Graph Neural Network and Reinforcement Learning [21.021840570685264]
  The interrupting swap-allowed blocking job shop problem (ISBJSSP) is able to model many manufacturing planning and logistics applications realistically. We introduce a dynamic disjunctive graph formulation characterized by nodes and edges subjected to continuous deletions and additions. A simulator is developed to simulate interruption, swapping, and blocking in the ISBJSSP setting.
  arXiv  Detail & Related papers  (2023-02-05T23:35:21Z)
• Scheduling Inference Workloads on Distributed Edge Clusters with Reinforcement Learning [11.007816552466952]
  This paper focuses on the problem of scheduling inference queries on Deep Neural Networks in edge networks at short timescales. By means of simulations, we analyze several policies in the realistic network settings and workloads of a large ISP. We design ASET, a Reinforcement Learning based scheduling algorithm able to adapt its decisions according to the system conditions.
  arXiv  Detail & Related papers  (2023-01-31T13:23:34Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• Towards Standardizing Reinforcement Learning Approaches for Stochastic Production Scheduling [77.34726150561087]
  reinforcement learning can be used to solve scheduling problems. Existing studies rely on (sometimes) complex simulations for which the code is unavailable. There is a vast array of RL designs to choose from. standardization of model descriptions - both production setup and RL design - and validation scheme are a prerequisite.
  arXiv  Detail & Related papers  (2021-04-16T16:07:10Z)
• Smart Scheduling based on Deep Reinforcement Learning for Cellular Networks [18.04856086228028]
  We propose a smart scheduling scheme based on deep reinforcement learning (DRL) We provide implementation-friend designs, i.e., a scalable neural network design for the agent and a virtual environment training framework. We show that the DRL-based smart scheduling outperforms the conventional scheduling method and can be adopted in practical systems.
  arXiv  Detail & Related papers  (2021-03-22T02:09:16Z)

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.