Question about benchmarking scheduling quality

[charlesnauroy-wq]

Hi guys

I'm studying how scheduling engines are evaluated (job-shop / FJSP variants)

When you measure plan quality, you compare against best-known solutions. My question : is the lack of a proven optimum — benchmarking against a moving record rather than the actual truth — a real gap in your practice, or is best-known largely enough?

What do you guys think ? =)

[triceo]

Hello @charlesnauroy-wq!

At Timefold, we specialize in real-world problems, with real-world constraints; we do not pay much attention to academic datasets, which are typically oversimplified and detached from practice.

The optimization models we provide have dozens, even hundreds of constraints. And that means we cannot rely on knowing optimal solutions - the solvers that are capable of solving problems to optimality are typically unable to model many of our constraints.

This means we do not have (and can not have) any golden standard to compare ourselves against. But we study the results we produce and when we identify inefficiencies in some of them, or when our customers occasionally do, we take it back to the solver and see if we can fine-tune the algorithm.

Often we find out that the solver needs a custom move implemented. But in very rare amount of cases, we actually had to go back and adjust the core algorithm.

[charlesnauroy-wq]

Makes total sense, thanks — really clear way to put it.

The shops I'm poking at (small machining / precision-turning) have two things that seem to wreck the clean academic version anyway: an operation needs a specific skilled operator, not just any free machine, and setup time depends on the sequence you run things in. Does that kind of mess land on your side too, or does it just disappear into the bigger constraint soup?

[noellynch-planufacture]

changeovers/set up times are relatively simple to model in timefold compared to any other solver i have seen

with the chaining/planning list approach it is simply a previous element shadow variable with a changeover time shadow variable that is triggered when the previous element changes, e.g. when the previous job changes look up the set up/changeover time from previous to this

then just write a simple minimise change over constraint to get the solver to reduce the accumulated change over time

[charlesnauroy-wq]

Thanks — that's a clear answer, and it matches what I keep hearing: the modelling side is the part people have solved.

Two things I'm still chewing on.

First, the half nobody mentions: the operator. In these shops an operation needs a machine and a person holding a specific named skill, at the same time — a free machine with nobody qualified in front of it starts nothing. Does that dual constraint show up in what you plan, or do you mostly model capacity as machines?

Second, the one I actually care about: once it's modelled, how do you know the plan that comes out is good? I saw your product talks about responding to disruptions — that's exactly my question. When a qualified operator calls in sick on a Tuesday and you re-plan, what do you compare the new plan against?

[Christopher-Chianelli]

1. The task assigning quickstart can be used as a base: https://github.com/TimefoldAI/timefold-quickstarts/tree/stable/use-cases/task-assigning ; there, an employee has a list of tasks, and each task has access to the employee doing it via an @InverseRelationShadowVariable. You may add an additional @PlanningVariable to task to represent the machine it is on, but then you need to determine how to order tasks when multiple tasks want the same machine at the same time. You could either do it as an additional constraint or try to account for it inside the shadow variable calculation; doing it as a seperate constraint will probably be easier but will increase the search space.
2. You would use either Score Analysis (https://docs.timefold.ai/timefold-solver/latest/constraints-and-score/understanding-the-score) or the Recommendations API (https://docs.timefold.ai/timefold-solver/latest/responding-to-change/recommendation-api) (both are enterprise only feature); you can use the recommendations API when an employee calls in sick to get a list of recommended assignments for the employee, and it will give you a score breakdown for each assignments (i.e. what constraints were broken and by what operator/machine/fact/etc); alternatively, you could do a full replan and then use the score analysis API to calculate the difference between the original and new solution. Do note the enterprise edition has a free license available for non-profit organizations and for academic research (https://docs.timefold.ai/timefold-solver/latest/commercial-editions/commercial-editions).

[zzk0803]

From what I've seen in recent discussions and public repos, people aren't just using Timefold as a pure discrete constraint programming solver to tackle old-school problems like timetabling or VRP. They are using it as a scheduling optimization solver, and the subject they're solving happens to be the "Flexible Job-shop Scheduling Problem", which is as far as I know extremely difficult in OR scheduling theory. I'm tinkering with it too, and I'm finding it's nowhere near as simple as the demos make it look. Regarding the "benchmark", it has its own specific meaning in this framework. I understand it's kind of like Grid Search in scikit-learn, used to screen and select solver configuration parameters.

[triceo]

I'm tinkering with it too, and I'm finding it's nowhere near as simple as the demos make it look.

That's a fair observation. Basic problems have simple implementations, and those are what we show in the quickstarts. As the complexity of constraints grows, and it often does in real-world problems, so does the complexity of the implementation. IMO that is unavoidable, and the correct approach - you want to start simple, and add complexity where needed. The key point here is that - unlike many other solvers - this complexity (and therefore solving these real-world problems) is even possible.

[zzk0803]

Indeed. Complexity is inevitable; it is either absorbed by the framework itself or pushed onto the end-user. In reality, the cost is always paid somewhere. Among the many Java-based OR (Operations Research) libraries, such as OR-Tools, Choco-Solver, and Jenetics, Timefold/OptaPlanner is a true gem—both invaluable and delightful. My mathematical background isn't strong enough to comfortably use the other libraries, but Timefold enables a "math dummy" like me to actually achieve operational research optimization results.

[triceo]

My mathematical background isn't strong enough to comfortably use the other libraries, but Timefold enables a "math dummy" like me to actually achieve operational research optimization results.

That's pretty much the mission. ;-)

[zzk0803]

Hey, are you building an APS (Advanced Planning and Scheduling) system or something similar? Besides the skill matrix and available machines you mentioned, you also talked about dynamically modifying resource availability. As far as I know, these are typical features of an APS system. On top of that, there might be other constraints like precedence constraints and material kitting checks. All in all, it's indeed a highly complex problem.
For modeling, the most intuitive approach would be a mixed model. It's very similar to the food-package demo in the quickstarts, but combined with the ai.timefold.solver.core.testdomain.shadow.multi_entity.TestdataMultiEntityDependencyValue class. As for dynamic resource state changes, I recall that this can be achieved using the ProblemChange API.
Another thing I can't help but bring up is your search space size. 10^1000? 10^10000? 10^50000? Or even larger? In my own toy projects, the scale tops out at around a search space of 10^2000. The solving speed (or rather, moves/second) is inversely proportional to the scale—the larger the scale, the lower the speed. For such massive scales, or if you're developing this for an enterprise, you might want to consider trying the Enterprise edition. I've previously helped out as a technical advisor for folks who had an Enterprise trial license. I found that at a search space of around 10^10000, the Community edition took about 30 minutes to reach a feasible state, whereas the Enterprise edition could achieve it in roughly 5 minutes. Of course, this is assuming your modeling, constraints, and configurations are all set up correctly.
I've really enjoyed joining this discussion, and I hope this helps!

[triceo]

The Enterprise Edition is indeed a must for problems at these large scales. Free time-limited trials are available:

https://licenses.timefold.ai

[zzk0803]

Sorry, I'm just a hobbyist, so I'm not eligible to register for the trial version 😂