Monday, September 21, 2009

Job Shop Scheduling

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.


10 comments:

  1. You can solve it easily with constraint programming using Comet ;-)
    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/

    Pierre

    ReplyDelete
  2. May be I should charge for advertisement

    ReplyDelete
  3. Very interesting. Are you planning to post your code too?

    ReplyDelete
  4. 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
  5. 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 in
    code-cp-scheduling/jobshop-cp.co and the instance is mt10.txt. It uses Constraint programming.
    Cheers,
    Stéphane.
    -----

    ReplyDelete
  6. Sorry for the advertisement, this was not my purpose.
    I only wanted to point that (from my point of view) Constraint Programming can be more suited than MIP for this kind of problem.

    Pierre

    ReplyDelete
  7. Excellent post. These are the types of tools that can really be useful to an OR analyst.

    ReplyDelete
  8. hi, this is exactly what i need. Could you please send me your vba?
    Thanks in advance
    quangnamps@yahoo.com

    ReplyDelete
  9. I'm interested in your VBA code. Could you send it to me for free? if not, how much it costs?

    Thanks in advance

    inner_mephisto@yahoo.es

    ReplyDelete
  10. Sorry, this is part of a larger project and is not available as standalone download.

    ReplyDelete