Bin Emballage: montant mis sur les bacs, veulent réduire le poids bin max

Question

Étant donné n bacs de capacité infinie, je veux emballer m articles en eux (chacun avec un poids spécifique), tout en minimisant le poids de la poubelle la plus lourde.

Ce n'est pas un problème traditionnel d'emballage/sac à dos où une poubelle a une capacité limitée et vous essayez de minimiser la quantité de bacs utilisée; J'ai un certain nombre de bacs et je veux les utiliser tous pour que le poids de la poubelle soit le plus bas possible.

Y a-t-il un nom pour ce problème? J'ai parcouru un certain nombre d'articles avec des mots clés, mais je n'ai rien trouvé de similaire.

Cheers.

Answer 1

Il est une forme d'un problème d'emballage bin 2D. La première dimension est une limite de la capacité par bac (= de contrainte dure), la seconde dimension est de minimiser le poids de le plus lourd bin (= de contrainte souple).

Avec Drools Planner, je « d commencer par the cloud balance example et mettent en place comme ceci:

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

Si la quantité de bacs est la contrainte, au lieu de la capacité des bacs, il est pas un emballage de bac, il est un problème multiprocessor scheduling.

Habituellement, vous pouvez approcher cela par un algorithme LPT avec de très bons résultats. Des optimisations seront nécessaires cependant et c'est là que le plaisir réside.