Проблема упаковки в мусорные баки

Математическая и вычислительная задача

Задача упаковки контейнеров ^{[1] [2] [3] [4]} — это задача оптимизации , в которой предметы разных размеров должны быть упакованы в конечное число контейнеров или ячеек, каждая из которых имеет фиксированную заданную вместимость, таким образом, чтобы минимизировать количество используемых ячеек. Задача имеет множество приложений, таких как заполнение контейнеров, загрузка грузовиков с ограничениями по грузоподъемности, создание резервных копий файлов на носителях, разделение сетевого префикса на несколько подсетей ^[5] и технологическое отображение в проектировании полупроводниковых чипов FPGA .

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

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

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

Другой вариант упаковки контейнеров, представляющий интерес на практике, — это так называемая онлайн- упаковка контейнеров. Здесь предполагается, что предметы разного объема поступают последовательно, и принимающий решение должен решить, выбрать ли и упаковать текущий наблюдаемый предмет или пропустить его. Каждое решение принимается без отзыва. Напротив, офлайн-упаковка контейнеров позволяет переупорядочивать предметы в надежде добиться лучшей упаковки, когда поступят дополнительные предметы. Это, конечно, требует дополнительного хранилища для хранения предметов, которые нужно переупорядочить.

Официальное заявление

В книге «Компьютеры и неразрешимость» ^{[8] : 226} Гари и Джонсон перечисляют задачу упаковки контейнеров под ссылкой [SR1]. Они определяют ее вариант решения следующим образом.

Экземпляр: Конечный набор элементов, размер каждого элемента , вместимость контейнера — положительное целое число , а также положительное целое число . ${\displaystyle I}$ ${\displaystyle s(i)\in \mathbb {Z} ^{+}}$ ${\displaystyle i\in I}$ ${\displaystyle B}$ ${\displaystyle K}$

Вопрос: Существует ли разбиение на непересекающиеся множества такое, что сумма размеров элементов в каждом из них равна или меньше? ${\displaystyle I}$ ${\displaystyle I_{1},\dots ,I_{K}}$ ${\displaystyle I_{j}}$ ${\displaystyle B}$

Обратите внимание, что в литературе часто используется эквивалентная запись, где и для каждого . Кроме того, исследования в основном интересуются вариантом оптимизации, который требует наименьшего возможного значения . Решение является оптимальным, если оно имеет минимальное . Значение - для оптимального решения для набора элементов обозначается или просто, если набор элементов ясен из контекста. ${\displaystyle B=1}$ ${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$ ${\displaystyle i\in I}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle I}$ ${\displaystyle \mathrm {OPT} (I)}$ ${\displaystyle \mathrm {OPT} }$

Возможная формулировка задачи целочисленного линейного программирования имеет вид:

где, если используется корзина и если предмет помещается в корзину . ^[9] ${\displaystyle y_{j}=1}$ ${\displaystyle j}$ ${\displaystyle x_{ij}=1}$ ${\displaystyle i}$ ${\displaystyle j}$

Твердость упаковки контейнера

Задача упаковки контейнеров является строго NP-полной . Это можно доказать, сведя строго NP-полную задачу 3-разбиения к задаче упаковки контейнеров. ^[8]

Более того, не может быть алгоритма приближения с абсолютным отношением приближения меньшим, чем , если только . Это можно доказать с помощью сокращения из проблемы разбиения : ^[10] учитывая экземпляр разбиения, где сумма всех входных чисел равна , построить экземпляр упаковки контейнеров, в котором размер контейнера равен T . Если существует равное разбиение входных данных, то для оптимальной упаковки требуется 2 контейнера; следовательно, каждый алгоритм с отношением приближения меньшим, чем ⁠ ${\displaystyle {\tfrac {3}{2}}}$ ${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$ ${\displaystyle 2T}$3/2⁠ должен вернуть менее 3 корзин, что должно быть 2 корзинами. Напротив, если нет равного разделения входов, то для оптимальной упаковки требуется не менее 3 корзин.

С другой стороны, упаковка контейнеров разрешима за псевдополиномиальное время для любого фиксированного числа контейнеров K и разрешима за полиномиальное время для любой фиксированной емкости контейнера B. ^[8 ]

Алгоритмы аппроксимации для упаковки в контейнеры

Для измерения производительности алгоритма аппроксимации в литературе рассматриваются два коэффициента аппроксимации. Для заданного списка элементов число обозначает количество ячеек, используемых при применении алгоритма к списку , а обозначает оптимальное число для этого списка. Абсолютный коэффициент производительности в худшем случае для алгоритма определяется как ${\displaystyle L}$ ${\displaystyle A(L)}$ ${\displaystyle A}$ ${\displaystyle L}$ ${\displaystyle \mathrm {OPT} (L)}$ ${\displaystyle R_{A}}$ ${\displaystyle A}$

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L\}.}$

С другой стороны, асимптотическое наихудшее отношение определяется как ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ for all lists }}L{\text{ with }}\mathrm {OPT} (L)\geq N\}.}$

Эквивалентно, является ли наименьшим числом, таким что существует некоторая константа K, такая, что для всех списков L: ^[4] ${\displaystyle R_{A}^{\infty }}$

${\displaystyle A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K}$.

Кроме того, можно ограничить списки теми, у которых все элементы имеют размер не более . Для таких списков коэффициенты производительности ограниченного размера обозначаются как и . ${\displaystyle \alpha }$ ${\displaystyle R_{A}({\text{size}}\leq \alpha )}$ ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )}$

