交错“任务列表”的数据结构和算法

Question

如果已经存在一些众所周知的数据结构和算法来实现下面概述的以下示例，我需要一些建议。由于缺乏CS词汇，我只能将其概括为“交错任务列表”

假设您还有 2 个以上的任务，分为 n_1 个步骤。您知道任务的持续时间以及这些任务之间的时间（最短时间、最长时间）。我想找到最短的时间来组合这些任务并最小化时间。

这是一个简单的例子：

Cooking Rice: (Duration: 24.5 minutes)
Wash Rice (3 min) -> Season Rice & Add water (0.5 min) -> Bring Rice to a Boil (4 min) -> Let Rice cook (10 min) -> Let Rice steam (5 min) -> Serve Rice (2 min) -> Ready

Steaming Broccoli: (Duration: 17 minutes)
Wash Broccoli (0.5 min) -> Cut Broccoli (1 min) -> Bring to a Boil (4 min) -> Steam (11 min) -> Serve Broccoli -> Ready. 

有多种方法可以并行这两个“任务链”。然而，存在边界条件并且节点可以延伸。 例如，我可以将米洗干净，加水并调味，然后静置 10-20 分钟，同时准备西兰花。 我想在时间方面进行优化。

仅对于这两项任务，结果可能是：

Wash Rice (3 min) -> Season Rice & Add water (3.5 min) -> Bring Rice to a Boil (7.5 min) -> Wash Broccoli (8 min) -> Cut Broccoli (9 min) -> Bring Broccoli to a Boil (13 min) -> Switch Broccoli to Steam (17) -> Turn off Rice (17.5 min) -> Serve Rice (22.5 min) -> Serve Broccoli (24.5 min) -> Ready (26 min)

显然，我想并行化多个任务而不仅仅是两个。

看到看似相似的帖子后，这里的区别是列表中的任务顺序必须保持不变，而其他列表的任务必须在已声明列表的进程暂停时完成。

我有点假设这个问题已经被解决了一百万次，但我只是不知道该寻找什么。我尝试研究多线程，但除了有关如何使用线程的高级提示之外无法细化资源。

如果有人能给我一些建议，我会非常高兴。

Answer 1

这里的技巧是专注于步骤。

每个步骤都有一个持续时间和一个指向另一个步骤的指针，该步骤必须完成才能开始。

有多种方法可以解决这个问题。获得可行解决方案的最简单方法是维护一个准备开始的步骤列表（它们所依赖的任务已完成）。当步骤处理器（或多个处理器）完成一个步骤时，它会找到现在准备好的步骤，将它们添加到列表中，然后从列表中选择一个步骤开始。

用您最喜欢的语言编写代码既快速又简单。一旦你完成了工作和调试，你将对复杂性有一个很好的感觉，并且可以从通过谷歌搜索找到的各种优化算法中进行选择。

执行此操作的传统方法称为关键路径方法https://en.wikipedia.org/wiki/Critical_path_method

现在开始了解技术。寻找关键路径：

• 将整个项目建模为树形图。
• 添加起始节点。这是树的根。使每个步骤不依赖于任何其他步骤，即根节点的子节点。
• 通过添加依赖步骤作为其依赖的步骤的子级来完成树。父节点和子节点之间的链接成本等于子步骤的持续时间。
• 使用深度优先搜索算法找到从根到达最昂贵的叶节点。
• 从根到最昂贵的叶子的路径是关键路径。

当步骤处理器完成一个步骤时，从就绪列表中选择关键路径上的步骤。如果关键路径上没有就绪任务，请选择具有最小浮动的就绪任务（导致该步骤成为关键路径一部分的延迟）