.jpg)
Introduction
What could possibly connect Peter, a 34-year-old crane operator in the Paris suburbs, with Chris, a 56-year-old child-care professional in Reims? At Maglia, their paths intersected around one of the most challenging fields of research: multi-skill workforce task assignment and scheduling.
Both Peter and Chris are skilled professionals with unique abilities – and this situation repeats itself across nearly all companies and institutions. Whenever someone is responsible for workforce planning, they must juggle these skill constraints. But other questions quickly arise:
- What other criteria matter when assigning people to tasks?
- How to take into account other objectives such as fairness, efficiency, cost and employee satisfaction?
- How advanced mathematic can help us leverage the task ?
- Can Artificial intelligence really adapt to real-world assignements?
In the end, it all comes down to a very human question. For Peter, it might be as simple as: “When do I start work on Monday?”
Mathematical Modeling
We consider a set of tasks $t \in T$, each defined by :
- its start time $s_t$,
- its end time $e_t$,
- its required skill set $S_t$,
- its required number of employees $r_t \in \mathbb{Z}_{\ge 0}$.
On the other side, we have employees $e \in E$, each characterized by :
- their skill set $S_e$
- their availability $U_e$.
The assignment decision is represented as a binary matrix $A$, where:
\(
a_{e,t} \in \{0,1\} =
\begin{cases}
1 & \text{if employee $e$ is assigned to task $t$,} \\
0 & \text{otherwise.}
\end{cases}
\)
Since tasks may require multiple employees, we define a vector $Y$:
\(
y_t =
\begin{cases}
1 & \text{if task $t$ is fully staffed,} \\
0 & \text{otherwise.}
\end{cases}
\)
After defining the assignment variables, we must also ensure the system respects some essential operational rules. For instance, a task should not be assigned more employees than required:
\[
\sum_{k\in R^q} x_{jk} \le r^{\mathrm{req}}_j.
\]
Or in some contexts (e.g., operating a crane like Peter does), a task only makes sense if it is fully staffed with the required number of skilled workers. In that case, we enforce:
\[
\sum_{k} x_{jk} = r^{\mathrm{req}}_j\,y_j
\]
Approaches to Solving the Problem
Solving the assignment of task force is now a discrete optimization problem. The goal is to choose values for $A$ (and consequently $Y$) such that:
- all tasks are covered,
- employees’ constraints are respected,
- broader objectives such as efficiency, fairness, or cost minimization are achieved.
In practice, this means that Peter’s question is answered not by guesswork, but by mathematics.
For instance, having no asignement overlaps can be defined by: $ \forall e_1, e_2 \in E, \forall t \in T, a_{e_1,t} + a_{e_2,t} \le 1$.
Open-source tools such as the CP-SAT solver from Google OR-Tools can be applied to tackle this problem. Available as a Python library, CP-SAT is considered state of the art in open-source Mixed-Integer Linear Optimization, providing a practical way to translate the abstract equations into real-world schedules.
Reducing Complexity Through Preprocessing
In practice, the full assignment matrix can become extremely large, making the optimization problem much harder to solve. At Maglia, we tackle this by applying a pre-processing step to reduce the search space to only plausible assignments.
Specifically, we construct a reduced matrix that includes only employees who are both available for a given task and possess the required skills. By eliminating impossible or irrelevant assignments upfront, the solver can focus on realistic options, dramatically reducing computational complexity while still finding optimal or near-optimal solutions.
Defining Objectives and Trade-offs
Each company or institution can have its own scheduling objectives. That’s why at Maglia we adapt our algorithms to the specific goals of every client. The most common objective is to maximize the number of fully staffed tasks, which translates mathematically into maximizing
\[
\sum_{j\in V} d_j\,y_j,
\]
where $y_j = 1$ if task $j$ is fully allocated.
Another common objective is to maximize the total scheduled hours, that is,
\[
\sum_{j\in V}\sum_{k\in R^q} d_j\,x_{jk}.
\]
In some cases, management may assign different priorities to tasks, weighting them according to their importance. This leads to an objective of the form
\[
\sum_{j\in V} w_j\,d_j\,y_j.
\]
Fairness objectives: Let $h_k = \sum_j d_j\,x_{jk}$ (workload of $k$).
- Minimax load: introduce $L$ and minimize $L$ subject to $h_k \le L$.
- Max-min fairness: introduce $m$ and maximize $m$ subject to $h_k \ge m$.
- Variance / Jain index approximation: minimize $\sum_k |h_k - \bar h|$ where $\bar h$ is mean workload.
The beauty of mathematics lies in this flexibility: once we understand the client’s real-world goals, we can translate them into precise mathematical formulations—the very core of our scheduling engine.
The Limits of Exact Methods
But then comes the challenge of real time. Figuring out something as simple as “When does Peter start work on Monday?” might take longer than expected. The more tasks and employees we add, the richer the possibilities, but also the heavier the computation. Even when we reduce the search space, the complexity of solving these problems grows exponentially with the number of tasks and employees.
To better illustrate this point, let us compare two different approaches. The figure below shows the runtime growth of our exact integer programming model versus Maglia heuristic.
While the heuristic remains extremely fast, the exact model quickly becomes computationally heavy, even for medium-size problems.
This highlights how complexity can escalate in practice.
Finding the exact mathematical optimum can be extremely time-consuming, and for a planner sitting in front of a computer, waiting minutes or even hours for a result is simply not practical. In real life, workforce allocation has to be decided on the run, with schedules often needing to be re-evaluated as soon as new information arrives. What happens if a worker suddenly becomes unavailable? How does this impact the rest of the calendar?
These challenges call for fast, adaptive methods. Rather than aiming for perfect optimality, we can rely on intelligent heuristics and AI-driven algorithms that deliver high-quality solutions in real time. Exploring these adaptive approaches will be the focus of a future article, as well as a central feature in the upcoming release of the Maglia software.
References
- Demir, O., Tolga, D., & Yücel, E. — An optimization framework for a dynamic multi-skill workforce scheduling and routing problem with time windows and synchronization constraints
- Fırat, M., & Hurkens, C.A.J. (2011) — An improved MIP-based approach for a multi-skill workforce scheduling problem
- Ahmadpour, S., & Ghezavati, V. (2019) — Modeling and solving multi-skilled resource-constrained project scheduling problem with calendars in fuzzy condition
- Fırat, M., Hurkens, C.A.J., & Laugier, A. (2012) — Stable multi-skill workforce assignments
- Golab, A. — Automatisation de la planification dynamique de projet à ressource limitée par l’intelligence artificielle (PhD Thesis)