Мой вопрос об ограничении ресурсов. Код задачи планирования проекта в cplex. Я пытаюсь применить Preemption к нему

Question

Я работаю над RCPSP и хочу применить к нему Preemption.
Я разделил продолжительность каждого задания на равные части. Теперь, после этого, я не могу применить ограничения Precedence к каждой отдельной единице продолжительности задачи.

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 отдельных действий. Если вы знаете, что у вас есть некоторые ограничения на приоритет выполнения задач (например, минимальная продолжительность каждого отдельного действия больше, чем единица времени), это можно использовать в модели для создания меньшего количества подэтапов.

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

Наконец (но это только для небольшого ускорения разрешения), вы можете переформулировать выражение 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]); 
  }
}