用「總和」將數字列表劃分爲更小的列表

我在網格上執行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

用「總和」將數字列表劃分爲更小的列表

回答

相關問題