Описание тега bin-packing

Из википедии

В задаче упаковки бункеров объекты разных объемов должны быть упакованы в конечное число бункеров или контейнеров, каждый объемом V, таким образом, чтобы минимизировать количество используемых бункеров. В теории сложности вычислений это комбинаторная NP-трудная задача.

Существует множество вариантов этой задачи, например двухмерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и так далее. У них есть много приложений, таких как наполнение контейнеров, загрузка грузовиков с ограничениями по весу, создание резервных копий файлов на съемных носителях и технологическое сопоставление в конструкции полупроводниковых кристаллов с программируемыми вентильными матрицами. Проблему упаковки бункера также можно рассматривать как частный случай проблемы раскроя. Когда количество ящиков ограничено до 1 и каждый предмет характеризуется как объемом, так и стоимостью, проблема максимизации ценности предметов, которые могут поместиться в корзину, известна как проблема ранца.

Несмотря на то, что задача упаковки контейнеров имеет NP-трудную вычислительную сложность, оптимальные решения для очень больших экземпляров проблемы могут быть получены с помощью сложных алгоритмов. Кроме того, было разработано множество эвристик: например, алгоритм первого соответствия обеспечивает быстрое, но часто неоптимальное решение, включающее размещение каждого предмета в первый контейнер, в который он поместится. Для этого требуется Θ(n log n) времени, где n - количество элементов, которые нужно упаковать. Алгоритм можно сделать намного более эффективным, сначала отсортировав список элементов в порядке убывания (иногда известный как алгоритм уменьшения первого соответствия), хотя это все еще не гарантирует оптимального решения, а для более длинных списков может увеличиться время работы алгоритм. Однако известно, что всегда существует по крайней мере одно упорядочивание позиций, которое позволяет первому подходить для получения оптимального решения. 1

Интересный вариант упаковки в контейнеры, который встречается на практике, - это когда предметы могут разделять пространство при упаковке в корзину. В частности, набор элементов может занимать меньше места при упаковке, чем сумма их индивидуальных размеров. Этот вариант известен как упаковка виртуальных машин [2], поскольку, когда виртуальные машины (ВМ) упаковываются на сервере, их общая потребность в памяти может уменьшаться из-за страниц, совместно используемых виртуальными машинами, которые необходимо сохранить только один раз. Если предметы могут разделять пространство произвольным образом, проблему упаковки мусора трудно даже приблизить. Однако, если совместное использование пространства укладывается в иерархию, как в случае с разделением памяти в виртуальных машинах, проблема упаковки ячеек может быть эффективно аппроксимирована.

1. Льюис, Р. (2009), "Универсальный метод восхождения на холм для задач независимой от порядка минимальной группировки: тематическое исследование в раскраске графа и упаковке бункеров", Computers and Operations Research 36 (7): 2295–2310, doi:10.1016/j.cor.2008.09.004
2. Синделар, Майкл; Ситараман, Рамеш; Шеной, Прашант (2011), "Совместное использование алгоритмов для размещения виртуальных машин", Труды 23-го симпозиума ACM по параллелизму в алгоритмах и архитектурах (SPAA), Сан-Хосе, Калифорния, июнь 2011: 367–378