资源分配算法

Question

资源分配算法

algorithmscheduling

4

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

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

- Kaiser

你必须定义什么是“最好”的方式来完成所有工作，但这仍然不是 Stack Overflow 的主题。 - chepner

1

一个混合元启发式算法用于资源受限的项目调度问题。 - Louis Ricci

听起来像是ICON挑战赛中的资源优化问题。元启发式算法在这个问题上表现良好。你在那个视频中看到的开源实现获得了第二名。 - Geoffrey De Smet

今天的工作又开始了，正在努力解决你发布的问题，Harold。希望几个小时后可以取得更多进展。 - Kaiser

@Kaiser，请问您能分享一下这个问题的方程式吗？ - alanextar

2个回答

1

这可能需要使用Dykstra算法。对于您的情况，如果您想最大化资源利用率，则搜索空间中的每个节点都是将作业添加到同时要执行的作业列表中的结果。然后，边缘将是添加作业到您要执行的作业列表中时剩下的资源。

因此，目标是找到具有最小值的入边的节点的路径。

另一种更直接的选择是将其视为背包问题。

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

假设我有J个工作，j_1，j_2，...，j_n和R个资源，我要找到子集J'，使得当该子集被调度时，R最小化。

伪代码如下：

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)

- David Weiser

你能详细说明如何将其视为背包问题吗？ - harold

@Davidann ，回答很有意思，但我不太明白它如何给出最优解，因为作业可能需要不同的时间。看起来背包代码没有考虑到可能需要多个资源并且运行时间长的作业，并将它们与可能不需要很长时间的作业分组。你对此有什么看法？ - Kaiser

@Kaiser：你的目标是要“最小化运行时间和/或最大化资源利用率”，我选择了资源利用率。 - David Weiser

@Davidann，抱歉我没有表达清楚，我想知道这个算法如何考虑到不同作业之间的运行时间差异。即使您正在优化资源利用率，似乎这个背包问题变体假设运行时间是均匀的。如果我错了，请纠正我。 - Kaiser

@Kaiser：我认为这个算法没有考虑到每个任务运行所需的时间，它只关注最大化资源利用率。 - David Weiser

@Davidann：明白了，我会进一步查看是否可以完全适应一种变体来解决我的问题。不过还是给你一个点赞表示感谢你的帮助。 - Kaiser

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- harold · Accepted Answer

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

定义一些常量，

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] 的总和或最大值）给它们打分，然后按得分从高到低排序。

作为额外的奖励，您可能不必总是解决完整的ILP问题（这是NP难的，因此有时可能需要一段时间），如果您只解决线性松弛问题（允许变量取分数值，而不仅仅是0或1），则可以获得下界，近似贪心解提供上界。如果它们足够接近，则可以跳过昂贵的整数阶段并采用贪心解决方案。在某些情况下，如果线性松弛舍入后的目标与贪心解决方案的目标相同，则甚至可以证明贪心解是最优的。