Photo by Andrew Neel on Unsplash Being able to solve complex optimization problems is critical for many enterprises and startups, but don’t think it is useful for only a few selected markets. Understanding these problems and their solutions highlight new applications in very different contexts, maybe even close to yours. If you understand these problems and their […]

Being able to **solve complex optimization problems** is critical for many enterprises and startups, but don’t think it is useful for only a few selected markets. Understanding these problems and their solutions highlight **new applications in very different contexts**, maybe even close to yours.

If you understand these problems and their solutions you may also find great applications for your company.

Think about the problem of **packing a suitcase**, meeting the **weight limit for the airline**, but including all of your necessary belongings: clothes, shoes, personal hygiene products, electronic devices, and so on. From all these categories you need to **pack enough items** for the entire trip, without leaving the **essentials ones**, but **being prepared for **the majority of **plans** (work, relaxing evenings, fancy dinners for work events, sports activities, *etc.*).

We can summarize the problem defining (1) the **constraints**:

- You have a finite amount of items in each category.
- The sum weight of your clothes should be lower than the maximum weight allowed by the airline.
- All the selected clothes have to fit within the suitcase capacity.
- Certain clothes have to be selected together (
*e.g.*, running shoes with running clothes and maybe a phone armband).

and the (2) **objective function**:

- Minimize the weight while maximizing the number of different activities you can do with the selected clothes.

Ideally, we could try all the valid solutions and select the best one given these criteria (hello Brute Force!). This is possible with a dummy example, but when the number of solutions is very high, this strategy is unrealistic, since the **search space** (the “list” of all possible solutions) will grow exponentially. Here is where **Combinatorial Optimization** comes to the rescue, often referred to as **Discrete Optimization** since we can mathematically formulate this problem using discrete variables.

Combinatorial optimizationmeans searching for an optimal solution in a finite set of potential solutions. Optimality is defined with respect to some criterion function, which is to be minimized (cost) or maximized (objective).

If you want to know more about these topics, you could start exploring the beautiful world of **Operations Research**.

**Traveling Salesman Problem**: find the best route a dispatcher should follow to visit a set of locations and go back to the origin, at a minimum cost (*e.g.*, time, distance). Probably the most famous NP-hard problem in combinatorial optimization. This is the basis for more complex problems like the (Capacitated) Vehicle Routing, daily bread for logistics companies such as Amazon, car-sharing, last-mile deliveries, etc.**Portfolio Optimization**: how you should balance your financial portfolio (of any asset) in order to minimize the risk of the overall portfolio while maintaining a level of monetary return.

**Assignment Problem**: A group of workers has to perform a set of tasks. For each worker and task, there is a fixed cost for that worker to perform the task. Find the best assignation that minimizes the total cost.**Crew scheduling**: Assign crews to different airline flight segments to minimize total cost while ensuring that a crew “rotation” begins and ends in the same city. Similar to shifts scheduling of hospital personnel.

There are plenty of use-cases in our everyday life in which Combinatorial Optimization plays an important role. That’s why it is a very interesting topic and an extremely useful one. More examples here and here.

In Jobandtalent, we had worked quite a lot with the **routing optimization problem**, but in this article, we want to focus on one of our specialties: **optimizing workers' and clients’ schedule** in their day-to-day lives.

The core business of many companies nowadays relies on a **dynamic work demand** that needs to be *fulfilled* by the **best** **workers** available at each moment (while trying to minimize the costs).

For some clients, scheduling is directly related to costs.

Think about delivery and logistics companies, supermarkets, warehouses, or any business that relies on a fleet or a crew of workers. One of the main problems they have in common is how to **optimize the working time of their staff** because it’s **one of the highest costs** they have to deal with, and it’s critical to increase their (often tiny) margins. For instance, imagine that your business needs 10 workers next Monday all-day, but you forecast a work peak in the morning (8:00–10:00) in which you should have 15 workers to maintain a high-quality service. Unfortunately, you cannot have 5 workers performing just 2h shift, because the minimum of their contract is 4h. Therefore, you have to decide whether to ** oversupply**, assigning 15 workers and incur extra costs for the extra hours, or

For some workers, scheduling is often related to better working conditions and, thus, happiness.

Another huge benefit of this problem, which is rarely taken into account, is that we can **include the workers’ preference in our cost function** such as working in the morning, weekdays, or being assigned to a particular part of the city or workplace. Having workers that are listened to, and have better working conditions, it is one of our priorities. Our algorithms will try to find a solution that satisfies both the client and the workers.

As you might guess, in order to solve these scheduling problems we need to design some **Discrete Optimization algorithms**.

The solution that Jobandtalent offers has been **developed internally from scratch** and integrated with the rest of Jobandalent’s product suits. It serves some of our clients that benefit the most from optimizing their workforce scheduling. It has a very cool interface (**Scheduler UI**) in which is possible to upload and change the demand, manually or automatically create the shifts and allocate them to the workers, and finally, also interact with them via the Jobandtalent’s mobile app. The **automatization** is taken care by a **set of optimization algorithms** that are working on two separated steps:

**Planner**: given the demand, they generate the shifts respecting its constraints and optimizing its objective function.**Allocator**: given the shifts and the clients’ workers, they allocate them respecting their constraints and optimizing their objective function.

