У этого варианта упаковки бина есть имя?
У меня есть то, что звучит как типичная проблема упаковки бункера: x продукты разных размеров должны быть упакованы в y контейнеры различной емкости, минимизируя количество используемых контейнеров, а также минимизируя потерянное пространство.
Я могу упростить проблему в том, что размеры продукта и вместимость контейнера могут быть уменьшены до стандартных одномерных единиц. т. е. этот продукт на 1 единицу больше, в то время как этот - 3 единицы, в этой коробке - 6 единиц, то есть 12. Подумайте о яйцах и коробках или ящиках пива.
Но есть дополнительное ограничение: у каждого контейнера есть определенный атрибут (назовем его цветом), и у каждого продукта есть набор цветов, с которыми он совместим. Нет корреляции между цветом и размерами продукта / контейнера; Один продукт может быть совместим по цвету со всей палитрой, другой может быть совместим только с красными контейнерами.
Этот вариант проблемы уже описан в литературе? Если так, как его зовут?
2 ответа
Я думаю, что нет особого названия для этого варианта. Хотя ограничение на цвет сначала создает впечатление, что это связано с окраской графа, это не так. Это просто ограничение значений для переменной.
В типичной реализации решателя каждый продукт (= item) будет иметь переменную, которой он назначен. Цветовые ограничения просто уменьшают диапазон значений для определенной переменной. Поэтому вместо указания того, что все переменные используют один и тот же диапазон значений, сделайте его специфичным для переменной. (Например, в OptaPlanner это разница между диапазоном значений, предоставляемым решением в целом или объектом в частности.) Таким образом, ограничение окраски даже не должно быть ограничением: оно может быть частью модели в большинстве решателей,
Любой решатель, способный справиться с упаковкой бункера, должен уметь работать с этим вариантом. Ваша проблема на самом деле ослабляет проблему переназначения машин Roadef 2012, которая касается назначения процессов компьютерам. Просто удалите все ограничения, за исключением 1 ограничения использования ресурса и ограничения, которое исключает определенные процессы для определенных машин. Этот вариант использования реализован во многих решателях. (Хотя на практике, вероятно, легче начать с базового примера упаковки бина, такого как Cloud Balancing.)
Скорее всего, проблема с упаковкой в 2d или классическим ранцем.