How can I make the variance of a multiple sum of set of fixed number of variables minimum? Here is the problem:
There are $MN$ people, where there are $M&gt;1$ seeds and $N&gt;0$ people are in each seed.
We have to make $N$ teams of $M$ people where everyone in the team have different seeds.
Each person have their own value; values are positive integers.
Assume there are no two people with same values.
For two distinct seeds $I$ and $J$, we say $I&lt;J$ if for all $x\in I$ and $y\in J$, $x&lt;y$ holds.
It is guaranteed that for any two distinct seeds $I$ and $J$ in the problem, $I&lt;J$ or $J&lt;I$ holds. In other words, we can set $M$ seeds $I_1,I_2,\cdots,I_M$ in the problem to satisfy $I_1&lt;I_2&lt;\cdots&lt;I_M$.
I am interested in two versions of this problem:

There are no paired people. This means in process of making $N$ teams, there is no restriction except given above.
There may be some paired people. This means a set of paired people that cannot be split is given, so that if a team contains one person from some pair, the team should also contain the other person from that pair. It is provided that every pair contains exactly two people from different seeds.

For each version, the task is to design an algorithm to make the variance of the sum of values of people in each team to be minimum.
Since this problem is NP (complete?), I would accept heuristics.
I hope that the heuristic method gives the solution with variance at most $25\%$ larger than the optimal solution, as I don't want to harm the balance of the team.
Could you please give an algorithm or heuristic that can solve this problem? Also, adding a time complexity would be highly appreciated!
If you're willing to replace 'variance' with 'max minus min' (spread), then you could formulate this as an instance of integer linear programming and apply an off-the-shelf ILP solver.  There is no guarantee that it finds an optimal solution in a reasonable amount of time, but if you're lucky, it might complete without taking too long; or if you stop it early, you might get a decent solution.
To formulate this as an instance of ILP, add zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means that person $i$ is assigned to team $j$.  Each requirement in the problem statement can be expressed as a linear inequality; for instance, the requirement that everyone in a team has a different can be expressed by inequalities of the form $x_{i,j} + x_{i',j} \le 1$ for each pair $i,i'$ of people from the same seed.
To minimize the spread, introduce variables $\ell,u$.  Let $v_i$ denote the value of person $i$ (this is a constant, not a variable).  Add linear inequalities $\ell \le \sum_i x_{i,j} v_i \le u$ for each team $j$.  Finally, minimize $u-\ell$, subject to the inequalities above.
If you want to use the variance, this becomes a mixed-integer quadratic program instead of a mixed-integer linear program, and I think quadratic programs are significantly harder.