algorithm - 如何为这个调度和资源分配问题建模

Question

我想实现以下作业/资源调度问题:

• 工作的 DAG，其中边编码优先关系。
• 如果没有优先关系，作业可以并行执行
• 多个资源池，每个资源池包含一个或多个类似的资源。
• 一项工作可能依赖于一个或多个池中的一个或多个资源。 IE。作业 J1 会这样说:“我需要池 P1 中的 2 个资源和池 P2 中的 7 个资源。”
• 一项工作可能会表达它想要与其直接前任之一完全相同的资源。 IE。作业 J2 可能会说“我需要池 P1 中的 1 个资源，但它必须是作业 J1 分配的资源之一。”作为一种简化，我假设作业 J2 必须是 J1 的直接后继者，才能满足这种约束。
• 资源依赖性可以是读或写或两者兼而有之，或者“不关心”
• 当作业 J1 说它写入池 P1 中的资源时，它的后续作业 J2 对“与 J1 从 P1 获得的相同资源”具有读取依赖性。在此期间，资源不可用于其他写入作业，因为资源是有状态的。
• 我事先不知道每个作业的执行时间，也没有优先级和截止日期要求。

我正在寻找:

1. 一种在正式领域表达这个问题的方法，
2. 离线可调度性测试，回答作业图是否可以在给定的要求和约束条件下执行的问题。
3. 在线调度算法的建议

如果没有资源池，而是每种类型只有一种资源，问题可能会简单得多。我熟悉图论和简单数据流分析算法的基础知识。

Answer 1

我想我会通过引入“命名资源”的概念来修改您的描述，其中命名资源是一个名称和未命名资源的集合。然后作业可以依赖命名和未命名资源，并且每个命名资源必须从第一个使用它的作业开始到最后一个使用它的作业结束的时间保持驻留。

正式地，我们有

• n 个工作 J = {0, 1, …, n-1}
• J 上的非自反传递优先关系 ≺
• 一组资源类型R
• 一组名字X
• 从 R 到 ℕ 的映射 A，表示可用资源(其中 ℕ = {0, 1, 2, …} 是自然数)
• 从 J 到 ℕ^R 的映射 U，表示未命名的资源需求(ℕ^R 是从 R 到 ℕ 的映射)
• 从 J 到 2^X 的映射 Y，表示指定的资源需求(2^X 是 X 的子集)
• 从 X 到 ℕ^R 的映射 Z，指示命名资源的组成。

为了检查计划的可行性，没有理由并行运行作业。因此，我们想要的是 < of ≺ 的线性扩展。在更接近求解器可以处理的形式上，我们将定义 < 从 J 到 {0, 1, …, n-1} 的双射 π 满足

• 对于所有作业 j₁ ≺ j₂，我们有 π(j₁) < π(j₂) [<是线性扩展]
• 对于 {0, 1, …, n-1} 中的每个时间 t，使用的资源不超过可用资源。正式地(urgh)，对于每个命名资源 x ∈ X，让 s_x 和 e_x 是 {π(j) | 的最小值和最大值。 j ∈ J ∧ x ∈ Y(j)} [即依赖于 x 的每个作业的时间]。那么对于所有的 t，我们想要

∑_{x ∈ X} [s_x ≤ t ≤ e_x] Z(x) + U(π^-1 (t)) ≤ A,

其中 [condition] 是 Iverson 括号(如果满足条件则为 1，否则为 0)并且 ≤ 是向量的标准偏序。

为了测试时间表的可行性，我会将类似此公式的内容提供给 CP-SAT 求解器(例如，https://developers.google.com/optimization/cp/cp_solver)。

要在线安排，我会使用 Dijkstra 的变体 Banker's algorithm它使用离线测试来查看启动依赖项已完成的作业是否安全。这将恢复并行性，因为启动多个作业可能没问题。