Optimisation de la planification de la production (OU-Tools)

introduction

Spécifications du plan de production

--Il y a plusieurs lots de travail et chaque lot se compose de travaux consécutifs.

Comment définir des variables

--Pour chaque tâche, définissez des variables qui représentent l'heure de début (var_début) et l'heure de fin (var_fin). --Définissez une variable booléenne (bool_var) qui indique s'il faut allouer ou non à chaque travail / équipement, et définissez une variable d'intervalle (interval_var). --Définissez une contrainte où la somme des variables booléennes est 1 pour chaque travail. --Définissez une contrainte selon laquelle les variables d'intervalle ne se chevauchent pas pour chaque fonction. --Définissez les contraintes de commande avant et après les travaux qui composent le même lot.

RCSP.png

Génération de données

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])

Définition des variables et des contraintes

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())

Dans l'environnement actuel, la valeur optimale de 28 a été obtenue en environ 230 ms.

Sortie de résultat

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

Affichage du diagramme de Gantt

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

La couleur est modifiée pour chaque lot. Il est bien emballé tout en satisfaisant l'ordre de traitement du travail.

en conclusion

Recommended Posts

Optimisation de la planification de la production (OU-Tools)
Optimisation du plan de production de plaquettes semi-conductrices
Optimisation de la planification de la production à l'aide de la programmation linéaire (Python + PuLP)
Résolution d'exercices de modèle d'optimisation mathématique avec les outils OR de Google (3) Problèmes d'optimisation de la production
Optimisation apprise avec OR-Tools Part0 [Introduction]
Explication du modèle d'optimisation de la production par Python