Production Planning Optimization (OR-Tools)

Introduction

--I tried to create a program to optimize the production plan using Google's mathematical optimization tools (OR-Tools).

Production plan specifications

--There are multiple work lots, and each lot consists of consecutive jobs. --For each job, the time required for production (size) is specified. --Each job needs to be assigned to one of multiple facilities. --Jobs assigned to the same equipment must not overlap each other. --Jobs that make up the same lot must be produced in sequence. --Minimize the time it takes for all jobs to finish.

How to define variables

--For each job, define variables that represent the start time (start_var) and end time (end_var). --Define a Boolean variable (bool_var) that indicates whether or not to allocate to each job / equipment, and define an interval variable (interval_var). --Define a constraint where the sum of Boolean variables is 1 for each job. --Define a constraint that interval variables do not overlap each other for each facility. --Define order constraints before and after jobs that make up the same lot.

RCSP.png

Data generation

from ortools.sat.python import cp_model
from collections import defaultdict
from dataclasses import dataclass
import pandas as pd
import matplotlib
import matplotlib.pyplot as plt
import random

num_machines = 3
num_lots = 5
num_jobs_per_lot = 3
num_jobs = num_lots * num_jobs_per_lot

@dataclass
class job_type:
    id: int
    lot_id: int
    size: int

random.seed(1)
jobs_list = [job_type(j, j//num_jobs_per_lot, random.randint(1, 10)) for j in range(num_jobs)]
horizon = sum([job.size for job in jobs_list])

Definition of variables and constraints

model = cp_model.CpModel()
machine_to_intervals = defaultdict(list)
for job in jobs_list:
    start_var = model.NewIntVar(0, horizon, 'start_' + str(job.id))
    end_var = model.NewIntVar(0, horizon, 'end_' + str(job.id))
    job.start_var = start_var
    job.end_var = end_var
    bool_var_list = []
    for m in range(num_machines):
        suffix = str(m) + '_' + str(job.id)
        bool_var = model.NewBoolVar('bool_' + suffix)
        bool_var_list.append(bool_var)
        interval_var = model.NewOptionalIntervalVar(start_var, job.size, end_var, bool_var, 'interval_' + suffix)
        interval_var.job = job
        interval_var.bool_var = bool_var
        machine_to_intervals[m].append(interval_var)
    model.Add(sum(bool_var_list) == 1)

for m in machine_to_intervals:
    model.AddNoOverlap(machine_to_intervals[m])

for j in range(num_jobs-1):
    if jobs_list[j].lot_id != jobs_list[j+1].lot_id: continue
    model.Add(jobs_list[j].end_var <= jobs_list[j+1].start_var)

optimisation

span_var = model.NewIntVar(0, horizon, 'span_var')
model.AddMaxEquality(span_var, [j.end_var for j in jobs_list])
model.Minimize(span_var)

solver = cp_model.CpSolver()
solver.Solve(model)
print(solver.StatusName(), solver.ObjectiveValue())

In the environment at hand, the optimum value of 28 was obtained in about 230 ms.

Result output

result = []
for m in machine_to_intervals:
    for i in machine_to_intervals[m]:
        if solver.Value(i.bool_var) == 0: continue
        result.append([m, i.job.lot_id, i.job.id, solver.Value(i.job.start_var), solver.Value(i.job.end_var), i.job.size])
result = pd.DataFrame(result, columns=['machine', 'lot', 'job', 'start', 'end', 'size']).sort_values(['machine', 'start'], ignore_index=True)
print(result)
machine lot job start end size
0 0 4 12 0 1 1
1 0 2 6 1 9 8
2 0 0 1 9 19 10
3 0 1 5 19 27 8
4 1 3 9 0 4 4
5 1 3 10 4 6 2
6 1 0 0 6 9 3
7 1 1 4 9 11 2
8 1 2 7 11 19 8
9 1 0 2 19 21 2
10 1 4 14 21 28 7
11 2 1 3 0 5 5
12 2 3 11 6 14 8
13 2 4 13 14 21 7
14 2 2 8 21 28 7

Gantt chart display

span_max = solver.Value(span_var)
cmap = plt.cm.get_cmap('hsv', num_lots+1)
fig = plt.figure(figsize=(12, 8))
for m in machine_to_intervals:
    ax = fig.add_subplot(num_machines, 1, m+1, yticks=[], ylabel=m)
    ax.set_xlim(-1, span_max+1)
    ax.set_ylim(-0.1, 1.1)
    for i in machine_to_intervals[m]:
        if solver.Value(i.bool_var) == 0: continue
        start = solver.Value(i.job.start_var)
        rectangle = matplotlib.patches.Rectangle((start, 0), i.job.size, 1, fill=False, color=cmap(i.job.lot_id), hatch='/')
        ax.add_patch(rectangle)
        rx, ry = rectangle.get_xy()
        cx = rx + rectangle.get_width()/2
        cy = ry + rectangle.get_height()/2
        lab = str(i.job.lot_id) + '-' + str(i.job.id)
        ax.annotate(lab, (cx, cy), ha='center', va='center')
plt.show()

gant.png

The color is changed for each lot. It is tightly packed while satisfying the job processing order.

in conclusion

--If the scale of the problem is small, you can use OR-Tools to solve the production planning optimization problem. ――However, in the actual problem, the number of variables may be tens of thousands. Need to be identified.

Recommended Posts

Production Planning Optimization (OR-Tools)
Optimization of semiconductor wafer production planning
Production planning optimization using linear programming (Python + PuLP)
Solving Mathematical Optimization Model Exercises with Google's OR-Tools (3) Production Optimization Problems
Optimization learned with OR-Tools Part0 [Introduction]
Explanation of production optimization model by Python