将数字列表划分为较小的列表,且“总和”大致相同

这样做是NP完全的。这是一个变体的 partition problem subset sum problem ,这本身就是 knapsack problem

在您的情况下,您可能不需要精确的解决方案,因此您可能可以使用一些启发式方法在合理的时间内获得“足够好”的结果。见 Methods 分区问题页面的一部分,介绍一些方法。

你要找的是k集的划分问题。

有许多启发式方法可以快速给出近似结果。

http://en.wikipedia.org/wiki/Partition_problem

希望这有帮助。

这是 a version 是子集和问题的一种,是NP完全的。你最好的办法是雇佣一些人 subset-sum heuristics .

你的问题听起来有点像车间调度问题。有各种不同的测序方法,其中一些已经描述 here . 例如,按处理时间的递增顺序排序将使平均等待时间和一系列其他措施最小化。如果您对目标、设置时间、处理时间以及任何有帮助的相互依赖性进行详细说明。

看着劳伦斯发布的链接,我想我应该试着做点什么。算法是将最长的测试分配给最短的任务列表(重复,直到分配了所有测试)。使用您的示例和随机测试时间,std偏差非常低,运行几次都不到2分钟(用C#编写代码,但转换起来并不容易):

    private static void BuildJobs()
    {
        PriorityQueue<Task> tasks = new PriorityQueue<Task>();

        //create a task list for each node
        for (int i = 0; i < 60; i++)
        {
            Task t = new Task();
            tasks.Enqueue(t);
        }

        //get the list of tests, in order from longest to shortest
        int[] testList = new int[2000];

        for (int i = 0; i < testList.Length; i++)
        {
            testList[i] = random.Next(5, 90);
        }

        Array.Sort<int>(testList);
        Array.Reverse(testList);

        // add the longest running test to the current shortest task list
        foreach (int time in testList)
        {
            Task t = tasks.Dequeue();
            t.addTest(time);
            tasks.Enqueue(t);
        }

        Debug.WriteLine(CalculateStdDev(tasks));

    }