JSSP Solver

[Luca Graebenteich]

Hi together,

I´m quite new to programming and directly got to this field of job shop scheduling.

I found OR-Tools pretty helpful and for our project I need an exact solver to compare solutions with others.

As I´ve been searching through the internet I found many heuristic algorithms and so on but it is pretty rare to find a "ready to use" program, or at least solver the explicitly gives out the exact/optimal solution.

From the basic code on the OR-Tools website for JSSP in line 77 you can change the if-statement from

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:

to only

 if status == cp_model.OPTIMAL:

So if I do this, will I definitely get the optimal solution for the problem?

The rest with constraintprogramming etc. is handable for me so far, I guess, I just need to be absolutely sure that I get the optimal solution and nothing worse.

Kind regards,

Luca

[Laurent Perron]

this is absurd.

If you have a time limit, you cannot guarantee that you will get the optimal solution.

If you are willing to wait millions of years, maybe.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/7696e632-359e-4f61-9d6f-cd5a10b0fcb6n%40googlegroups.com.

[Priidik Vilumaa]

To ensure you only get optimal results, then do not add a time limit (using something like parameters.max_time_in_seconds). Checking the status is just for postprocessing and won't affect the search.

However, as Laurent said, it will never work in practice unless you are only solving very small problems. The world runs on non-optimal solutions and it's not a bad thing because, well, it runs :)

Best,

Priidik

[Luca Graebenteich]

First of all: Thanks for answering so fast!

The thing is:

we have a pretty strong high performance computer at our university. Not in the top rankings in Germany anymore but still pretty strong.

It´s not about the computing time. It´s about a comparison result for classic heuristic approaches and some technically still mostly untapped computing hardware.

Our problems are not very small, but also not too big, so we`re prepared to await computing times of days, if it´s necessary. Most important really is the optimal solution for reference.

For an estimation let´s say there´s a manufacturer with 20-30 machines, 100-200 orders each day and  5-10 constraints. Calculating an optimal solution should be possible, isn´t it? Like I said, I´ll not be running this on an office PC, or maybe a better work station in a company but on a pretty remarkable high performance computer of a technical university, not in seconds or minutes, but up to days. Right now the project is in the beginning and the computational effort is far smaller. But later on the said dimensions will be necessary and therefore we also need optimal references to compare our other approaches with smaller computing times.

I´d be glad for a rough estimation if my ideas are realistic, or rather not.

Kind regards,

Luca

[Laurent Perron]

Realistically, you cannot assume optimality. Proofs are really hard.

This being said, CP-SAT is state of the art on JSSP with 16-32 workers.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/cb93fc1c-1485-45f1-b24c-14989567d48an%40googlegroups.com.

[Luca Graebenteich]

Thanks again for the answer.

I´m still looking for an algorithm/solver that gives me optimal solutions. In the most papers which contain a topic for exact solutions it is never explicitly mentioned, that the related algorithm acutally gives an optimal solution in all cases.

Is there any case you know, how it is possible? I already realized, as you said, true optimality is mostly assumed, but I didn´t a code with an actual proof that it`s acutally achieved.

So should I just assume an optimal solution if I get same results in every new processing? Even if it could still only be a local optimum, but not a global one? If my problem gets "bigger" should I just try different computing times until I start getting the same result (minimum makespan) for every run?

Thank you anyway for your help. I´m still pretty new also to the theory of constraint programming, especially the case of JSSP.

[Laurent Perron]

These problems are NP-Hard.

Nobody can guarantee optimality on all problems.

You are confused by the notion of exact algorithms vs approximate algorithms.

Exact algorithms may prove optimality. Approximate algorithms like local search are good at finding good solution, but usually never prove optimality.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1fb005cd-b290-4301-902b-d2ab74baace4n%40googlegroups.com.