Алгоритмы аппроксимации для упаковки в контейнеры можно разделить на две категории:

1. Онлайн эвристики, которые рассматривают элементы в заданном порядке и помещают их один за другим в контейнеры. Эти эвристики также применимы к офлайн версии этой проблемы.
2. Офлайновые эвристики, которые изменяют заданный список элементов, например, сортируя элементы по размеру. Эти алгоритмы больше не применимы к онлайн-варианту этой задачи. Однако они имеют улучшенную гарантию аппроксимации, сохраняя преимущество их малой временной сложности. Подкатегория офлайновых эвристик — это асимптотические схемы аппроксимации. Эти алгоритмы имеют гарантию аппроксимации в виде некоторой константы, которая может зависеть от . Для произвольно большого эти алгоритмы произвольно приближаются к . Однако это достигается ценой (резко) увеличенной временной сложности по сравнению с эвристическими подходами. ${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$ ${\displaystyle 1/\varepsilon }$ ${\displaystyle \mathrm {OPT} (L)}$ ${\displaystyle \mathrm {OPT} (L)}$

Онлайн эвристика

В онлайн- версии проблемы упаковки контейнеров предметы поступают один за другим, и (необратимое) решение, куда поместить элемент, должно быть принято до того, как станет известно о следующем элементе или даже о том, будет ли еще один. Разнообразный набор офлайн- и онлайн-эвристик для упаковки контейнеров был изучен Дэвидом С. Джонсоном в его докторской диссертации. ^[11]

Одноклассовые алгоритмы

Существует множество простых алгоритмов, использующих следующую общую схему:

• Для каждого элемента в списке ввода:
  1. Если предмет помещается в один из открытых ящиков, поместите его в один из этих ящиков;
  2. В противном случае откройте новый контейнер и положите в него новый предмет.

Алгоритмы различаются по критерию, по которому они выбирают открытую корзину для нового элемента на шаге 1 (более подробную информацию см. на связанных страницах):

• Next Fit (NF) всегда сохраняет одну открытую ячейку. Когда новый элемент не помещается в нее, он закрывает текущую ячейку и открывает новую ячейку. Его преимущество в том, что это алгоритм с ограниченным пространством, поскольку ему нужно хранить в памяти только одну открытую ячейку. Его недостаток в том, что его асимптотическое приближение равно 2. В частности,, и для каждогосуществует список L такой, чтои. ^[11] Его асимптотическое приближение можно несколько улучшить на основе размеров элементов:для всехидля всех. Для каждого алгоритма A , который является алгоритмом AnyFit, он сохраняет, что. ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$ ${\displaystyle N\in \mathbb {N} }$ ${\displaystyle \mathrm {OPT} (L)=N}$ ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$ ${\displaystyle \alpha \geq 1/2}$ ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$ ${\displaystyle \alpha \leq 1/2}$ ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )}$
• Next-k-Fit (NkF) — это вариант Next-Fit, но вместо того, чтобы держать открытым только один контейнер, алгоритм оставляет открытыми последние k контейнеров и выбирает первый контейнер, в который помещается элемент. Поэтому он называется алгоритмом k-ограниченного пространства . ^[12] ДляNkF результаты улучшены по сравнению с результатами NF, однако увеличение k до постоянных значений больше 2 не улучшает алгоритм в его худшем случае. Если алгоритм A является алгоритмом AlmostAnyFit итогда. ^[11] ${\displaystyle k\geq 2}$ ${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$ ${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m}$
• First-Fit (FF) сохраняет все ячейки открытыми в том порядке, в котором они были открыты. Он пытается поместить каждый новый элемент в первую ячейку, в которую он помещается. Его коэффициент аппроксимации равен, и существует семейство списков ввода L, для которыхсоответствует этой границе. ^[13] ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle FF(L)}$
• Best-Fit (BF) также сохраняет все ячейки открытыми, но пытается поместить каждый новый элемент в ячейку с максимальной загрузкой, в которую он помещается. Его коэффициент аппроксимации идентичен коэффициенту FF, то есть:, и существует семейство списков ввода L, для которыхсоответствует этой границе. ^[14] ${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle BF(L)}$
• Worst-Fit (WF) пытается поместить каждый новый элемент в корзину с минимальной загрузкой. Он может вести себя так же плохо, как Next-Fit, и будет делать это в списке худших случаев для этого . Более того, он считает, что . Поскольку WF является AnyFit-алгоритмом, существует AnyFit-алгоритм такой, что . ^[11] ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ ${\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}$ ${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$
• Почти худшее соответствие (AWF) пытается поместить каждый новый элемент во вторую по величине пустую открытую ячейку (или в самую пустую ячейку, если таких ячеек две). Если не помещается, то пробует самую пустую. Асимптотическое отношение наихудшего случая равно . ^[11] ${\displaystyle {\tfrac {17}{10}}}$

Для того чтобы обобщить эти результаты, Джонсон ввел два класса онлайн-эвристик, называемых алгоритмами любого соответствия и алгоритмами почти любого соответствия : ^{[4] : 470}

• В алгоритме AnyFit (AF) , если текущие непустые ячейки — это B ₁ ,..., B _j , то текущий элемент не будет упакован в B _{j +1,} если только он не поместится ни в одну из ячеек B ₁ ,..., B _j . Алгоритмы FF, WF, BF и AWF удовлетворяют этому условию. Джонсон доказал, что для любого алгоритма AnyFit A и любого : ${\displaystyle \alpha }$

  ${\displaystyle R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )}$.

