2 added possible local search approach

The problem is NP-complete, because it contains the problems Partition and 3-Partition (problems 41 and 46 in http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html). If your instances are not extremely huge, I would give an integer programming formulation a try. The heuristics build into modern solvers will probably be competitive (and come without any implementation work on your side).

For a heuristic, local search seems to be a natural approach. After greedily generating a start solution you can repeat the following steps.

• pick blocks $A$ and $B$ with maximal weight difference $w(A)-w(B)$
• find subsets $A'\subseteq A$ and $B'\subseteq B$ such that $|w((A\setminus A')\cup B')-w((B\setminus B')\cup A')|<w(A)-w(B)$
• replace $A$ by $(A\setminus A')\cup B'$ and $B$ by $(B\setminus B')\cup A'$

To spice it up a bit one could GRASP it (see http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_procedure ). That just means that the greedy generation of the start solution is randomized: instead of adding the heaviest object to the lightest block, an object, randomly chosen from the $k_1$ heaviest is added to a block randomly chosen from the $k_2$ lightest. Then you start the local search, and when that becomes boring, you just generate a new randomized greedy start solution. This procedure is iterated very often with varying $(k_1,k_2)$, and one can keep track of which parameters $(k_1,k_2)$ tend to lead to good solutions.

1

The problem is NP-complete, because it contains the problems Partition and 3-Partition (problems 41 and 46 in http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html). If your instances are not extremely huge, I would give an integer programming formulation a try. The heuristics build into modern solvers will probably be competitive (and come without any implementation work on your side).