Modeling and Explaining an Industrial Workforce Allocation Problem (Extended Abstract)

1 Introduction

The assignment of workers to different tasks is a recurring challenge in many industries. Effective allocation of workers directly impacts key business metrics such as productivity, cost management, and overall organizational performance. Solving an industrial workforce allocation problem requires considering several factors such as such as employee availability, required qualifications of workers for a task, regulatory requirements, and task priorities.

We address the problem of workforce allocation for logistical tasks among worker teams at an aircraft manufacturing site, where hundreds of tasks need to be allocated on a daily basis. These logistical tasks are interleaved with production activities on assembly lines [Boysen et al., 2022], and need to be aligned with timings of higher-level logistics involving deliveries of raw materials or components provided by external parties via trucks, ships, or cargo aircraft. Delivered components then have to be transported to internal hangars at the right time, where they will be assembled with other aircraft parts. We incorporate these operational requirements into the allocation and scheduling problem as part of the input data. More specifically, each task has a predefined release time, duration, and deadline, and certain tasks share precedences. E.g., when two parts must be delivered in sequence before assembly. Apart from explicit precedence constraints, there are no requirements on the task ordering, as the duration of any task includes returning to the home base of the manufacturing plant. Hence, the transition time between the end location of one task and the starting location of the next is included in the duration of each task. This differs from the traditional definition of a workforce-scheduling and routing problem (WSRP) [Castillo-Salazar et al., 2016] and allows to formulate the problem as a pure scheduling problem instead.

∗The original paper won the Best Application Paper award at the CP'25 conference [Bleukx et al., 2025]

The goal is to find an allocation of tasks to working teams, such that the total number of required teams is minimized. Additionally, the workload should be distributed fairly among the teams. That is, the allocation of tasks should be done such that all teams do a similar amount of work.

Currently, transportation tasks are manually allocated and scheduled by a team of planners. These planners also coordinate the fine-grained synchronization among teams to ensure dependencies between tasks are satisfied. During the working day, they continuously monitor real-time updates and adjust schedules as needed to handle unforeseen disruptions. Such disruptions can arise for multiple reasons, including:

• Weather-related: Extreme wind or rain prevents the use of some hangars.
• External logistics: Delays or cancellations from suppliers impact the arrival time of essential parts.
• Human resource: Unexpected worker absences or team meetings temporarily reduce workforce availability.
• Material availability: Vehicles like trucks or trailers may become temporarily unavailable due to technical breakdowns, accidents or maintenance operations.

Large disruptions can impact the predefined plan in such a way that the set of disrupted tasks cannot be reallocated to other teams. This requires the planners to revise the plan, which may involve multiple re-allocation and/or rescheduling operations. As this is tedious and time-consuming to do by hand, planners often drop disrupted tasks from the current planning horizon and move them to the next one. To help the planners revise the allocation more efficiently, we propose to automatically repair disrupted schedules and show several alternatives to the planners [Senthooran et al., 2023]. This allows them to further adapt or merge alternatives based on their experience and knowledge about the problem.

2 ACP-model forWorkforce Allocation

We propose to solve this complex scheduling and allocation problem using Constraint Programming. The model needs to solve two aspects of the problem: (1) allocate each task to a compatible team, and (2) schedule all tasks such that those tasks assigned to the same team do not overlap. I.e., such that each team executes at most one task at the same time. For objectives, we require a minimal number of worker teams in the schedule and a fair workload distribution. In what follows, we discuss the input data, the mathematical formulation of the constraints and objectives, and one advanced modeling technique to improve the runtime of the solver.

Input data

• T : a set of n tasks to assign to teams.
• W: a set of mworker-teams to assign tasks to.
• Comp ∈ Bn×m where Compt,w indicates team w and task t are compatible.
• D: the fixed durations of each task, with di ∈ D the duration of task i.
• G: set of task clusters where tasks in cluster g ⊆ T should be executed by the same team.
• R: set with the release time of each task.
• E: set with the deadline of each task.
• Prec: a set of precedence tuples (t, t′ ).
• Calw: a set of tuples (cs, cd) that represent intervals during which team w is off-duty.