• В алгоритме AlmostAnyFit (AAF) , если текущие непустые ячейки — это B ₁ ,..., B _j , и из этих ячеек B _k — единственная ячейка с наименьшей загрузкой, то текущий элемент не будет упакован в B _k , если только он не поместится ни в одну из ячеек слева от него. Алгоритмы FF, BF и AWF удовлетворяют этому условию, но WF — нет. Джонсон доказал, что для любого алгоритма AAF A и любого α :

  ${\displaystyle R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )}$ В частности: . ${\displaystyle R_{A}^{\infty }=1.7}$

Усовершенствованные алгоритмы

Лучшие коэффициенты аппроксимации возможны с эвристиками, которые не являются AnyFit. Эти эвристики обычно сохраняют несколько классов открытых ячеек, предназначенных для элементов разных диапазонов размеров (см. связанные страницы для получения дополнительной информации):

• Упаковка ячеек Refined-first-fit (RFF) разбивает размеры элементов на четыре диапазона:,,, и. Аналогично ячейки делятся на четыре класса. Следующий элементсначала назначается соответствующему классу. Внутри этого класса он назначается ячейке с помощью first-fit . Обратите внимание, что этот алгоритм не является алгоритмом Any-Fit, поскольку он может открыть новую ячейку, несмотря на то, что текущий элемент помещается в открытую ячейку. Этот алгоритм был впервые представлен Эндрю Чи-Чи Яо ^[15], который доказал, что он имеет гарантию аппроксимациии представил семейство списковсfor. ${\displaystyle \left({\frac {1}{2}},1\right]}$ ${\displaystyle \left({\frac {2}{5}},{\frac {1}{2}}\right]}$ ${\displaystyle \left({\frac {1}{3}},{\frac {2}{5}}\right]}$ ${\displaystyle \left(0,{\frac {1}{3}}\right]}$ ${\displaystyle i\in L}$ ${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$ ${\displaystyle L_{k}}$ ${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$ ${\displaystyle \mathrm {OPT} (L)=6k+1}$
• Harmonic-k разбивает интервал размеровна основе гармонической прогрессии начастидляитакие, что. Этот алгоритм был впервые описан Ли и Ли. ^[16] Он имеет временную сложностьи на каждом шаге существует не более k открытых ячеек, которые потенциально могут быть использованы для размещения предметов, т. е. это алгоритм с k -ограниченным пространством. Дляего отношение аппроксимации удовлетворяет, и он асимптотически плотен. ${\displaystyle (0,1]}$ ${\displaystyle k-1}$ ${\displaystyle I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]}$ ${\displaystyle 1\leq j<k}$ ${\displaystyle I_{k}:=\left(0,{\frac {1}{k}}\right]}$ ${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$ ${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$
• Refined-harmonic объединяет идеи из Harmonic-k с идеями из Refined-First-Fit . Он размещает элементы большего размера, чеманалогичные, как в Refined-First-Fit, в то время как элементы меньшего размера размещаются с помощью Harmonic-k. Интуиция этой стратегии заключается в том, чтобы сократить огромные отходы для контейнеров, содержащих элементы, которые просто больше, чем. Этот алгоритм был впервые описан Ли и Ли. ^[16] Они доказали, что длянего выполняется, что. ${\displaystyle {\tfrac {1}{3}}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle k=20}$ ${\displaystyle R_{RH}^{\infty }\leq 373/228}$

Общие нижние границы для онлайн-алгоритмов

Яо ^[15] доказал в 1980 году, что не может быть онлайн-алгоритма с асимптотическим конкурентным отношением меньше . Браун ^[17] и Лян ^[18] улучшили эту границу до ${\displaystyle {\tfrac {3}{2}}}$1,536 35. Впоследствии эта граница была улучшена до1,540 14 по Влиету. ^[19] В 2012 году эта нижняя граница была снова улучшена Бекеши и Галамбосом ^[20] до . ${\displaystyle {\tfrac {248}{161}}\approx 1.54037}$

Сравнительная таблица

Оффлайн алгоритмы

В офлайн-версии упаковки контейнеров алгоритм может видеть все предметы до того, как начнет их раскладывать по контейнерам. Это позволяет достичь улучшенных коэффициентов аппроксимации.

Мультипликативное приближение

Простейший метод, используемый в схемах офлайн-аппроксимации, следующий:

• Упорядочивание входного списка по убыванию размера;
• Запустите онлайн-алгоритм по упорядоченному списку.

Джонсон ^[11] доказал, что любая схема AnyFit A, которая работает на списке, упорядоченном по убыванию размера, имеет асимптотическое отношение аппроксимации

${\displaystyle 1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25}$.

Некоторые методы этого семейства (для получения дополнительной информации см. связанные страницы):

• First-fit-decreasing (FFD) упорядочивает элементы по убыванию размера, затем вызывает First-Fit. Его коэффициент аппроксимации равен, и это плотно. ^[23] ${\displaystyle FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$
• Next-fit-decreasing (NFD) упорядочивает элементы по убыванию размера, затем вызывает Next-Fit . Его приблизительное отношение немного меньше 1,7 в худшем случае. ^[24] Он также был проанализирован вероятностно. ^[25] Next-Fit упаковывает список и его обратный список в то же количество ячеек. Следовательно, Next-Fit-Increasing имеет ту же производительность, что и Next-Fit-Decreasing. ^[26]
• Модифицированный метод первого подходящего уменьшения (MFFD) ^[27] улучшает FFD для элементов, размер которых больше половины ячейки, классифицируя элементы по размеру на четыре класса: большой, средний, маленький и крошечный, что соответствует элементам с размером > 1/2 ячейки, > 1/3 ячейки, > 1/6 ячейки и меньшим элементам соответственно. Его гарантия аппроксимации составляет. ^[28] ${\displaystyle MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$

Фернандес де ла Вега и Люкер ^[29] представили PTAS для упаковки контейнеров. Для каждого их алгоритм находит решение с размером не более и работает за время , где обозначает функцию, зависящую только от . Для этого алгоритма они изобрели метод адаптивного округления входных данных : входные числа группируются и округляются до значения максимума в каждой группе. Это дает экземпляр с небольшим количеством различных размеров, который можно точно решить с помощью линейной программы конфигурации . ^[30] ${\displaystyle \varepsilon >0}$ ${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$ ${\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}$ ${\displaystyle {\mathcal {O}}_{\varepsilon }(1)}$ ${\displaystyle 1/\varepsilon }$

Аддитивное приближение

Алгоритм упаковки Кармаркара-Карпа находит решение размером не более и выполняется за полиномиальное по n время (полином имеет высокую степень, не менее 8). ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))}$

Ротвосс ^[31] представил алгоритм, который генерирует решение с максимальным количеством ячеек. ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$

Хоберг и Ротвосс ^[32] улучшили этот алгоритм, чтобы сгенерировать решение с максимумом ячеек. Алгоритм рандомизирован, и его время выполнения полиномиально по n . ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))}$

