I am working with a variant of the job shop problem where I wish to modify the task duration based on their assignment/rank in the machine schedule.
e.g. a simple case would be that the first task assigned on the machine will take 50% longer to complete.
A more general case would be that every nth task on a machine would require X% longer.
I have read about channelling constraints but I am not sure how to implement them in this scenario or if there are other better alternatives. Any direction would be much appreciated.
Below is the code I am using from or tools documentation for the job shop problem.
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).
[(2, 1), (0, 1), (1, 1)], # Job0
[(0, 1), (1, 1)], # Job1
[(1, 1), (2, 1)] # 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 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]
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)
all_tasks[job_id, task_id] = task_type(
start=start_var, end=end_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.
# Change constraint to only respect the project start date i.e. the first dummy task
for job_id, job in enumerate(jobs_data):
for task_id in range(len(job) - 1):
model.Add(all_tasks[job_id, task_id + 1].start >= all_tasks[job_id, task_id].end)
The modified output we would expect for this case would be the following, where the duration of the first task on each machine is increased by 50%
Optimal Schedule Length: 4
Machine 0: job_1_0 job_0_1
[0,2] [2,3]
Machine 1: job_2_0 job_0_2 job_1_1
[0,2] [2,3] [3,4]
Machine 2: job_0_0 job_2_1
[0,2] [2,3]
Look at this constraint, it creates a circuit constraint that does the transitive reduction of precedences into a sequence of tasks.
Now you can use the start literal of each task to imply the correct duration
model.Add(duration[i] == int(nominal_duration * 1.5)).OnlyEnforceIf(start_lit)
model.Add(duration[i] == nominal_duration).OnlyEnforceIf(start_lit.Not())