[PYTHON] Optimisation du plan de production de plaquettes semi-conductrices

introduction

Spécifications du plan de production

--Le lot a le nombre de plaquettes (n), la priorité (priorité), la date de début de production (release_date) et la date de livraison (due_date).

\begin{align*}
V_1&=\sum_{\mathrm{Step}} \min(c,c\max(0,\mathrm{lag}-a)^2/(b-a)^2)\\
V_2&=\sum_{\mathrm{Lot}} p\max(0,\mathrm{EndOfLot}-\mathrm{DueDate})
\end{align*}

Mise en œuvre par CP Optimizer

using CP;
tuple Lot { key int id; int n; float priority; int release_date; int due_date; }
tuple LotStep { key Lot lot; key int pos; int f; }
tuple Lag { Lot lot; int pos1; int pos2; int a; int b; float c; }
tuple Machine { key int id; int capacity; }
tuple MachineFamily { Machine machine; int f; int process_time; }
tuple MachineStep { Machine machine; LotStep lot_step; int process_time; }
tuple Setup { int f1; int f2; int duration; }

{Lot} Lots = ...;
{LotStep} LotSteps = ...;
{Lag} Lags = ...;
{Machine} Machines = ...;
{MachineFamily} MachineFamilies = ...;
{Setup} MachineSetups[machine in Machines] = ...;

{MachineStep} MachineSteps = {<machine_family.machine,lot_step,machine_family.process_time>
  | lot_step in LotSteps, machine_family in MachineFamilies: machine_family.f==lot_step.f};

dvar interval d_lot[lot in Lots] in lot.release_date .. 48*60;
dvar interval d_lot_step[lot_step in LotSteps];
dvar interval d_machine_step[ms in MachineSteps] optional size ms.process_time;

dvar int d_lag[Lags];

stateFunction batch[machine in Machines] with MachineSetups[machine];
cumulFunction load [machine in Machines] = 
  sum(ms in MachineSteps: ms.machine==machine) pulse(d_machine_step[ms], ms.lot_step.lot.n);

minimize staticLex(
  sum(lag in Lags) minl(lag.c, lag.c * maxl(0, d_lag[lag]-lag.a)^2 / (lag.b-lag.a)^2),
  sum(lot in Lots) lot.priority * maxl(0, endOf(d_lot[lot]) - lot.due_date));
subject to {
  forall(lot in Lots)
    span(d_lot[lot], all(lot_step in LotSteps: lot_step.lot==lot) d_lot_step[lot_step]);
  forall(lot_step in LotSteps) {
    alternative(d_lot_step[lot_step], all(ms in MachineSteps: ms.lot_step==lot_step) d_machine_step[ms]);
    if (lot_step.pos > 1)
      endBeforeStart(d_lot_step[<lot_step.lot,lot_step.pos-1>],d_lot_step[lot_step]);
  }
  forall(ms in MachineSteps)
    alwaysEqual(batch[ms.machine], d_machine_step[ms], ms.lot_step.f, true, true);
  forall(machine in Machines)
    load[machine] <= machine.capacity;
  forall(lag in Lags)
    endAtStart(d_lot_step[<lag.lot,lag.pos1>], d_lot_step[<lag.lot,lag.pos2>], d_lag[lag]);
}

Créer des exemples de données

Créez des exemples de données à l'aide de nombres aléatoires. «Alpha» est le rapport entre les machines pouvant être produites.

class Lag():
  def __init__(self, pos1, pos2, a, b, c):
    self.pos1 = pos1
    self.pos2 = pos2
    self.a = a
    self.b = b
    self.c = c

class Lot():
  def __init__(self, id, n, priority, release_date, due_date):
    self.id = id
    self.n = n
    self.priority = priority
    self.release_date = release_date
    self.due_date = due_date
    self.lag_list = []
  def create_step_list(self, families):
    self.step_list = families
  def add_lag(self, pos1, pos2, a, b, c):
    self.lag_list.append(Lag(pos1, pos2, a, b, c))

class Setup():
  def __init__(self, family1, family2, duration):
    self.family1 = family1
    self.family2 = family2
    self.duration = duration

