How can I extend the example of or tools in the job shop problem so that parallel work processes are also possible?

70 views Asked by At

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:

enter image description here

0

There are 0 answers