Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem

We address the problem of workforce allocation for logistical tasks among worker teams at an aircraft manufacturing site. These logistical tasks are interleaved with production activities on assembly lines [4], 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. These 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 follow precedence constraints, such as 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. As a result, 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) [5] and allows to formulate the problem as a pure scheduling problem instead. In our setting, 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 balanced fairly among the teams [12]. That is, the allocation of tasks should be done such that all teams have a similar amount of work.

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

• $\mathrm{■}$

  Weather-related disruptions: Extreme wind or rain prevents the use of some hangars.

• $\mathrm{■}$

  External logistics disruptions: Delays or cancellations from third-party suppliers impact the arrival time of essential parts.

• $\mathrm{■}$

  Human resource disruptions: Unexpected worker absences, team meetings or fire-drills in a hangar temporarily reduces workforce availability.

• $\mathrm{■}$

  Material availability disruptions: 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 re-scheduling operations. When disruption occurs, given than individual activity execution times range from 15 to 60 minutes, planners have a limited window to adjust schedules. As this is tedious and time-consuming to do by hand, planners often drop disrupted tasks from the current planning horizon and move it to a next one. In order to help the planners revise the allocation in a more efficient way, we propose to automatically repair disrupted schedules and show several alternatives to the planners. This allows them to further adapt or merge proposed alternatives based on their experience or other tacit knowledge.

We consider problems involving scheduling and allocating sets of tasks. The CP-community has developed several global constraints for such problems, and in this paper we use the NoOverlap (also called Disjunctive) and Cumulative global constraints. These global constrains reason over uninterruptible tasks, which are represented as intervals using an $\text{Interval}(s,d)$ variable with start $s$ and duration $d$. The $\text{NoOverlap}(I)$ constraint ensures intervals $I$ are scheduled such that they do not overlap. $\text{Cumulative}(I,D,c)$ is a generalization of this constraint where a set of intervals with a corresponding set of resource requirements $D$ are scheduled in such as manner that the total capacity $c$ of the resource is never exceeded [29, 32, 33].

An extension to interval variables was introduced by Laborie et al. [21], namely optional intervals. Such an interval is declared as $\text{OptInterval}(s,d,p)$ where the Boolean variable $p$ controls whether the interval (that is the task it represents) is present in the solution.

For explaining and resolving infeasible schedules due to disruptions, we will rely on techniques from explainable constraint solving. In particular, we compute Minimal Unsatisfiable Subsets (MUS) [23] to explain the user why the allocation problem is unsatisfiable after disruptions, and compute Minimal Correction Subsets (MCS) [24] to pinpoint the user to a set of constraints that should be relaxed or removed in order to resolve the conflicts in the problem.

Note that several MUSes may exist, and one may have a preference on which conflict to compute [20]. E.g., it is common to compute a smallest MUS [19], or optimal MUS [15].

Similar to MUSes, a problem may contain multiple MCSes. To find an optimal MCS, we can reify each constraint and minimize the number of falsified indicator variables.

This problem consists of assigning each task to a compatible team. Teams can be (in)compatible with a task due to their working hours, or due to specific technical qualifications required to execute the task. No team can execute two tasks at once, and hence overlapping tasks should be assigned to different teams. Finally, some tasks are required to be assigned to the same team, e.g., when two tasks involve transporting the same part from one place to another.

In the second variant of the problem, the tasks are not yet fixed in time and should be scheduled in a predefined time-window. That is, each task has a earliest time it can be started (the release time), and a deadline by which it should be completed. Moreover, some tasks depend on one another and therefore share a precedence constraint. Also, each of the worker teams has fixed working-hours and hence, any task assigned to a given team, must start and finish within the working hours of that team.

From the planner’s perspective, the scenario is as follows: an initial schedule and allocation is established for upcoming shifts, with an estimate of available teams. This schedule can be computed using the CP-models from the previous section or manually constructed by the planners. As discussed in Section 1.1, various disruptions can affect the plan and possibly make the foreseen allocation infeasible. In response, the planner must first understand the implications of the disruption, and then adapt and reallocate the available resources such that as many tasks as possible can still be allocated, without wasting resources.

To evaluate our explanation methods in a broad range of disruption scenarios, we use a generator with adjustable parameters for simulating disruptions. These generator parameters are designed in coordination with the real planners, to cover a range of realistic and complex scenarios that arise in their daily practice. Table 1 details the parameters used for generating resource disruption scenarios based on three key factors: the number of disruptions, the number of affected teams, and the duration of the disruptions. As an illustration, the all teams affected scenario corresponds to a situation where all working teams are unavailable for a given amount of time, which can occur during extreme weather conditions. In less extreme cases, such as the few disruptions scenario, some teams are unavailable for a period of time caused by team meetings, transport accidents, or unexpected worker absences. A single disruption can affect multiple teams when they need to share a certain resource in the manufacturing site, e.g., when a hangar has to be evacuated due to a fire-drill. Figure 1 visualizes two instances of disruptions.

After a disruption in the schedule has occurred, 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. In the next two sections, we explore how to assist the planner in resolving these disruptions.

In this first setting, we aim to explain to the planner why it was not possible to reallocate all the tasks affected by the disruption. That is, we compute a minimal conflict in the constraints by using a Minimal Unsatisfiable Subset (MUS)-extraction algorithm. As is typical in MUS-extraction, we split the problem constraints into a set of foreground and background constraints [18]. Foreground constraints are those that are explicitly presented as part of the conflict while background constraints are assumed to always hold. In our setting, we treat constraints that require tasks to be allocated (1), constraints that require tasks to be allocated to the same team (3) and no-overlap constraints (4) as foreground constraints. The remaining constraints are background, in combination with an encoding of the disruptions. As a result, a MUS corresponds to a minimal set of overlapping tasks that cannot be executed given the available teams. Section 6.1 experimentally compares the Shrink and SMUS algorithms for computing MUSes for this setting. SMUS computes the smallest MUS in terms of the number of constraints [19], while Shrink computes an arbitrary MUS.

Figure 2(a) visualizes a set of task is allocated (3) constraints that together form a MUS. Indeed, this irreducible set of tasks cannot be allocated given available teams and disruptions.

After understanding the conflict in the allocation problem, the next step is to revise the model such that a new schedule can be computed. Model diagnosis [26] can be used to iteratively resolve all conflicts in the problem by sequentially resolving each individual MUS. Indeed, a conflict represented by a MUS is resolved after the removal of one of its constraints. However, by solving each conflict locally, in the end, more constraints may be removed from the problem than strictly necessary. Therefore, we investigate two types of feasibility restoration methods that can globally resolve all conflicts in the model.

We first compare different solvers and models for allocating tasks with fixed start-times.

We now turn to the much more computationally intensive case of scheduling, where tasks are not yet fixed in time. We only use OR-Tools CP-SAT as it is the only solver we tested with support for the appropriate global constraints. Figure 5, left side, shows the runtime for optimizing the number of teams in the scheduling problem. While OR-Tools is able to solve only $\pm 100$ instances to optimality in the bare-bones model, adding the lower-bound of the relaxed problem greatly improves the performance of the solver and $\pm$100 extra instances are solved. The right-side of Figure 5 reveals that the lower-bound found by the solver is close to or equal to the true optimal number of teams required to allocate all tasks and hence, by adding the lower-bound to the model, we alleviate a lot of the work in proving optimality. In 83% of instances, the computed lower-bound is a proven optimal for the relaxed problem.

The results presented in this section were obtained by running default implementations of MUS and MCS-algorithms as implemented in CPMpy v0.9.23, on the unsatisfiable scenarios listed in Table 7. In particular, we use Shrink [23] for computing any MUS, SMUS [19] for computing a smallest MUS, Grow [24, 25] for finding any MCS and finally we use a reified Max-CSP formulation for finding an optimal MCS. In all MUS and MCS-experiments we use Exact [11] as solver, as it supports incremental and assumption-based solving [34].

We now investigate the effectiveness of restoring feasibility by computing fine-grained alterations to the schedule as described in Section 4.3.2. We use OR-Tools CP-SAT with 10 search workers to solve the lexicographic optimization models as introduced in Section 4.3.1, using the sequential solving approach outlined in Section 2. For each of the 5 objectives, we set a time-limit of 5 seconds, such that the total time for feasibility restoration is limited to 25s. Table 4 summarizes the final objective value for each similarity objective for each of the optimization orders and across all scenario types. The number of not-done tasks (#not-done) is derived from the #done similarity objective.

Comparing the number of dropped tasks in the above table to the MCS-results in Table 3, we can clearly see that more-fine grained feasibility restoration leads to less tasks dropped. Indeed, repaired schedules using the optimal MCS drops on average 6.29 tasks, whereas allowing for re-scheduling of tasks only drops a single task on average.

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 re-allocated 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.

Table 4 shows that by altering the order of the objectives, the resulting repaired schedule can be influenced significantly, and hence, we can use these orderings to propose several alternatives to the planners.

Interestingly, optimizing the total magnitude of shifted tasks, results in less tasks that are shifted on average, compared to minimizing #shift directly. Table 5 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 this continuity objective first. In “Sum Shift First (C)”, the sum-shift continuity objective was proven optimal in 80% of the instances and, by minimizing this simpler objective first, the resulting repaired schedule contains less shifted tasks overall.