Flexible job shob with no idle time on a group of machines

[Agathe MM.]

Hello,

I am currently working on a flexible job shop with some additional constraints, and there is one constraint I struggle with.

I have a set of jobs that each contains a set of tasks, and some tasks can be done on alternative machines. So far it's a classical flexible job shop problem. My objective is to minimize the makespan.

For each job, the first task is always done on the same machine type i.e. on the same group of alternative machines. For this particular set of machines, I want to enforce the tasks to be done without any waiting time on each machine, which means I want no idle time on these machines (except when all tasks have been done).

Using the resources on the github and the group, I added the following code to model this constraint.

When I run the code, the solver returns 'INFEASIBLE', and I don't understand why. Is there something I am missing in the code ?

Thank you by advance,
Agathe Métaireau Manche

[Laurent Perron]

Is there a solution ? Playing tetris with exact matching start - end times can easily be infeasible.

Can you post the full code for a small problem?

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 visit https://groups.google.com/d/msgid/or-tools-discuss/38fbcc51-42bb-4119-b3a6-9d118be4747cn%40googlegroups.com.

[Agathe MM.]

Normally the problem is always feasible, as there are no constraint on the makespan or on due dates. So if I add a constraint, this theoretically only makes the optimal makespan longer. But maybe I missed something. Here is the code for a toy problem.

jobs = [  # task = (processing_time, machine_id)

        # Utilisation Tunnel

        [[(200, 1)]],

        [[(400, 2)]],

        # Job 1

        [[(600, 0), (600, 1), (600, 2)],

         [(120, 3), (180, 4), (240, 5)],

         [(1350, 7)]],

        # Job 2

        [[(600, 0), (600, 1), (600, 2)],

         [(779, 6)]],

        # Job 3

        [[(600, 0), (600, 1), (600, 2)],

         [(1800, 3), (2160, 4), (2700, 5)],

         [(864, 8)]],

        # Job 4

        [[(600, 0), (600, 1), (600, 2)],

         [(554, 6)]]]

num_jobs = len(jobs)

all_jobs = range(num_jobs)

machines_count = 9

all_machines = range(machines_count)

model = cp_model.CpModel()

horizon = 0

for job in jobs:

    for task in job:

        max_task_duration = 0

        for alternative in task:

            max_task_duration = max(max_task_duration, alternative[0])

        horizon += max_task_duration

# Global storage of variables.

intervals_per_resources = collections.defaultdict(list)

starts = {}  # indexed by (job_id, task_id).

ends = {} # 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.

        if len(jobs[job_id]) > 1:

            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

            )

        # Create artificial tasks for tunnel (i.e. les seuls jobs n'ayant qu'une seule tâche sont les jobs artificiels)

        else:

            suffix_name = "_j%i_t%i_off" % (job_id, task_id)

            start = 0

            duration = task[0][0]

            end = start + duration

            interval = model.NewIntervalVar(start, duration, end, "interval" + suffix_name)

        # Store the start and end for the solution.

        starts[(job_id, task_id)] = start

        ends[(job_id, task_id)] = end

        # Add precedence with previous task in the same job.

        if previous_end is not None:

            model.Add(start >= previous_end)

            # Add constraint on task 1 and 2 : no waiting time

            if task_id == 1:

                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 primary/global 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.AddExactlyOne(l_presences)

        else:

            intervals_per_resources[task[0][1]].append(interval)

            presences[(job_id, task_id, 0)] = model.NewConstant(1)

    job_ends.append(previous_end)

# Create machines constraints.

for machine_id in all_machines:

    intervals = intervals_per_resources[machine_id]

    # print(intervals)

    if len(intervals) > 1:

        model.AddNoOverlap(intervals)

# Pas de temps d'attente pour le tunnel

no_idle_machine_range = range(3)

arcs = {i: [] for i in no_idle_machine_range}

for job_id in all_jobs:

    for alt_id in all_alternatives:

        job = jobs[job_id][0]

        machine = job[alt_id][1]

        start_lit = model.NewBoolVar("%i_%i is first job" % (job_id, alt_id))

        arcs[machine].append((0, job_id + 1, start_lit))

        min_start_time = 0

        model.Add(starts[(job_id, 0)] == min_start_time).OnlyEnforceIf(start_lit)

        end_lit = model.NewBoolVar("%i_%i is last job" % (job_id, alt_id))

        arcs[machine].append((job_id + 1, 0, end_lit))

        for job_id_2 in all_jobs:

            if job_id == job_id_2:

                continue

            lit = model.NewBoolVar("%i follows %i_%i" % (job_id_2, job_id, alt_id))

            arcs[machine].append((job_id + 1, job_id_2 + 1, lit))

            model.Add(starts[(job_id_2, 0)] == ends[(job_id, 0)]).OnlyEnforceIf(lit)

for machine_id in no_idle_machine_range:

    if len(arcs[machine]) > 1:

        model.AddCircuit(arcs[machine])

# Makespan objective

makespan = model.NewIntVar(0, horizon, "makespan")

model.AddMaxEquality(makespan, job_ends)

model.Minimize(makespan)

# Solve model.

solver = cp_model.CpSolver()

solution_printer = SolutionPrinter()

solver.parameters.enumerate_all_solutions = False

solver.parameters.max_time_in_seconds = 300

status = solver.Solve(model, solution_printer)

print(solver.StatusName(status))

This is the flexible job shop available on github with the addition of 2 constraints :

1. For each job, there is no waiting time between task 1 and task 2

2. The machines used for task 1 must have no idle time until all tasks are completed

