algorithm - 将 "parallelism"引入一个任务调度问题

Question

qoutes 中的并行性，因为我实际上并不是指并行编程(线程/ fork 等)

目前正在研究一个依赖图问题，给定一个 DAG(有向无环图)，其中每个顶点代表一个必须完成的任务，以及从一个顶点 v 到另一个顶点的边 u 表示 v 必须在 u 完成之前完成。每个任务都需要一定的时间才能完成。

例子: dependency graph

(这只是一个例子，程序应该能够解决任何 DAG)

如果一次完成一项任务，我发现使用拓扑排序可以完成所有任务的多个顺序。但是，我有兴趣介绍可以同时启动和/或处理多个任务的想法。我假设无限的“人力”，这意味着可以同时处理任意数量的任务。我想找到一种方法，在尽可能快的时间内完成项目中的所有任务。

我的任务(顶点)类有以下变量(Java):

class Task{
    int id, time;
    String name;
    List<Task> outEdges;
    List<Task> inEdges;
    boolean isFinished;
    Task(int id, String name, int time){
        this.id = id;
        this.name = name;
        this.time = time;
        isFinished = false;
        outEdges = new ArrayList<Task>();
        inEdges = new ArrayList<Task>();
//Tasks and edges between them are generated while reading from a file.
    }
      ...
}

(以及获取/操作它们的方法)该图本身由一组任务表示。

我可以使用哪些概念/算法来做到这一点？

Answer 1

假设你的意思是如果你的图中有一条从v到u的弧，那么v必须在之前完成u 可以启动了。

这只是简单地寻找最短的项目完成时间，当您将图形视为项目优先级图时。给定事件时间为 dj >= 0 的节点 j(任务)，让 sj 表示其开始时间。

那么，下面的线性程序解决了你的问题

Minimize  sN [i.e., minimize the starting time of the last activity]
such that sj >= si + di , forall (i,j) in graph [i.e., ensure starting time of jth activity is after completion of ith activity if j follows i in the precedence graph]
such that all si's >= 0 [i.e., all starting times are nonnegative. Without these constraints, problem is unbounded.]

这里为方便起见，1和N分别为项目开始和结束的虚拟事件，事件次数为0。 1 在图中的所有其他节点之前。 N 落后于图中所有其他节点。