Building a Modern Scheduler (III)

This article is the third in a series in which we explore the discovery and development process for a feature at Bold. You can read the first article here and the second article here

A complex problem

After covering usability and functionality in the previous articles, it's now time to focus on the core of the feature: the optimization algorithm.

The scheduling problem as we've framed it at Bold is what's known as a Job-shop scheduling problem, more specifically, Flexible Job-shop scheduling, and it's a problem that's been widely studied in combinatorial optimization.

It's an NP-hard problem, which means that solving it requires time that grows exponentially with the size of the problem. Or, put another way, it's a damn hard problem to solve.

All of this already gives us a clue as to where the solution should go, since it's a widely studied problem and there are people much smarter than me who've created more complex and faster solving algorithms than I could ever dream of.

It's all about algorithms

If we take a look at our options, we can group the solutions into three categories:

Heuristic methods

If you present this problem to a programmer with zero knowledge of mathematics, creating a heuristic would be their first instinct. It's a defined sequence of steps to execute.

We have several options, such as Shortest Processing Time (SPT) or Earliest Due Date (EDD), which are easy to implement but don't guarantee finding an optimal solution.

A little more complex are genetic algorithms, which are based on making semi-random mutations to gradually improve the objective. They improve solution quality, but they're slower.

Metaheuristic methods

Metaheuristic methods take things a step further than simple heuristics and are designed to explore large solution spaces more efficiently. Some of the best known are:

• Simulated Annealing: It draws inspiration from the process of cooling metals, temporarily accepting worse solutions to avoid getting stuck in local optima.
• Tabu Search: It uses short-term memory to avoid cycles, continuously improving the solution.
• Ant Colony Optimization: It simulates the behavior of ants searching for optimal routes. It's effective, but computationally expensive.

These methods are powerful and flexible, capable of finding good, though not always optimal, solutions, but they require fine-tuning their parameters.

Exact methods

Here we find things like integer linear programming (ILP) or mixed-integer linear programming (MILP). Probably the most useful thing I learned throughout my entire degree. It's surprising how a problem this complex can be modeled as equations, and solvers can be run to guarantee that they find the optimum.

The problem with these kinds of solutions is that they greatly limit how you can express the problem. For example, representing something like "a machine can only perform one operation at a time" translates into a huge number of constraints, especially as the number of jobs and machines grows.

This makes them impractical for solving real-world problems, where the number of jobs can reach thousands and the number of machines hundreds.

Constraint Programming (CP)

Although metaheuristic methods offer good solutions by efficiently exploring the solution space, they don't always guarantee finding the optimal solution, and their performance can vary depending on the parameters and the nature of the problem. For this reason, I decided to use Constraint Programming, or Constraint Programming (CP).

Constraint Programming is a problem-solving paradigm in which you define a set of constraints that must be satisfied. Instead of directly searching for a solution, CP works by eliminating impossible solutions and reducing the search space until it finds the optimal solution.

CP lets you express the problem more naturally and directly through constraints. For example, the requirement that "a machine can only perform one operation at a time" can be described in a single line of code.

What's more, CP can handle problems with a large number of constraints and variables more efficiently than traditional exact methods such as ILP, using advanced constraint propagation and search techniques to reduce the space of possible solutions.

Unlike metaheuristics, CP guarantees finding the optimal solution as long as there's enough time and computational resources.

Google to the rescue

Once I've decided how to solve this problem, it's time to implement it, so I start looking for alternatives that I can implement in C#.

Basically, we find about five alternatives:

• OptaPlanner: it's an open-source planning engine that looks very promising, but it's written in Java, so interoperability could increase the complexity of the solution.
• Gurobi Optimizer: this is one of the most famous, and in theory one of the most powerful, but it's paid.
• IBM ILOG CPLEX: like Gurobi, it's a commercial solver, so we have to rule it out for now.
• Microsoft Solver Foundation: focused on C#, but Microsoft has abandoned support, so that's ruled out.

Finally, we have Google OR-Tools, which is described as:

OR-Tools is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming.

Looks good, like OptaPlanner, but it also offers support for several languages, including C#. We have a winner.

Putting it into practice

Once I've decided to use this package, it's not particularly difficult to implement; they even give us a small example of how to implement the Job Shop Problem using CpSatSolver.

Fortunately, Dr. Dominik Krupke has written a magnificent guide to CP-SAT that makes things much easier than the official documentation.

Basically, it's a matter of translating our domain into variables and constraints. For example, we convert dates into minutes measured from the start of planning. All of this amounts to fewer than 200 lines of code, thanks to the flexibility and options the solver provides, such as NoOverlap.

What's left is deciding which objective function to optimize. Minimizing the makespan is all well and good in theory, but in the real world what we want is to satisfy our customers as best we can—that is, minimize delays (or tardiness).

It's most likely that not all customers or orders are equally important, so it makes sense to convert this tardiness into a weighted unit to which we can assign different weights for different orders.

In this case, I think it makes sense to translate everything into costs because, although it may not be obvious, a delay in shipping an order is a form of cost (to our reputation) with an implicit monetary value.

Of course, no one really knows what that value is, but even with an invented figure, it gives us room to weigh different concepts against one another.

For example, we could compare a scenario where we add overtime hours (which we'd have to pay for) so we can fulfill orders sooner with one where we don't, and adjust the parameters until the result makes sense for our company.

The result

After running a few tests with a size of 1000x100, aside from the smoke coming out of my PC while it's solving the problem, we see that it doesn't usually reach the optimum easily, so I have to limit the solving time.

However, in 30 seconds it's capable of reaching very good solutions that I'm unable to improve at a glance. More than acceptable for our MVP.

And that's it for today's article. Next week we'll see the result of this month's work and analyze it. I'll see you there!