A scheduling problem

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).