class Machine():
  def __init__(self, id, capacity):
    self.id = id
    self.capacity = capacity
    self.proc_time = {}
    self.setup_list = []
  def add_proc_time(self, family, proc_time):
    self.proc_time[family] = proc_time
  def add_setup(self, family1, family2, duration):
    self.setup_list.append(Setup(family1, family2, duration))

##############################

import random
random.seed(5)

n_lot, n_step, n_family, n_machine = 4, 5, 3, 4
lot_n = (5, 15)
capa = (20, 60)
proc_time = (20, 30)
takt, LT = 30, 100
a, b, c = 10, 20, 5
alpha = 0.5
duration = 20

lots = []
for i in range(n_lot):
  n = random.randint(lot_n[0], lot_n[1])
  p = random.randint(1, 10) / 10
  lot = Lot(i, n, p, takt*i, takt*i+LT)
  lot.create_step_list([random.randint(0, n_family-1) for j in range(n_step)])
  for j in range(n_step-1):
    lot.add_lag(j, j+1, a, b, c)
  lots.append(lot)

machines = []
for i in range(n_machine):
  c = random.randint(capa[0], capa[1])
  machine = Machine(i, c)
  for j in range(n_family):
    for k in range(n_family):
      machine.add_setup(j, k, 0 if j == k else duration)
  machines.append(machine)

for f in range(n_family):
  cnt = 0
  for m in range(n_machine):
    if random.random() > alpha: continue
    machines[m].add_proc_time(f, random.randint(proc_time[0], proc_time[1]))
    cnt += 1
  if cnt == 0:
    m = random.randint(0, n_machine-1)
    machines[m].add_proc_time(f, random.randint(proc_time[0], proc_time[1]))

##############################

path_file_name = 'sample.dat'
def mytuple(obj):
  if type(obj) == Lot:
    return f'<{obj.id},{obj.n},{obj.priority},{obj.release_date},{obj.due_date}>'
  if type(obj) == Machine:
    return f'<{obj.id},{obj.capacity}>'

with open(path_file_name, 'w') as o:
  o.write('Lots = {\n')
  for lot in lots:
    o.write(f'  {mytuple(lot)}\n')
  o.write('};\n')
  o.write('LotSteps = {\n')
  for lot in lots:
    for f, fm in enumerate(lot.step_list):
      o.write(f'  <{mytuple(lot)},{f+1},{fm}>\n')
  o.write('};\n')
  o.write('Lags = {\n')
  for lot in lots:
    for lag in lot.lag_list:
      o.write(f'  <{mytuple(lot)},{lag.pos1+1},{lag.pos2+1},{lag.a},{lag.b},{lag.c}>\n')
  o.write('};\n')
  o.write('Machines = {\n')
  for machine in machines:
    o.write(f'  {mytuple(machine)}\n')
  o.write('};\n')
  o.write('MachineFamilies = {\n')
  for machine in machines:
    for f, proc_time in machine.proc_time.items():
      o.write(f'  <{mytuple(machine)},{f},{proc_time}>\n')
  o.write('};\n')
  o.write('MachineSetups = #[\n')
  for machine in machines:
    o.write(f'  <{machine.id}>:{{')
    for setup in machine.setup_list:
      o.write(f'<{setup.family1},{setup.family2},{setup.duration}>')
    o.write('}\n')
  o.write(']#;\n')

Implémenté par la bibliothèque Python

L'objet utilisé pour créer les exemples de données est utilisé tel quel. Création et optimisation du modèle, sortie des résultats.

import docplex.cp.model as cp
model = cp.CpoModel()

for machine in machines:
  machine.interval_list = []

for lot in lots:
  lot.interval = cp.interval_var(start=[lot.release_date,48*60], end=[lot.release_date,48*60])
  lot.step_interval_list = cp.interval_var_list(len(lot.step_list))
  model.add(cp.span(lot.interval, lot.step_interval_list))
  for f in range(1, len(lot.step_list)):
    model.add(cp.end_before_start(lot.step_interval_list[f-1], lot.step_interval_list[f]))
  lot.machine_interval_list = []
  for f, fm in enumerate(lot.step_list):
    interval_dict = {}
    for machine in machines:
      if fm not in machine.proc_time: continue
      interval = cp.interval_var(length=machine.proc_time[fm], optional=True)
      interval_dict[machine.id] = interval
      machine.interval_list.append([interval, fm, lot.n])
    model.add(cp.alternative(lot.step_interval_list[f], interval_dict.values()))
    lot.machine_interval_list.append(interval_dict)
  lot.lag_ivar_list = []
  for lag in lot.lag_list:
    ivar = cp.integer_var()
    model.add(cp.end_at_start(lot.step_interval_list[lag.pos1], lot.step_interval_list[lag.pos2], ivar))
    lot.lag_ivar_list.append(ivar)

