I'm new to Google OR-Tools (and constraint programming in general) and I'm trying to add deadlines to the Jobshop example, but it's not really working.
The job-shop example I took can be found here: https://developers.google.com/optimization/scheduling/job_shop#entire-program
I changed a few things:
model.Add(all_tasks[job_id, task_id].end <= all_tasks[job_id, task_id].deadline)But it doesn't work. It does do something, as the schedule it outputs changes and when I input impossible deadlines it returns 0 results. But it doesn't properly take into account the deadlines. What am I doing wrong?
This is the output I get with my modified version:
Optimal Schedule Length: 11
Machine 0: job_0_0 job_1_0
[0,3] [3,5]
Machine 1: job_2_0 job_0_1 job_1_2
[0,4] [4,6] [6,10]
Machine 2: job_1_1 job_0_2 job_2_1
[5,6] [6,8] [8,11]
As you can see, job 0 has a deadline of 7, but in the schedule it ends at 8.
Here's my full modified example:
from __future__ import print_function
import collections
# Import Python wrapper for or-tools CP-SAT solver.
from ortools.sat.python import cp_model
def MinimalJobshopSat():
"""Minimal jobshop problem."""
# Create the model.
model = cp_model.CpModel()
jobs_data = [ # task = (machine_id, processing_time).
[(0, 3, 7), (1, 2, 7), (2, 2, 7)], # Job0
[(0, 2, 12), (2, 1, 12), (1, 4, 12)], # Job1
[(1, 4, 12), (2, 3, 12)] # Job2
]
machines_count = 1 + max(task[0] for job in jobs_data for task in job)
all_machines = range(machines_count)
# Computes horizon dynamically as the sum of all durations.
horizon = sum(task[1] for job in jobs_data for task in job)
# Named tuple to store information about created variables.
task_type = collections.namedtuple('task_type', 'start end deadline interval')
# Named tuple to manipulate solution information.
assigned_task_type = collections.namedtuple('assigned_task_type',
'start job index duration')
# Creates job intervals and add to the corresponding machine lists.
all_tasks = {}
machine_to_intervals = collections.defaultdict(list)
for job_id, job in enumerate(jobs_data):
for task_id, task in enumerate(job):
machine = task[0]
duration = task[1]
deadline = task[2]
suffix = '_%i_%i' % (job_id, task_id)
start_var = model.NewIntVar(0, horizon, 'start' + suffix)
end_var = model.NewIntVar(0, horizon, 'end' + suffix)
interval_var = model.NewIntervalVar(start_var, duration, end_var,
'interval' + suffix)
deadline_var = model.NewIntVar(deadline, deadline,
'deadline' + suffix)
all_tasks[job_id, task_id] = task_type(
start=start_var, end=end_var, deadline=deadline_var, interval=interval_var)
machine_to_intervals[machine].append(interval_var)
# Create and add disjunctive constraints.
for machine in all_machines:
model.AddNoOverlap(machine_to_intervals[machine])
# Precedences inside a job.
for job_id, job in enumerate(jobs_data):
for task_id in range(len(job) - 1):
model.Add(all_tasks[job_id, task_id].end <= all_tasks[job_id, task_id].deadline)
model.Add(all_tasks[job_id, task_id +
1].start >= all_tasks[job_id, task_id].end)
# Makespan objective.
obj_var = model.NewIntVar(0, horizon, 'makespan')
model.AddMaxEquality(obj_var, [
all_tasks[job_id, len(job) - 1].end
for job_id, job in enumerate(jobs_data)
])
model.Minimize(obj_var)
# Solve model.
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
# Create one list of assigned tasks per machine.
assigned_jobs = collections.defaultdict(list)
for job_id, job in enumerate(jobs_data):
for task_id, task in enumerate(job):
machine = task[0]
assigned_jobs[machine].append(
assigned_task_type(
start=solver.Value(all_tasks[job_id, task_id].start),
job=job_id,
index=task_id,
duration=task[1]))
# Create per machine output lines.
output = ''
for machine in all_machines:
# Sort by starting time.
assigned_jobs[machine].sort()
sol_line_tasks = 'Machine ' + str(machine) + ': '
sol_line = ' '
for assigned_task in assigned_jobs[machine]:
name = 'job_%i_%i' % (assigned_task.job, assigned_task.index)
# Add spaces to output to align columns.
sol_line_tasks += '%-10s' % name
start = assigned_task.start
duration = assigned_task.duration
sol_tmp = '[%i,%i]' % (start, start + duration)
# Add spaces to output to align columns.
sol_line += '%-10s' % sol_tmp
sol_line += '\n'
sol_line_tasks += '\n'
output += sol_line_tasks
output += sol_line
# Finally print the solution found.
print('Optimal Schedule Length: %i' % solver.ObjectiveValue())
print(output)
MinimalJobshopSat()
It doesn't work because you introduced the constraint in the for loop made for the precedences.
Create a new loop and remove the -1 from for task_id in range(len(job) - 1).
You can also set the deadline when creating end_var by restricting its upper bound.
Also, this github issue have some ideas that you could use: https://github.com/google/or-tools/issues/960