资源分配算法 [英] Resource allocation algorithm

问题描述

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

我的问题如下:

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

• 完成所有作业所需的时间不同，但时间是已知的.

• 我有一组 R 资源.

• 每个资源 R 可能有 1 到 100 个实例.

• 一个作业可能需要使用任意数量的资源 R.

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

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

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

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

• 这不是有向图问题，作业 J 可以按任何顺序执行，只要它们可以声明其资源即可.

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

解决方案

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

定义一些常量，

Use[j,i] = 作业 j 使用的资源量时间[j] = 作业j的长度容量[i] = i 可用的资源量

定义一些变量，

x[j,t] = 作业 j 在时间 t 开始r[i,t] = 在时间 t 使用的类型 i 的资源量slot[t] = 是使用的时隙 t

约束是，

//每个作业必须刚好开始一次(1).对于每个 j，sum[t](x[j,t]) = 1//资源只能使用到它的容量(2).r[i,t] <= 容量[i]//如果作业正在运行，则它使用资源(3).r[i,t] = sum[j |s <= t &&s + 时间[j] >= t] (x[j,s] * 使用[j,i])//如果作业正在运行，则使用时隙(4).slot[t] >= x[j,s] 仅当 s <= t &&s + 时间[j] >= t

第三个约束意味着如果一个作业最近启动的时间足够长并且它仍在运行，那么它的资源使用量会被添加到当前使用的资源中.第四个约束意味着，如果一个作业最近启动的时间足够长，它仍在运行，则使用这个时间段.

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

您将需要足够的槽数来存在解决方案，但最好不要超过您最终需要的太多，所以我建议您从一个贪婪的解决方案开始，为您提供一个非常重要的时间上限槽(显然还有所有任务的长度之和).

有很多方法可以得到一个贪心的解决方案，例如只需在最早的时间段内一个一个地安排作业.通过某种程度的硬度"对它们进行排序并把困难的放在第一位可能会更好，例如，您可以根据他们使用资源的严重程度给他们打分(例如，Use[j,i]/Capacity[i]，或者可能是最大值?谁知道，尝试一些事情)然后按该分数降序排列.

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

I know the algorithm exists but i and having problems naming it and finding a suitable solutions.

My problem is as follows:

• I have a set of J jobs that need to be completed.

• All jobs take different times to complete, but the time is known.

• I have a set of R resources.

• Each recourse R may have any number from 1 to 100 instances.

• A Job may need to use any number of resources R.

• A job may need to use multiple instances of a resource R but never more than the resource R has instances. (if a resource only has 2 instances a job will never need more than 2 instances)

• Once a job completes it returns all instances of all resources it used back into the pool for other jobs to use.

• A job cannot be preempted once started.

• As long as resources allow, there is no limit to the number of jobs that can simultaneously execute.

• This is not a directed graph problem, the jobs J may execute in any order as long as they can claim their resources.

My Goal: The most optimal way to schedule the jobs to minimize run time and/or maximize resource utilization.

解决方案

I'm not sure how good this idea is, but you could model this as an integer linear program, as follows (not tested)

Define some constants,

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

Define some variables,

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

The constraints are,

// 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

The third constraint means that if a job was started recently enough that it's still running, then its resource usage is added to the currently used resources. The fourth constraint means that if a job was started recently enough that it's still running, then this time slot is used.

The objective function is the weighted sum of slots, with higher weights for later slots, so that it prefers to fill the early slots. In theory the weights must increase exponentially to ensure using a later time slot is always worse than any configuration that uses only earlier time slots, but solvers don't like that and in practice you can probably get away with using slower growing weights.

You will need enough slots such that a solution exists, but preferably not too many more than you end up needing, so I suggest you start with a greedy solution to give you a hopefully non-trivial upper bound on the number of time slots (obviously there is also the sum of the lengths of all tasks).

There are many ways to get a greedy solution, for example just schedule the jobs one by one in the earliest time slot it will go. It may work better to order them by some measure of "hardness" and put the hard ones in first, for example you could give them a score based on how badly they use a resource up (say, the sum of Use[j,i] / Capacity[i], or maybe the maximum? who knows, try some things) and then order by that score in decreasing order.

As a bonus, you may not always have to solve the full ILP problem (which is NP-hard, so sometimes it can take a while), if you solve just the linear relaxation (allowing the variables to take fractional values, not just 0 or 1) you get a lower bound, and the approximate greedy solutions give upper bounds. If they are sufficiently close, you can skip the costly integer phase and take a greedy solution. In some cases this can even prove the greedy solution optimal, if the rounded-up objective from the linear relaxation is the same as the objective of the greedy solution.

这篇关于资源分配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！