0

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

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

提前致谢。

4

2 回答 2

0

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

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

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

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]); 
  }
}
于 2019-03-11T16:02:36.347 回答
0

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

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

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

于 2019-02-14T15:59:33.053 回答