\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*}
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]);
}
Erstellen Sie Beispieldaten mit Zufallszahlen. "Alpha" ist das Verhältnis der Maschinen, die produziert werden können.
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')
Das beim Erstellen der Beispieldaten verwendete Objekt wird unverändert verwendet. Modellerstellung und -optimierung, Ergebnisausgabe.
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')
Die optimale Lösung wurde erhalten. Die Berechnungszeit beträgt ca. 0,1 Sekunden. Das gleiche Ergebnis wurde mit CP Optimizer und Python erzielt.
| 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 |
――Es ist erstaunlich, dass Sie auch für ein etwas kompliziertes Problem leicht die optimale Lösung finden können.