Can TimefoldAI solve a manufacturing problem (BOM + BOP + job creation + ressource allocation)

[borisboc]

Dear you all.
I am completely new to Timefold (and OptaPlanner).
I was wondering if Timefold was the correct library to solve some manufacturing planning problems.

Basically, a factory has goods in stock. E.g. cables, pipes, screws, casing, etc. The factory has some purchased orders to fulfill (e.g. produce this amount of product P for deadline D under price limit L). The factory knows the Bill Of Material for the product P. The factory knows the Bill Of Processes (BOP) for the product P and there may be additional known processes that may help to parallelize production, or subcontract processes to save some time or employee assignation (so there is not one and only one way to produce a product). The processes (that we could assimilate to "actions", in PDDL) have preconditions (such as the needed material), post conditions (such as producing an intermediate material/product) and machinery + employee resources to be assigned. The planning problem to solve is : how to generate and plan the processes (actions), and allocate the resources (machinery, employees etc.) so that the stocks of materials are respected (e.g. I cannot call process P1 at time T if some materials are not in stock at time T), and the final products are produced before deadline D and bellow a price limit L. Price limit L helps to avoid to buy more "intermediate" material if you can produce it yourself. And this avoids to allocate to many employees for the same order. And avoids to subcontract too much.

This is a kind of domain / problem I can more or less write in PDDL (with Temporal features). But I am not OK with the PDDL solvers (for temporal planning) especially for the "Scoring" of the plans. Whereas Scoring in Timefold looks really human friendly. What I like with PDDL is that it will generate "automatically" the instances of the Durative Actions and sequence / parallelize / allocate them automatically, with respect to the constraints. And I am not sure that Timefold can do this. In the examples I have seen, it looks like all "objects" (or instances) such as Jobs already exist, and the solver has to organize them. I base this conclusion after looking at the examples python/employee-scheduling, java/food-packing, java/maintenancescheduling. They both work with respectively Shifts and Jobs, and there are already "known" / "instanciated" and the solver has to organize them. I my manufacturing project, the jobs have to be "generated". E.g. "soldering wires" is instantiated 2 times, first time it last 7 hours and is assigned to "Paul" (so it will takes all Paul's day), it will consume 700 wires and will produce 350 soldered wires. Then second time it last 2 hours and is assigned to "Andrew", it will consume 200 wires and will produce 100 soldered wires. But the solver could also propose another solution where it generates 9 jobs of 1 hour each, 9 employees in parallel, who will have 100 wires each and produce 50 soldered wires each.

And I am really unsure this can be implemented with Timefold... I would be very happy it is feasible. And thus, I was hoping than someone knowledgeable could give me some answers and good hints so that I can correctly start my coding journey (or not, if this is not feasible with Timefold).

Thanks in advance, kind regards

[greyhairredbear]

Disclaimer: Members of the Timefold team are certainly more qualified to answer this question than myself. So if anyone of the has the time to add their two cents, definitely listen to them instead of me ;)

From what I know, the feature to apply changes to your problem are not intended to dynamically create or remove lots of entities to find the right amount.

What you could think about however is to create more jobs that could possibly be assigned and leave jobs that are not needed unassigned. What could be tricky here is figuring out the "flexible duration" part... I guess you could create jobs that lead to the same output but have different durations etc. so you would have jobs A->B for 1,2,..,n hours each. Of course, if you create lots of planning entities, your search space will increase rapidly and your problem will become more difficult to solve. So you probably would need to come up with some heuristic of what jobs (and how many of them) to create.

I suppose with this approach you would also have to dynamically calculate job start and end times based on the previous assignment (something similar is done in the vehicle-routing examples). Maybe take a look at the chained through time pattern.

Modelling intermediate products could be tricky. Trying to connect jobs that produce intermediate results and jobs that require these intermediate products could be quite inefficient in terms of computation. Maybe you could avoid this with writing custom moves that schedule or unschedule such connected jobs together. Custom moves take some time to understand and implement. Also, you might be starting to go off track when diving deeper into this feature.

I'm not sure if I've taken all your requirements into account correctly, so it is still possible that this approach won't lead to the solution you desire.

Bottom line: Is it possible to model your problem with Timefold? Maybe. Is this model going to perform well (in terms of solution quality and speed)? I can't tell. Is the implementation going to be easy? Possibly not (but what real operations research problem is easy?) Might it be worth a try? Depends on how much time you're willing to spend to learn about Timefold and toy around with a basic implementation.

I suppose you would have liked a simple yes or no answer better, but I hope this answer has given you at least some starting points to gather more information and come to a decision 🤞

[borisboc]

Dear @greyhairredbear , thanks for your reply and your efforts to make it clear for me. Indeed, I was hopping for a nice "Yes it is feasible, you just missed the right information which is ...". Or the contrary like "No, by design, Timefold is meant to work like ... and not like what you propose". What I understand from your reply, is that it will definitely require a lot of learning from my side. I am always happy to learn new skills, but I also need to properly invest my time ^^. And currently, for the above proposed problem, I don't know if Timefold is a better choice than PDDL (e.g. with unified-planning, I did a proof of concept with it, but I am not happy with the metrics / scoring) or CP (e.g. with Google OR tools or Pyomo, or Gurobi, I have tried none of them so far). May I ask for your opinion ?

[greyhairredbear]

Unfortunately, my experience with other tools is very limited. I haven't worked with PDDL before. I have looked into Google's OR tools before for my the work I did on my Master's, but decided to go with Optaplanner (the Timefold predecessor) for better testability and, as you've already noted, good score explanation.

At my current company, it has been tried to solve a Vehicle Routing Problem (VRP) with OR tools, but results were not good enough (for whatever reasons, from what I've heard, lack of score explanation was one issues). They decided to pivot to use Optaplanner/Timefold and (luckily for me) hire a dedicated engineer for this.

So my experience with Timefold applications is limited to my Master's (a project scheduling problem) and my current position (VRP).

A note in case you (or your company) are willing to spend money on this: The first 2 weeks at my current position, we additionally hired an Simon Tiffert from Optazen as an external consultant to get up to speed. This helped a great deal. But VRPs have been solved with Timefold before, so there was definitely less risk involved with doing this. It might be possible to get paid support from Timefold directly too, but I don't know the conditions here.

Others (people on the Timefold team or Simon) have worked on way more possible applications for Timefold than myself, so their insights would definitely be more valuable and could help you figure out if going this way is feasible. Depending on if you're willing to spend money to save yourself some time, this can be a good alternative.

[greyhairredbear]

This morning, another possible approach to model your problem came to my mind: You could have Jobs as a fixed set of possible paths through your production line. Something like:

J1: A->C
J2: A->B
J3: B->C

Then, depending on how many employees are assigned to each job, the duration of that job would vary and would need to be calculated after changing employee assignment.

This approach could make your solution more efficient than my first proposal, but I guess the most other modelling challenges would still persist.

Now that I put more thought to this, I think your problem should be solvable with Timefold. Still no guarantees, and I'm still convinced the effort required will be significant. But again, I guess that would apply to any possible tool out there, because your problem is not simple. (as no real world problem is)

[borisboc]

Hello @greyhairredbear , thanks for your advises. I think I will then standby this project as it sadly requires more efforts than I though. It is for sure a very nice subject I would like to work on, but I have to correctly allocate my time (e.g. to pay myself ^^). I wish you good luck on your projects.

[greyhairredbear]

No need to explain, you're welcome. It was a fun exercise to think about your problem 😃