Thank you for your time,

Agathe METAIREAU MANCHE

[Agathe MM.]

I actually ran some additional tests and the toy problem I proposed may be infeasible, after analysis.

However, I have this set of jobs :

# Job 0.1

[[(200, 1)]],

# Job 0.2

 [[(400, 2)]],

# Job 1

[[(600, 0), (600, 1), (600, 2)],

 [(800, 6)]]]

# Job 2

[[(600, 0), (600, 1), (600, 2)],

 [(600, 6)]],

# Job 3

[[(600, 0), (600, 1), (600, 2)],

 [(1000, 3), (1000, 4), (1000, 5)],

 [(1000, 8)]]

# Job 4

[[(600, 0), (600, 1), (600, 2)],

[(200, 3), (200, 4), (200, 5)],

 [(1400, 7)]],

 

With a resolution "by hand", I can find the feasible solution below (with grey jobs being jobs 0.1 and 0.2).

The solver however still returns "infeasible" (with the same code)

[Laurent Perron]

Can you send me the full code with the data included ?

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/05d149df-f5ea-4e1f-9c9e-7fd57f9a7de9n%40googlegroups.com.

[Agathe MM.]

jobs = [

[[(200, 1)]],

# Job 0.2

 [[(400, 2)]],

# Job 1

[[(600, 0), (600, 1), (600, 2)],

 [(800, 6)]]]

# Job 2

[[(600, 0), (600, 1), (600, 2)],

 [(600, 6)]],

# Job 3

[[(600, 0), (600, 1), (600, 2)],

 [(1000, 3), (1000, 4), (1000, 5)],

 [(1000, 8)]]

# Job 4

[[(600, 0), (600, 1), (600, 2)],

[(200, 3), (200, 4), (200, 5)],

 [(1400, 7)]]]

[Agathe MM.]

Hello,

Sorry to bother, but did you have the time to check the code provided in the previous message ?

Have a nice day.

[Laurent Perron]

data seems to be wrong at the start of the file. The last bracket is dandling

jobs = [

[[(200, 1)]],

# Job 0.2

[[(400, 2)]],

# Job 1

[[(600, 0), (600, 1), (600, 2)],

[(800, 6)]]]

# Job 2

[[(600, 0), (600, 1), (600, 2)],

[(600, 6)]],

# Job 3

[[(600, 0), (600, 1), (600, 2)],

[(1000, 3), (1000, 4), (1000, 5)],

[(1000, 8)]]

# Job 4

[[(600, 0), (600, 1), (600, 2)],

[(200, 3), (200, 4), (200, 5)],

[(1400, 7)]]]

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/43d479fc-21f0-473e-ba0a-e76773a6ba06n%40googlegroups.com.

[Agathe MM.]

Here is the correct version with data and code. Sorry for the mistyping error.

jobs = [ # Job 0.1

[[(200, 1)]], # Job 0.2

  [[(400, 2)]],

# Job 1

[[(600, 0), (600, 1), (600, 2)],

  [(800, 6)]], # Job 2

[[(600, 0), (600, 1), (600, 2)],

  [(600, 6)]], # Job 3

[[(600, 0), (600, 1), (600, 2)],

  [(1000, 3), (1000, 4), (1000, 5)],

  [(1000, 8)]], # Job 4

[[(600, 0), (600, 1), (600, 2)],

[Laurent Perron]

You need to create one set of arcs per machine

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/53413781-1c83-4277-a02b-16cd8b9547f1n%40googlegroups.com.

[Agathe MM.]

I have a dictionary of arcs where each entry corresponds to a set of arcs for one machine:

no_idle_machine_range = range(3)

arcs = {i: [] for i in no_idle_machine_range}

Then I define the arcs, and at the end I add one circuit constraint per machine :

for machine_id in no_idle_machine_range:

    if len(arcs[machine_id]) > 1:

        model.AddCircuit(arcs[machine_id])

[Laurent Perron]

but you are mixing jobs between machines.

You need to project all jobs on one machine, create the arcs, add the circuit constraint.

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/25a408cd-8ff2-46c6-a1f2-2042550d8af9n%40googlegroups.com.

[Agathe MM.]

Ok, let me reformulate to see if I understood everything.

I have a flexible job shop problem. All of my jobs have one or several tasks. For all jobs, the first task has to be performed on machines 1, 2 or 3.

For this set of machines I want to have no waiting time between tasks (i.e. setup time of 0 seconds).

This is why I wanted to add the circuit constraints.

So this would only be possible if the first tasks were to be performed on only one machine, is that right ?

Thanks for your time,

Agathe Métaireau Manche

[Laurent Perron]

not what I said.

You are parsing all jobs, and adding arcs for transitions where the first job is on one machine, and the second one on another machine.

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

To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/5476418c-ff1d-4eab-aaa4-5546716aba8an%40googlegroups.com.

[Agathe MM.]

But with the dictionnary it adds the job on the arc of the machine, so normally it does not mix the jobs between the arcs.

I get that there is a problem in the arcs conception, but I just don't understand how to fix it.

[Laurent Perron]

Look at the ft06 distance example 

[Agathe MM.]

Ok this helps me get how to build the for loop, is there an example with machine alternatives somewhere ?

Thank you for your help.

[Laurent Perron]

https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md#transitions-in-a-no_overlap-constraint

shows how to deal with optional tasks in the circuit.

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 visit https://groups.google.com/d/msgid/or-tools-discuss/caa849b7-98e7-46c8-8a7d-012db527e7can%40googlegroups.com.