Incluyendo una matriz de distancias en un CP schedulling problema

Question 1

Quiero intentar agregar una matriz de distancias a un simple problema de programación en CPLEX el uso de CP, sin embargo yo no puede conseguir esto sin la necesidad de un error en mi nuevo bdvar secuencia.

Estoy tratando de incluir a los tiempos de instalación entre los productos de 1,2 y 3, que dependen de la secuencia en que los productos están programados. Los tiempos de preparación de las diferentes secuencias se dan en un distancematrix.Traté de definir la distancia de la matriz como una tupla triplete en el archivo mod y como una matriz en el archivo dat pero ambas opciones no funcionan para mí.

La nueva configuración de bdvar de secuencia para este tiempo de configuración se llama el programa de instalación, y debe representar la secuencia de cada trabajo J en la máquina. Sin embargo, me aparece el error de que " la función noOverlap dvarsequence,[rango][rango] no existe. No entiendo lo que estoy haciendo mal, ya que he definido la bdvar seq y la matriz de modo que, en mi entender debería funcionar

Podría alguien ayudarme a salir de aquí? Pegado con este problema por un tiempo ahora.

Por favor buscar debajo de la mod. y dat. los archivos.

Gracias de antemano! 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

usted debe girar a la matriz de distancias en una tupla conjunto.

Véase el ejemplo de Cómo con OPL ?

TSP (Traveling Salesman Problem) en OPL con la programación, con la Restricción de Programación, o con quitar los circuitos y 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

usted debe girar a la matriz de distancias en una tupla conjunto.

Véase el ejemplo de Cómo con OPL ?

TSP (Traveling Salesman Problem) en OPL con la programación, con la Restricción de Programación, o con quitar los circuitos y 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
}

Traté de construir una tupla, así, sin embargo me preguntaba si era posible construir una tupla triplete con Tareas se define como una cadena { int loc1; int loc2; int valor; }; {triplete} transitionTimes = { <i,j, ftoi(abs(i-j))> | yo en Tareas, j en Tareas }; Cuando las Tareas se define como una cadena de Tareas = {"Ketchup", "Mayo","la BARBACOA","KetchLight"}; O puede tupla conjuntos sólo se construye no con los tipos de cadena?
La documentación dice : Un opcional de transición de la matriz M (en la forma de un entero no negativo tupla conjunto) se puede pasar a la noOverlap restricción, lo que significa que si ai aparece antes de aj en la secuencia, a una distancia mínima M[typei,typej] debe ser respetada entre el final de la ia y el inicio de aj (typei y typej indicar los tipos de ai y aj en la secuencia).
Gracias Alex! Ahora puedo ver cómo puedo configurar mi propio tupla usando sólo números enteros! Sin embargo, cuando trato de construir una tupla establece para la matriz de transición, en sustitución de int loc1 y int loc2 con (cadena job1 y la cadena de trabajo 2), me sale el error en el noOVerlap línea: Argumento no coincide el tipo de función de llamada noOverlap(bdvar secuencia,{tupla de tipo}):boolean con argumentos bdvar secuencia, {de la Matriz}'. ¿Esto quiere decir que solo puedo utilizar una tupla conjunto que existe de enteros no negativos para todos los componentes de la tupla? Todavía no está completamente claro para mí.. ¿Podría tal vez confirmar esto?

Incluyendo una matriz de distancias en un CP schedulling problema

Pregunta

Mejor respuesta

En otros idiomas

Esta página está en otros idiomas

Popular en esta categoría

Las preguntas más habituales en esta categoría