资源分配算法

Question

我知道算法存在，但我在命名它和找到合适的解决方案时遇到问题。

我的问题如下：

我有一组作业需要完成。
所有作业需要不同的时间才能完成，但时间是已知的。
我有一套R资源
每个资源 R 可以有 1 到 100 个实例。
一个Job可能需要使用任意数量的资源R。
一个作业可能需要使用资源 R 的多个实例，但绝不会超过资源 R 拥有的实例。（如果资源只有 2 个实例，作业将永远不需要超过 2 个实例）
作业完成后returns它使用的所有资源的所有实例都返回到池中供其他作业使用。
作业一旦开始就不能被抢占。
只要资源允许，同时执行的作业数量没有限制。
这不是一个有向图问题，作业J可以以任何顺序执行，只要它们能够索取它们的资源。

我的目标：安排作业以最小化运行时间 and/or 最大化资源利用率的最佳方式。

Answer 1

我不确定这个想法有多好，但您可以将其建模为整数线性程序，如下所示（未测试）

定义一些常量，

Use[j,i] = amount of resource i used by job j
Time[j] = length of job j
Capacity[i] = amount of resource i available

定义一些变量，

x[j,t] = job j starts at time t
r[i,t] = amount of resource of type i used at time t
slot[t] = is time slot t used

约束是，

// every job must start exactly once
(1). for every j, sum[t](x[j,t]) = 1
// a resource can only be used up to its capacity
(2). r[i,t] <= Capacity[i]
// if a job is running, it uses resources
(3). r[i,t] = sum[j | s <= t && s + Time[j] >= t] (x[j,s] * Use[j,i])
// if a job is running, then the time slot is used
(4). slot[t] >= x[j,s] iff s <= t && s + Time[j] >= t

第三个约束意味着，如果一个作业最近才开始，它仍然是运行，那么它的资源使用量将添加到当前使用的资源中。第四个约束意味着，如果一个作业最近才开始，它仍然是运行，那么将使用这个时间段。

objective函数是slots的加权和，后面的slots权重高，所以优先填充前面的slots。从理论上讲，权重必须呈指数增长，以确保使用较晚的时隙总是比仅使用较早时隙的任何配置都差，但求解器不喜欢这样，在实践中，您可能可以使用增长较慢的权重。

您将需要足够的插槽以便存在一个解决方案，但最好不要比您最终需要的更多，所以我建议您从一个贪婪的解决方案开始，希望为您提供一个非平凡的数字上限时隙（显然还有所有任务长度的总和）。

有很多方法可以得到贪婪的解决方案，例如，只需将作业一个一个地安排在最早的时间段内。将它们按 "hardness" 的某种度量排序并将困难的放在第一位可能会更好，例如，您可以根据他们使用资源的严重程度给他们打分（例如 [=13 的总和） =]，或者可能是最大值？谁知道呢，尝试一些东西）然后按该分数降序排列。

作为奖励，如果您只解决线性松弛（允许变量取分数值，而不仅仅是 0 或 1) 你得到一个下界，近似贪婪的解决方案给出了上界。如果它们足够接近，您可以跳过代价高昂的整数阶段并采用贪婪的解决方案。在某些情况下，如果线性松弛的向上舍入 objective 与贪婪解的 objective 相同，这甚至可以证明贪婪解是最优的。

Answer 2

这可能是 Dykstra's Algorithm 的工作。对于您的情况，如果您想最大限度地利用资源，那么搜索 space 中的每个节点都是将作业添加到您将立即执行的作业列表中的结果。边缘将成为您将工作添加到您将要做的工作列表时剩下的资源。

然后，目标是找到到具有最小值的传入边的节点的路径。

另一种更直接的方法是将其视为 knapsack problem。

要将此问题构造为背包问题的实例，我将执行以下操作：

假设我有 J 个工作、j_1, j_2, ..., j_n 和 R 资源，我想找到 J 的子集，以便在安排该子集时，R 被最小化（我称之为 J'）。

在伪代码中：

def knapsack(J, R, J`):
  potential_solutions = []
  for j in J:
    if R > resources_used_by(j):
      potential_solutions.push( knapsack(J - j, R - resources_used_by(j), J' + j) )
    else:
      return J', R
  return best_solution_of(potential_solutions)

资源分配算法

Resource allocation algorithm

algorithm

scheduling