Decision variables and constraints Our model is inspired by flexible-jobshop problems [Beck and Fox, 2000], where a set of jobs (tasks) need to be scheduled on a compatible resource (a worker team). To indicate which team a task is assigned to, we use a n×m Boolean matrix with variables xt,w indicating task t is assigned to team w. To model the scheduling aspect of the problem, we rely on scheduling-specific global constraints developed by the CP community [van Hoeve and Katriel, 2006]. These global constraints reason over uninterruptible tasks, which are represented as interval variables INTERVAL(s, d) with an integer variable start s and an integer variable d as duration. An extension to interval variables is optional intervals OPTINTERVAL(s, d, p) where Boolean variable p indicates whether the task is present or absent in the schedule [Laborie et al., 2009]. In our model, we duplicate each task for each team using an optional interval, and determine whether the interval is present in the solution using the variable xt,w.

Each task is allocated to a team:

Tasks are only assigned to compatible teams:

All tasks in cluster g are assigned to the same team:

Tasks are scheduled within their allowed time frame:

Enforce precedences between tasks:

Teams cannot perform overlapping tasks and can only work when available.

Auxiliary variables and objectives We introduce auxiliary variables usedw ∈ Bm that indicate whether team w is used, and integer variables timew ∈ Nm that indicate the time worked by each team. These auxiliary variables relate to the decision variables x as follows:

A team is used if a task is allocated to it:

Definition of the time worked by a team, only enforced if the team is used:

We consider two objectives in the problem: the number of teams used and the fairness of the schedule, formulated as time dispersion, which is the difference between the maximum and minimum workload of any pair of teams. This corresponds to a spread-based fairness measure from the literature [Chen and Hooker, 2021; D¨onmez et al., 2023]. Formally, our model becomes a bi-objective lexicographic minimization problem with primary objective ∑w∈W usedw and secondary objective maxw∈W timew - minw∈W timew.

Redundant constraints During experimentation, we found that when minimizing the number of required teams, the solver is often stuck on proving optimality of the solution. That is, a solution was found with an optimal objective value, but the solver could not determine a better solution cannot exist. We want to help the solver by enforcing a reasonable lower-bound on the number of teams. This is done by adding a redundant or implied constraint to the problem, which is common in CP [Smith, 2006]. For our setting, we add the following CUMULATIVE constraint to the problem.

This constraint effectively treats each team as equivalent and ignores any team-task compatibility or calendar restrictions. This allows to model the set of worker teams as a pooled resource, with a capacity equal to the number of teams that are actually working. Clearly, any solution to the original model also satisfies this constraint, as it is relaxation of the original model. Efficient propagators for the CUMULATIVE constraint can efficiently compute lower bounds on the capacity of this resource [Schutt et al., 2011], which for our problem means the solver can efficiently derive a lower-bound on the objective of the optimization problem.

3 Explaining and Resolving Disruptions

We now outline our efforts to develop an explainable decision-making tool for the allocation-and-scheduling problem, with the potential for generalization to similar use cases. Our primary application of explanation techniques will be to handle disruptions, which invalidate the precomputed schedule and require the planner to re-allocate and/or re-schedule a subset of the tasks. We here focus on resolving disruptions in the schedule using automatic re-allocation and shifting of tasks, while more elaborate explanation techniques are discussed in the full version of our paper [Bleukx et al., 2025].

3.1 Disruption scenarios

From the planner's perspective, the scenario is as follows: an initial schedule is established for the upcoming shift, with an estimate of available teams. This schedule can be computed using the CP model from the previous section or it can be manually constructed by the planners. As discussed previously, various disruptions can affect the plan and possibly make the foreseen allocation infeasible. In response, the planner must adapt and reallocate the tasks to available resources such that as many tasks as possible can still be executed, without wasting resources. To do so, the planners will try to reallocate tasks to other, free teams. However, in practice, this is often not possible as task-compatible teams are usually already occupied with other tasks. Instead, some tasks need to be delayed in order to free up a worker team in the required time window. However, this process is tedious and time-consuming for planners to do by hand; as all operational constraints must remain satisfied during the rescheduling process. Instead, we propose to automatically revise the schedule, as outlined in the next section.

3.2 Automated rescheduling

To restore the feasibility of the schedule after a disruption, we can, in theory, simply rerun the solver with the changed input data. E.g., by changing a team's availability for a certain time window during which the duration happened. However, the resulting solution may be significantly different from the current schedule, and several teams and tasks will be impacted by the revised schedule. Inspired by classic feasibility restoration and re-planning approaches [Fox et al., 2006; Senthooran et al., 2023], we instead propose to re-optimize the schedule, while staying close to the one that was originally constructed. More specifically, based on the original assignment α, we define several similarity objectives. These objectives ensure the new solution is as similar as possible to the original assignment. We define five such similarity objectives, which minimize the number of re-allocated tasks, the number of delayed tasks, and the magnitude of delays.

