Yet*_*osh 6 algorithm parallel-processing graph directed-acyclic-graphs
假设我有一个图表,其中节点是各种工作负载,边缘是工作负载之间的依赖关系.(这是DAG,因为不能存在循环依赖.)
我还有一组可以执行工作的多个代理.
一些工作负载变种可以给予任何代理,其他工作量必须给予特定代理,而其他工作量必须给予特定代理组中的一个代理.
如何分配工作负载,以便:
在完成所有阻塞工作负载之前,不会向代理提供任何工作负载
完成总工作负载图需要最短的时间.(请注意,最小化代理程序空闲时间通常是好的,但不是基本要求 - 可能存在一个特定代理程序闲置的时间更长但是完成所有代理程序中所有作业的总时间最少.)
工作负载具有持续时间估计值,但为简单起见假设每个工作负载需要相同的计算时间.(只需将每个工作负载分解为多个依赖于串行的工作负载,直到每个工作负载实际上都是一个恒定时间操作.)
我知道拓扑DAG排序,但它产生一个单一的序列节点排序.我有多个并行运行的代理,并且这种关系可以通过非显而易见的任务重新排序来实现潜在的大时序优化.
这样的结果将作为最小总持续时间的甘特图得到最佳结果.实际上,如果您将问题视为在团队中的工程师的里程碑中分配错误票据,目标是尽快完成里程碑,那么您就会明白这一点.(不......请不要告诉我将我的图表导入MS Project然后将其导出:) - 我对它背后的算法感兴趣!)
非常感谢知名算法,软件库或一般问题和原则的指针!
除非您有无限数量的代理，以便在任务的所有前置任务完成后立即可以使用兼容的代理，否则这是一个 NP 困难问题。
<无耻插件>
我的书《面试算法》中也有一个非常相似的问题
</无耻插件>
这是书中的问题和解决方案：
我们需要在 M 个教室安排 N 个讲座。其中一些讲座是其他讲座的先决条件。为了尽快完成所有的讲座，您会如何选择上课的时间和地点？
解决方案：我们有一组 N 个单位持续时间的讲座和 M 个教室。只要同一教室不需要同时进行两场讲座并且满足所有优先级限制，讲座就可以同时举行。安排这些讲座以最小化完成时间所需的时间的问题被称为 NP 完全问题。这个问题自然可以使用图来建模。我们将讲座建模为顶点，如果 u 是 v 的先决条件，则具有从顶点 u 到顶点 v 的边。显然，为了满足优先约束，该图必须是非循环的。如果只有一间教室，我们可以简单地按照拓扑顺序举办讲座，并在 N 次内完成 N 场讲座（假设每场讲座都是单位时长）。我们可以通过观察以下情况来发展启发式：在任何时候，都有一组讲座其优先级约束已得到满足。如果这个集合小于M，我们可以将它们全部调度；否则，我们需要选择一个子集来进行调度。子集选择可以基于几个指标：
我们还可以使用这些标准的组合来排序当前可安排的讲座。例如，对于每个顶点，我们将其关键性定义为从它到接收器的最长路径的长度。我们通过按拓扑顺序处理顶点来安排讲座。在我们的算法中的任何一点，我们都有一组候选讲座——这些讲座的先决条件已经安排好了。如果候选集小于M，我们安排所有讲座；否则，我们选择 M 个最关键的讲座并安排它们——我们的想法是，它们应该尽早安排，因为它们位于较长依赖链的开始处。该标准是启发式的，可能不会导致最佳调度——这是可以预料的，因为问题是 NP 完全的。可以采用其他启发法，例如，我们可以使用依赖于讲座L的讲座的数量作为讲座L的关键性或标准的某种组合。