For a scheduling that I could not solve in one swoop I tried to develop a small algorithm. Basically: schedule the m<n jobs that come first, then fix the m jobs and schedule the next m jobs. This seems to work with Cplex. The algorithm looks like:
loop(k, j(j0) = kj(k,j0); solve sched minimizing makespan using mip; report(k,'obj') = sched.objval; report(k,'modelstat') = sched.modelstat; report(k,'solvestat') = sched.solvestat; xstart.fx(j,t) = xstart.l(j,t); ); |
This algorithm will perform the following:
1-10 | 11-20 | 21-30 | 31-40 | 41-50 |
solved | | | | |
fixed | solved | | | |
fixed | fixed | solved | | |
fixed | fixed | fixed | solved | |
fixed | fixed | fixed | fixed | solved |
For Cplex we get:
---- 180 PARAMETER report obj modelstat solvestat k1 1480.000 1.000 1.000 k2 2940.000 1.000 1.000 k3 4400.000 1.000 1.000 k4 5860.000 1.000 1.000 k5 7320.000 1.000 1.000
|
However for Gurobi we get:
---- 180 PARAMETER report obj modelstat solvestat k1 1480.000 1.000 1.000 k2 2940.000 1.000 1.000 k3 4400.000 1.000 1.000 k4 19.000 1.000 k5 19.000 1.000
|
It turns out that the fixing of a solution causes the next iteration to be infeasible. We can actually isolate step k3 and do:
solve m minimizing makespan using mip; xstart.fx(j,t) = xstart.l(j,t); solve m minimizing makespan using mip; |
This will make the second model infeasible: i.e. Gurobi does not like its own solution! In this case it is a tolerance question: the final solution is slightly infeasible. We can fix this by:
loop(k, j(j0) = kj(k,j0); solve m minimizing makespan using mip; report(k,'obj') = m.objval; report(k,'modelstat') = m.modelstat; report(k,'solvestat') = m.solvestat; xstart.fx(j,t) = round(xstart.l(j,t)); );
|
because we know all job step times are in whole seconds. Now both Cplex and Gurobi can solve the problem just fine.
A reasonable good solution looks like:
By accident our algorithmic batch size is the same as the batch size for a good solution (this is not required for the algorithm to work).
The solution is somewhat sensitive where we put the breaks when decomposing the model. This may indicate a rolling horizon algorithm may work better (see http://yetanothermathprogrammingconsultant.blogspot.com/2008/06/rolling-horizon-implementation-in-gams.html).