Сравнительная таблица

Точные алгоритмы

Мартелло и Тот ^[34] разработали точный алгоритм для одномерной задачи упаковки контейнеров, названный MTP. Более быстрой альтернативой является алгоритм Bin Completion, предложенный Корфом в 2002 году ^[35] и позже улучшенный. ^[36]

Дальнейшее улучшение было представлено Шрайбером и Корфом в 2013 году. ^[37] Показано, что новый алгоритм Improved Bin Completion на пять порядков быстрее, чем Bin Completion на нетривиальных задачах со 100 элементами, и превосходит алгоритм BCP (branch-and-cut-and-price) Белова и Шайтхауэра на задачах, в которых оптимальное решение составляет менее 20 ячеек. Какой алгоритм работает лучше, зависит от свойств задачи, таких как количество элементов, оптимальное количество ячеек, неиспользуемое пространство в оптимальном решении и точность значений.

Небольшое количество разных размеров

Частный случай упаковки контейнеров — это когда есть небольшое число d различных размеров элементов. Может быть много различных элементов каждого размера. Этот случай также называется упаковкой контейнеров с высокой множественностью , и он допускает более эффективные алгоритмы, чем общая задача.

Упаковка в контейнеры с фрагментацией

Упаковка контейнеров с фрагментацией или фрагментируемыми объектами Упаковка контейнеров — это вариант задачи упаковки контейнеров, в которой разрешено разбивать элементы на части и помещать каждую часть отдельно в другой контейнер. Разбиение элементов на части может позволить улучшить общую производительность, например, минимизировать общее количество контейнеров. Более того, вычислительная задача поиска оптимального расписания может стать проще, поскольку некоторые из переменных оптимизации становятся непрерывными. С другой стороны, разбиение элементов может быть затратным. Впервые эта задача была представлена ​​Мандалом, Чакрабари и Гхошем. ^[38]

Варианты

Задача имеет два основных варианта.

1. В первом варианте, называемом упаковкой в ​​контейнеры с фрагментацией по увеличению размера ( BP-SIF ), каждый элемент может быть фрагментирован; к размеру каждого фрагмента добавляются накладные единицы.
2. Во втором варианте, называемом упаковкой в ​​контейнеры с фрагментацией, сохраняющей размер ( BP-SPF ), каждый элемент имеет размер и стоимость; фрагментация элемента увеличивает его стоимость, но не изменяет его размер.

Сложность вычислений

Мандал, Чакрабари и Гош ^[38] доказали, что BP-SPF является NP-трудной задачей .

Менакерман и Ром ^[39] показали, что BP-SIF и BP-SPF оба являются сильно NP-трудными . Несмотря на сложность, они представляют несколько алгоритмов и исследуют их производительность. Их алгоритмы используют классические алгоритмы для упаковки в контейнеры, такие как next-fit и first-fit reduce , в качестве основы для своих алгоритмов.

Бертацци, Голден и Ванг ^[40] представили вариант BP-SIF с правилом разделения: элемент может быть разделен только одним способом в соответствии с его размером. Это полезно, например, для задачи маршрутизации транспортных средств . В своей статье они приводят предел производительности для худшего случая варианта. ${\displaystyle 1-x}$

Шахнай, Тамир и Йехезкели ^[41] разработали схемы аппроксимации для BP-SIF и BP-SPF; двойственную PTAS (PTAS для двойственной версии задачи), асимптотическую PTAS, называемую APTAS, и двойственную асимптотическую FPTAS, называемую AFPTAS, для обеих версий.

