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