Adding resource constraints to the job shop example

[kevinl412]

Hi,

I am very new to using the ortools and I am trying to do the job shop example that google ortools has online but I am trying to add resource constraints (meaning that at each moment, the sum of demand of the tasks are not exceeded by the availability of the resource). I have tried to use the AddCumulative but I can't figure out how to use it... Can anybody help me with this? Thank you:)

This is what I have:

import collections
from ortools.sat.python import cp_model, visualization
import pandas as pd
import numpy as np

jobs_data = [
    [(0, 30, 1), (0, 20, 1), (0, 60, 1), (0,80, 1), (0,60, 1), (0, 100, 1), (0, 20, 1)], #work order 1, duration, demand
    [(1, 45, 1), (1, 20, 1), (1,40, 1), (1,120, 1), (1,40, 1), (1, 100, 1), (1,20, 1)], #work order 2, duration, demand
    [(2, 50, 1), (2, 20, 1), (2,60, 1), (2,120, 1), (2,60, 1), (2, 100,1), (2, 20, 1)] #work order 3, duration, demand
]

demands = [[task[2] for task in job] for job in jobs_data]

machines_count = 3
all_machines = range(machines_count)

resources_count = 1 + max(task[2] for job in jobs_data for task in job)
all_resources = range(resources_count)

horizon = sum(task[1] for job in jobs_data for task in job)

model = cp_model.CpModel()

task_type = collections.namedtuple('task_type', 'start end interval')
assigned_task_type = collections.namedtuple('assigned_task_type', 'start job index duration')

all_tasks = {}
machine_to_intervals = collections.defaultdict(list)

resource_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]
        demand = 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)
        all_tasks[job_id, task_id] = task_type(start=start_var, end= end_var, interval = interval_var)
        machine_to_intervals[machine].append(interval_var)

for job_id, job in enumerate(jobs_data):
    for task_id, task in enumerate(job):
        machine = task[0]
        duration = task[1]
        demand = 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)
        resource_to_intervals[machine].append(demand)

for machine in all_machines:
    model.AddCumulative(intervals = machine_to_intervals[machine], demands = resource_to_intervals[machine], capacity = 1)

for machine in all_machines:
    model.AddNoOverlap(machine_to_intervals[machine])

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)

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)

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print('Solution:')
    # 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 = 'wo_%i_activity_%i' % (assigned_task.job,
                                       assigned_task.index)
            # Add spaces to output to align columns.
            sol_line_tasks += '%-15s' % 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 += '%-15s' % sol_tmp

        sol_line += '\n'
        sol_line_tasks += '\n'
        output += sol_line_tasks
        output += sol_line

    # Finally print the solution found.
    print(f'Optimal Schedule Length: {solver.ObjectiveValue()}')
    print(output)
else:
    print('No solution found.')

[lperron]

have you checked examples with the cumulative constraint ? gate_scheduling, rcpsp ?

[kevinl412]

I have checked the gate_scheduling example. I have followed this example and I was able to create a schedule. However, this example has one fixed capacity (max_width). I want to be able to have varying values for this variable per certain interval. I saw something about using fixed intervals but I do not quite know how to do this... (i'm quite new to this)