빈 포장 : 쓰레기통에 설정 금액,

Question

무한 용량의 N 쓰레기통을 감안할 때 최대 빈 무게를 최소화하려면, 난의 무게를 최소화하면서, 그들 (특정 무게 각)에 미터 항목을 포장 할 가장 무거운 빈.

이것은 bin이 제한된 용량을 가지고 있고 사용 된 bin의 양을 최소화하려고 시도하는 전통적인 bin packing/napsack 문제는 아닙니다. 나는 일정량의 쓰레기통을 가지고 있으며 가능한 한 가장 무거운 쓰레기통의 무게를 줄이기 위해 그것들을 모두 사용하기를 원합니다.

이 문제의 이름이 있습니까? 몇 가지 핵심 단어로 된 논문을 살펴 보았지만 비슷한 점은 발견하지 못했습니다.

건배.

Answer 1

2D 빈 포장 문제입니다. 첫번째 차원은 빈 (= 하드 제약) 당 용량에 한계가 제 치수 에게 무거운 빈 (= 소프트 제약)의 무게를 최소화하는 것이다. Drools Planner와

, 나는 the cloud balance example에서 시작하고 이런 식으로 구현 거라고 :

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

빈의 양이 대신 빈의 용량의 제약 조건이면, 그것은 그것의, 큰 상자 포장이 아니다 a multiprocessor scheduling 문제입니다.

일반적으로 LPT 알고리즘을 사용하면 꽤 좋은 결과를 얻을 수 있습니다. 최적화가 필요하지만 재미가있는 부분입니다.