0

How can I define a constraint that prevents a resource to be allocated to 2 tasks that overlap?

I have defined 5 resources: R1,R2,...,R5 and 3 tasks: T1,T2,T3 that have their corresponding start and end date(s1, e1 represent the start and end date of the first task, s2,e2 of second task and so on). My constraint should prevent R1 to be allocated to task T1 and task T2 if these two tasks overlap. R1 can be allocated to any number of tasks so if T1 and T3 do not overlap, they can both be performed by R1.

I am planning to use C# and Microsoft Solver Foundation to solve this problem but of course this is not so important. My problem is that I don't know how to formulate this problem as a constraint.

4

1 に答える 1

1

オーバーラップとコンフリクトを処理するために、この種の制約を定式化する方法は多数あります。

ここでは、非常に一般的で標準的な方法を 1 つ紹介します。

競合マトリックスを作成するための前処理

最初に、サイズ T^2 の競合マトリックス(技術的には下の三角形で十分です) を作成します。ここで、T はタスクの数です。Tj と Tk が重複する場合は 1 をマークし、そうでない場合は 0 (競合がないことを示す) をマークします。

たとえば、これは競合マトリックスである可能性があります。

     T1  | T2 | T3
T1   --  | 1  | 0
T2    1  | -- | 1
T3    0  | 1  | --

この行列を作成するには、タスクの各ペアjとk(sj, ej) および (sk, ek) を含む O(T^2) 比較を行う必要があります。これは、ソルバーを呼び出す前にオフラインで 1 回計算できることに注意してください。

処方

リソース i がタスク j に割り当てられている場合、X_Ri_Tj = 1 とします。

これで、「重複防止制約」を記述できます。マトリックス内の競合ごとに、R 個の制約があります。

具体的な例として、上記のマトリックスから、同じリソースがタスク T2 と T3 に割り当てられるのを防ぐための制約を書きたいとしましょう (重複しているため)。それらを次のように記述します。

  Xr1t2 + Xr1t3 <= 1
  Xr2t2 + Xr2t3 <= 1
  Xr3t2 + Xr3t3 <= 1
  ... for each resource R

このタイプの制約生成は、Job Shop Schedulingおよび「タイム テーブル」クラスの問題でかなり一般的です。

于 2014-03-16T18:53:15.133 に答える