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

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

0 голосов
/ 14 февраля 2019

Я работаю над 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);  
  } 
}

Заранее спасибо.

Ответы [ 2 ]

0 голосов
/ 11 марта 2019

Я думаю, что в вашей модели отсутствует важное ограничение, согласно которому сумма длительностей разных частей задачи равна времени обработки задачи.Примерно так: 

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

Наконец (но это только для ускорения разрешениянемного), вы можете переформулировать составное выражение в цели, используя интервалы охвата задачи, а не части (это будет включать меньше переменных): 

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]); 
  }
}
0 голосов
/ 14 февраля 2019

Во-первых, вы должны добавить некоторые ограничения, которые говорят, что каждая задача, представленная интервалом itvs [t], охватывает набор отдельных действий a [], что-то вроде: span (itvs [t], all (i в 1..t.pt) a [])

А затем, скажем, что отдельные действия данной задачи t образуют цепочку с такими ограничениями, как: endBeforeStart (a [], [])

Но учтите, что для этой упреждающей версии проблемы вы потеряете один из основных интересов оптимизатора CP, который заключается в том, что он избегает перечисления времени.Здесь, если задачи являются полностью упреждающими, вы должны разделить каждую задачу продолжительностью D на D отдельных действий.Если вы знаете, что у вас есть некоторые ограничения на приоритет выполнения задач (например, каждая отдельная операция имеет минимальную продолжительность, превышающую единицу времени), это можно использовать в модели для создания меньшего количества подэтапов.

...