Although standard MIP formulations do not work very well on this problem, the current crop of MIP solvers can solve problems that used to be very difficult to solve. As example consider ft10 with 100 operations (10 machines, 10 jobs). This problem was unsolved for 26 years after its introduction in 1963. Now this can be solved in about 5 minutes to optimality using solvers like Gurobi and Cplex. (Some tabu search based methods have been able to find the optimal solution in seconds).
I wanted to solve this from Excel, but as Excel has no native GANTT charts, I created some VBA code so I could at least inspect the results.
You can solve it easily with constraint programming using Comet ;-)ReplyDelete
Comet has also a native GANTT chart so that you can make a nice animation of the solution progress.
You can download Comet here http://dynadec.com/
May be I should charge for advertisementReplyDelete
Very interesting. Are you planning to post your code too?ReplyDelete
Yes; after I cleaned it up a little bit. Also I did a few things manually, so want to make sure it is more automated to be useful more generally.ReplyDelete
Comet can solve and proves optimiality on this instance in 7,5 seconds (makespan 930). There is also a version with built-in vizualization (easier than writing VBA code I think). The code for this problem is included in the Comet package that can be downloaded online. The code is located inReplyDelete
code-cp-scheduling/jobshop-cp.co and the instance is mt10.txt. It uses Constraint programming.
Sorry for the advertisement, this was not my purpose.ReplyDelete
I only wanted to point that (from my point of view) Constraint Programming can be more suited than MIP for this kind of problem.
Excellent post. These are the types of tools that can really be useful to an OR analyst.ReplyDelete
hi, this is exactly what i need. Could you please send me your vba?ReplyDelete
Thanks in advance
I'm interested in your VBA code. Could you send it to me for free? if not, how much it costs?ReplyDelete
Thanks in advance
Sorry, this is part of a larger project and is not available as standalone download.ReplyDelete