活动的最佳执行

假设我有活动或任务

1. 应该全部执行。
2. 没有预定的时间，但有些活动需要比其他活动更长的时间
3. 不受CPU限制，受网络/IO延迟和瞬态错误的影响
4. 依赖于其他li;在下面的示例中，C只能在A和B完成后执行。

用来安排活动以最小化完成所有任务的总时间的最合适的算法是什么?我目前的方法不是最优的，因为(在下面的例子中)G的调度方式给执行增加了20秒的额外延迟。这个问题的答案让我走上了我现在的道路。

这里有一个例子(如果是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类。

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]。如果我用的是依赖项，而不是依赖项，就会是[A,B,C,G,D,E,F]。

Assign a Level to Each Node

现在我有一个排序节点的数组，下一步是更新每个节点的level属性。

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]的东西，其中字母是活动名称，数字是级别。如果我反过来做，它看起来会像[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;
}

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)));   
    }
}