CPLEX OPL 问题如何安排 even/odd 时间任务

Question

为了简单起见，假设我们有 10 个任务 t0、t1、... t9，为了简单起见，我们忽略任务之间的依赖关系。

我有一个 OPL 问题，我必须在偶数时间（0、2、4、6、8 等）安排第一个任务。第二个任务必须在第一个任务和奇数时间（1、3、5、...）之后。第 3 个偶数、第 4 个奇数、第 5 个偶数，依此类推。第一个任务不一定是 0，因为实际上还有其他任务。

如果我可以抓取已排序的任务间隔，然后在主题中说类似 Mod(t[i+1]-t[i],2) == 1 的内容，那应该可以。我该怎么做？

int Max = 4;
{string} TaskNames = {t0,t1,t2,t3,t4,t5,t6,t7,t8,t9};


// Other intervals and sequences setup...

dvar Interval taskIntervals [t in TaskNames] size 1;

dvar sequence taskSequences in taskIntervals;

subject to {
   //Other constraints and constraint to prevent overlap of TaskIntervals is already setup here

   //I need to loop through the intervals of the taskSequences except last one then
   //(startofNext(taskSequences, t, 0) - t)  % 2 == 1

}

Answer 1

对于每个任务，你可以引入一个辅助整数变量x，然后要求任务的开始时间是2*x或2*x + 1，这取决于你是否想要甚至或奇数开始时间。

Answer 2

你可以从

开始

using CP;

int n=10;

range r=0..n-1;

dvar interval itvs[r] size 1..100;

subject to
{
  forall(i in r:i!=0) startBeforeStart(itvs[i-1],itvs[i]);
  
  startOf(itvs[0]) mod 2==0;
  
  forall(i in r : i!=0) (startOf(itvs[i])-startOf(itvs[i-1])) mod 2==1-(i mod 2);
}

Answer 3

如果（据我所知）任务的顺序不是先验的，我会考虑这样的模型：

using CP;

int n=10;

dvar interval x [i in 0..n] size 1;
dvar sequence s in x;

subject to {
  noOverlap(s);
  forall(i in 0..n-2) {
    (endOfPrev(s,x[i],0) == 0) => (startOf(x[i]) % 2==0); // First task starts at even time
    // Then the delay between consecutive tasks alternates between even and odd
    ( (startOf(x[i])-endOfPrev(s,x[i],0)) % 2) + ((startOfNext(s,x[i],0)-endOf(x[i])) % 2)  == 1;
  }
  last(s, x[n]); // x[n] is a technical interval variable at the end of the sequence
}

'forall' 循环中的第一个约束确保第一个间隔（唯一一个 endOfPrev(s,x[i],0) == 0 ）在偶数时间开始。第二个约束确保序列中任务之间的连续延迟交替出现。

Answer 4

我成功了。我认为大多数答案都误解了一些东西。约束不保证 t0 在 t1 之前。这意味着我可以在序列中获得不同的位置和声明的位置，这会使 Prev 或 Next（基于位置）输出乱序。

我用的是isomorphism constraint. Basically, this constraint does a 1-to-1 correspondence between two sets. The first set is my task set. The second set is based on @Alex Fleischer 。然后，CPLEX 将强制第一组在优化期间遵循与第二组相同的模式。

{string} TaskNames = {t0,t1,t2,t3,t4,t5,t6,t7,t8,t9};


dvar Interval taskIntervals [t in TaskNames] size 1;

int n=10;
range r=0..n-1;
dvar interval itvs[r] size optional;

subject to {
  // other constraints for taskIntervals

  forall(i in r : i!=0) {
      startBeforeStart(itvs[i-1],itvs[i]);
      (startOf(itvs[i])-startOf(itvs[i-1])) mod 2==1;
  }
  isomorphism(taskInverals, itvs);
}

CPLEX OPL 问题如何安排 even/odd 时间任务

CPLEX OPL problem how to schedule even/odd time tasks

cplex

opl