constraint-programmingoplibm-ilog-oplcp-optimizer

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


I am working on RCPSP and want to apply Preemption to it.
I have divided the duration of every task into equal parts. Now after doing that I am unable to apply Precedence constraints to each of individual unit duration of a task.

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

Thanks in Advance.


Solution

  • First, you should add some constraints that says that each task represented by interval itvs[t] spans the set of individual activities a[<t,i>], something like: span(itvs[t], all(i in 1..t.pt) a[<t,i>])

    And then, say that the individual activities of a given task t form a chain, with constraints like: endBeforeStart(a[<t,i-1>],[<t,i>])

    But note that for this preemptive version of the problem, you will loose one of the major interest of CP Optimizer which is the fact it avoids the enumeration of time. Here, if tasks are fully preemptive, you have to divide each task of duration D into D individual activities. If you know you have some constraints on the preemption of tasks (for instance that each individual activity has a minimal duration larger than the time unit), this can be exploited in the model to create less sub-activities.