- 我有一组J工作需要完成
- 所有作业需要不同的时间才能完成，但时间是已知的
- 我有一组R资源
- 每个追索权R可以具有从1到100个实例中的任意数目
- 作业可能需要使用任意数量的资源R
- 一个作业可能需要使用资源R的多个实例，但永远不会超过资源R的实例(如果一个资源只有2个实例，则一个作业永远不会需要超过2个实例(
- 作业完成后，它会将其使用的所有资源的所有实例返回到池中，供其他作业使用
- 作业一旦启动就不能被抢占
- 只要资源允许，可以同时执行的作业数量没有限制
- 这不是一个有向图问题，作业J可以按任何顺序执行，只要它们可以声明其资源即可
我的目标：安排作业以最大限度地减少运行时间和/或最大限度地提高资源利用率的最佳方式。
我不确定这个想法有多好，但你可以将其建模为一个整数线性程序，如下所示(未测试(
定义一些常量，
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(，你会得到一个下界，近似贪婪解会给出上界。如果它们足够接近，您可以跳过代价高昂的整数阶段，采用贪婪的解决方案。在某些情况下，如果线性松弛的四舍五入目标与贪婪解的目标相同，这甚至可以证明贪婪解是最优的。
这可能是Dykstra算法的工作。对于您的情况，如果您想最大限度地提高资源利用率，那么搜索空间中的每个节点都是将一个作业添加到您要同时执行的作业列表中的结果。边缘将是当你将一个作业添加到你要做的作业列表中时剩下的资源。
然后，目标是找到具有最小值的传入边的节点的路径。
另一种更直接的选择是将其视为背包问题。
为了将这个问题构造为背包问题的一个实例，我将执行以下操作：
假设我有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)