CP-SAT solver doesn't use all space available for scheduling

Question

This problem is a continuation of this problem. The issue here is the solver doesn't use the whole space available for the scheduling and thus some jobs are not being scheduled. For example: we need to schedule 9 jobs of given durations: job_durations = [10, 10, 10, 30, 30, 30, 50, 50, 50]. Just like in referenced higher problem, jobs have their release dates: release_dates = [0, 0, 0, 0, 0, 0, 0, 0, 0] and due dates: due_dates = [1200, 1200, 1200, 1800, 1800, 1800, 2400, 2400, 2400]. As you can see, jobs of indices 0-2 require 30 of 1200 available units of time, jobs of indices 3-5 need 90 of 1800 available units of time and jobs of indices 6-8 require 150 of 2400 available time units. If you launch the script, you'll see that job 0 won't be scheduled at all. Now if you'll append another job, say job_duration = 50, job_due_date = 2400 and job_release_date = 0 and start the program, you'll see all jobs are scheduled nicely despite having enough space for all jobs before new job appending and after it.

I have set the flag enumerate_all_solutions = True to make solver find all solutions, but this didn't help. I also tried using flag num_search_workers = 6 and sometimes the solver doesn't schedule job 0 also. Do you know what might be wrong here? Does this have something to do with circuit constraint?

Here's the code in Python:

from ortools.sat.python import cp_model

# ----------------------------------------------------------------------------
# Model.
model = cp_model.CpModel()

# ----------------------------------------------------------------------------
# Data.

job_durations = [10, 10, 10, 30, 30, 30, 50, 50, 50]

release_dates = [0, 0, 0, 0, 0, 0, 0, 0, 0]

due_dates = [1200, 1200, 1200, 1800, 1800, 1800, 2400, 2400, 2400]

# ----------------------------------------------------------------------------
# Helper data.
num_jobs = len(job_durations)
all_jobs = range(num_jobs)

# True is job of 'job_id' is scheduled, false otherwise.
x = [model.NewBoolVar(f'x_{job_id}') for job_id in all_jobs]

# ----------------------------------------------------------------------------
# Set big enough horizon value.
horizon = max(due_dates)
print('Horizon =', horizon)

# ----------------------------------------------------------------------------
# Global storage of variables.
intervals = []
starts = []
ends = []

# ----------------------------------------------------------------------------
# Scan the jobs and create the relevant variables and intervals.
for job_id in all_jobs:
    duration = job_durations[job_id]
    release_date = release_dates[job_id]
    due_date = due_dates[job_id] if due_dates[job_id] != -1 else horizon
    print('job %2i: start = %5i, duration = %4i, end = %6i' %
          (job_id, release_date, duration, due_date))
    name_suffix = '_%i' % job_id
    start = model.NewIntVar(release_date, due_date, 's' + name_suffix)
    end = model.NewIntVar(release_date, due_date, 'e' + name_suffix)
    interval = model.NewOptionalIntervalVar(start, duration, end, x[job_id], 'i' + name_suffix)
    starts.append(start)
    ends.append(end)
    intervals.append(interval)

# No overlap constraint.
model.AddNoOverlap(intervals)

# ----------------------------------------------------------------------------
# Transition times using a circuit constraint.
arcs = []

# No job scheduled.
empty_lit = model.NewBoolVar('empty_lit')
arcs.append([0, 0, empty_lit])

for i in all_jobs:
    # Initial arc from the dummy node (0) to a job.
    start_lit = model.NewBoolVar('')
    arcs.append([0, i + 1, start_lit])

    # If this job is the first, set to minimum starting time.
    model.Add(starts[i] == release_dates[i]).OnlyEnforceIf(start_lit)

    # Job is scheduled if the graph starts with it.
    model.AddImplication(start_lit, x[i])

    # Final arc from an arc to the dummy node.
    arcs.append([i + 1, 0, model.NewBoolVar('')])

    # Add 'x[job_id].Not()' literal to each node
    arcs.append([i + 1, i + 1, x[i].Not()])

    # Link empty_lit and x[i]
    model.AddImplication(empty_lit, x[i].Not())

    # Fix start and end for unperformed jobs.
    model.Add(starts[i] == release_dates[i]).OnlyEnforceIf(x[i].Not())

    for j in all_jobs:
        if i == j:
            continue

        lit = model.NewBoolVar('%i follows %i' % (j, i))
        arcs.append([i + 1, j + 1, lit])

        # Force gaps between tasks of same jobs.
        model.Add(starts[j] >= ends[i]).OnlyEnforceIf(lit)

        # job[i] and job[j] are scheduled if they are successively scheduled by the solver.
        model.AddImplication(lit, x[i])
        model.AddImplication(lit, x[j])

model.AddCircuit(arcs)

# ----------------------------------------------------------------------------
# Objective.
makespan = model.NewIntVar(min(release_dates), horizon, 'makespan')
for i in all_jobs:
    model.Add(makespan >= ends[i]).OnlyEnforceIf(x[i])
model.Maximize(makespan)

# ----------------------------------------------------------------------------
# Solve.
solver = cp_model.CpSolver()
# solver.parameters.max_time_in_seconds = 60 * 60 * 2
solver.parameters.enumerate_all_solutions = True
# solver.parameters.num_search_workers = 6
solver.Solve(model)
print(solver.ResponseStats())
for job_id in all_jobs:
    if solver.BooleanValue(x[job_id]):
        print(
            f'job {job_id} starts at {solver.Value(starts[job_id])} and ends at {solver.Value(ends[job_id])}'
        )
    else:
        print(f'job {job_id} is not scheduled')

Answer 1

Once again, the objective does not incentive scheduling tasks. So you rely on the randomness of the multi threaded search