Modelando custos clássicos de planejamento
Os custos de planejamento clássicos, como makespan, antecipação/atraso, custos de alocação de recursos e custos de execução de atividade, podem ser modelados de forma eficiente no CP Optimizer.
Custos de não execução
Um custo de não execução de atividade K é modelado por uma expressão K * presenceOf(a) se a é a variável de intervalo opcional representando a atividade.
Makespan
Um custo de makespan é modelado como o valor máximo do fim de um
conjunto de variáveis de intervalo. No caso de uma variável de
intervalo opcional, o valor da expressão IloEndOf(a)
é 0 quando o intervalo a
está ausente.
dvar interval act[i in 1..n];
dexpr int makespan = max(i in 1..n) endOf(act[i]);
minimize makespan;
subject to { // ... }
IloIntervalVarArray act(env,n);
IloIntExprArray end(env);
for (IloInt i = 0; i < n; i++) {
act[i] = IloIntervalVar(env);
ends.add(IloEndOf(act[i]);
}
m.add(IloMinimize(env,IloMax(ends)));
Custos de antecipação/atraso
O custo de uma antecipação/atraso pode ser modelado por um
conjunto de funções lineares compostas f que representam o custo
f(t) de concluir (ou iniciar) uma atividade em uma data
t. As expressões de números inteiros IloStartEval
e IloEndEval
são usadas para avaliar a função no
ponto de início ou de término de uma variável de intervalo. Um
exemplo de custo de antecipação/atraso em que o custo de uma
atividade é expresso como uma função de formato V avaliada no
horário de encerramento da atividade está a seguir. Essa amostra
combina os custos de antecipação/atraso com um custo de não execução:
no exemplo, as atividades deveriam ser opcionais e não
executar uma atividade incorre em um custo.
pwlFunction etcost[i in 1..n] = piecewise{-earliW[i]->targetEnd[i]; tardiW[i]}(targetEnd[i],0); dexpr float cost = sum(i in 1..n) endEval(act[i], etcost[i], nonExecCost[i]);
IloIntArray targetEnd(env,n); // populate
IloNumArray earliW(env,n); // populate
IloNumArray tardiW(env,n); // populate
IloNumArray nonExecCost(env,n); // populate
IloNumExpr cost(env);
IloIntervalArray act(env,n);
IlNumExpr cost(env);
for (IloInt i = 0; i < n; i++) {
act[i] = IloIntervalVar(env);
act[i].setOptional();
IloNumToNumSegmentFunction etcost = IloPiecewiseLinearFunction(env,
IloNumArray(env,1, targetEnd[i]),
IloNumArray(env,2,-earliW[i],tardiW)
targetEnd[i],0);
cost += IloEndEval(act[i],etcost,nonExecCost[i]);
}
m.add(IloMinimize(env,cost));
Quando a função é muito simples, como um custo de atraso puro e a
atividade não é opcional, é ligeiramente mais eficiente usar uma
expressão IloMax
em vez de uma função linear
composta, conforme ilustrado.
IloIntArray dueDate(env,n); // populate
IloNumArray tardiW(env,n); // populate
IloIntervalVarArray act(env,n);
IloNumExpr cost(env);
for (IloInt i = 0; i < n; i++) {
act[i] = IloIntervalVar(env);
cost += tardiw[i]*IloMax(0,IloEndOf(act[i])-dueDate[i]);
}
m.add(IloMinimize(env,cost));
Custos de alocação de recurso
Um custo de alocação de recursos ou de modo especificando um custo
K
incorrido por uma atividade em execução em um
recurso específico ou em um modo específico é modelado por uma
expressão K * IloPresenceOf(a)
se a
é a variável de intervalo opcional que representa
a execução da atividade no recurso ou no modo especificado
(consulte Usos diferentes da restrição alternativa). A
amostra a seguir ilustra um custo de alocação de recurso simples para
uma atividade em execução em um conjunto de recursos alternativos.
IloInt nbMachines = 5;
IloInt nbActivities = 10;
IloIntArray ptime(env,nbActivities); // populate
IloIntArray2 allocCost(env,nbActivities);
IloIntervalVar activity(env,nbActivities);
IloIntervalVarArray2 actonMach(env,nbActivities);
for (IloInt i=0; i<nbActivities;i++) {
activity[i] = IloIntervalVar(env,ptime[i]);
allcost[i] = IloIntArray(env,nbMachines); // populate
actOnMach[i] = IloIntervalVarArray(env,nbMachines);
for (IloInt j=0; j< nbMachines; j++) {
actOnMach[i][j] = IloIntervalVar(env);
actOnMach[i][j].setOptional();
}
m.add(IloAlternative(env,activity[i],actOnMach[i]));
}
IloIntervalVarArray2 resOnAct(env,nbMachines);
for (IloInt j=0; j<nbMachines; j++) {
resHasAct[j] = IloIntervalVarArray(env,nbActivities);
for (IloInt i=0; i<nbActivities;i++) {
resHasAct[j][i] = actOnMach[i][j];
}
m.add(IloNoOverlap(env, resOnAct[j]));
}
IloIntExpr cost(env);
for (i=0; i<n; i++ )
for (IloInt j=0; j<m; j++)
cost += allocCost[i][m]*IloPresenceOf(env,actOnMach[i][m]);
m.add(IloMinimize(env,cost));
Custos da configuração dependente de sequência
O custo de uma configuração dependente de sequência em uma máquina é geralmente
expresso como uma matriz de custos M[ti][tj]
que
fornece o custo de configuração para a máquina para alternar de uma
atividade do tipo ti
para uma atividade do tipo tj
.
Tal custo de configuração pode ser modelado usando as expressões typeOfNext e typeOfPrev na variável de sequência que
representa a máquina, conforme ilustrado na amostra a seguir. Um
exemplo completo modelando um custo de configuração total está
disponível no exemplo fornecido em <Install_dir>/cpoptimizer/examples/src/cpp/sched_tcost.cpp
.
IloEnv env;
IloModel model(env);
IloInt m = ...; // Number of types { 0, 1, ..., m-1 }
IloInt last = m; // Type of next for the last activity on the machine
IloInt abs = m+1; // Type of next for a non-executed activity on the machine
IloIntArray2 M(env, m);
for (IloInt ti=0; ti<m; ++ti) {
M[ti]= IloIntArray(env, m+2);
for (IloInt tj=0; tj<m; ++tj) {
M[ti][tj] = ...; // Setup cost between types ti and tj
}
M[ti][last] = ...; // Cost if an activity of type ti is last
M[ti][abs] = ...; // Cost if an activity of type ti is not executed
}
IloInt n = ...; // Number of activities on the machine
IloIntervalVarArray act(env, n); // Activities on the machine
IloIntArray type(env, n); // Activity types
// ...
IloIntervalSequenceVar machine(env, act, type);
model.add(IloNoOverlap(env, machine));
IloIntExpr totalCost(env);
for (IloInt i=0; i<n; ++i)
totalCost += M[type[i]][IloTypeOfNext(machine, act[i], last, abs)];
model.add(IloMinimize(env, totalCost));
IloCP cp(model);
cp.solve();
env.end();