ビンパッキング：ビンに設定された量は、

Question

は無限の容量のNビンを考えると、最大のビンの重みを最小限にしたい、私は重量を最小限に抑えながら、彼ら（特定の重量と各）へメートルアイテムをパックしたいです最も重いビン。

これは、ビンが有限の容量を持ち、使用されるビンの量を最小限にしようとする伝統的なビンのパッキング/ナップザックの問題ではありません。私は一定量のビンを持っていて、最も重いビンの重量をできるだけ少なくするためにそれらをすべて使いたいと思う。

この問題の名前はありますか？私はキーワードを使っていくつかの論文を見てきましたが、私は何も似たものを見つけませんでした。

乾杯。

Answer 1

2Dビン詰め問題です。第一次元ビン（= ハード制約）当たり容量に制限され、第二次元はに重いビン（= ソフト制約）の重量を最小にすることです。 Drools Plannerで

、私はthe cloud balance exampleから開始し、このようにそれを実装するD」：

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

ビンの量ではなく、ビンの容量の制約であれば、それはそれはだ、ビンパッキングではありませんmultiprocessor scheduling問題です。

通常、これはかなり良い結果を得てLPTアルゴリズムによってこれに近づくことができます。しかし、最適化が必要になるでしょう。それが楽しいところです。