We can upload a demand of a few days, few weeks, or even entire months. Below you can see an example of a weekly demand, one for each different workplace (*e.g.*, different warehouses or supermarkets) of a demo client.

In order to generate the “optimal shifts” we need to **understand when a shift is a valid shift**, and what **makes one solution better than another one**. From our web interface, we can specify a set of requirements that can be **constraints**, *i.e.* mandatory characteristics that define a valid solution, or **preferences**, *i.e.* “nice-to-have” characteristics. For example:

- Shifts should last
**a maximum of 8 hours**for standard contracts (*e.g.*, but night shifts in hospitals might even last 12h, and we should also support lunch-breaks). - Shifts should last
**at least 4 hours**since your workers might not be happy to work less (in some cases they won’t accept a shift if it’s shorter). **Minimize**the**hours of****oversupply**(how much does it cost to have a worker doing nothing?) and**undersupply**(how much does it cost not having enough workers to finish a task or cover the service?).**Minimize**the**total number of shifts**generated (the highest, the more workers are required and the more expensive will be to cover the demand).

Once we have all this information, we can map them into our Combinatorial Optimization model (that we have previously designed and mathematically formulated), and we will get the best solution that our algorithm is able to find, again within our Scheduler UI.

It’s important to understand that **the more constraints and preferences** we have to consider when searching for the solution, **the more complex** it will be to design an algorithm that works well and fast.

It’s not a big deal with these dummy examples, but when you have 20, 50, 100, or higher peaks of demand over time, then the problem becomes exponentially more complex. Not surprisingly this type of problem is classified as NP-hard.

We have seen how the **planning **phase works. Now that we created the shifts, we have to allocate our workers, and this is the second part: the **allocation**. We have a **bunch of shifts** previously generated and a **list of workers** for the current client that has to be assigned to these shifts in order to properly fulfill the demand.

Even for the **allocator’s algorithms,** we have different **constraints** and **preferences** that we have to use to design our model and find the solution that minimizes our **cost function**. Some examples below.

**Minimum**and**maximum working hours**(*e.g.*, workers cannot work less/more than 40 hours per week). These constraints should also be formulated with the monthly limits.**Compatibility between workers’ skills and workplace**(in some cases only workers with*special training*can perform certain tasks).**Balance**the number of**weekends**and**night shifts**assigned across the workers (avoid the risk of always assigning the weekend to the same workers).- Keep in mind the
**preferred working hours**of the workers to keep them happy and engaged.

As usual, the more flexible we are, **the better the solution for our workers and clients will be**, but also the more complex the search for optimality will be.

As with the Planner, we define all of this information from the Scheduler UI and with the power of a click, we just wait for the best solution to appear. The interface would look like this:

From the Scheduler UI, we can ** manage** all the shifts and workers,

With the Scheduler UI it is very easy to manage a fleet and quickly control the dynamic demand even in real-time for day-to-day operations.

As we have discussed, in order to solve the whole scheduling problem, we had split it into two different sub-problems: Planner and Allocator. We have formulated both of them as an **Integer Programming** (IP) **problem**, which is a particular approach to solving Discrete Optimization problems.

In the next article (below), we are going to explore in more detail **how we can build a model that solves the Planner**.

Solve the “Planning Problem” with Integer Programming (2/2)

It’s one of the first models we built, and it cannot handle all of the clients’ requests, but it’s a **good starting point** since it’s able to solve complex scenarios while remaining fairly easy to understand.

body[data-twttr-rendered=”true”] {background-color: transparent;}.twitter-tweet {margin: auto !important;}

function notifyResize(height) {height = height ? height : document.documentElement.offsetHeight; var resized = false; if (window.donkey && donkey.resize) {donkey.resize(height);resized = true;}if (parent && parent._resizeIframe) {var obj = {iframe: window.frameElement, height: height}; parent._resizeIframe(obj); resized = true;}if (window.location && window.location.hash === “#amp=1” && window.parent && window.parent.postMessage) {window.parent.postMessage({sentinel: “amp”, type: “embed-size”, height: height}, “*”);}if (window.webkit && window.webkit.messageHandlers && window.webkit.messageHandlers.resize) {window.webkit.messageHandlers.resize.postMessage(height); resized = true;}return resized;}twttr.events.bind(‘rendered’, function (event) {notifyResize();}); twttr.events.bind(‘resize’, function (event) {notifyResize();});if (parent && parent._resizeIframe) {var maxWidth = parseInt(window.frameElement.getAttribute(“width”)); if ( 500 < maxWidth) {window.frameElement.setAttribute("width", "500");}}

If you want to know more about how it works at Jobandtalent, you can read the first impressions of some of our teammates on this blog post or visit our Twitter.

*Acknowledgments: thanks to **Ana Freire**, **Antoine Hachez**, and **Daniel Lovazzano** for feedback and reviews. Thanks to the Data Science and Operations teams for making this project a success.*

Save Money and Increase Workers Happiness by Optimising your Workforce Schedule was originally published in Jobandtalent Engineering on Medium, where people are continuing the conversation by highlighting and responding to this story.

Source: Jobandtalent