How to solve the problem of static balancing?

Question

Algorithms

Suggest an algorithm for solving the following problem.
Given N tasks with their a priori estimates of labor intensity and M parallel computing nodes.
It is required to distribute tasks between nodes so that the total task execution time is minimal, that is, to perform static balancing.

Answer 1

In English, this task is called multiprocessor scheduling . The problem is NP-hard, so don't expect an exact algorithm. Wikipedia suggests a 4/3 approximation: sort all jobs in descending order of length, in the resulting order, assign work to the node that is released first.

Answer 2

The exact solution can be obtained only by exhaustive enumeration, M ^N options. Approximate - by empirical algorithms, for example, greedy .