3

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

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

我在寻找：

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

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

4

1 回答 1

1

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

正式地，我们有

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

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

  • 对于所有工作 j 1 ≺ j 2，我们有 π(j 1 ) < π(j 2 ) [< 是线性扩展]
  • 对于 {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 的银行家算法的变体，该算法使用离线测试来查看是否可以安全地开始依赖已完成的作业。这将恢复并行性，因为启动多个作业可能是可以的。

于 2019-09-04T13:20:36.793 回答