PROSAGA码农传奇-Xedge-将工作流DAG转换为并行资源分配的算法？

<div class =“post-text”itemprop =“text”>
  
    除非您拥有无限数量的代理，以便在任务的所有前任完成后立即提供兼容代理，否则这是一个NP难题。
  
  
    ＆LT;无耻插头＆gt;
  
  
    我的书中有一个非常类似的问题“
    <a href="http://algorithmsforinterviews.com" rel="nofollow">
      面试的算法
    </A>
    “
  
  
    ＆LT; /无耻插头＆gt;
  
  
    这是本书的问题和解决方案：
  
  
    我们需要在M个教室安排N个讲座。其中一些讲座是其他讲座的先决条件。您如何选择何时何地举办讲座以尽快完成所有讲座？
  
  
    解：
我们获得了一套N单元持续时间讲座和M个教室。只要同一个教室不需要同时进行两个讲座并且满足所有优先约束，讲座就可以同时进行。
已知调度这些讲座以最小化完成所花费的时间的问题是NP完全的。
这个问题很自然地使用图表建模。我们将讲座建模为顶点，如果u是v的先决条件，则从顶点u到顶点v的边缘。显然，图形必须是非循环的，才能满足优先约束。
如果只有一个演讲室，我们可以简单地按照拓扑顺序举办讲座，并在N时间内完成N个讲座（假设每个讲座都是单位持续时间）。
我们可以通过观察以下内容来开发启发式：在任何时候，都有一组优先约束得到满足的讲座。如果此组小于M，我们可以安排所有这些;否则，我们需要选择一个子集来安排。
子集选择可以基于几个指标：
  
  <UL>
    <LI>
      排序顺序讲座基于它们在开始时的最长依赖关系链的长度。
    </LI>
    <LI>
      根据他们是当前先决条件的讲座数量排序讲座。
    </LI>
    <LI>
      根据讲座总数直接或间接的先决条件，对讲座进行排序。
    </LI>
  </UL>
  
    我们还可以使用这些标准的组合来订购当前可调度的讲座。
例如，对于每个顶点，我们将其临界值定义为从它到接收器的最长路径的长度。我们通过以拓扑顺序处理顶点来安排讲座。在我们算法的任何一点，我们都有一套候选讲座 - 这些讲座的先决条件已经安排好了。
如果候选集小于M，我们安排所有讲座;否则，我们选择M个最重要的讲座并安排那些 - 这个想法是他们应该尽快安排，因为他们处于更长的依赖链的开始。
该标准是启发式的，可能不会导致最佳的时间表 - 这是预期的，因为问题是NP完全的。可以采用其他启发法，例如，我们可以使用依赖于讲座L的讲座的数量作为讲座L的关键性或标准的某种组合。
  
</DIV>