TL;DR
This paper introduces a new, more realistic scheduling problem called HM-RCPSP/L-C, which accounts for learning effects (activities get faster with repetition) and compound activities (groups of smaller tasks). They developed a Constraint Programming model and a heuristic search strategy to solve it, showing promising results on satellite production data.
What Problem Does This Paper Address?
The paper tackles the challenge of scheduling multiple, similar projects that share limited resources, a problem known as the High Multiplicity Resource-Constrained Project Scheduling Problem (HM-RCPSP). The authors extend this by incorporating two crucial real-world complexities:
- Learning Effect: In many manufacturing settings, workers become more efficient with repetition, making tasks faster over time. This "learning curve" phenomenon significantly impacts production timelines.
- Compound Activities: Complex tasks are often composed of several smaller, sequential or parallel sub-tasks. Representing these as single, higher-level activities simplifies modeling and resource management.
The authors aim to create a more accurate scheduling model for industries like satellite production, where these factors are significant.
Methods
The paper proposes two main approaches to solve the newly defined HM-RCPSP/L-C problem:
- Constraint Programming (CP) Model: They developed an interval-based CP model using OPL and CP Optimizer. This model incorporates constraints for precedence, resource capacity, and importantly, the learning effect (using a log-linear learning curve) and compound activities. A key innovation here is a symmetry-breaking technique to handle identical activities across different projects, significantly improving performance.
- Squeaky Wheel Optimization (SWO): This is a heuristic-based search strategy that iteratively builds and improves solutions. It uses a greedy algorithm with a novel project selection heuristic that considers project due dates and remaining critical path lengths.
These approaches can be used independently or combined in a hybrid approach (SWO for an initial solution, then CP to refine it).
Datasets
The authors evaluated their methods on two datasets:
- PSP-based Dataset: Created from existing RCPSP instances (from PSPLIB), this dataset was adapted to include multiple projects and learning effects. It does not include compound activities.
- Satellite Dataset: This dataset is based on real-world data from a satellite manufacturer, incorporating compound activities and learning effects. They also created larger instances by increasing the number of classes, projects, and the time horizon.
Key Insights and Ideas
- Realism in Scheduling: The paper highlights that traditional RCPSP models are insufficient for complex manufacturing like satellite production, where learning effects and compound activities are critical for accurate scheduling.
- Symmetry Breaking is Crucial: For identical activities across different projects, the authors demonstrate that breaking symmetries is essential for the CP approach to perform efficiently, especially on industrial instances.
- Learning Curves Impact Timelines: The learning effect can significantly alter project completion times, making it vital to account for it in planning.
- Compound Activities Simplify Resource Management: Representing complex tasks as compound activities allows for more abstract reasoning about resource consumption over the entire duration of the group of sub-tasks.
Key Results
- CP Performance Boosted by Symmetry Breaking: On the satellite dataset, the CP approach with symmetry breaking (LCSB) significantly outperformed the basic CP model (LC), especially in terms of finding better solutions within reasonable timeframes.
- Hybrid Approach Shows Promise: The hybrid approach (HYB), combining SWO's speed with LCSB's refinement, achieved the best overall performance on the PSP-based dataset in the 15-second test.
- SWO Excels in Large Instances (Low Timeout): SWO demonstrated strengths in handling large instances within short time limits, though its makespan values were not always optimal.
- Zero Tardiness Achieved: For the original satellite instances, all approaches achieved zero tardiness within 15 seconds.
- LCSB Outperforms on Extended Satellite Instances: For more challenging extended satellite instances, LCSB clearly outperformed other methods in minimizing tardiness and often makespan.
Limitations and Future Work
- Learning Effect Across Classes: The current model assumes learning effects are confined within activities of the same class. Future work could explore learning effects shared across similar activities in different classes, creating interdependencies between projects of different types.
- Uncertainty in Learning Efficiency: The paper uses a deterministic learning curve. Investigating how to handle uncertainty in learning efficiency would enhance schedule robustness.
- Optimality Not Always Proven: While good solutions were found, the optimality of these solutions was not always proven within the experimental timeouts.
Summary updated