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.


Posted by at

10 comments:

  1. pschausSeptember 21, 2009 at 3:32 AM

    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. Erwin KalvelagenSeptember 21, 2009 at 4:12 AM

    May be I should charge for advertisement

    ReplyDelete
  3. AnonymousSeptember 21, 2009 at 4:48 AM

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

    ReplyDelete
  4. Erwin KalvelagenSeptember 21, 2009 at 5:02 AM

    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. AnonymousSeptember 21, 2009 at 8:55 AM

    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. pschausSeptember 21, 2009 at 8:55 AM

    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. Larry (IEOR Tools)September 21, 2009 at 9:41 AM

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

    ReplyDelete
  8. namgiaonlineNovember 29, 2012 at 12:08 PM

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

    ReplyDelete
  9. AnonymousJanuary 14, 2013 at 6:42 AM

    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. Erwin KalvelagenJanuary 14, 2013 at 9:43 AM

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

    ReplyDelete

Subscribe to: Post Comments (Atom)