The following shows the example code of https://developers.google.com/optimization/scheduling/job_shop#python_8 according to my input:
| Job | Machine | Duration |
|-----|---------|----------|
| A | 1 | 5 |
| A | 2 | 4 |
| A | 3 | 6 |
| A | 1 | 8 |
| A | 2 | 3 |
| B | 3 | 7 |
| B | 1 | 4 |
| B | 3 | 3 |
| C | 2 | 8 |
| C | 1 | 1 |
"""Minimal jobshop example."""
import collections
from ortools.sat.python import cp_model
def main():
"""Minimal jobshop problem."""
# Data.
jobs_data = [
[(1, 5), (2, 4), (3, 6), (1, 8), (2, 3)], # job A
[(3, 7), (1, 4), (3, 3)], # job B
[(2, 8), (1, 1)], # job C
]
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)
# Create the model.
model = cp_model.CpModel()
# 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, duration = task
suffix = f"_{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.
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
)
# Makespan objective.
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)
# Creates the solver and solve.
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 = f"job_{assigned_task.job}_task_{assigned_task.index}"
# Add spaces to output to align columns.
sol_line_tasks += f"{name:15}"
start = assigned_task.start
duration = assigned_task.duration
sol_tmp = f"[{start},{start + duration}]"
# Add spaces to output to align columns.
sol_line += f"{sol_tmp:15}"
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.")
# Statistics.
print("\nStatistics")
print(f" - conflicts: {solver.NumConflicts()}")
print(f" - branches : {solver.NumBranches()}")
print(f" - wall time: {solver.WallTime()}s")
if __name__ == "__main__":
main()
Question: Is it possible to modify the job shop problem so that parallel work processes within one job are also possible?
My data looks as follows:
| ID | Job | Machine | Duration | Order within job |
|----|-----|---------|----------|------------------|
| 1 | A | 1 | 5 | 1 |
| 2 | A | 2 | 4 | 1 |
| 3 | A | 3 | 6 | 2 |
| 4 | A | 1 | 8 | 2 |
| 5 | A | 2 | 3 | 3 |
| 6 | B | 3 | 7 | 1 |
| 7 | B | 1 | 4 | 2 |
| 8 | B | 3 | 3 | 2 |
| 9 | C | 2 | 8 | 1 |
| 10 | C | 1 | 1 | 2 |
So I want for example that ID 1
and ID 2
can be operated in parallel and it does not necessarily have to be sequential. ID 3
and ID 4
could be also done in parallel and also ID 7
and ID 8
The condition for me would be: It doesn't necessarily HAVE TO be parallel, but it CAN if possible.
Illustration: