Modeling and optimization of a weekly workforce with Python and Pyomo
Step-by-step modeling and optimization of a workforce design and assignation problem using Python and Pyomo.
In this post, we will go through the modeling and solution finding of a scheduling problem where workers have to be assigned to shifts to optimize given criteria, satisfying diverse imposed constraints to the working conditions.
When starting a new project, planning to open a new store or even preparing the schedule for the classes at the university, the person in charge of the task has two options: solving it by hand or modeling and solving it as an optimization problem.
Even if there was a great workforce planner, dealing with the problem using the optimization framework can have multiple benefits:
- Scaling: the problem might become as big as the proper environment, which may exceed the capabilities of a person.
- Unbalances: there are lots of situations where unbalances among staff will be unavoidable. In this case, the decision will not be personal.
Pyomo as optimization modeling environment
To solve this problem we will make use of Pyomo, in their own words a “Python-based, open-source optimization modeling language with a diverse set of optimization capabilities”. For the ones that already use Python, modeling and solving a problem with Pyomo would be straightforward.
Pyomo allows to choosing among a variety of solvers, both open-source and commercial. Moreover, the user can choose to solve problems in Neos Server, a free internet-based solver which can be used directly from Pyomo. This frees us from downloading and installing different solvers in our machine and it also permits to use commercial ones for free. More information in https://neos-server.org/neos.
I have installed Pyomo with conda in my machine, but it can also be done with pip. Installation instructions can be read in http://www.pyomo.org/installation.
For this post, we will make use of the COIN-OR project Cbc, https://projects.coin-or.org/Cbc, to solve a Mixed Integer Programming problem.
Problem description
A new food store has been opened at the University Campus which will be open 24 hours a day, 7 days a week. Each day, there are three eight-hour shifts. Morning shift is from 6:00 to 14:00, evening shift is from 14:00 to 22:00 and night shift is from 22:00 to 6:00 of the next day.
During the night there is only one worker while during the day there are two, except on Sunday that there is only one for each shift. Each worker will not exceed a maximum of 40 hours per week and have to rest for 12 hours between two shifts.
As for the weekly rest days, an employee who rests one Sunday will also prefer to do the same that Saturday.
In principle, there are available ten employees, which is clearly over-sized. The less the workers are needed, the more the resources for other stores.
Model formulation
To use Pyomo and solve the problem some packages are imported.
The first step is to enter the data, this means to provide the model, in this case, the days we are considering, workers, shifts… We could not define them explicitly and feed the data later by using AbstractModel(), but for this post continue with ConcreteModel() so all data must be available during the modeling step.
We have added all data needed for the model. We will be able to call these elements when defining constraints, without the need of manually inserting each element or considering if, else clauses.
To build the model, we need to initialize the model and create the decision variables.
After the initialization of the model as an object, elements such as variables constraints and objective function are added as attributes. As it was explained before, we create a ConcreteModel() because data is being provided at the moment. We add with Var() variables to the model, indexed by lists.
- works: binary variable indexed by workers, days and shifts. 1 if the worker has to work that day on that shift.
- needed: binary variable indexed by workers. 1 if the worker is necessary to include in the workforce.
- no_pref: binary variable indexed by workers. 1 if it does not work on Sunday but it does on Saturday.
After defining all the variables, we are able to add the objective function.
The objective is to find a schedule that minimizes the number of workers and once this is achieved, also the number of workers that work on Sundays but not on Saturdays. We multiplied the part of the number of workers by a constant big enough so that minimizing the weekend preference is considered only after deciding the optimal number of workers.
We also need to add the constraints, creating first a container of constraints calling ConstraintList() and then adding whatever constraints we want to the container with the function add. Code for the constraints is the following, with the explanation of each one as inline comments:
Now, the model created can be solved. A model can be visualized with model.pprint(). This problem is composed of binary variables, so a Mixed Integer Programming solver suits our requirements and CBC from COIN-OR will be selected, https://projects.coin-or.org/Cbc.
This would require to install the solver locally (and do not forget to add it to the path so that Pyomo recognizes it). However, running it in neos-server frees us from this process.
Extract the solution
We did this to get a solution to a problem, so this is the next step. Solution to the problem is sparse in the sense that we just want to know which of them are non-zero, and to visualize it we have to process the given solution.
We can check now the solution obtained and verify that all the proposed constraints are satisfied. Saving the dictionary of the optimal timetable in JSON format, the solution looks like:
An optimal solution needs to activate 7 workers. Then, with 7 workers, the number of them not satisfied because they do not work on Sunday but they have to do on Saturday is 2 (W6, W9). Observing the problem formulation, as there are 3 shifts on Sundays and 5 on Saturdays, one could not expect that less than 2 Saturday workers would not work on Sunday.
Conclusion
In this post we have gone through the objectives of:
- Explaining the basics of Pyomo as an Optimization Modeling framework in Python.
- Learning how to model a particular problem in which a workforce planner has to optimize a weekly timetable under diverse restrictions.
This post was aimed to be a friendly introduction to both the usage of Pyomo and the Modeling of Optimization problems and thus, solving harder problems because of the size of the problem or the difficulties to formulate a good model (yes, modeling can be considered an art) may require to get deeper in the topics.
Thank you for reading. Have fun!
Latest code is available in https://github.com/ccarballolozano/blog-post-codes/tree/master/Modeling-and-optimization-of-a-weekly-workforce-with-Python-and-Pyomo.
