在DAG中查找最大可并行化任务的算法？

Question

想象一下，我有一个有顶点和边的有向无环图（DAG）。

顶点可以是以下两种类型之一：

• 计算任务（T）
• 资源（R）

边表示依赖关系。它始终源自一些计算任务顶点T并以某些资源顶点R结束。

图结构的限制：

• 任务顶点仅依赖于资源顶点（而不依赖于其他任务）。这意味着计算任务只有传出边缘，并且只有传入边缘进入资源。
• 任务顶点不能有多个边到同一个资源顶点。
• 资源顶点不依赖于任何东西（没有外向边）。
• 每个计算任务顶点可以具有最少3个输出边缘，最多4个输出边缘。这意味着，计算任务取决于最少3个资源，最多4个。

语义：

• 上图是任务依赖图。每当任务Tx运行时，它都会阻止它所依赖的所有资源，直到它完成为止。
• 在任何给定时间，每个资源都不能被超过1个任务使用。因此，任务可以暂时阻止其他任务运行，直到完成为止。

题：

鉴于上面的图表，我可以使用什么算法来计算我可以并行运行的所有可能任务，以便它们不会相互阻塞？即在任何给定时间，我希望能够实现最大的并行化。我将使用该算法来发现所有不会相互阻塞的任务，并运行它们。每当任务完成时，我都想重新评估图形以查看是否可以分离出更多未被阻止的任务。

我想知道我可以用于这种计算的算法。这听起来像一个硬图问题，但我怀疑这种问题并不完全是全新的......

例：

在提供的示例中，我可以先运行T1和T3。完成后，我可以运行T2和T4。

Answer 1

将资源集表示为S，并将每个任务表示为S的子集，您的问题是maximum set packing。另见here。