We could not solve my job shop formulations in http://yetanothermathprogrammingconsultant.blogspot.com/2014/04/playing-with-job-shop-problem-ft10-2.html but actually Or-tools has a pretty good C++ based implementation: https://code.google.com/p/or-tools/source/browse/trunk/examples/cpp/jobshop.cc. This can solve the ft10 problem in reasonable time:
The problem is solved to a proven optimal solution in less than 5 minutes.
Some obvious questions arise:
- So how is this implementation different from the Minizinc models I did before? One difference is that it is using interval variables. These variables have a start and a duration, and are often used in scheduling models. I am not sure how to use these variable in a Minizinc model.
- Can we create a Minizinc model with similar performance?
- The optimization is probably done by:
- Find solution
- If infeasible stop
- Else add the constraint obj < obj_found to the model and go to step 1
- When invoked without a data file name, the program crashes:
Looks like this is caused by an abort() statement (replace by exit(-1) to stop more gracefully).
- The performance over time looks vey much like a MIP solver:
i.e. quick progress at the beginning and slowing down later on.