algorithm - 排序并发任务以最小化等待

Question

在一个有多个并发任务对数据进行操作的系统中，我想对任务进行排序，以使等待时间最少。系统中的每个任务都使用一定的资源集合，任务是按照一定的顺序发出的(这个顺序就是我要计算的)，一个任务只有在获得所有需要的资源的锁后才会开始。任务是顺序发出的，所以第3个任务要等到第2个任务获得所有锁后才会开始，以此类推。

Task 1, Resources [A, B]
Task 2, Resources [B, C]
Task 3, Resources [C, D]
Task 4, Resources [E]

Best Solution
Task 1, [A, B]
Task 3, [C, D] //No waiting is possibly required
Task 4, [E] //Put this before task 3, to maximise the distance between uses of the same resource (minimise chances of lock contention)
Task 2, [B, C] //Some waiting *might* be required here

可以使用什么算法来计算最佳排序，以便在使用资源和再次使用资源之间存在最大差距？

铌。这是与语言无关的，但是在 C# 中实现的加分点

Answer 1

编辑: 给定的目标函数是非线性的，正如 Moron 在 commmets 中指出的那样。因此，这个答案不能不使用。

一种可能的方法是使用线性规划来解决它。这就是我的想法。如果我们在时间 j 开始任务 i，则引入一个设置为 1 的决策变量 T_i_j(我将从 0 到 3 计算任务)。此外，如果它们需要相同的资源，我们希望“惩罚”彼此靠近的调度任务。在给定的示例中，我们希望根据 m 和 n 之间的差异 3 来惩罚 T0_m 和 T1_n。然后我们可以按如下方式对问题进行建模

Minimize:
   3 * T0_0 * T1_1 + 2 * T0_0 * T1_2 + 1 * T0_0 * T1_3
 + 3 * T0_1 * T1_2 + 2 * T0_1 * T1_3
 + 3 * T0_2 * T1_3

 + 3 * T1_0 * T2_1 + 2 * T1_0 * T2_2 + 1 * T1_0 * T2_3
 + 3 * T1_1 * T2_2 + 2 * T1_1 * T2_3
 + 3 * T1_2 * T2_3  

Subject to
// We start a task exactly once.
T0_0 + T0_1 + T0_2 + T0_3 = 1
T1_0 + T1_1 + T1_2 + T1_3 = 1
T2_0 + T2_1 + T2_2 + T2_3 = 1
T3_0 + T3_1 + T3_2 + T3_3 = 1

// We can only start a single task at a given time.
T0_0 + T1_0 + T2_0 + T3_0 = 1
T0_1 + T1_1 + T2_1 + T3_1 = 1
T0_2 + T1_2 + T2_2 + T3_2 = 1
T0_3 + T1_3 + T2_3 + T3_3 = 1

然后我们可以使用 integer programming solver找到启动工作的最佳组合。

上面的模型是用这个(非常糟糕，但应该给你想法)代码生成的

class Program
{
    private static string[][] s_tasks = new string[][]
    {
        new string[] { "A", "B"},
        new string[] { "B", "C"},
        new string[] { "C", "D"},
        new string[] { "E" }
    };

    static void Main(string[] args)
    {
        string filePath = Path.Combine(Environment.GetEnvironmentVariable("USERPROFILE"), @"Desktop\lin_prog.txt");
        using (TextWriter writer = new StreamWriter(filePath, false))
        {
            Console.SetOut(writer);
            Console.WriteLine("Given tasks");
            PrintTasks();
            Console.WriteLine();

            Console.WriteLine("Minimize:");
            PrintObjectiveFunction();
            Console.WriteLine();

            Console.WriteLine("Subject to");
            PrintConstraints();
        }
    }

    static void PrintTasks()
    {
        for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++)
        {
            Console.WriteLine("Task {0}: [ {1} ]", taskCounter, String.Join(", ", s_tasks[taskCounter]));
        }
    }

    static void PrintConstraints()
    {
        Console.WriteLine("// We start a task exactly once.");
        for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++)
        for (int timeCounter = 0; timeCounter < s_tasks.Length; timeCounter++)
        {
            Console.Write("T{0}_{1}", taskCounter, timeCounter);
            if (timeCounter != s_tasks.Length - 1)
            {
                Console.Write(" + ");
            }
            else
            {
                Console.WriteLine(" = 1");
            }
        }

        Console.WriteLine();
        Console.WriteLine("// We can only start a single task at a given time.");
        for (int timeCounter = 0; timeCounter < s_tasks.Length; timeCounter++)
        for (int taskCounter = 0; taskCounter < s_tasks.Length; taskCounter++)
        {
            Console.Write("T{0}_{1}", taskCounter, timeCounter);
            if (taskCounter != s_tasks.Length - 1)
            {
                Console.Write(" + ");
            }
            else
            {
                Console.WriteLine(" = 1");
            }
        }

    }

    static void PrintObjectiveFunction()
    {
        StringBuilder objective = new StringBuilder();
        for (int currentTaskCounter = 0; currentTaskCounter < s_tasks.Length; currentTaskCounter++)
        {
            string[] currentTask = s_tasks[currentTaskCounter];
            for (int otherTaskCounter = currentTaskCounter + 1; otherTaskCounter < s_tasks.Length; otherTaskCounter++)
            {
                string[] otherTask = s_tasks[otherTaskCounter];
                if (ShouldPunish(currentTask, otherTask))
                {
                    int maxPunishment = s_tasks.Length;
                    for (int currentTimeCounter = 0; currentTimeCounter < s_tasks.Length; currentTimeCounter++)
                    {
                        string currentTaskDecisionVar = String.Format("T{0}_{1}", currentTaskCounter, currentTimeCounter);
                        for (int otherTimeCounter = currentTimeCounter + 1; otherTimeCounter < s_tasks.Length; otherTimeCounter++)
                        {
                            string otherTaskDecisionVar = String.Format("T{0}_{1}", otherTaskCounter, otherTimeCounter);
                            // Punish tasks more in objective function if they are close in time when launched.
                            int punishment = maxPunishment - (otherTimeCounter - currentTimeCounter);
                            if (0 != objective.Length)
                            {
                                objective.Append(" + ");
                            }

                            objective.AppendFormat
                            (
                                "{0} * {1} * {2}",
                                punishment, currentTaskDecisionVar, otherTaskDecisionVar
                            );
                        }
                        objective.AppendLine();
                    }
                }
            }
        }

        // Nasty hack to align things.
        Console.Write("   " + objective.ToString());
    }

    static bool ShouldPunish(string[] taskOne, string[] taskTwo)
    {
        bool shouldPunish = false;
        foreach (string task in taskOne)
        {
            // We punish tasks iff. they need some of the same resources.
            if(taskTwo.Contains(task))
            {
                shouldPunish = true;
                break;
            }
        }

        return shouldPunish;
    }
}

注意事项

• 上述代码的运行时间类似于 O(n^5)，其中 n 是任务数。那只是生成模型；整数规划是 NP 完全的。
• 我绝不是手术室专家。我只是为了好玩而试了一下。
• 上述解决方案没有使用问题可能包含的固有约束。我可以很容易地想象一个专门的作业调度算法会表现得更好(尽管我仍然认为这个问题是 NP 完全的)
• 如果我的事实是正确的，即问题是 NP 完全问题，那么使用便宜的启发式算法并快速启动任务可能会更好(除非您可以预先计算解决方案并多次使用) .