Divida una lista de números en una lista más pequeña con "suma" aproximadamente igual

Question

Ejecuto alrededor de 2000 pruebas en la cuadrícula, cada prueba se ejecuta como una tarea separada en la cuadrícula. Las pruebas tienen bastante tiempo de inicio. La ejecución total demora 500 horas y finaliza en menos de 10 horas en SunGridEngine de 60 nodos. El tiempo de ejecución de las pruebas varía de 5 minutos a 90 minutos. La combinación de pruebas sin mucha inteligencia dio algunos beneficios de rendimiento. Me gustaría crear "tareas" que sean aproximadamente del mismo tamaño. ¿Como lo puedo hacer?

(lo que hacemos ahora:. Clasificación de todas las pruebas y seguir sumando hasta la suma del tiempo de ejecución es de aproximadamente 5 horas en busca de algo mejor)

Answer 1

Hacer esto de manera óptima es NP-completo. Esta es una variación del partition problem, que es un caso especial del subset sum problem, que a su vez es un caso especial del knapsack problem.

En su caso, usted probablemente no necesita una solución exacta, por lo que probablemente puede utilizar algunas heurísticas para conseguir algo "suficientemente bueno" en un plazo razonable de tiempo. Consulte la sección Methods de la página del problema de partición para obtener una descripción de algunos enfoques.

Answer 2

Su problema suena un poco como un problema de programación de la tienda. Hay todo tipo de enfoques de secuenciación diferentes, algunos de los cuales se describen here. Clasificar en orden creciente de tiempo de procesamiento, por ejemplo, minimizará el tiempo medio de espera y un montón de otras medidas. Si elabora un poco más sobre el objetivo, los tiempos de preparación, el tiempo de procesamiento y cualquier interdependencia que pueda ayudar.

Answer 3

Lo que se busca es el problema de reparto para k conjuntos.

Existe literatura som sobre k = 3, llamado el problema 3-partición. Esto es NP completo en el sentido fuerte.

Hay muchas heurística que deben dar un resultado aproximado rápidamente.

Le sugiero que comience aquí: http://en.wikipedia.org/wiki/Partition_problem

Espero que esto ayude.

Answer 4

Esta es a version del problema subconjunto de suma, y ​​es NP-completo. Su mejor opción es emplear algunos subset-sum heuristics.

Answer 5

En cuanto a los enlaces Laurence publicada pensé que iba a tratar de batir algo. El algoritmo es asignar la prueba más larga a la lista de tareas más corta (repita hasta que se hayan asignado todas las pruebas). Usando sus ejemplos y los tiempos de prueba al azar la desviación std era bastante bajo, menos de 2 minutos en el funcionamiento de varias veces (código en C#, pero nada que no sería trivial para convertir):

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

    }