In quite a few cases I have been unable to reproduce published results. Here is an example. (Update: actually the presented results are correct, just a typo in the problem description: see the comments). In the paper http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.138.5011 an example is given of a job shop problem. The data is as follows:
I.e. there are 10 jobs each having 3 job steps. The job steps have to be executed in a certain given order (it might have been easier just to reorder the job step numbers and say all job steps have to be executed in the given order). The authors mention the following:
However when I try to reproduce this with a MIP model I can achieve a makespan of 7. Below is the GAMS model:
The model has a few interesting wrinkles:
- I remap the job steps from tuples (job1,op1),(job1,op2),.. to a one dimensional set js1,js2,… This causes some headaches when converting the input data but makes the model equations simpler.
- I map the solution back to the tuples (job1,op1),(job1,op2),.. after the solve.
- A problem with these models is always to find a good big-M. For real problems you may find one by preceding the MIP model with a simple heuristic that constructs an initial solution.
- I try to make sure we don’t compare the job steps twice for overlap if they are scheduled on the same machine. Hence the set UT.
Here are my results:
---- 157 PARAMETER results
start proc finish machine
j1 .op1 1 1 2 1
Of course it is possible there is a transcription error in the data table, or may be I am misreading the model, or some other trivial problem. However the results look reasonable when looking at the GANTT charts, i.e. there is no overlap, and the selected machines for processing the job steps are efficient in doing so (we did not select slow machines).
This is actually a fairly small problem and a good MIP code has no problem with it. For instance Gurobi says:
Explored 0 nodes (287 simplex iterations) in 0.47 seconds
I would expect that genetic algorithms become more interesting for larger instances where a MIP solver may not get anywhere.