Given a list of N non-negative real numbers:
t = [2.99, 7.9, 24.58, ..., 3.1415, 40.4]
I want to partition the elements of $t$ into $M$ groups, $g_1$, $g_2$, ..., $g_M$, so that the sum of each group is as close as possible to $sum(t)/M$, i.e. minimizing the root mean square error:
Minimize: $\sqrt{\Sigma_i^M (sum(g_i) - sum(t)/M)^2 }$.
Do anyone know a close-to-optimal algorithm of doing this generally? Or do anyone know the name of this problem? (My google-fu failed me).
Background: $t$ represents time in seconds to run $N$ different tasks, and I want to schedule the $N$ tasks on $M$ different computers in such a way that all computers finish their tasks at the same time (or as close as possible).
Let $ M \leq N $. I try to reply to your question in terms of a problem of optimization attributable to a Boolean linear programming problem. You need $ m \cdot n $ Boolean variables to trace the assignment of task to computer: $ x_{i,j} $ is a Boolean variable whose value is 1 if i-th task is assigned to j-th computer, zero otherwise.
The objective function can be properly formulated as
$ \min \sum_{j,k=1}^m | g_j – g_k | $
where $ |.| $ is the absolute value.
Constraints:
$\left\{ \begin{array}{l} \sum_{j=1}^m x_{i,j} = 1 \forall i=1, \cdots , n \\ x_{ij} \in \left \{ 0 ; 1 \right \} \forall i,j \\ \end{array} \right. $
where
$ g_j = \sum_{i,j=1}^n t_i \cdot x_{i,j} $ is the service time for j-th computer
$ \sum_{j=1}^m x_{i,j} = 1 $ requires that i-th task is assigned to one and only one computer
$ x_{i,j} $ is a Boolean variable whose value is 1 if i-th task is assigned to j-th computer, 0 otherwise.
By means of $z_1, \cdots , z_m$ real variables, the problem can be formulated as a linear programming model.
$ \min \sum_{j=1}^m z_j $
subject to
$\left\{ \begin{array}{l} \sum_{j=1}^m x_{i,j} = 1 \forall i=1, \cdots , n \\ g_j – g_k \leq z_j \forall j,k=1, \cdots , m \\ g_j – g_k \geq - z_j \forall j,k=1, \cdots , m \\ x_{ij} \in \left \{ 0 ; 1 \right \} \forall i,j \\ \end{array} \right. $