algoritmo - dijkstra java github

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: ordenar todas las pruebas y seguir sumando hasta que la suma del tiempo de ejecución sea de aproximadamente 5 horas. Buscando algo mejor)

Answer 1

Esta es una versión del problema de suma de subconjuntos, y es NP-completa. Su mejor opción es emplear algunas heurísticas de suma de subconjuntos .

Answer 2

Haciendo esto de manera óptima es NP-completo. Esta es una variación del problema de partición , que es un caso especial del problema de la suma de subconjuntos , que a su vez es un caso especial del problema de la mochila .

En su caso, es probable que no necesite una solución exacta, por lo que probablemente pueda utilizar algunas heurísticas para obtener algo "lo suficientemente bueno" en un tiempo razonable. Consulte la sección Métodos de la página del problema de partición para obtener una descripción de algunos enfoques.

Answer 3

Lo que está buscando es el problema de Partición para k conjuntos.

Hay un poco de literatura sobre k = 3, llamada problema de 3 divisiones. Esto es NP completo en el sentido fuerte.

Hay muchas heurísticas que deberían dar un resultado aproximado rápidamente.

Te sugiero que comiences aquí: http://en.wikipedia.org/wiki/Partition_problem

Espero que esto ayude.

Answer 4

Mirando los enlaces que Laurence colgó, pensé que trataría de inventar 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 tiempos de prueba aleatorios, la desviación estándar fue bastante baja, menos de 2 minutos en ejecutarla varias veces (código en C #, pero nada que no sea trivial de 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));

    }

Answer 5

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 aquí . 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.