Incluindo uma matriz de distância em um CP schedulling problema

Question 1

Eu quero tentar adicionar uma matriz de distância de um simples problema de programação no CPLEX usando o CP no entanto, eu não conseguiria isso sem um erro no meu novo bdvarest sequência.

Estou tentando incluir o tempo de instalação entre os produtos 1, 2 e 3, que dependem da seqüência em que os produtos são agendadas. Os tempos de preparação para as diversas sequências são dadas em um distancematrix.Tentei definir a matriz de distância como uma tupla trio no arquivo mod e como uma matriz no arquivo dat, mas ambas as opções não funcionam para mim.

A nova configuração bdvarest de seqüência para esta configuração de tempo é chamado de instalação, e deve representar a seqüência de cada tarefa J na máquina. No entanto, recebo a mensagem de erro que " a função noOverlap dvarsequence,[intervalo][intervalo] não existe. Eu não entendo o que estou fazendo de errado, já que eu defini o bdvarest seq e a matriz portanto, no meu entendimento, isso deve funcionar

Alguém poderia me ajudar aqui? Preso com esse problema por um tempo agora.

Veja abaixo o mod. e dat. ficheiros.

Obrigado antecipadamente! mod.


using CP;

// Number of Machines (Packing + Manufacturing)
int nbMachines = ...;
range Machines = 1..nbMachines;

// Number of Jobs
int nbJobs = ...;
range Jobs = 1..nbJobs;

int duration[Jobs,Machines] = ...;

int release = ...;
int due     = ...;

int distanceMatrix[1..nbJobs][1..nbJobs] = ...;
 
dvar interval task[j in Jobs] in release..due;
dvar interval opttask[j in Jobs][m in Machines] optional size duration[j][m];

dvar sequence tool[m in Machines] in all(j in Jobs) opttask[j][m];
dvar sequence setup[j in Jobs] in all (m in Machines,j in Jobs)opttask[j][m];      

execute {
        cp.param.FailLimit = 5000;
}


// Minimize the total processing cost (24)

 dexpr int day = sum(j in Jobs, m in Machines) duration[j][m] * presenceOf(opttask[j][m]);
 minimize  day;
subject to {
  // Each job needs one unary resource of the alternative set s (28)
  forall(j in Jobs){
    alternative(task[j], all(m in Machines) opttask[j][m]);
     noOverlap(setup[j],distanceMatrix);
   }     
  // No overlap on machines
   forall(m in Machines){
     noOverlap(tool[m]);
   }     
  // forall(m in Machines,j in Jobs)
     
};

execute {
  writeln(task);
};

dat.

nbMachines = 2;

nbJobs = 3;

duration = [
        [5,1], 
        [3,4],
        [5,7]
            ];

release = 1;

due = 30;

distanceMatrix = [
1:[0,2,0],
2:[4,0,6],
3:[0,2,0]
]};

Question 2

você deve ativar a matriz de distância em um conjunto de tupla.

Veja um exemplo de Como com a OPL ?

TSP (Traveling Salesman Problem) no OPL com agendamento, com Restrição de Programação, ou com a remoção de circuitos e MTZ

using CP; 
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;



// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);


dvar interval itvs[1..n+1] size 1;


dvar sequence seq in all(i in 1..n+1) itvs[i]; 

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { 
    <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};
           
           
minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);   // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
}

Alex Fleischer · Answer 1 · 2021-11-20T18:49:09

você deve ativar a matriz de distância em um conjunto de tupla.

Veja um exemplo de Como com a OPL ?

TSP (Traveling Salesman Problem) no OPL com agendamento, com Restrição de Programação, ou com a remoção de circuitos e MTZ

using CP; 
int     n       = ...;
range   Cities  = 1..n;

int realCity[i in 1..n+1]=(i<=n)?i:1;



// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in 1..n};
setof(edge) Edges2       = {<i,j> | i,j in 1..n+1};  // node n+1 is node 1

int         dist[Edges] = ...;
int         dist2[<i,j> in Edges2]=(realCity[i]==realCity[j])?0:
((realCity[i]<realCity[j])?dist[<realCity[i],realCity[j]>]:dist[<realCity[j],realCity[i]>]);


dvar interval itvs[1..n+1] size 1;


dvar sequence seq in all(i in 1..n+1) itvs[i]; 

execute
{

cp.param.TimeLimit=60;
var f = cp.factory;
  cp.setSearchPhases(f.searchPhase(seq));
}

tuple triplet { int c1; int c2; int d; };
{triplet} Dist = { 
    <i-1,j-1,dist2[<i ,j >]>
           |  i,j in 1..n+1};
           
           
minimize endOf(itvs[n+1]) - (n+1);           
subject to
{
    startOf(itvs[1])==0; // break sym
    noOverlap(seq,Dist,true);   // nooverlap with a distance matrix
    last(seq, itvs[n+1]); // last node
}

Eu tentei construir uma tupla bem definido, no entanto, eu me perguntava se era possível construir uma tupla trio com Tarefas é definida como uma seqüência de caracteres { int loc1; int loc2; int valor; }; {tipo} transitionTimes = { <i,j, ftoi(abs(i-j))> | i em Tarefas, j em Tarefas }; Quando as Tarefas é definida como uma seqüência de Tarefas = {"Ketchup", "Maio","CHURRASCO","KetchLight"}; Ou pode tupla define apenas ser construído com tipos de cadeia?
A documentação diz : opcional matriz de transição M (na forma de um número inteiro não negativo conjunto de tupla) podem ser passados para o noOverlap restrição de significado que, se ai aparece antes de aj na seqüência, em seguida, a uma distância mínima M[typei,typej] deve ser respeitado entre o final de ai e o início de aj (typei e typej denotar os tipos de ai e aj na sequência).
Obrigado Alex! Agora vejo como eu posso montar o meu próprio tupla usando apenas números inteiros! No entanto, quando eu tentar construir um conjunto de tupla para a matriz de transição, substituindo int loc1 e int loc2 com (cadeia de trabalho1 e cadeia job2), recebo a mensagem de erro no noOVerlap linha: Argumento de incompatibilidade de tipo de chamada de função noOverlap(bdvarest sequência,{tupla do tipo}):boolean argumentos bdvarest sequência, {Matrix}'. Isso significa que só posso usar um conjunto de tupla que existe de números inteiros não negativos para todos os elementos da tupla? Ela ainda não está completamente claro para mim.. você Poderia talvez confirmar isso?

Incluindo uma matriz de distância em um CP schedulling problema

Pergunta

Melhor resposta

Em outros idiomas

Esta página está em outros idiomas

Popular nesta categoria

Perguntas populares nesta categoria