[PYTHON] Optimization of semiconductor wafer production planning

Introduction

--I tried to reproduce the optimization of the semiconductor wafer production plan explained in the material of CPLEX CP Optimizer.

• https://www.slideshare.net/PhilippeLaborie/introduction-to-cp-optimizer-for-scheduling
• https://ibmdecisionoptimization.github.io/docplex-doc/cp/index.html

Production planning specifications

--The lot has the number of wafers (n), priority (priority), production start date (release_date), and delivery date (due_date). --For each lot, a sequence of production steps is given. --Costs are incurred when the interval (lag) between the steps that make up a lot is long. --Each step has a family (f). --The family is given a machine that can be produced and a production time (process_time). --Steps of the same family can be produced at the same time. The start and end are the same. ――It takes a certain amount of time to switch the family of production steps. --The machine has capacity. The upper limit of the number of wafers that can be produced at the same time. --There are two indicators to minimize: step interval cost $ V_1 $ and late delivery cost $ V_2 $.

\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*}

--Lot number: 1000 --Number of steps: 5000 --Number of machines: 150 --Number of machines that can produce each step: 10 --Production planning period is 48 hours in minutes

Implementation by CP Optimizer

--The programming language is OPL. Run in CPLEX Optimization Studio. ――Excellent Performance can be obtained in 50 lines. --Changed the variable name to be longer.

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

Creating sample data

Create sample data using random numbers. ʻAlpha` is the ratio of machines that can be produced.

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

Implementation by Python Library

The object used in creating the sample data is used as it is. Model creation and optimization, result output.

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

Execution result

The optimum solution was obtained. The calculation time is about 0.1 seconds. The same result was obtained with CP Optimizer and Python.

in conclusion

――It is amazing that you can easily obtain the optimum solution even for a slightly complicated problem. --The production planning model can be easily expressed by using the Interval variable and the Optional attribute. --It has not been verified whether a solution can be obtained even with 1000 lots. There are too many variables in Community Edition.