如何将一组相关步骤分成组
How to split set of dependent steps into groups
我有一组要执行的步骤，每个步骤都有一个时间（以分钟为单位）。
我还有一组依赖项（即第 7 步必须在第 5 步之后）。
假设没有循环，将它们分组的正确算法是什么，其中每个组的总时间少于一定数量。
很明显，除非依赖关系给出线性顺序，否则有多种安排步骤的方法，是否easy/possible找出最优化的（即需要最少的组）。
目前我的步骤和依赖项在 SQL 中，但我很乐意用另一种语言提供解决方案。
当没有依赖关系时，这就是NP-hard bin packing问题。 Bin packing 有一些聪明的精确算法，但我不确定如何调整它们，而且它们很难实现。这是非常好的 First Fit Decreasing approximation 的模拟（原始版本的 11/9 渐近近似比率；不知道新版本是否有用）。
首先从数据库中转储所有任务及其依赖项。使用 Kahn's algorithm 的变体对任务进行拓扑排序，其中，在之前已选择所有依赖项的所有任务中，选择最长的作为下一个。将此任务安排在第一组中，它既适合又不在依赖项之前。
我有一组要执行的步骤，每个步骤都有一个时间（以分钟为单位）。
我还有一组依赖项（即第 7 步必须在第 5 步之后）。
假设没有循环，将它们分组的正确算法是什么，其中每个组的总时间少于一定数量。
很明显，除非依赖关系给出线性顺序，否则有多种安排步骤的方法，是否easy/possible找出最优化的（即需要最少的组）。
目前我的步骤和依赖项在 SQL 中，但我很乐意用另一种语言提供解决方案。
当没有依赖关系时，这就是NP-hard bin packing问题。 Bin packing 有一些聪明的精确算法，但我不确定如何调整它们，而且它们很难实现。这是非常好的 First Fit Decreasing approximation 的模拟（原始版本的 11/9 渐近近似比率；不知道新版本是否有用）。
首先从数据库中转储所有任务及其依赖项。使用 Kahn's algorithm 的变体对任务进行拓扑排序，其中，在之前已选择所有依赖项的所有任务中，选择最长的作为下一个。将此任务安排在第一组中，它既适合又不在依赖项之前。