Разделите список чисел на меньший список с «суммой» примерно такой же

Question

Я выполняю около 2000 тестов на сетке, каждый тест выполняется как отдельная задача на сетке. Тесты имеют довольно большое время запуска. Общее выполнение занимает 500 часов, заканчивается менее чем за 10 часов на 60 узле SunGridEngine. Время выполнения тестов варьируется от 5 минут до 90 минут. Объединение тестов без особого интеллекта дало некоторый прирост производительности. Я хотел бы создать «задачи» примерно одинакового размера. Как я могу это сделать?

(что мы делаем сейчас: сортировка всех тестов и добавление до суммирования времени выполнения приблизительно 5 часов. Ищем что-то лучше)

Answer 1

Это оптимально для NP-завершения. Это разновидность проблемы разбиения , которая является частным случаем проблемы суммы подмножеств , которая сама по себе является частным случаем проблемы ранца .

В вашем случае вам, вероятно, не нужно точное решение, поэтому вы можете использовать некоторые эвристические методы, чтобы получить что-то "достаточно хорошее" за разумное время. См. Methods раздел проблемной страницы раздела для описания некоторых подходов.

Answer 2

Это версия задачи о сумме подмножеств и NP-полная. Лучше всего использовать некоторую эвристику с подмножеством .

Answer 3

Что вы ищете, так это проблема разбиения для k множеств.

Существует некоторая литература о k = 3, называемая проблемой трех разделов. Это полный NP в сильном смысле.

Есть много эвристик, которые должны быстро дать приблизительный результат.

Я предлагаю вам начать здесь: http://en.wikipedia.org/wiki/Partition_problem

Надеюсь, это поможет.

Answer 4

Ваша проблема немного похожа на проблему с расписанием магазинов. Существуют все виды различных подходов к секвенированию, некоторые из которых описаны здесь . Например, сортировка по возрастанию времени обработки сведет к минимуму среднее время ожидания и целый ряд других мер. Если вы уточните немного о цели, времени установки, времени обработки и любой взаимозависимости, которая может помочь.

Answer 5

Просматривая ссылки, опубликованные Лоуренсом, я подумал, что попытаюсь что-то поднять. Алгоритм состоит в том, чтобы назначить самый длинный тест кратчайшему списку задач (повторять, пока не будут назначены все тесты). Используя ваши примеры и случайное время тестирования, стандартное отклонение было довольно низким, менее 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));

    }