Maximize the number of tasks that are allocated:

Minimize the number of tasks that are re-allocated:

Minimize the number of shifted tasks:

Minimize the total shift in time of the tasks:

Minimize the maximum shift in time of the tasks:

Instead of optimizing only one of these similarity objectives, we combine them into a Lexicographic MultiObjective Optimization Problem (LMOCOP) [Schaus and Hartert, 2013; Cortes et al., 2023]. This allows us to adjust the ordering of objectives, which influences the final repaired schedules after disruptions. Figure 1 shows two repairs for different orders of the sub-objectives on the same instance. Depending on the ordering of the objectives, a different tradeoff between reallocating and rescheduling tasks is found.

By optimizing this multi-objective optimization problem for each order, we can present the decision maker with multiple alternatives on how to resolve the disruption. They can then pick one or combine alternatives to construct a final schedule.

4 Experimental Evaluation

In this section, we investigate the runtime performance of CP solvers for solving the large-scale workforce scheduling and allocation problem, and we evaluate our approach for automatically resolving disruptions. All code and benchmarks are available on github 1 .

4.1 Solving theWorkforce Allocation Problem

We first compare the runtime of the OR-Tools when considering a single objective: minimization of the number of teams. The left-hand side of Figure 2 shows a cactus plot, counting the number of solved instances within a given runtime. It is clear that the addition of the redundant cumulative constraint is essential for the solver to prove optimality of the solution. Indeed, the solver was able to solve 253 instances to optimality using the redundant constraint, compared to only 117 without.

Next, we compare the objective value over time found by the solver on the right-hand side of the figure. While optimal solutions were never found for our benchmark when considering both objectives, the figure clearly shows the solver finds a solution with a good objective value early on in the search. Indeed, after 10 seconds of solve-time, the time dispersion drops to 6.2 minutes on average.

4.2 Rescheduling after disruptions

We now investigate our method for restoring feasibility by computing fine-grained alterations to the schedule as described in Section 3.2. To evaluate our method in a broad range of disruption scenarios, we used a generator with adjustable parameters for simulating disruptions. These generator parameters were designed in coordination with the planning team to cover a range of realistic and complex scenarios that arise in their daily practice. We solve the lexicographic optimization problem by iteratively optimizing for each objective. For each solver call (one for each objective), we set a time limit of 5 seconds, such that the total time for feasibility restoration is limited to 25 seconds.

1 github.com/ML-KULeuven/Explainable-Workforce-Scheduling

Table 1 shows that by altering the order of the objectives, the resulting repaired schedule can be influenced significantly. As expected, there is a clear trade-off between shifting tasks and re-allocating tasks after a disruption. In "Reallocation first (A)", which prioritizes minimization of reallocated tasks, 8.37 tasks are re-allocated on average, while for the other orders between 22 and 23 tasks are re-allocated. Conversely, prioritizing minimization of shift-related metrics amounts to a lower number of shifted tasks (16-17) at the cost of more re-allocations.

Interestingly, optimizing the total magnitude of shifted tasks, results in less tasks that are shifted on average, compared to minimizing #shift directly. Further investigation reveals that this is due to #shift being a more difficult objective to optimize compared to sum-shift, thereby often reaching the time limit of 5s. Indeed, in only 60% of the instances, OR-Tools was able to provide an optimal solution when optimizing the #shift similarity objective first. In "Sum Shift First (C)", the sum-shift similarity objective was proven optimal in 80% of the instances and, by minimizing this simpler objective first, the resulting repaired schedule contains fewer shifted tasks overall.

5 Conclusion and FutureWork

We have presented a workforce-allocation and scheduling problem from the aircraft manufacturing industry. We have shown that, by using the right modeling techniques, CP solvers are able to find good solutions for this problem. In the future, we plan to adapt our model, allowing for direct transfers between locations, which requires extending the formulation to a full allocation-and-routing problem [CastilloSalazar et al., 2016]. Additionally, we have identified several disruption scenarios and investigated how to support a decision maker in resolving them efficiently. We deem it feasible to deploy such an interactive system as a decision support system for the planners. A future user study will enable us to further tune the type of explanations generated by the system, and, going further, could allow us to learn preferences of the planners in repairing the schedule [Guerreiro et al., 2023; Benabbou and Lust, 2019; Toffano et al., 2022].

Acknowledgments

This work was partially supported by the European Research and Innovation program TUPLES (101070149). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.