Learning Effect and Compound Activities in High Multiplicity RCPSP: Application to Satellite Production

Duc Anh Le, Stéphanie Roussel, Christophe Lecoutre, Anouck ChanCP 2024 · OpenReview

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:

  1. 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.
  2. 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

Abstract

This paper addresses the High Multiplicity Resource-Constrained Project Scheduling Problem (HM-RCPSP), in which multiple projects are performed iteratively while sharing limited resources. We extend this problem by integrating the learning effect, which makes the duration of some activities decrease when they are repeated. Learning effect can be represented by any decreasing function, allowing us to get flexibility in modeling various scenarios. Additionally, we take composition of activities into consideration for reasoning about precedence and resources in a more abstract way. A Constraint Programming model is proposed for this richer problem, including a symmetry-breaking technique applied to some activities. We also present a heuristic-based search strategy. The effectiveness of these solving approaches is evaluated through an experimentation conducted on data concerning real-world satellite assembly lines, as well as on some adapted literature benchmarks. Obtained results demonstrate that our methods serve as robust baselines for addressing this novel problem (denoted by HM-RCPSP/L-C).
BibTeX
@inproceedings{le2024learning,
  author = {Duc Anh Le and Stéphanie Roussel and Christophe Lecoutre and Anouck Chan},
  title = {{Learning Effect and Compound Activities in High Multiplicity RCPSP: Application to Satellite Production}},
  booktitle = {CP},
  year = {2024},
  url = {https://openreview.net/forum?id=qQUV3UYbc0},
}

Loading related content...

Figure