CP-SAT solver (Job Shop Scheduling): Add Worker constraint & PK to data

[Iana de Castro]

Hello!

I use this model for my Job Shop Scheduling: https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py

I wish to add a Worker constraint that is to be scheduled with the Machine. Workers are categorized into the Machine/Task types as well.

So the resulting schedule would be:

task_x_y starts at z (alt a, machine b, duration c, worker d)

Thank you! 

[Laurent Perron]

Just to it :-)

Change the tuples, add the constraints.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Also, I wish to add a sort of PK or ID to the jobs in the data.

 

jobs = [[[(11, 1), (11, 5)], [(8, 3)]], [[(11, 1), (11, 5)], [(8, 3)]], [[(11, 1), (11, 5)], [(8, 3)]], [[(13, 1), (13, 5)], [(10, 3)]], [[(17, 1), (17, 5)], [(12, 3)]], [[(22, 1), (22, 5)], [(17, 3)]], [[(26, 1), (26, 5)], [(20, 3)], [(33, 2)], [(20, 4)]], [[(12, 1), (12, 5)], [(9, 3)]], [[(28, 1), (28, 5)], [(21, 3)], [(35, 2)]], [[(28, 1), (28, 5)], [(21, 3)]], [[(11, 1), (11, 5)], [(8, 3)]], [[(28, 1), (28, 5)], [(21, 3)], [(35, 2)]], [[(26, 1), (26, 5)], [(19, 3)], [(33, 2)]]]

I understand these are denoted by (duration, machine) but I wish to also assign an ID to each task before the generation of schedule.

Thank you! 

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5a3ce922-8305-4eb4-b36d-a177ad36eabb%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Iana de Castro]

What else should be added in this part? I haven't fully grasped the concept behind the intervals. :/

# Global storage of variables.
intervals_per_resources = defaultdict(list)
starts = {}  # indexed by (job_id, task_id).
presences = {}  # indexed by (job_id, task_id, alt_id).
job_ends = []

# Scan the jobs and create the relevant variables and intervals.
for job_id in all_jobs:
    job = jobs[job_id]
    num_tasks = len(job)
    previous_end = None

    for task_id in range(num_tasks):
        task = job[task_id]

        min_duration = task[0][0]
        max_duration = task[0][0]

        num_alternatives = len(task)
        all_alternatives = range(num_alternatives)

        for alt_id in range(1, num_alternatives):
            alt_duration = task[alt_id][0]
            min_duration = min(min_duration, alt_duration)
            max_duration = max(max_duration, alt_duration)

        # Create main interval for the task.
        suffix_name = '_j%i_t%i' % (job_id, task_id)
        start = model.NewIntVar(0, horizon, 'start' + suffix_name)
        duration = model.NewIntVar(min_duration, max_duration,
                                   'duration' + suffix_name)
        end = model.NewIntVar(0, horizon, 'end' + suffix_name)
        interval = model.NewIntervalVar(start, duration, end,
                                        'interval' + suffix_name)

        # Store the start for the solution.
        starts[(job_id, task_id)] = start

        # Add precedence with previous task in the same job.
        if previous_end:
            model.Add(start >= previous_end)
        previous_end = end

        # Create alternative intervals.
        if num_alternatives > 1:
            l_presences = []
            for alt_id in all_alternatives:
                alt_suffix = '_j%i_t%i_a%i' % (job_id, task_id, alt_id)
                l_presence = model.NewBoolVar('presence' + alt_suffix)
                l_start = model.NewIntVar(0, horizon, 'start' + alt_suffix)
                l_duration = task[alt_id][0]
                l_end = model.NewIntVar(0, horizon, 'end' + alt_suffix)
                l_interval = model.NewOptionalIntervalVar(
                    l_start, l_duration, l_end, l_presence,
                    'interval' + alt_suffix)
                l_presences.append(l_presence)

                # Link the master variables with the local ones.
                model.Add(start == l_start).OnlyEnforceIf(l_presence)
                model.Add(duration == l_duration).OnlyEnforceIf(l_presence)
                model.Add(end == l_end).OnlyEnforceIf(l_presence)

                # Add the local interval to the right machine.
                intervals_per_resources[task[alt_id][1]].append(l_interval)

                # Store the presences for the solution.
                presences[(job_id, task_id, alt_id)] = l_presence

            # Select exactly one presence variable.
            model.Add(sum(l_presences) == 1)
        else:
            intervals_per_resources[task[0][1]].append(interval)
            presences[(job_id, task_id, 0)] = model.NewIntVar(1, 1, '')

    job_ends.append(previous_end)

# Create machines constraints.
for machine_id, intervals in intervals_per_resources.items():
    intervals = intervals_per_resources[machine_id]

    if len(intervals) > 1:
        model.AddNoOverlap(intervals)

# Create workers constraints.
for worker_id, intervals in intervals_per_resources.items():
    intervals = intervals_per_resources[worker_id]

    if len(intervals) > 1:
        model.AddNoOverlap(intervals)

On Thursday, May 23, 2019 at 6:53:07 PM UTC+8, Laurent Perron wrote:

Just to it :-)

Change the tuples, add the constraints.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le jeu. 23 mai 2019 à 12:02, Iana de Castro <decat...@gmail.com> a écrit :

Hello!

I use this model for my Job Shop Scheduling: https://github.com/google/or-tools/blob/stable/examples/python/flexible_job_shop_sat.py

I wish to add a Worker constraint that is to be scheduled with the Machine. Workers are categorized into the Machine/Task types as well.

So the resulting schedule would be:

task_x_y starts at z (alt a, machine b, duration c, worker d)

Also, I wish to add a sort of PK or ID to the jobs in the data.

 

jobs = [[[(11, 1), (11, 5)], [(8, 3)]], [[(11, 1), (11, 5)], [(8, 3)]], [[(11, 1), (11, 5)], [(8, 3)]], [[(13, 1), (13, 5)], [(10, 3)]], [[(17, 1), (17, 5)], [(12, 3)]], [[(22, 1), (22, 5)], [(17, 3)]], [[(26, 1), (26, 5)], [(20, 3)], [(33, 2)], [(20, 4)]], [[(12, 1), (12, 5)], [(9, 3)]], [[(28, 1), (28, 5)], [(21, 3)], [(35, 2)]], [[(28, 1), (28, 5)], [(21, 3)]], [[(11, 1), (11, 5)], [(8, 3)]], [[(28, 1), (28, 5)], [(21, 3)], [(35, 2)]], [[(26, 1), (26, 5)], [(19, 3)], [(33, 2)]]]

I understand these are denoted by (duration, machine) but I wish to also assign an ID to each task before the generation of schedule.

Thank you! 

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Iana de Castro]

How to incorporate in the intervals the new Worker cosntraint?

[Laurent Perron]

Create a new no_overlap per worker, and add the relevant intervals to this constraint.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/2cdc6227-e7ab-4a17-81f6-7223ee1888af%40googlegroups.com.

[Iana de Castro]

What seems to be missing in this part? 

[Laurent Perron]

A worker is another no_overlap constraint.

You create your master interval variable, assign it to a per_worker list, and create the constraint in the end. (here I assume the type of worker is independent of the alternative used).

You can read this nice introduction to scheduling with optional intervals

https://www.slideshare.net/PhilippeLaborie/conditional-interval-variables-a-powerful-concept-for-modeling-and-solving-complex-scheduling-problems

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/fdd8ea01-190a-4eb7-b8c7-3e114b77a563%40googlegroups.com.

[Iana de Castro]

Hello! Attached is my code. I've added the constraints but I'm still not sure how to modify the master interval variable :( Pls help