In the model I am working on we use a time indexed binary variable to model the schedule:
When I solved this model for 1000 seconds, I observed that most of the action takes place in the first few nodes. I was thinking that the following simple algorithm may work to get better improvements:
- Solve for a shorter time with initial planning horizon giving us a makespan<horizon.
- Reduce planning horizon to the makespan, and resolve. This model is now smaller, and with MIPSTART we can quickly branch towards the last found solution.
- Repeat step 2 until out of time.
The loop looks like:
solve dt minimizing makespan using mip;
z.fx$(z.l<0.01) = 0;
This looks like a reasonable approach:
At least for this case it is better to solve 5 models for 200 seconds than one model for 1,000 seconds. Notice that we reduce the size of the problem in each cycle.