用“总和”将数字列表划分为更小的列表

我在网格上执行2000次左右的测试，每个测试都作为网格上的单独任务运行。测试确实有相当大的启动时间。总执行时间为500小时，在60个节点SunGridEngine上不到10小时内完成。测试运行时间从5分钟到90分钟不等。在没有太多智能的情况下结合测试可以提高性能。我想创建大小几乎相同的“任务”。我该怎么做？用“总和”将数字列表划分为更小的列表

（我们现在做的：排序的所有测试和不断增加，直到执行时间的总和为约5小时寻找一些东西更好）

来源

2010-01-29 Jayan

你在问什么确切地说？一个算法，将数字列表放入桶中，平衡每个桶中数字的总和？ – 2010-01-29 18:13:24

优化这样做是NP完全问题。这是partition problem的变体，这是subset sum problem的一个特例，它本身就是knapsack problem的特例。

在你的情况下，你可能不需要一个确切的解决方案，所以你可以使用一些启发式方法在合理的时间内获得“足够好”的东西。有关某些方法的说明，请参阅分区问题页面的Methods部分。

来源

2010-01-29 18:14:46

你的问题听起来有点像店铺调度问题。有各种不同的测序方法，其中一些被描述为here。例如，按照处理时间的增加顺序进行排序，可以最大限度地减少平均等待时间和其他一系列措施。如果您详细阐述目标，安装时间，处理时间以及任何相互依赖性都会有所帮助。

来源

2010-01-29 18:14:55 Grembo

你在找什么是k组的分区问题。

有关于k = 3的som文献，称为3分区问题。在强烈的意义上这是NP完整的。

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

我建议你从这里开始：http://en.wikipedia.org/wiki/Partition_problem

希望这有助于。

来源

2010-01-29 18:16:08

这是子集和问题的a version，并且是NP完全的。你最好的选择是雇用一些subset-sum heuristics。

来源

2010-01-29 18:17:25

看着链接劳伦斯张贴我认为我会尝试掀起一些东西了。该算法是将最长的测试分配给最短的任务列表（重复直到所有的测试被分配为止）。使用你的例子和随机测试时间，std偏差非常低，运行几次（用C＃代码，但没有什么不会是微不足道的转换）的2分钟内：

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

    }

来源

2010-01-29 21:12:12 Dolphin

用“总和”将数字列表划分为更小的列表

回答

相关问题