Упаковка бункера: установите количество на бункерах, хотите уменьшить максимальный вес бункера

Question

Учитывая n бункеров бесконечной вместимости, я хочу упаковать в них m элементов (каждый с определенным весом), одновременно минимизируя вес самого тяжелого бункера.

Это не традиционная проблема упаковки / рюкзака, когда емкость имеет конечную емкость, и вы пытаетесь минимизировать количество используемых бункеров;У меня есть определенное количество корзин, и я хочу использовать их все, чтобы максимально уменьшить вес самой тяжелой корзины.

Есть ли название для этой проблемы?Я просмотрел несколько статей с ключевыми словами, но ничего подобного не нашел.

Приветствия.

Answer 1

Если количество бункеров является ограничением, а не емкостью бункеров, то это не упаковка бинов, а многопроцессорное планирование проблема.

Обычно вы можете подойти к этому алгоритму LPT с довольно хорошими результатами. Оптимизация, тем не менее, будет необходима, и именно в этом заключается веселье.

Answer 2

Это форма проблемы упаковки бункера 2D .Первое измерение - это ограничение на емкость на бункер (= жесткое ограничение ), второе измерение - минимизация веса самого тяжелого бункера (= мягкое ограничение ).

С Drools Planner я бы начал с примера облачного баланса и реализовал бы его следующим образом:

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