insert only a proportion of unassigned jobs

[oblonski]

Currently, the insertion heuristic tries to assign the entire set of unassigned jobs. This significantly impacts performance if there are many unassigned jobs. Therefore, the algorithm is way faster if only a proportion will be inserted, and it might have no impact on overall solution quality.

[LCenteleghe]

Trying to insert all of the unassigned jobs also makes the algorithm not to evaluate solutions that would be better without some jobs. I myself run into this problem, and my solution was to create a Hard Constraint that randomly (with a 10% chance) blocks some insertions, thus the algorithm would also try to consider solutions that do not include some of the jobs. So I believe that this insertion of only a proportion of unassigned jobs might help in such cases also.

[oblonski]

When using box.Jsprit one can configure the algorithm like this:

builder.setProperty(Jsprit.Parameter.MIN_UNASSIGNED, "10");
builder.setProperty(Jsprit.Parameter.PROPORTION_UNASSIGNED, "0.05");

This means that in each iteration at least 10 previously unassigned jobs are reinserted (at least the algo tries to reinsert it) and, at max,

previousSolution.getUnassignedJobs().size() * 0.05

For example, if there 400 jobs and 50 jobs are still unassigned in iteration i, then 20 out of these 50 jobs are randomly chosen to be inserted in iteration i.