Экичи ^[42] представил вариант BP-SPF, в котором некоторые элементы конфликтуют, и запрещено упаковывать фрагменты конфликтующих элементов в одну корзину. Они доказали, что этот вариант также является NP-трудным.

Кассацца и Чезелли ^[43] представили вариант без стоимости и накладных расходов, а число ячеек фиксировано. Однако число фрагментаций должно быть минимизировано. Они представляют алгоритмы математического программирования как для точных, так и для приближенных решений.

Связанные проблемы

Задача дробного рюкзака со штрафами была представлена ​​Малагути, Моначи, Паронуцци и Пферши. ^[44] Они разработали FPTAS и динамическую программу для задачи, а также продемонстрировали обширное вычислительное исследование, сравнивающее производительность их моделей. См. также: Дробное планирование заданий .

Производительность с делимыми размерами элементов

Важным частным случаем упаковки контейнеров является то, что размеры элементов образуют делимую последовательность (также называемую факторизованной ). Частный случай делимых размеров элементов возникает при распределении памяти в компьютерных системах, где все размеры элементов являются степенями 2. Если размеры элементов делимы, то некоторые эвристические алгоритмы для упаковки контейнеров находят оптимальное решение. ^[45]

Ограничения мощности для ячеек

Существует вариант упаковки контейнеров, в котором на контейнеры накладываются ограничения по количеству элементов: каждый контейнер может содержать не более k элементов для некоторого фиксированного целого числа k .

• Краузе, Шен и Шветман ^[46] представляют эту проблему как вариант оптимального планирования заданий : компьютер имеет несколько k процессоров. Есть несколько n заданий, которые занимают единицу времени (1), но имеют разные требования к памяти. Каждая единица времени считается одним контейнером. Цель состоит в том, чтобы использовать как можно меньше контейнеров (=единиц времени), гарантируя, что в каждом контейнере выполняется не более k заданий. Они представляют несколько эвристических алгоритмов, которые находят решение с не более чем контейнерами. ${\displaystyle 2\mathrm {OPT} }$
• Келлерер и Пферши ^[47] представляют алгоритм с временем выполнения , который находит решение с максимум ячейками. Их алгоритм выполняет бинарный поиск OPT. Для каждого искомого значения m он пытается упаковать элементы в 3 m /2 ячейки. ${\displaystyle O(n^{2}\log {n})}$ ${\displaystyle \left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil }$

Неаддитивные функции

Существуют различные способы расширения модели упаковки в контейнеры до более общих функций стоимости и нагрузки:

• Анили, Брамел и Симчи-Леви ^[48] изучают ситуацию, когда стоимость контейнера является вогнутой функцией количества элементов в контейнере. Цель состоит в том, чтобы минимизировать общую стоимость , а не количество контейнеров. Они показывают, что упаковка контейнеров с возрастанием по принципу «следующий-подходящий» достигает абсолютного коэффициента приближения в худшем случае не более 7/4 и асимптотического коэффициента в худшем случае 1,691 для любой вогнутой и монотонной функции стоимости.
• Коэн, Келлер, Миррокни и Задимогхаддам ^[49] изучают ситуацию, когда размер элементов заранее неизвестен, но является случайной величиной . Это особенно распространено в средах облачных вычислений . Хотя существует верхняя граница количества ресурсов, необходимых определенному пользователю, большинство пользователей используют гораздо меньше, чем емкость. Таким образом, менеджер облака может получить много за счет небольшого перерасхода . Это вызывает вариант упаковки ячеек с ограничениями вероятности: вероятность того, что сумма размеров в каждой ячейке не превышает B, должна быть не менее p , где p — фиксированная константа (стандартная упаковка ячеек соответствует p = 1). Они показывают, что при умеренных предположениях эта проблема эквивалентна субмодулярной задаче упаковки ячеек, в которой «нагрузка» в каждой ячейке равна не сумме элементов, а определенной субмодулярной функции от нее.

Связанные проблемы

В задаче об упаковке контейнеров размер контейнеров фиксирован, а их количество может быть увеличено (но должно быть как можно меньше).

Напротив, в задаче многоканального разбиения чисел число ячеек фиксировано, а их размер может быть увеличен. Цель состоит в том, чтобы найти разбиение, в котором размеры ячеек настолько близки, насколько это возможно (в варианте, называемом задачей многопроцессорного планирования или задачей минимального объема выполнения , цель состоит в том, чтобы минимизировать размер наибольшей ячейки).

В обратной задаче упаковки контейнеров ^[50] как количество контейнеров, так и их размеры фиксированы, но размеры элементов могут быть изменены. Цель состоит в том, чтобы достичь минимального возмущения вектора размеров элементов, чтобы все элементы могли быть упакованы в предписанное количество контейнеров.

В задаче максимальной упаковки контейнеров ресурсов ^[51] цель состоит в том, чтобы максимизировать количество используемых контейнеров, так что при некотором порядке контейнеров ни один элемент из более позднего контейнера не помещается в более ранний контейнер. В двойственной задаче количество контейнеров фиксировано, и цель состоит в том, чтобы минимизировать общее количество или общий размер элементов, помещенных в контейнеры, так что ни один оставшийся элемент не помещается в незаполненный контейнер.

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

В задаче о справедливом неделимом распределении дел (вариант справедливого распределения предметов ) предметы представляют собой дела, и есть разные люди, каждый из которых приписывает разное значение сложности каждому делу. Цель состоит в том, чтобы распределить между каждым человеком набор дел с верхней границей его общего значения сложности (таким образом, каждый человек соответствует корзине). В этой задаче также используются многие методы из упаковки корзин. ^[52]

