Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags

Kim van den Houten, Léon Planken, Esteban Freydell, David M. J. Tax, Mathijs de WeerdtAAAI 2025 · DOI

TL;DR

This paper introduces novel proactive and reactive scheduling methods for the complex Stochastic Resource-Constrained Project Scheduling Problem with Maximal Time-Lags (SRCPSP/max). By leveraging advances in Constraint Programming and Temporal Networks, they demonstrate that a STNU-based approach significantly outperforms existing methods in solution quality, while also offering competitive computation times.

What Problem Does This Paper Address?

Real-world project scheduling often involves uncertainty in activity durations and strict temporal constraints, such as minimal and maximal time lags between tasks. The Stochastic Resource-Constrained Project Scheduling Problem with Maximal Time-Lags (SRCPSP/max) captures this complexity. Existing approaches to SRCPSP/max fall into two main camps: proactive (finding a robust schedule offline) and reactive (adapting the schedule online). However, a comprehensive comparison of these methods, particularly incorporating recent advancements in Constraint Programming (CP) and Temporal Networks, has been lacking. This paper aims to fill this gap by proposing and evaluating new CP-based proactive and reactive methods, alongside a novel STNU-based approach, to provide a clearer understanding of their trade-offs in terms of solution quality, feasibility, and computation time.

Methods

The authors propose three new methods for SRCPSP/max:

  • Proactive (proactive_saa): This method extends the Sample Average Approximation (SAA) approach, commonly used for stochastic optimization, by employing a CP model instead of Mixed Integer Programming (MIP). It aims to find a schedule that is feasible for a set of sampled scenarios, minimizing the average makespan. A simplified version, proactive_0.9, uses a single quantile of the duration distribution to approximate the a-robust makespan, making it computationally cheaper.
  • Reactive (reactive): This approach implements a fully reactive strategy using a deterministic CP model. At each decision point (when an activity finishes), the system reschedules the remaining activities. This method is inspired by industrial practice where decisions are often made based on the latest information, despite concerns about computational cost and schedule stability in prior research.
  • STNU-based (stnu): This novel method combines partial order schedules (POS) with Simple Temporal Networks with Uncertainty (STNU). It first constructs a POS using a fixed-point schedule and chaining heuristics. This POS is then translated into an STNU, which is tested for dynamic controllability (DC). If DC, the STNU is fed into a Real-Time Execution (RTE*) algorithm to generate a schedule. This approach leverages recent advances in temporal networks to handle uncertainty.

Datasets

The paper evaluates the proposed methods on benchmark instances from the PSPlib library, specifically the j10, j20, j30, ubo50, and ubo100 sets. These deterministic instances are transformed into stochastic versions by introducing uncertainty in activity durations, modeled as discrete uniform distributions. The noise level is controlled by a parameter ε, with values of 1 and 2 used for evaluation. The authors sampled 10 times for each instance to generate stochastic scenarios.

Key Insights and Ideas

  • CP's Advantage: The paper reinforces the growing trend of CP outperforming MIP for scheduling problems, even in stochastic settings, by demonstrating a CP-based SAA approach.
  • Reactive Rescheduling is Viable: Contrary to previous assumptions about computational burden, a reactive approach with complete rescheduling can yield better solution quality than purely proactive methods, especially when leveraging modern CP solvers.
  • STNU-based Approach Dominates: The STNU-based method, which integrates partial order schedules with temporal networks, emerges as the superior approach for solution quality (makespan minimization). This highlights the power of explicitly modeling temporal uncertainty and dynamic controllability.
  • Feasibility is Crucial: The paper emphasizes the importance of considering feasibility ratios alongside solution quality and computation time, especially when comparing methods that may fail on certain instances.
  • Trade-offs Exist: While the STNU-based method excels in solution quality, proactive methods (proactive_0.9 and proactive_saa) generally offer better offline and online computation times, making them suitable for scenarios where speed is paramount.

Key Results

  • Solution Quality: The STNU-based method (stnu) consistently achieved the best solution quality (lowest makespan) across various instance sets and noise levels. For example, on ubo50 with ε=1, stnu had an average makespan of 0.958 compared to 1.015 for the reactive method, indicating a significant advantage.
  • Feasibility: For ε=1, the proactive methods (proactive_saa, proactive_0.9) and reactive showed similar feasibility ratios, while stnu was slightly lower. However, for ε=2 (higher variance), stnu achieved the highest feasibility ratios, demonstrating its robustness to larger duration uncertainties.
  • Computation Time: Proactive methods (proactive_0.9 and proactive_saa) generally had the lowest relative offline and online runtimes. The stnu method's online performance was competitive due to its polynomial-time execution algorithm, outperforming the reactive method which relies on repeatedly solving a deterministic CP model.
  • Statistical Significance: Wilcoxon and proportion tests confirmed significant differences in performance between methods, allowing for the construction of partial orderings that summarize these findings.

Limitations and Future Work

  • Limitations: The paper notes that the STNU-based method's feasibility ratio can be lower than others for smaller noise levels, and the distinction between strong and weak partial orderings was omitted in figures for brevity. The authors also acknowledge that the reactive method's performance is sensitive to the rescheduling time limit.
  • Future Work: The authors suggest extending the evaluation to other scheduling problems and practical scenarios. Investigating end-to-start temporal constraints and exploring probabilistic STNs are identified as interesting future research directions. Additionally, incorporating sequential approaches or machine learning-based methods (like graph neural networks) for SRCPSP is proposed as a way to broaden the set of methods for comparison.

Summary updated

BibTeX
@inproceedings{houten2025proactive,
  author = {Kim van den Houten and Léon Planken and Esteban Freydell and David M. J. Tax and Mathijs de Weerdt},
  title = {{Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34854},
}
Figure