Why Automatic Workforce Scheduling is Hard

Automatic Workforce Scheduling is a well known problem. Indeed, and due to its complexity, it is still one of the hardest to solve successfully. If we think of retail stores, we find highly flexible shift regulations, which make the problem much more complex.

In this post, we’ll try to define the underlying optimization problem.  We will also explain why it is difficult to solve, in a way that I hope everyone can understand.

Problem Definition

In the shake of simplicity, we’ll try to define a really simple Workforce Scheduling scenario, that afterwards we will measure.

Our simple problem has just 10 employees. This is a fairly small ammount of people for a regular store.

Each employee can work between 3 and 8 consecutive hours per day. She also has to respec a rest of 12 hours between two consecutive working days.

There are three tasks that are regularly performed in the store: Management, Sales and Replenishment. For the shake of simplicity, every employee can do any of them.

The employees can work in the store from 08:00 to 20:00 every day.

Our goal is to assign a shift to each employee each day, satisfying all the defined labor constraints, and maximizing the coverage of the store workforce needs.

Problem Size

There are many ways of measuring the complexity of a problem. In fact there is a lot of theory around it and even some interesting unsolved problems. In this post, we will just focus on measuring the size of the problem, which is one of the main indicators of complexity. And as a measure of its size, we will estimate the number of possible solutions.

Number of Shifts per day

First, let’s measure the number of different shifts that one of our employees can work in a certain day. As it’s clearer, we’ll do it for each possible shift duration.

For a shift of certain duration, we could imagine sliding it from the opening time to the closing time, in order to represent all the possibilities to place it. Supposing an slicing granularity of 30 minutes, which is fair enough, we’d have:

• For 3 hour shifts, 19 different possibilities.
• For 3.5 hour shifts, 18 different possibilities.

And we can continue this up to 8 hours, the maximum working time per day, where we find 9 ways of assigning the shift.

Summing up, we have 19 + 18 + … 10 + 9 = 135 different possibilities of assigning a shift for a particular employee in a particular day. Not so many, indeed.

Number of Shifts per Week

We have then estimated as 135 the number of possible assignments that a particular employee can be given at a certain day. Now we want to estimate how many assignment possibilities we have for a certain person on 7 consecutive days. To do so, we will start with  days 1 and 2.

First of all, it is easy to see that it is possible to combine every possible assignment on day 1 with every possible assignment on day 2. That is, for any single shift assigned to a particular person on the first day, we still can assign any of the possible shifts on day 2.

Then, we can estimate all the possible assignments for day 1 and 2 as 135 * 135 = 18.225 possible  assignments.

Extrapolating the previous reasoning to the rest of the week, we can easily infer that the number of possible different assignments for a single person in the whole week sums up to 135 * 135 * 135 * 135 * 135 * 135 * 135. If we compute this number, we finally have:

817.215.093.984.375 possibilities!!!

That’s really a lot of possibilities. And we are just planning a single week, for a single person, on the simplest conditions. We are not taking into account even the fact that inside each shift we have to decide which exact tasks the employee performs!!

So then, which is the standard problem size?

We have seen that the simplest problem that we could imagine is itself huge. If we keep growing that problem to match a real case, the problem becomes even bigger. Intractable problem immediatly comes to mind.

With such a big problem, is it possible to  solve it, or to even find a good solution? Well the short answer is yes, we have done it in ORQUEST, but we need to elaborate a little bit more.

Trying to solve an UNSOLVABLE problem

In the data science world, there are a bunch of techniques, normally under the denomination of combinatorial optimization, that are designed to face such challenges, though it is still really hard. Lets introduce the most relevant ones, and briefly analyze their applicability to the Automatic Workforce Scheduling problem.

Heuristics

Heuristics are the simplest of these techniques. By exploiting both the problem structure and the business knowledge, they construct the solution in a step by step procedure. At each moment, and from the current partially constructed solution, they make the best decision they can with the information they have at hand.

By using branching techniques, they manage to take back some of those decisions and somehow amplify the portion of visited solutions a little bit. But as we have seen before, the number of different solutions to our problem is really huge, so even if we are able to explore alternatives really fast, we’ll always be far away of exploring enough.

Several times we have seen Workforce Management algorithms that use this kind of techniques and proudly log the number of solutins they have found so far, but they will barely be less than 0.001% of the whole!!!

Metaheuristics

Metaheuristics are techniques that, starting from an initial complete solution, evolve it by evaluating neighborhoods of that solution and moving through them in the aim of finding the optimal one.

Many techniques match this characteristic, such as Tabu Search, Simulated Annealing, and more recent ones, such as Ant Colony Optimization, Particle Swarm Optimization, etc., Also Evolutionary Algorithms can be included in this category.

While these techniques have proven to be really effective in solving tons of extremely complex problems in areas such as logistics, retail, transportation, etc., they have not proven to be effective for Automatic Workforce Scheduling. The reasons behind that are quite complex to explain in a short post, but I’d say that the tight relationships between the several components of the problem is one of the main root causes of it.

Integer Linear Programming

Integer Linear Programming is a well known technique, with powerful state of the art commercial products behind it, such as IBM CPLEX and Gurobi. It is known to solve huge problems in areas such as manufacturing, logistics, transportation and many others.

But again, Automatic Workforce Scheduling has proven to be a hard-enough problem for them, and we’ve never seen a successful approach for this problem using these techniques (although we have actually seen several failures)

So then, is this problem solvable or not?

OK, as I said before, ORQUEST is able to obtain really good solutions (many of them optimal solutions) to the Automatic Workforce Scheduling problem.

ORQUEST team has invested huge ammounts of gray matter on developing sophisticated algorithms that, by mixing all of the techniques explained above, are able to solve real workforce scheduling problems with more than 100 employees and more than 1 month horizon in an automatic way in minutes.

And now, should you believe us? Well, I’d say you shouldn’t. But you can contact us, and we’ll plan a demo for you, so you can see it first hand.