Learning to Solve Resource-Constrained Project Scheduling with Duration Uncertainty using GNNs

Quick Overview

The Wheatley AI scheduling system successfully solves resource-constrained project scheduling problems under duration uncertainty by using a novel approach that combines Deep Reinforcement Learning (DRL) with a novel GNN-based approach, significantly outperforming traditional heuristics like Shortest Processing Time (SPT) and CP50 by achieving a notably lower expected makespan across various test cases, including a large-scale, real-world industrial dataset.

Key Points: Wheatley, an AI scheduling method combining DRL and GNNs, addresses Resource-Constrained Project Scheduling with Duration Uncertainty (RCPSP-DU). Wheatley outperformed traditional heuristics like Shortest Processing Time (SPT) and CP50, achieving a 1.3% lower expected makespan compared to the best solutions found by CP50. The core innovation involves using a novel GNN structure to encode complex, multi-perspective information (precedence, resource constraints, probability distributions) into resource nodes. The DRL agent learns a Priority Dispatch Rule (PDR) that intelligently selects the next task based on future uncertainty and available resources, avoiding the pitfalls of simple rules. In a large-scale test case involving 120 jobs from a public industrial dataset, Wheatley successfully found robust, feasible schedules that traditional solvers failed to solve within the 60-second time limit. Wheatley embeds resilience directly into the scheduling decision, allowing it to anticipate and mitigate potential future resource conflicts before they occur.

Context: The video discusses a new Artificial Intelligence approach, named Wheatley, designed to tackle the complex problem of Resource-Constrained Project Scheduling with Duration Uncertainty (RCPSP-DU). This problem is common in sectors like aerospace manufacturing and logistics where project schedules must account for unknown task durations while respecting resource limits. Traditional methods often rely on reactive scheduling or simple heuristics, which perform poorly when uncertainty is high, leading to schedule breakdowns and operational nightmares.