algorithm - 资源分配算法

Question

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

我的问题如下:

• 我有一组 J 个作业需要完成。

• 所有工作需要不同的时间才能完成，但时间是已知的。

• 我有一套 R 资源。

• 每个资源 R 可以有 1 到 100 个实例。

• 一个 Job 可能需要使用任意数量的资源 R。

• 一个作业可能需要使用资源 R 的多个实例，但绝不会超过资源 R 的实例数。 (如果资源只有 2 个实例，则作业永远不需要超过 2 个实例)

• 作业完成后，它会将其使用的所有资源的所有实例返回到池中以供其他作业使用。

• 作业一旦开始就不能被抢占。

• 只要资源允许，同时执行的作业数量没有限制。

• 这不是一个有向图问题，作业 J 可以以任何顺序执行，只要它们可以索取它们的资源。

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

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

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

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

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

有很多方法可以获得贪婪的解决方案，例如，只需将作业一个接一个地安排在最早的时间段内。通过某种“硬度”度量对它们进行排序并将较难的放在第一位可能会更好，例如，您可以根据它们使用资源的严重程度给它们打分(例如，Use[ 的总和) j,i]/Capacity[i]，或者可能是最大值？谁知道呢，尝试一些东西)然后按该分数降序排序。

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