--I tried to create a program to optimize the production plan using Google's mathematical optimization tools (OR-Tools).
--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.
--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.
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])
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)
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 = []
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 |
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()
The color is changed for each lot. It is tightly packed while satisfying the job processing order.
--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