How to Solve Scheduling Problems in Python
Use linear programming to minimize the difference between required and scheduled resources
In workforce management, scheduling refers to finding the “optimal” way to schedule a set of resources depending on the projected demand per interval. This may be, for example, finding how many call center agents to schedule per one-hour interval, given some demand (for instance, using ErlangC) and some restrictions.
The “optimal” criterion is defined under an objective function, for example, minimizing the number of scheduled resources or the absolute difference between the required and the planned resources.
1. Formulation
Let’s assume that we are creating the scheduling for a call center operation; we have the estimated number of people we need per 60 minutes interval. Check this other post to learn how to find that requirement.
The requirement may look like this:
We want to answer the question: Given a set of shifts covering part of those intervals, how many agents should I schedule each shift? Such as the difference between the required and the people planned per interval is as low as possible to ensure that the demand is covered as close as possible without a huge under or overstaffing.
Take into account that the shift coverage might look like this, so at one interval, people from different shifts are working simultaneously.
1.1 Mathematical Formulation
In this section, I’ll define this case as an optimization problem. With this I introduce the following variables and notation:
Notice that the definition of period allows splitting a day in any number of intervals; it may be 24 intervals of one hour, 48 intervals of 30 minutes, etc. It will depend on the granularity of the requirements.
Now we must define the objective function and the restrictions of the model; this step might change depending on the available data and business requirements.
I’ll call this formulation the “Minimum Absolute Difference” model; in this method, the solver will minimize the absolute difference between the required and scheduled resources; this implies that the planned resources may be higher or lower than the actual requirement.
Under this definition, the objective function is formulated as:
Notice that the term Xds∗Esp would result in the number of scheduled resources for a period and day, and the term Ndp is the required resources. Hence, the objective effectively minimizes the absolute difference over all days and periods of the requirements vs. the actual scheduling.
Now we Introduce the restrictions of this model:
- The number of scheduled resources for a period p and day d can’t exceed the maximum allowed capacity.
- The number of scheduled resources on the same shift can’t exceed the maximum allowed capacity.
- Positive integers restriction
- Bool restriction
2. Python Solution
As you can see from the previous section, the problem is fully defined, and you can use any solver that supports defining the different variables and an objective function.
However, translating those equations to code and solving them may require a considerable knowledge in optimization; fortunately, some packages already simplify this process; in this case, I’ll use pyworkforce, a python interface for common problems in operations research applied to queuing, scheduling, rostering and optimization problems.
First, let’s define the requirements per interval and the fixed shifts we can use, I’ll only solve the problem for one day:
Now, with the help of pyworkfoce, we only need to pass this data to the MinAbsDifference object and run the solve method:
For this particular run, I get the following output:
The first thing to notice is that the status is “optimal”, which means the solver was able to find an optimal feasible solution. Next, we have a cost of 35.0, this is the value of the objective function after finding the solution.
The resources_shifts object will tell us how many agents to schedule in each of the shifts we have available; for example, you should schedule 13 agents at shift 3.
If we match this information with the shifts coverage, i.e, we find Xds∗Esp, we get the following scheduled agents per interval vs. the theoretically required agents:
You can see that there are intervals where we may have more/fewer agents than we need; you can think of it as having six shifts can only get some degree of discretization of the required curve, but it’s guaranteed to be the best of under the definition of the objective function and its restrictions.
I hope you find this article useful to get started with scheduling problems. If you want to learn more about pyworkforce and how to solve other optimization problems, you can check the docs and its repo:
