Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem

Ignace Bleukx, Ryma Boumazouza, Tias Guns, Nadine Laage, Guillaume PovédaCP 2025 · DOI

TL;DR

This paper tackles the complex industrial challenge of assigning teams to logistical tasks in aircraft manufacturing, aiming for efficient allocation and fair workload distribution. They introduce Constraint Programming (CP) models and novel techniques for explaining and restoring schedules when disruptions occur, offering valuable decision support for human planners.

What Problem Does This Paper Address?

The core problem is optimizing workforce allocation and scheduling for logistical operations in a large-scale aircraft manufacturing environment. This involves assigning available teams to numerous tasks, each with specific release times, durations, and deadlines. Key challenges include:

  • Scale: The problem involves hundreds of tasks daily.
  • Fairness: Ensuring an equitable distribution of workload among teams is crucial.
  • Disruptions: Unforeseen events like technical malfunctions, weather, or resource unavailability can invalidate schedules, requiring rapid understanding and correction.
  • Manual Effort: Currently, human planners manually manage these complex schedules, which is time-consuming and prone to errors, especially when dealing with disruptions.

The authors aim to automate parts of this process and provide decision support to help planners manage disruptions more effectively.

Methods

The paper proposes several key methodological contributions:

  • Constraint Programming (CP) Models: They develop and compare different CP models for both the pure allocation problem (tasks with fixed times) and the scheduling-allocation problem (tasks with flexible time windows).
  • Workload Balancing: Special attention is given to modeling the "time-dispersion" objective, which quantifies the difference between the maximum and minimum time worked by teams, to ensure fairness. They explore various formulations for this objective.
  • Symmetry Breaking: To improve solver efficiency, they introduce techniques to break symmetries between equivalent teams.
  • Explainable Constraint Solving: For handling disruptions, they leverage techniques from explainable AI:
  • Minimal Unsatisfiable Subsets (MUSes): Used to explain why a schedule becomes infeasible after a disruption by identifying the minimal set of conflicting constraints.
  • Minimal Correction Subsets (MCSes): Used to suggest a minimal set of constraints to relax or remove to restore feasibility.
  • Feasibility Restoration: They propose methods to automatically repair disrupted schedules. This includes:
  • MCS-based Restoration: Removing tasks or allocation constraints.
  • Multi-Objective Rescheduling: Converting the problem into a Lexicographic Multi-Objective Constraint Optimization Problem (LMOCOP) to find alternative schedules that are "close" to the original, balancing objectives like minimizing re-allocated tasks, shifted tasks, and total shift time.

Datasets

The paper does not explicitly mention using pre-existing datasets for training. Instead, they generate instances for their use case, simulating an 8-hour shift over a three-month period, with an average of 67.6 tasks per shift. They also introduce a disruption generator to create various realistic disruption scenarios for evaluating their explanation and restoration techniques. All models and instances are made publicly available.

Key Insights and Ideas

  • Modeling Matters for Fairness: Different formulations of the time-dispersion objective significantly impact solver performance, even if optimality isn't always proven. Exact formulations, despite not always reaching optimality, perform well in practice for achieving fair schedules.
  • Symmetry Breaking is Crucial for Allocation: Breaking symmetries between equivalent teams dramatically improves the efficiency of CP and Pseudo-Boolean solvers for the allocation problem.
  • Lower Bounds Aid Scheduling: For the more complex scheduling problem, adding a lower bound derived from a relaxed problem significantly boosts solver performance and the ability to prove optimality.
  • Explainability is Practical: MUSes and MCSes can be computed efficiently for this industrial problem, providing actionable insights to human planners about why a schedule failed and how to fix it.
  • Rescheduling Offers Nuance: Beyond simply removing tasks (MCS), multi-objective rescheduling allows for finer-grained adjustments, finding alternative schedules that minimize changes from the original, which is often more desirable than drastic removals.

Key Results

  • Allocation Efficiency: With symmetry breaking, OR-Tools and Exact solvers can solve a large portion of the allocation instances to optimality. Gurobi consistently solves all instances quickly, though it doesn't benefit from symmetry breaking.
  • Time Dispersion: While proving optimality for time dispersion is challenging, solvers achieve good dispersion values (around 15 minutes on average) within seconds.
  • Scheduling Improvement: Adding a lower bound to the scheduling problem significantly improves the number of instances solved to optimality, with the lower bound often being proven optimal for the relaxed problem.
  • Explanation Computation: MUSes and MCSes can be computed quickly (under 1 second on average for MCSes). SHRINK is a good choice for computing MUSes due to its speed and comparable explanation size to SMUS.
  • Feasibility Restoration: Fine-grained rescheduling using multi-objective optimization leads to fewer dropped tasks (around 1 task on average) compared to MCS-based restoration (around 6 tasks). The order of objectives in the LMOCOP significantly influences the trade-off between re-allocating and shifting tasks.

Limitations and Future Work

  • Optimality Proofs: Proving optimality for time-dispersion and scheduling problems remains a challenge, though practical solutions are found quickly.
  • Generalization: The authors plan to extend their formulation to a full allocation-and-routing problem, which is more complex.
  • User Study: A crucial next step is a user study to evaluate the practical effectiveness of the generated explanations and restoration techniques for human planners. This will help tune the explanations and learn planner preferences.
  • Robustness: Exploring robust scheduling solutions that remain feasible even when parameters change is a future direction.
  • Scheduling Explanations: Extending the explainability techniques to the full scheduling variant (with flexible task times) is a significant future challenge, especially concerning global constraints.

Summary updated

BibTeX
@inproceedings{bleukx2025modeling,
  author = {Ignace Bleukx and Ryma Boumazouza and Tias Guns and Nadine Laage and Guillaume Povéda},
  title = {{Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem}},
  booktitle = {CP},
  year = {2025},
  doi = {10.4230/lipics.cp.2025.6},
}
Figure