Bin Packing: Set amount on bins, want to minimize the max bin weight

Question

Given n bins of infinite capacity, I want to pack m items into them (each with a specific weight), whilst minimizing the weight of the heaviest bin.

This isn't a traditional bin packing / knapsack problem where a bin has a finite capacity and you attempt to minimize the amount of bins used; I have a set amount of bins and want to use them all in order to make the heaviest bin's weight as low as possible.

Is there a name for this problem? I have looked through a number of papers with key words, but I have found nothing similar.

Cheers.

Answer 1

It's a form of a 2D bin packing problem. The first dimension is a limit on capacity per bin (= hard constraint), the second dimension is to minimize the weight of the heaviest bin (= soft constraint).

With Drools Planner, I 'd start from the cloud balance example and implement it like this:

rule "maxCapacity"
  when
    // When there is a bin ...
    $bin : Bin($binCapacity : binCapacity)
    // ... where the total of the item capacity is bigger than the bin capacity ...
    $itemCapacityTotal : Number(intValue > $binCapacity) from accumulate(
        ItemAssignment(
            bin == $bin,
            $itemCapacity : itemCapacity),
        sum($itemCapacity)
    )
  then
    // ... then lower the hard score with the insufficient capacity
    insertLogical(new IntConstraintOccurrence("maxCapacity",
            ConstraintType.NEGATIVE_HARD,
            $itemCapacityTotal.intValue() - $binCapacity,
            $bin));
end


rule "calculateWeight"
  when
    $bin : Bin()
    $itemWeightTotal : Number() from accumulate(
        ItemAssignment(
            bin == $bin,
            $itemWeight : itemWeight),
        sum($itemWeight)
    )
  then
    insertLogical(new BinToWeight($bin, $itemWeightTotal);
end
rule "minimizeWeight"
  when
    BinToWeight($bin : bin, $itemWeightTotal : itemWeightTotal)
    not BinToWeight (itemWeightTotal > $itemWeightTotal,  bin != $bin)
  then
    insertLogical(new IntConstraintOccurrence("minimizeWeight",
            ConstraintType.NEGATIVE_SOFT,
            $itemWeightTotal,
            $bin));
end

Answer 2

If the amount of bins is the constraint, instead of the capacity of bins, then it's not a bin packing, it's a multiprocessor scheduling problem.

Usually, you can approach this by a LPT algorithm with pretty good results. Optimizations will be needed though and that's where the fun lies.