0

如何定义一个约束以防止将资源分配给两个重叠的任务？

我定义了 5 个资源：R1、R2、...、R5 和 3 个任务：T1、T2、T3，它们具有相应的开始和结束日期（s1、e1 代表第一个任务的开始和结束日期，s2、e2第二个任务等等）。如果这两个任务重叠，我的约束应该防止将 R1 分配给任务 T1 和任务 T2。R1 可以分配给任意数量的任务，因此如果 T1 和 T3 不重叠，它们都可以由 R1 执行。

我打算使用 C# 和 Microsoft Solver Foundation 来解决这个问题，但这当然不是那么重要。我的问题是我不知道如何将这个问题表述为一个约束。

4

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) 比较。请注意，这可以在您调用求解器之前离线计算一次。

公式

如果资源 i 分配给任务 j，则令 X_Ri_Tj = 1。

现在，您可以编写“重叠预防约束”。对于矩阵中的每个冲突，将有 R 个约束。

作为一个具体的例子，从上面的矩阵中，假设我们要编写约束以防止将相同的资源分配给任务 T2 和 T3（因为它们是重叠的）。你将把它们写成：

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

这种类型的约束生成在作业车间调度和“时间表”类问题中相当普遍。

于 2014-03-16T18:53:15.133 回答