2
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.