for machine in machines:
  tmat = cp.transition_matrix(n_family)
  for setup in machine.setup_list:
    tmat.set_value(setup.family1, setup.family2, setup.duration)
  state = cp.state_function(tmat)
  for interval, fm, n in machine.interval_list:
    model.add(cp.always_equal(state, interval, fm, True, True))
  pulse_list = []
  for interval, fm, n in machine.interval_list:
    pulse_list.append(cp.pulse(interval, n))
  model.add(cp.sum(pulse_list) <= machine.capacity)

obj_lag = cp.sum([cp.min(lag.c, lag.c * cp.square(cp.max(0, lot.lag_ivar_list[l] - lag.a)) / (lag.b - lag.a)**2)
  for lot in lots for l, lag in enumerate(lot.lag_list)])

obj_lot = cp.sum([lot.priority * cp.max(0, cp.end_of(lot.interval) - lot.due_date) for lot in lots])

model.add(cp.minimize_static_lex([obj_lag, obj_lot]))
msol = model.solve(TimeLimit=30, LogVerbosity='Terse')

##############################

path_file_name = 'cplex_python.csv'
with open(path_file_name, 'w') as o:
  o.write('l,n,priority,release_date,due_date,pos,f,start,end,length,m,capacity\n')
  for lot in lots:
    for f, interval_dict in enumerate(lot.machine_interval_list):
      for m, v in interval_dict.items():
        x = msol[v]
        if(len(x) == 0): continue
        o.write(f'{lot.id},{lot.n},{lot.priority},{lot.release_date},{lot.due_date}')
        o.write(f',{f},{lot.step_list[f]},{x[0]},{x[1]},{x[2]},{m},{machines[m].capacity}\n')

Résultat d'exécution

La solution optimale a été obtenue. Le temps de calcul est d'environ 0,1 seconde. Le même résultat a été obtenu avec CP Optimizer et Python.

l n priority release_date due_date pos f start end length m capacity
0 14 0.5 0 100 0 2 0 23 23 1 44
0 14 0.5 0 100 1 1 30 53 23 2 30
0 14 0.5 0 100 2 2 53 76 23 1 44
0 14 0.5 0 100 3 2 76 99 23 1 44
0 14 0.5 0 100 4 2 99 122 23 1 44
1 13 0.1 30 130 0 1 30 53 23 2 30
1 13 0.1 30 130 1 0 53 76 23 3 24
1 13 0.1 30 130 2 2 76 99 23 1 44
1 13 0.1 30 130 3 0 99 128 29 0 31
1 13 0.1 30 130 4 0 128 151 23 3 24
2 6 0.6 60 160 0 1 60 83 23 2 30
2 6 0.6 60 160 1 0 83 106 23 3 24
2 6 0.6 60 160 2 1 106 129 23 2 30
2 6 0.6 60 160 3 2 129 152 23 1 44
2 6 0.6 60 160 4 0 152 172 20 2 30
3 14 0.4 90 190 0 0 99 128 29 0 31
3 14 0.4 90 190 1 2 129 152 23 1 44
3 14 0.4 90 190 2 0 152 172 20 2 30
3 14 0.4 90 190 3 1 172 194 22 1 44
3 14 0.4 90 190 4 1 194 216 22 1 44

en conclusion

――Il est étonnant que vous puissiez facilement obtenir la solution optimale même pour un problème légèrement compliqué.

Recommended Posts

Optimisation du plan de production de plaquettes semi-conductrices
Optimisation de la planification de la production (OU-Tools)
Optimisation de la planification de la production à l'aide de la programmation linéaire (Python + PuLP)