It seems that the dependencies are not satisfied after random_insert. I put assertions after it and it turns out the assertions fail.
The reason looks like the line ll = np.max(indices[preds[job]], initial=0) + 1. When there is no predecessor of job, ll will be 1 and never be 0, which means if we remove the first job, it must be put after another job (the one whose index is 0 after removal) after random_insert.
def random_insert(state, rnd_state):
"""
Randomly inserts jobs into the schedule. The resulting solution state
is guaranteed to be feasible.
"""
indices = state.indices
preds = instance.all_predecessors
succs = instance.all_successors
for job in state.unscheduled:
# Left and right insertion limits. The job must be inserted
# between these indices - the interval is [ll, rl).
ll = np.max(indices[preds[job]], initial=0) + 1
rl = np.min(indices[succs[job]], initial=len(state.jobs))
idx = rnd_state.randint(ll, rl) if ll < rl else ll
state.jobs.insert(idx, job)
indices[indices >= idx] += 1
indices[job] = idx
for job in range(instance.num_jobs):
for pre in instance.predecessors[job]:
assert(state.indices[pre] < state.indices[job])
for job in range(instance.num_jobs):
for suc in instance.successors[job]:
assert(state.indices[job] < state.indices[suc])
return justify(state)
It seems that the dependencies are not satisfied after
random_insert
. I put assertions after it and it turns out the assertions fail. The reason looks like the linell = np.max(indices[preds[job]], initial=0) + 1
. When there is no predecessor ofjob
,ll
will be 1 and never be 0, which means if we remove the first job, it must be put after another job (the one whose index is 0 after removal) afterrandom_insert
.