在有向图中找到节点的最佳时间安排

Question

所以我有一个 DAG 代表一个项目，每个节点都是一个任务，它有一个变量，说明完成该任务需要多长时间。

我们可以假设可以同时处理任意数量的任务。我如何找到最佳的任务时间表，以便找到能够最早完成项目的任务序列。

Answer 1

如果您可以并行处理任意数量的任务，则可以轻松计算出最佳计划。最佳调度中任务的开始时间可以递归地定义为其图中所有前任节点的最佳结束时间（即最佳开始时间加上持续时间）的最大值。没有前置任务的任务都从时间 0 开始（或者在您希望它们开始的任何时间）。

可以通过按拓扑顺序迭代任务来迭代计算此递归。在伪代码中，该算法可能如下所示：

// Computes optimal starttime for tasks in the dag.
// Input:  dag      : DAG with tasks as nodes
//         duration : Array with duration of tasks
// Output: Array with optimal starttime of tasks
def computeSchedule(dag, duration)
    starttime := [0 for each node in dag]
    for t in nodesInTopologicalOrder(dag):
        starttime[t] = max(starttime[p] + duration[p] for p in predecessors(t))
    return starttime

在有向图中找到节点的最佳时间安排

Find optimal time schedule for nodes in a directed graph

graph

directed-acyclic-graphs