在 CPU 调度问题中包含距离矩阵

Question

我想尝试使用 CP 将距离矩阵添加到 CPLEX 中的一个简单调度问题，但是我无法设法在我的新 dvar 序列中没有错误地得到它。

我正在尝试包括产品 1、2 和 3 之间的设置时间，这取决于产品安排的顺序。 distancematrix.I 中给出了不同序列的设置时间，试图将距离矩阵定义为 mod 文件中的元组三元组和 dat 文件中的矩阵，但这两个选项对我都不起作用.

此设置时间的新设置 dvar 序列称为设置，应该表示机器上每个作业 J 的序列。但是，我收到“函数 noOverlap dvarsequence,[range][range] 不存在”的错误。我不明白我做错了什么，因为我定义了 dvar seq 和矩阵，所以据我所知它应该可以工作

有人可以帮我吗？被这个问题困扰了一段时间。

请在 mod 下方查找。和数据。文件。

提前致谢！ 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);
};

数据

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]
]};

Answer 1

你应该把距离矩阵变成一个元组集。

参见 How to with OPL ?

中的示例

OPL 中的 TSP（旅行商问题）scheduling、约束编程或删除电路和 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
}

在 CPU 调度问题中包含距离矩阵

Including a distance matrix in a CP schedulling problem

optimization

sequence

constraint-programming

cplex

job-scheduling