Research map / Learning theory and algorithms / Combinatorial and search optimization
Proactive and Reactive Constraint Programming for Stochastic Project Scheduling with Maximal Time-Lags
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Benchmarks new CP-based proactive (SAA), CP-based fully reactive (rescheduling), and STNU/partial-order-schedule methods for SRCPSP/max using statistical tests that treat infeasibility explicitly, finding the STNU method best on solution quality.
Problem
Stochastic resource-constrained project scheduling with maximal time lags (SRCPSP/max), where stochastic durations can violate time-lag or resource constraints, and methods are hard to compare when some fail to produce feasible schedules.
Approach
Formulates proactive SAA and fully reactive rescheduling with interval-variable CP (IBM CP Optimizer), and an STNU-based partial order schedule executed via RTE* after a dynamic controllability check; compares them with statistical tests that assign infinite cost to infeasible runs.
Key results
- The STNU-based method achieved the best solution quality (makespan) in the pairwise tests, e.g. normalized average 0.985 vs 1.015 for the reactive method on ubo50 with epsilon=1.
- The STNU method had the lowest feasibility ratio for epsilon=1 (e.g. 0.65 on j10 vs 0.85 for SAA and proactive), but the highest feasibility for epsilon=2 on ubo50 and ubo100 (0.67 and 0.79).
- Proactive gamma=0.9 and reactive methods had the lowest offline runtime; SAA and proactive methods had the lowest online runtime, while STNU online time was polynomial via RTE*.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the STNU-based partial-order scheduling method instead of the alternatives | SRCPSP/max scheduling methods · Across evaluated instance sets and noise levels | makespan: STNU: 0.985; Reactive: 1.015 | Helped |
| Add online rescheduling to proactive γ=0.9 scheduling | Proactive γ=0.9 · Across evaluated instance sets and noise levels | makespan | Helped |
| Use SAA with multiple smart samples instead of the single γ=0.9 quantile | Proactive scheduling · Across evaluated instance sets | makespan | Mixed |
| Use STNU rather than SAA or Proactive γ=0.9 | SRCPSP/max scheduling methods · ε=2, ubo50 and ubo100 | feasibility ratio: 0.67 vs 0.41 and 0.42; 0.79 vs 0.35 and 0.36 | Helped |
| Use the STNU method rather than the other methods | SRCPSP/max scheduling methods · ε=1, j10–ubo100 | feasibility ratio: j10: 0.65 vs 0.85; j20: 0.65 vs 0.76; j30: 0.78 vs 0.89; ubo50: 0.77 vs 0.86; ubo100: 0.84 vs 0.91 | Hurt |
| Use Proactive γ=0.9 rather than SAA | Proactive scheduling · ubo100, ε=1 | makespan | No clear effect |
| Increase the proactive single-sample quantile from γ=0.5 to γ=0.9 (ablation) | Proactive method · j10, tuning subset | feasibility ratio: 0.11 -> 0.94 | Helped |
| Increase the proactive single-sample quantile from γ=0.5 to γ=0.9 (ablation) | Proactive method · ubo50, tuning subset | feasibility ratio: 0 -> 0.92 | Helped |
| Increase the number of proactive multiple samples from n=5 to n=50 (ablation) | Proactive SAA · j10, tuning subset | feasibility ratio: 0.63 -> 0.94 | Helped |
| Increase the number of proactive multiple samples from n=5 to n=50 (ablation) | Proactive SAA · ubo50, tuning subset | feasibility ratio: 0.12 -> 0.91 | Helped |
| Increase the proactive SAA time limit from 600s to 3600s (ablation) | SAA with four scenarios · ubo50 and ubo100, tuning subset | average makespan: ubo50: 232 -> 231; ubo100: 480 -> 472 | Helped |
| Increase the reactive rescheduling time limit from 1s to 30s (ablation) | Reactive · j10, tuning subset | makespan: 38 -> 39 | Hurt |
Surprising findings
- The STNU-based partial order schedule outperformed the state-of-the-art proactive SORU-H-style methods on solution quality, contrary to earlier assumptions that proactive methods are best.
- Fully reactive rescheduling with CP outperformed the proactive approaches on solution quality despite being considered impractical.
Limitations
- STNU method has the lowest feasibility ratio at epsilon=1 on several instance sets.
- Infeasible runs are assigned infinite time or quality, so results depend on the test design and feasibility affects Wilcoxon outcomes.
- Only discrete uniform duration distributions with PSPlib-derived noise are evaluated; end-to-start constraints are left to future work.
Experimental setup
Datasets: PSPlib j10 PSPlib j20 PSPlib j30 PSPlib ubo50 PSPlib ubo100
Benchmarks: PSPlib j10 PSPlib j20 PSPlib j30 PSPlib ubo50 PSPlib ubo100
Metrics: feasibility ratio makespan solution quality offline computation time online computation time Wilcoxon test proportion test magnitude t-test
Baselines: SORU-H BACCHUS SAA with multiple scenarios (CP) Proactive gamma=0.9 (CP) Fully reactive rescheduling (CP)
Builds on: SORU SORU-H RTE* Sample Average Approximation partial order schedules
Closest papers by meaning
- A Proactive Sampling Approach to Project Scheduling under Uncertainty (AAAI 2016 · similarity 0.86)
- Dynamic Control of Probabilistic Simple Temporal Networks (AAAI 2020 · similarity 0.83)
- Risk-Aware Proactive Scheduling via Conditional Value-at-Risk (AAAI 2018 · similarity 0.83)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.82)
- Abstract Action Scheduling for Optimal Temporal Planning via OMT (AAAI 2024 · similarity 0.80)
- Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.79)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.