活动的最佳执行

Question

假设我有

的活动或任务

应该都执行了。
没有预定时间，但有些活动比其他活动花费的时间更长
不受 CPU 约束，并受到 network/IO 延迟和瞬态错误的影响
对他人有依赖性；在下面的示例中 C 只能执行一次 A 并且 B 已完成。

用于安排活动以最小化完成所有任务的总时间的最合适算法是什么？我当前的方法不是最佳方法，因为（在下面的示例中）G 的调度方式会额外增加 20 秒的执行延迟。 this question 的答案让我走上了现在的道路。

这是一个示例（如果它是 DSL）

Task A
{
    Estimation: 10s;
}

Task B
{
    Estimation: 10s;
}

Task C
{
    Estimation: 10s;
    DependsOn A, B;
}

Task D
{
    Estimation: 10s;
    DependsOn C;
}

Task E
{
    Estimation: 10s;
    DependsOn C;
}

Task F
{
    Estimation: 10s;
    DependsOn E, D;
}

Task G
{
    Estimation: 30s;
    DependsOn A, B;
}

这是我所做的（在 C# 中）

创建了活动图（有向无环图）。

以下代码片段来自 TaskManager class。

private static Graph<ITask> CreateGraph(IEnumerable<ITask> tasks)
{
    if (tasks == null)
        throw new ArgumentNullException(nameof(tasks));

    var nameMap = tasks.ToDictionary(task => task.Id);
    var graph = new Graph<ITask>(nameMap.Values);
    foreach (var task in nameMap.Values)
    {
        foreach (var depdendantTaskName in task.DependsOn)
        {
            var from = nameMap[depdendantTaskName];
            var to = task;
            graph.AddDependency(from, to);
        }
    }
    return graph;
}

执行拓扑排序

public static Node<T>[] Sort<T>(this Graph<T> graph) where T : IComparable
{
    var stack = new Stack<Node<T>>();
    var visited = new HashSet<Node<T>>();

    foreach (var node in graph)
    {
        if (!visited.Contains(node))
        {
            visited.Add(node);
            InternalSort(node, stack, visited);
        }
    }
    return stack.ToArray();
}

private static void InternalSort<T>(Node<T> node, Stack<Node<T>> stack, ISet<Node<T>> visited)
    where T : IComparable
{
    var dependants = node.Dependants;
    foreach (var dependant in dependants)
    {
        if (!visited.Contains(dependant))
        {
            visited.Add(dependant);
            InternalSort(dependant, stack, visited);
        }
    }
    stack.Push(node);
}

这给了我类似 [F,E,D,C,G,B,A] 的东西。如果我使用 dependencies 而不是 dependents，它应该是 [A,B,C,G,D,E,F]。

为每个节点分配一个级别

现在我有了一个排序节点数组，接下来是更新每个节点的级别属性。

public static void Level<T>(this IEnumerable<Node<T>> nodes) where T : IComparable
{
    foreach (var sortedTask in nodes)
    {
        sortedTask.Level = CalculateLevel(sortedTask.Dependencies);
    }
}

public static int CalculateLevel<T>(ICollection<Node<T>> nodes) where T : IComparable
{
    if (nodes.Count <= 0) return 1;
    return nodes.Max(n => n.Level) + 1;
}

这给了我类似 [F:1,G:1,E:2,D:2,C:3,B:4,A:4] 的东西，其中字母是 activity 名称数字是级别。如果我反过来这样做，它看起来会像 [F:4,E:3,D:3,G:2,C:2,B:1,A:1].

组任务

public static SortedDictionary<int, ISet<T>> Group<T>(this IEnumerable<Node<T>> nodes) where T : IComparable
{
    var taskGroups = new SortedDictionary<int, ISet<T>>();
    foreach (var sortedNode in nodes)
    {
        var key = sortedNode.Level;
        if (!taskGroups.ContainsKey(key))
        {
            taskGroups[key] = new SortedSet<T>();
        }
        taskGroups[key].Add(sortedNode.Value);
    }
    return taskGroups;
}

执行任务

以下遍历每个 "level" 并执行任务。

private async Task ExecuteAsync(IDictionary<int, ISet<ITask>> groups, ITaskContext context,
    CancellationToken cancellationToken)
{
    var keys = groups.Keys.OrderByDescending(i => i);
    foreach (var key in keys)
    {
        var tasks = groups[key];
        await Task.WhenAll(tasks.Select(task => task.ExecuteAsync(context, cancellationToken)));   
    }
}

如果任务从最依赖节点到最不依赖节点排序（F 首先，A 或 B 最后），OrderByDescending 是必需的

问题

虽然这种方法仍然比顺序方法执行得更快，但无论我如何处理它，总有一些事情在等待 G 完成。如果 G 与 C 分组，那么 D 和 E 将延迟 20 秒，即使它们不依赖于 G。

如果我反转排序（并调整代码），G 仅在 F 开始执行时才开始执行。

Answer 1

既然你说（在评论中）可以同时执行的任务数量没有限制，那么有一个简单的解决方案：

为每个任务 i.

taskState[i] = UNSTARTED

对于每个没有剩余依赖项（即空 DependsOn 列表）且尚未启动（即 taskState[i] == UNSTARTED）的任务 i（请注意，有时可能没有此类任务):
- 开始任务。
- 设置taskState[i] = RUNNING.
如果当前没有任务运行则停止 - 您已经完成所有任务，或者存在循环依赖。（你可以通过检查是否有任何任务 i 满足 taskState[i] == UNSTARTED。）
等待任何运行任务完成。让这成为任务 i.
设置taskState[i] = FINISHED.
遍历所有尚未开始的任务，如果任务 i 存在，则从每个此类任务的 DependsOn 列表中删除任务 i。
转到 2.

活动的最佳执行

Optimal Execution of Activities

c#

algorithm

directed-acyclic-graphs