algorithm - 用拓扑排序求调度任务的最短完成时间

Question

Assume that there are an unlimited number of workers each of which can complete one task, each of which takes some time. There are also precedence constraints where one task cannot be completed until another is. What is the minimum amount of time needed for each task to be completed while respecting the precedence order?

As an example, lets say you have 3 tasks.

The first task takes 10 units of time to complete, the second takes 5 units of time to complete, and the third takes 6 units of time to complete.

The constraint is that the 2nd task cannot be started until the 3rd task is finished.

Given this, you can conclude that the minimum time needed for all the tasks to be completed while respecting the precedence is 11.

This is because you can do tasks 1 and 3 (which take times 10 and 6 respectively) simultaneously, and after task 3 is finished, you can begin on task 2 (which takes 5 units of time). Thus, all tasks will end at time 11.

似乎这可以通过拓扑排序来解决，它可以为您提供完成任务的顺序以满足约束。

例如，在这个问题中，在对任务进行拓扑排序后，你最终会得到

Task 1 (10 Units of time) -> Task 3 (6 Units of time) -> Task 2 (5 Units of time)

但是，一旦您获得了执行任务的顺序，您如何确定哪些可以同时完成，哪些需要一个接一个地完成？此外，您如何计算完成所有这些所需的最短时间？

Answer 1

我假设任务没有循环依赖。因此，任务及其依赖关系可以表示为 有向无环图 (从这里缩写为 dag )，其中任务是顶点，边是 u -> v表示任务 u必须在任务之前完成 v可以开始了。

您的方法在使用拓扑排序来计算任务完成的顺序方面是正确的，因为该图是一个 dag。我看到您有两个主要问题。

计算可能同时完成的任务

计算完成所有任务的最短时间

数字 2 更简单，所以我将首先解决它。一旦计算了拓扑顺序，找出完成所有任务的最短时间并不困难。它本质上是在寻找 dag 中最长的路径 ，您可能在 Critical path method 中听说过它的应用。 .从本质上讲，完成所有任务所需的最短时间是用 完成任务链所需的时间。最长持续时间 .乍一看这似乎违反直觉，但其想法是所有任务的最终完成取决于我们需要完成多长时间 任何 任务链，因此，这取决于完成占用时间最长的任务链所需的时间。

下面是算法的伪代码(我觉得应该是对的，但是因为我有一段时间没有这样做，所以我可能是错的，所以请自行验证):

min_time_for_tasks(Graph, topological order):
    distance <- integer array whose size is number of vertices
    set all entries in visited array to negative infinity
    maxDist <- 0
    for v in topological order:
        if distance[v] == negative infinity:
            maxDist <- max(maxDist, longest_path(Graph, distance, v))
    return maxDist

// computes the longest path from vertex v
longest_path(Graph, distance, v):
    maxDist <- 0
    for all edges (v,w) outgoing from v:
        // vertex w has not been visited
        if distance[w] == negative infinity:
            longest_path(Graph, distance, w)
        // get the longest path among all vertices reachable from v
        maxDist <- max(maxDist, distance[w])
    distance[v] <- maxDist + time to complete task v
    return distance[v]

至于第 1 项，计算可以同时完成的任务，这稍微有点棘手。我以前实际上没有这样做过，但我确实认为可以使用名为 的拓扑排序算法来完成。卡恩算法 (这是维基百科上第一个拓扑排序算法，链接是 here )。我不了解你，但通常我使用深度优先搜索和堆栈来执行拓扑排序，然后从堆栈中弹出顶点以获得顺序。本质上，卡恩算法是一种拓扑排序算法，稍加修改，应该可以解决我们的第一个问题。我以前没有这样做过，所以请再次验证。注释中带有解释的伪代码:

// This is a modified kahn's algorithm.
// Again, the graph is assumed to be a dag, and we first compute
// the number of incoming edges to every vertex, since Kahn's
// algorithm is dependent on this information.
// This function will return an array of sets of tasks which
// can be done at the same time.
// So all tasks in the set in returnArray[0] can be done at the same
// time, all tasks in the set in returnArray[1] can be done at the
// same time, etc. Explanation will be available after the
// pseudocode
compute_simultaneous_tasks(Graph):
    into <- integer array, all entries initialized to 0
    // this function is defined below
    compute_incoming_edges(Graph, into)
    returnArray <- empty array
    VSet <- Set of all vertices in the graph
    while VSet is not empty:
        // retrieve all vertices with no incoming edges
        // this means their prerequisite tasks have been completed,
        // and we can execute that particular task
        headVertices <- all vertices `v` in VSet such that into[v] is 0

        // remove all the vertices in headVertices from VSet
        VSet <- VSet.remove(headVertices)

        // we are going to remove the vertices in headVertices,
        // so the edges outgoing from them will be removed as well.
        for each vertex v in headVertices:
            for each vertex w outgoing from v:
                into[w] <- into[w] - 1

        // all the vertices in headVertices can be started at the
        // same time, since their prerequisite tasks have been
        // completed
        returnArray.append(headVertices)

    return returnArray

// computes the number of edges leading into each vertex
// so into[x] gives the number of edges leading into vertex x
// from some other vertex
compute_incoming_edges(Graph, into):
    for each vertex v in Graph:
        for each vertex w outgoing from v:
            into[w] <- into[w] + 1

所以 compute_simultaneous_tasks函数将返回一组集合。每个集合包含可以同时完成的顶点/任务。为了了解为什么会这样，在 compute_simultaneous_tasks 的主循环中，我们提取所有没有传入边的顶点。这相当于在没有先决条件的情况下提取所有任务。因此，我们可以看到同时执行这组任务是安全的，因为它们没有先决条件，而且肯定不相互依赖!然后，我们移除它们的出边，以模拟它们的完成。然后我们继续循环的下一次迭代，等等。

所以我们看到在 while 的每次迭代中循环，我们正在做我们刚刚描述的事情，因此在 returnArray[0] 中执行所有任务是安全的。同时，所有任务在 returnArray[1]同时 但是 只有在 returnArray[0] 中的所有任务之后已完成， returnArray[2] 中的所有任务在 returnArray[1] 之后完成，等等。

因此，在 Kahn 算法的这一修改中，我们不是一步移除一个具有 0 个传入边的顶点，而是一步移除所有具有 0 个传入边的顶点，以获得所有可以在“波浪”中模拟完成的任务, 与 returnArray[0]正在第 0 波， returnArray[1]是第 1 波，等等。请注意，我们只从波 中删除所有顶点的出边边。后 我们已经提取了所有具有 0 个传入边的顶点。

虽然我无法给出正式的证明，但我确实相信，如果一个人同时完成所有 a wave，那么由于如何考虑依赖关系，一个人将能够在我们上面计算的最短时间内完成所有任务的帐户。

希望有帮助，新年快乐 =)