我的问题是关于 cplex 中的资源约束项目调度问题代码。我正在尝试对其应用抢占

Question

我正在研究 RCPSP 并想对其应用抢占。
我将每项任务的持续时间分成相等的部分。这样做之后，我无法将优先级约束应用于任务的每个单独单位持续时间。

using CP;

int NbTasks = ...;
int NbRsrcs = ...;
range RsrcIds = 1..NbRsrcs;  

int Capacity[r in RsrcIds] = ...;    

tuple Task {                        
  key int id;
  int     pt;
  int     dmds[RsrcIds];
  {int}   succs;            
  {int}   pred;
}
{Task} Tasks=...;


tuple sub_task { 
  Task task; 
  int p_no;
 }

 {sub_task} sub_activities = {<t,i > | t in Tasks, i in 1..t.pt  };  
 dvar interval itvs[t in Tasks]  size t.pt;
 dvar interval a[p in sub_activities] size 1;
 cumulFunction rsrcUsage[r in RsrcIds] = 
   sum (p in sub_activities: p.task.dmds[r]>0) pulse(a[p], p.task.dmds[r]);
 minimize max(t in Tasks) endOf(itvs[t]);

subject to {
  forall (r in RsrcIds)
  rsrcUsage[r] <= Capacity[r];
  forall (t1 in Tasks, t2id in t1.succs)
    endBeforeStart(itvs[t1], itvs[<t2id>]);
}     

execute {
  for (var p in sub_activities) {
    writeln("subactivity of " + p.task.id + " - " + p.p_no + " starts at " + a[p].start + " Ends at " + a[p].end);  
  } 
}

提前致谢。

Answer 1

首先，您应该添加一些约束，说明由区间 itvs[t] 表示的每个任务跨越单个活动集合 a[]，例如： span(itvs[t], all(i in 1..t.pt) a[])

然后，假设给定任务 t 的各个活动形成了一个链，具有如下约束： endBeforeStart(a[],[])

但请注意，对于问题的这个先发制人版本，您将失去 CP Optimizer 的主要兴趣之一，即它避免了时间枚举。在这里，如果任务是完全抢占式的，则必须将持续时间为 D 的每个任务划分为 D 个单独的活动。如果您知道您对任务的抢占有一些限制（例如每个人 activity 的最小持续时间大于时间单位），则可以在模型中利用它来创建更少的子活动。

Answer 2

我认为您的模型缺少一个重要的约束条件，即任务不同部分的持续时间总和等于任务处理时间。类似于：

forall (t in Tasks) {
  sum(p in sub_activities: p.task==t) lengthOf(a[p]) == t.pt;
}

此外，考虑到整数除法会将结果四舍五入，您可能会错过一些子活动，所以我宁愿使用类似的东西：

{sub_task} sub_activities = {<t,i > | t in Tasks, i in 1..1+(t.pt div t.smin )};

此外，跨任务的大小不能t.pt，但如果允许抢占会更大，所以它应该是这样的：

dvar interval itvs[t in Tasks] size t.pt..H; // H being a large number

最后（但这只是为了稍微加快分辨率），您可以使用任务跨越间隔而不是部分（这将涉及更少的变量）重新制定 objective 中的 makespan 表达式):

minimize max(t in Tasks) endOf(itvs[t]);

此外，如果你的部分有最大持续时间，你需要防止两个连续的部分连续（否则，我想它会被认为是同一部分），所以部分的区间变量链应该有最小延迟 1:

forall(p in sub_activities){ 
  forall(s in sub_activities: s.task==p.task && s.p_no==p.p_no+1){ 
    endBeforeStart(a[p],a[s],1); 
    presenceOf(a[s])=> presenceOf(a[p]); 
  }
}

我的问题是关于 cplex 中的资源约束项目调度问题代码。我正在尝试对其应用抢占

My question is about Resource constraint Project Scheduling Problem code in cplex. I am trying to apply Preemption to it

constraint-programming

opl

ibm-ilog-opl

cp-optimizer