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

Question

我想实现以下job/resource调度问题：

• 作业的 DAG，其中边对优先关系进行编码。
• 如果没有优先关系，作业可以并行执行
• 多个资源池，每个资源池包含一个或多个类似资源。
• 一项工作可能依赖于一个或多个池中的一个或多个资源。 IE。 job J1 是这样写的："I need 2 resources from pool P1 and 7 resources from pool P2."
• 一项工作可能表示它需要与其直接前任之一完全相同的资源。 IE。作业 J2 可能会说 "I need 1 resource from pool P1, but it must be one of the resources that job J1 got assigned." 作为简化，我假设作业 J2 必须是 J1 的直接继承者才能满足这种约束。
• 资源相关性可以是读或写或两者或"don't care"
• 当作业 J1 表示它写入池 P1 中的资源时，其后续作业 J2 对 "the same resource as J1 got from P1" 具有读取依赖性。在这两者之间，资源不可用于其他写入作业，因为资源是有状态的。
• 我事先不知道每个作业的执行时间，作业也没有优先级和截止日期要求。

我正在寻找：

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

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

Answer 1

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

正式地，我们有

• n 个工作 J = {0, 1, …, n-1}
• J
上的非自反传递优先关系≺
• 一组资源类型R
• 一组名字X
• 从 R 到 ℕ 的映射 A，表示可用资源（其中 ℕ = {0, 1, 2, …} 是自然数）
• a map U from J to ℕ^R 指示未命名的资源需求（ℕ^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] 是艾弗森括号（如果满足条件则为 1，否则为 0）并且 ≤ 是向量的标准偏序。

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

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