Как решить задачу на статическую балансировку?

Question

[Alex Serov]

Подскажите алгоритм решения следующей задачи.
Дано N задач с их априорными оценками трудоёмкости и M параллельно работающих вычислительных узлов.
Требуется распределить задачи между узлами так, чтобы суммарное время выполнения задач было минимальным, то есть произвести статическую балансировку.

Answer 1

[SeptiM]

На английском эта задача называется multiprocessor scheduling. Задача NP-трудная, так что точного алгоритма не ждите. В википедии предлагают 4/3 приближение: отсортировать все работы в порядке убывания длины, в полученном порядке назначать работу узлу, который освобождается раньше всех.

Answer 2

[Rsa97]

Точное решение можно получить только полным перебором, M^N вариантов. Приближённое - эмпирическими алгоритмами, например жадным.