Solve flexible job shop problem with sequence dependent setup times

[Toby Q]

Dear OR tools community,

I am working on a rather complex problem that I did not manage to model so far, so I would kindly request your help. The parameters are as follows:

- I have a job shop with different machines

- Jobs are atomic (exactly one task per job)

- Each job can only be processed by a subset of available machines

- Depending on the job sequence, there are different setup times in-between jobs

- Both setup times and processing times of the jobs are different for each machine

Using the available examples in the OR tools repository, I managed to get a working example to run. The function `optimize` takes as argument the `jobs_data`, which is a list of lists, where each sub-list is a job, containing two-tuples for each possible job configuration. The two-tuples have machine ID as the first value and the processing time of the job using this machine as the second value:

```

[[(2, 8), (1, 7)], # job 1 alternatives: (machine:2, duration:8), (machine:1, duration: 7) [(1, 6)], [(0, 3), (1, 1)], [(1, 7)], [(0, 5), (1, 2), (2, 3)]]

```

The second input are the `setup_times`. This is simply a dictionary, where `setup_times[machine_id][job_1_id][job_2_id]` encodes the setup time to go from `job_1` to `job_2` on the machine with ID `machine_id`.

Here is the function I came up with to model the problem:

```python

def optimize(jobs_data, setup_times):

model = cp_model.CpModel()

machines_count = len(setup_times.keys())

all_machines = range(machines_count)

all_jobs = range(len(jobs_data))

# Computes horizon dynamically as the sum of all durations and setup times.

horizon = 0

for job in jobs_data:

max_job_duration = max(duration for _, duration in job)

horizon += max_job_duration

for machine in setup_times.keys():

for j1 in setup_times[machine].keys():

for j2 in setup_times[machine][j1].keys():

horizon += setup_times[machine][j1][j2]

presences = {}

# Creates job intervals and add to the corresponding machine lists.

starts = {} # indexed by job_id

ends = []

machine_to_intervals = collections.defaultdict(list)

for job_id in all_jobs:

job = jobs_data[job_id]

min_duration = min(duration for _, duration in job)

max_duration = max(duration for _, duration in job)

num_configs = len(job)

suffix = "_%i" % job_id

start_var = model.NewIntVar(0, horizon, "start" + suffix)

end_var = model.NewIntVar(0, horizon, "end" + suffix)

duration = model.NewIntVar(min_duration, max_duration, "duration" + suffix)

interval_var = model.NewIntervalVar(start_var, duration, end_var, "interval" + suffix)

starts[job_id] = start_var

# create alternative intervals for each configuration

if num_configs > 1:

l_presences = []

for config_id, config in enumerate(job):

alt_suffix = "_j%i_a%i" % (job_id, config_id)

l_presence = model.NewBoolVar("presence" + alt_suffix)

l_start = model.NewIntVar(0, horizon, "start" + alt_suffix)

l_duration = config[1]

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 primary variable with alternative variable

model.Add(start_var == l_start).OnlyEnforceIf(l_presence)

model.Add(duration == l_duration).OnlyEnforceIf(l_presence)

model.Add(end_var == l_end).OnlyEnforceIf(l_presence)

# Add local interval to right machine list

machine = config[0]

machine_to_intervals[machine].append(l_interval)

# Store presences for the solution

presences[(job_id, config_id)] = l_presence

# Add constraint that only one of the alternative intervals can be active

model.Add(sum(l_presences) == 1)

else:

machine_to_intervals[job[0][0]].append(interval_var)

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

ends.append(end_var)

# Create and add disjunctive constraints.

for machine in all_machines:

job_starts = []

job_ends = []

job_indices = []

job_config_ids = []

for job_id in all_jobs:

job = jobs_data[job_id]

for config_id, config in enumerate(job):

if config[0] == machine:

job_starts.append(starts[job_id])

job_ends.append(ends[job_id])

job_indices.append(job_id)

job_config_ids.append(config_id)

intervals = machine_to_intervals[machine]

if len(intervals) > 1:

model.AddNoOverlap(intervals)

arcs = []

for j1 in range(len(job_starts)):

# Initial arc from the dummy node (0) to a task.

start_lit = model.NewBoolVar("%i is first job" % j1)

arcs.append((0, j1 + 1, start_lit))

# Final arc from an arc to the dummy node.

arcs.append((j1 + 1, 0, model.NewBoolVar("%i is last job" % j1)))

for j2 in range(len(job_starts)):

if j1 == j2:

continue

lit = model.NewBoolVar("%i follows %i" % (j2, j1))

arcs.append((j1 + 1, j2 + 1, lit))

tmp = [

lit,

presences[(job_indices[j1], job_config_ids[j1])],

presences[(job_indices[j2], job_config_ids[j2])]

]

min_distance = setup_times[machine][job_indices[j1]][job_indices[j2]]

model.add(starts[job_indices[j2]] >= ends[job_indices[j1]] + min_distance).OnlyEnforceIf(tmp)

model.AddCircuit(arcs)

# Makespan objective.

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

model.AddMaxEquality(obj_var, ends)

model.Minimize(obj_var)

# Solve model.

solver = cp_model.CpSolver()

solution_printer = SolutionPrinter()

status = solver.Solve(model, solution_printer)

if status == cp_model.OPTIMAL:

# Print out makespan.

print("Optimal Schedule Length: %i" % solver.ObjectiveValue())

print()

```

My problem occurs where the circuit is built: I do not know how to correctly combine the condition that job 2 follows job 1 (i.e. `lit`) with the condition that both job 1 and job 2 have actually been chosen to be run on the current machine (encoded in `presences[(job_id, config_id)]`). When using the `tmp` list in the `OnlyEnforceIf`, the solver finds an optimal solution, but it does not account correctly for the setup times. In particular, there are often no gaps at all between the jobs if I look at a gantt chart. If I use `lit` instead of the `tmp` list inside the `OnlyEnforceIf`, the setup times are correctly being accounted for, but they are considered even wen job 1 and job 2 run on different machines, which is not what I want.

How can the two conditions be correctly combined in this case?

Thank you already in advance!

[Laurent Perron]

https://github.com/google/or-tools/blob/main/ortools/sat/docs/scheduling.md#ranking-tasks-in-a-disjunctive-resource-with-a-circuit-constraint

--
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/48694b1e-f3c4-4e2d-870a-2252cd472094n%40googlegroups.com.