В задаче о гильотинной резке и предметы, и «контейнеры» представляют собой двумерные прямоугольники, а не одномерные числа, и предметы необходимо вырезать из контейнера, используя сквозные разрезы.

В задаче об эгоистичной упаковке каждый предмет — это игрок, который хочет минимизировать его стоимость. ^[53]

Существует также вариант упаковки в контейнеры, в котором стоимость, которую следует минимизировать, представляет собой не количество контейнеров, а скорее определенную вогнутую функцию количества предметов в каждом контейнере. ^[48]

Другие варианты: двухмерная упаковка в контейнеры, ^[54] трехмерная упаковка в контейнеры , ^[55] упаковка в контейнеры с доставкой , ^[56]

Ресурсы

• BPPLIB — библиотека обзоров, кодов, тестов, генераторов, решателей и библиографии.

Ссылки

1. Мартелло, Сильвано; Тот, Паоло (1990), "Задача об упаковке в контейнеры" (PDF) , Задачи о ранце: алгоритмы и компьютерные реализации , Чичестер, Великобритания: John Wiley and Sons, ISBN 0471924202
2. Корте, Бернхард; Виген, Йенс (2006). «Упаковка в контейнеры». Комбинаторная оптимизация: теория и алгоритмы . Алгоритмы и комбинаторика 21. Springer. стр. 426–441. doi :10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.
3. Barrington, David Mix (2006). "Bin Packing". Архивировано из оригинала 2019-02-16 . Получено 2016-02-27 .
4. Коффман младший, Эдвард Г.; Чирик, Янош; Галамбос, Габор; Мартелло, Сильвано; Виго, Даниэле (2013), Пардалос, Панос М.; Ду, Дин-Чжу; Грэм, Рональд Л. (ред.), «Алгоритмы аппроксимации упаковки контейнеров: обзор и классификация», Справочник по комбинаторной оптимизации , Нью-Йорк, Нью-Йорк: Springer, стр. 455–531, doi : 10.1007/978-1-4419-7997 -1_35, ISBN 978-1-4419-7997-1, получено 2021-08-08
5. "DHCPv6-PD - Первые шаги" . Получено 12 июня 2024 г.
6. Льюис, Р. (2009), «Универсальный метод восхождения на вершину для задач по порядково-независимой минимальной группировки: пример раскраски графов и упаковки контейнеров» (PDF) , Computers and Operations Research , 36 (7): 2295–2310, doi :10.1016/j.cor.2008.09.004, S2CID  1577334
7. Синделар, Майкл; Ситараман, Рамеш ; Шеной, Прашант (2011), «Алгоритмы с поддержкой совместного использования для размещения виртуальных машин» (PDF) , Труды 23-го симпозиума ACM по параллелизму в алгоритмах и архитектурах (SPAA), Сан-Хосе, Калифорния, июнь 2011 г .: 367–378
8. Garey, M. R. ; Johnson, D. S. (1979). Victor Klee (ред.). Computers and Intractability: A Guide to the Theory of NP-Completeness . Серия книг по математическим наукам. Сан-Франциско, Калифорния: W. H. Freeman and Co. стр. x+338. ISBN 0-7167-1045-5. МР  0519066.
9. Мартелло и Тот 1990, с. 221
10. Вазирани, Виджай В. (14 марта 2013 г.). Аппроксимационные алгоритмы . Springer Berlin Heidelberg. стр. 74. ISBN 978-3662045657.
11. Джонсон, Дэвид С. (1973). "Почти оптимальные алгоритмы упаковки контейнеров" (PDF) . Массачусетский технологический институт .
12. Гонсалес, Теофило Ф. (23 мая 2018 г.). Справочник по аппроксимационным алгоритмам и метаэвристикам. Том 2 Современные и новые приложения . Taylor & Francis Incorporated. ISBN 9781498770156.
13. Доса, Дьёрдь; Сгалл, Иржи (2013). «Упаковка контейнера с первой посадкой: тщательный анализ». 30-й Международный симпозиум по теоретическим аспектам информатики (STACS 2013) . 20 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 538–549. дои : 10.4230/LIPIcs.STACS.2013.538 .
14. Дьёрдь, Доса; Сгалль, Иржи (2014). «Оптимальный анализ наилучшей упаковки контейнеров». Автоматы, языки и программирование . Конспект лекций по информатике. Том 8572. С. 429–441. doi :10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0. {{cite book}}: |journal=проигнорировано ( помощь )
15. Яо, Эндрю Чи-Чи (апрель 1980 г.). «Новые алгоритмы упаковки контейнеров». Журнал ACM . 27 (2): 207–227. doi : 10.1145/322186.322187 . S2CID  7903339.
16. Ли, CC; Ли, DT (июль 1985). «Простой алгоритм онлайн-упаковки контейнеров». Журнал ACM . 32 (3): 562–572. doi : 10.1145/3828.3833 . S2CID  15441740.
17. Донна Дж., Браун (1979). «Нижняя граница для одномерных алгоритмов упаковки контейнеров в режиме онлайн» (PDF) . Технический отчет . Архивировано (PDF) из оригинала 17 марта 2022 г.
18. Лян, Фрэнк М. (1980). «Нижняя граница для онлайновой упаковки контейнеров». Information Processing Letters . 10 (2): 76–79. doi :10.1016/S0020-0190(80)90077-0.
19. Ван Влит, Андре (1992). «Улучшенная нижняя граница для алгоритмов упаковки контейнеров в режиме онлайн». Information Processing Letters . 43 (5): 277–284. doi :10.1016/0020-0190(92)90223-I.
20. Балог, Янош; Бекеши, Йожеф; Галамбос, Габор (июль 2012 г.). «Новые нижние оценки для некоторых классов алгоритмов упаковки контейнеров». Теоретическая информатика . 440–441: 1–13. дои : 10.1016/j.tcs.2012.04.017 .
21. Ramanan, Prakash; Brown, Donna J; Lee, CC; Lee, DT (сентябрь 1989). «Онлайн-упаковка контейнеров за линейное время». Journal of Algorithms . 10 (3): 305–326. doi :10.1016/0196-6774(89)90031-X. hdl : 2142/74206 .
22. Seiden, Steven S. (2002). «О проблеме упаковки контейнеров в режиме онлайн». Журнал ACM . 49 (5): 640–671. doi :10.1145/585265.585269. S2CID  14164016.
23. Доса, Дьёрдь (2007). "Жесткая граница алгоритма First Fit Decreasing bin-Packing составляет FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9". Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии. ESCAPE . doi :10.1007/978-3-540-74450-4_1.
24. Бейкер, Б. С.; Коффман, младший, Э. Г. (1981-06-01). «Жесткая асимптотическая граница для убывающей упаковки контейнеров с помощью следующего соответствия». Журнал SIAM по алгебраическим и дискретным методам . 2 (2): 147–152. doi :10.1137/0602019. ISSN  0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)
25. Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1 ноября 1986 г.). «Вероятностный анализ эвристики следующей подгонки с убывающей упаковкой контейнеров». Operations Research Letters . 5 (5): 233–236. doi : 10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN  0167-6377. S2CID  50663185.
26. Фишер, Дэвид К. (1988-12-01). «Next-fit упаковывает список и его обратный список в то же количество ячеек». Operations Research Letters . 7 (6): 291–293. doi :10.1016/0167-6377(88)90060-0. ISSN  0167-6377.
27. Джонсон, Дэвид С.; Гари, Майкл Р. (октябрь 1985 г.). «Теорема 7160 для упаковки контейнеров». Журнал сложности . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .
28. Юэ, Миньи; Чжан, Лэй (июль 1995 г.). «Простое доказательство неравенства MFFD(L) ≤ 71/60 OPT(L) + 1,L для алгоритма упаковки ячеек MFFD». Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi :10.1007/BF02011198. S2CID  118263129.
29. Фернандес де ла Вега, В.; Люкер, Г. С. (1981). «Упаковка контейнеров может быть решена за 1 + ε за линейное время». Combinatorica . 1 (4): 349–355. doi :10.1007/BF02579456. ISSN  1439-6912. S2CID  10519631.
30. Клэр Матье. «Алгоритмы аппроксимации, часть I, неделя 3: упаковка контейнеров». Coursera . Архивировано из оригинала 2021-07-15.
31. Rothvoß, T. (2013-10-01). "Аппроксимация упаковки ячеек в пределах O(log OPT · Log Log OPT) ячеек". 2013 IEEE 54-й ежегодный симпозиум по основам компьютерной науки . стр. 20–29. arXiv : 1301.4010 . doi :10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID  15905063.
32. Хоберг, Ребекка; Ротвосс, Томас (2017-01-01), "Логарифмический аддитивный разрыв целостности для упаковки контейнеров", Труды ежегодного симпозиума ACM-SIAM 2017 года по дискретным алгоритмам , Труды, Общество промышленной и прикладной математики, стр. 2616–2625, arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2, S2CID  1647463
33. Кармаркар, Нарендра; Карп, Ричард М. (ноябрь 1982 г.). «Эффективная схема аппроксимации для одномерной задачи упаковки в контейнеры». 23-й ежегодный симпозиум по основам компьютерной науки (SFCS 1982) : 312–320. doi :10.1109/SFCS.1982.61. S2CID  18583908.
34. Мартелло и Тот 1990, стр. 237–240.
35. Корф, Ричард Э. (2002). Новый алгоритм оптимальной упаковки контейнеров (PDF) . AAAI-02.
36. RE Korf (2003), Улучшенный алгоритм оптимальной упаковки контейнеров . Труды Международной объединенной конференции по искусственному интеллекту, (стр. 1252–1258)
37. Шрайбер, Итан Л.; Корф, Ричард Э. (2013), «Улучшенное завершение бинов для оптимальной упаковки бинов и разбиения чисел» (PDF) , Труды Двадцать третьей Международной совместной конференции по искусственному интеллекту , IJCAI '13, Пекин, Китай: AAAI Press, стр. 651–658, ISBN 978-1-57735-633-2
38. Mandal, CA; Chakrabarti, PP; Ghose, S. (1998-06-01). «Сложность упаковки фрагментируемых объектов в контейнеры и ее применение». Компьютеры и математика с приложениями . 35 (11): 91–97. doi :10.1016/S0898-1221(98)00087-X. ISSN  0898-1221.
39. Нир Менакерман и Рафаэль Ром «Упаковка контейнеров с фрагментацией элементов». Алгоритмы и структуры данных, 7-й международный семинар, WADS 2001, Провиденс, Род-Айленд, США, 8-10 августа 2001 г., Труды.
40. Бертацци, Лука; Голден, Брюс; Ван, Сининь (31.05.2019). «Проблема упаковки контейнеров с фрагментацией элементов: анализ наихудшего случая». Дискретная прикладная математика . Встреча GO X, Риги Калтбад (CH), 10–14 июля 2016 г. 261 : 63–77. doi : 10.1016/j.dam.2018.08.023 . ISSN  0166-218X. S2CID  125361557.
41. Shachnai, Hadas; Tamir, Tami; Yehezkely, Omer (2006). «Схемы аппроксимации для упаковки с фрагментацией элементов». В Erlebach, Thomas; Persinao, Giuseppe (ред.). Аппроксимация и онлайн-алгоритмы . Конспект лекций по информатике. Том 3879. Берлин, Гейдельберг: Springer. стр. 334–347. doi :10.1007/11671411_26. ISBN 978-3-540-32208-5.
42. Экичи, Али (2021-02-01). «Проблема упаковки контейнеров с конфликтами и фрагментацией элементов». Computers & Operations Research . 126 : 105113. doi : 10.1016/j.cor.2020.105113. ISSN  0305-0548. S2CID  225002556.
43. Casazza, Marco; Ceselli, Alberto (2014-06-01). «Математические алгоритмы программирования для задач упаковки в контейнеры с фрагментацией элементов». Computers & Operations Research . 46 : 1–11. doi :10.1016/j.cor.2013.12.008. ISSN  0305-0548.
44. Малагути, Энрико; Моначи, Микеле; Паронуцци, Паоло; Пферши, Ульрих (16.03.2019). «Целочисленная оптимизация со штрафными дробными значениями: случай ранца». European Journal of Operational Research . 273 (3): 874–888. doi : 10.1016/j.ejor.2018.09.020. hdl : 11585/657029 . ISSN  0377-2217. S2CID  31722681.
45. Коффман, Э. Г.; Гарей, М. Р.; Джонсон, Д. С. (1987-12-01). «Упаковка контейнеров с делимыми размерами предметов». Журнал сложности . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
46. Краузе, К. Л.; Шен, В. Я.; Шветман, Х. Д. (1975-10-01). «Анализ нескольких алгоритмов планирования задач для модели многопрограммных компьютерных систем». Журнал ACM . 22 (4): 522–550. doi : 10.1145/321906.321917 . ISSN  0004-5411. S2CID  10214857.
47. Келлерер, Х.; Пферши, У. (1999-01-01). «Проблемы упаковки в контейнеры с ограничением мощности». Annals of Operations Research . 92 : 335–348. doi :10.1023/A:1018947117526. ISSN  1572-9338. S2CID  28963291.
48. Анили, Шошана; Брамель, Жюльен; Симчи-Леви, Дэвид (1994-04-01). "Анализ наихудшего случая эвристики для задачи упаковки в контейнеры с общими структурами затрат". Исследование операций . 42 (2): 287–298. doi :10.1287/opre.42.2.287. ISSN  0030-364X.
49. Коэн, Максим С.; Келлер, Филипп В.; Миррокни, Вахаб; Задимогхаддам, Мортеза (01.07.2019). «Избыточные обязательства в облачных сервисах: упаковка контейнеров с ограничениями вероятности». Management Science . 65 (7): 3255–3271. arXiv : 1705.09335 . doi :10.1287/mnsc.2018.3091. ISSN  0025-1909. S2CID  159270392.
50. Чунг, Йерим; Пак, Мён-Джу (2015-01-01). «Заметки о задачах обратной упаковки в контейнеры». Information Processing Letters . 115 (1): 60–68. doi :10.1016/j.ipl.2014.09.005. ISSN  0020-0190.
51. Бояр, Жанна ; Эпштейн, Лия; Фаврхольдт, Лене М.; Корт, Йенс С.; Ларсен, Ким С.; Педерсен, Мортен М.; Вёлк, Санне (11 октября 2006 г.). «Проблема упаковки контейнера с максимальным ресурсом». Теоретическая информатика . 362 (1): 127–139. дои : 10.1016/j.tcs.2006.06.001. ISSN  0304-3975.
52. Хуан, Синь; Лу, Пиньян (10.11.2020). «Алгоритмическая структура для аппроксимации распределения максиминных долей домашних дел». arXiv : 1907.04505 [cs.GT].
53. Ma, Ruixin; Dósa, György; Han, Xin; Ting, Hing-Fung; Ye, Deshi; Zhang, Yong (2013-08-01). «Заметка о проблеме эгоистичной упаковки контейнеров». Journal of Global Optimization . 56 (4): 1457–1462. doi :10.1007/s10898-012-9856-9. ISSN  0925-5001. S2CID  3082040.
54. Лоди А., Мартелло С., Моначи М., Виго Д. (2010) «Двумерные проблемы упаковки контейнеров». В V.Th. Paschos (ред.), Парадигмы комбинаторной оптимизации , Wiley/ISTE, стр. 107–129
55. Оптимизация трехмерной упаковки контейнеров с помощью моделирования
56. Benkő A., Dósa G., Tuza Z. (2010) «Упаковка/покрытие контейнеров с доставкой, решенная с помощью эволюции алгоритмов», Труды 2010 IEEE 5-й Международной конференции по биоинспирированным вычислениям: теории и приложения, BIC-TA 2010 , статья № 5645312, стр. 298–302.