Проблема с упаковкой контейнера

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

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

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

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

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

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

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

В книге «Компьютеры и трудноразрешимость» ^{[7] : 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} }$

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

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

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

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

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

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

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

Для измерения производительности алгоритма аппроксимации в литературе рассматриваются два коэффициента аппроксимации. Для данного списка элементов число обозначает количество ячеек, используемых при применении алгоритма к списку , а обозначает оптимальное число для этого списка. Абсолютный коэффициент производительности алгоритма в наихудшем случае определяется как ${\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)}$

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

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

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

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

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

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

• Функция Next Fit (NF) всегда оставляет одну открытую корзину. Когда новый товар в него не помещается, он закрывает текущую корзину и открывает новую корзину. Его преимущество состоит в том, что это алгоритм с ограниченным пространством, поскольку ему нужно хранить в памяти только один открытый интервал. Его недостатком является то, что его коэффициент асимптотической аппроксимации равен 2. В частности,, и для каждогосуществует список L такой, чтои. ^[10] Его коэффициент асимптотической аппроксимации можно несколько улучшить в зависимости от размеров элемента:for allиfor all. Для каждого алгоритма 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-ограниченным пространством . ^[11] ПосколькуNkF дает результаты, которые улучшаются по сравнению с результатами NF, однако увеличение k до постоянных значений, превышающих 2 , не приводит к дальнейшему улучшению алгоритма в его худшем случае. Если алгоритм A является алгоритмом ПочтиAnyFit итогда. ^[10] ${\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 , для которогосоответствует эта граница. ^[12] ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle FF(L)}$
• Best-Fit (BF) также оставляет все контейнеры открытыми, но пытается поместить каждый новый предмет в контейнер с максимальной загрузкой , в которую он помещается. Его коэффициент аппроксимации идентичен коэффициенту аппроксимации FF, то есть:, и существует семейство входных списков L , для которогосоответствует эта граница. ^[13] ${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ ${\displaystyle BF(L)}$
• Worst-Fit (WF) пытается поместить каждый новый предмет в корзину с минимальной загрузкой. Он может вести себя так же плохо, как Next-Fit, и попадет в список наихудших для этого случаев . Более того, он утверждает, что . Поскольку WF является алгоритмом AnyFit, существует алгоритм AnyFit такой, что . ^[10] ${\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) пытается поместить каждый новый товар во вторую по величине пустую открытую корзину (или самую пустую корзину, если таких корзин две). Если не подходит, пробует самый пустой. Он имеет асимптотическое отношение наихудшего случая . ^[10] ${\displaystyle {\tfrac {17}{10}}}$

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

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

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

• В алгоритме ПочтиAnyFit (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. Эти эвристики обычно содержат несколько классов открытых ячеек, посвященных предметам разных размеров (дополнительную информацию см. на связанных страницах):

• Усовершенствованная упаковка контейнеров по принципу «первая подгонка» (RFF) разделяет размеры предметов на четыре диапазона:,,и. Аналогичным образом контейнеры делятся на четыре класса. Следующий элементсначала присваивается соответствующему классу. Внутри этого класса он назначается ячейке с помощью first-fit . Обратите внимание, что этот алгоритм не является алгоритмом Any-Fit, поскольку он может открыть новую корзину, несмотря на то, что текущий элемент помещается в открытую корзину. Этот алгоритм был впервые представлен Эндрю Чи-Чи Яо ^[14] , который доказал, что он имеет гарантию аппроксимации,и представил семейство списковсдля. ${\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 разбивает интервал размеровна основе гармонической прогрессии начастидляитакие, что. Этот алгоритм был впервые описан Ли и Ли. ^[15] Его временная сложность равнаи на каждом шаге имеется не более 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. Идея этой стратегии состоит в том, чтобы уменьшить количество огромных отходов в контейнерах, содержащих куски размером чуть больше 0,000. Этот алгоритм был впервые описан Ли и Ли. ^[15] Они доказали, что дляэтого справедливо. ${\displaystyle {\tfrac {1}{3}}}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle k=20}$ ${\displaystyle R_{RH}^{\infty }\leq 373/228}$

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

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

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

Автономные алгоритмы

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

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

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

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

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

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

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

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

Фернандес де ла Вега и Люкер ^[28] представили PTAS для упаковки в контейнеры. Для каждого их алгоритм находит решение с размером не более и работает за время , где обозначает функцию, зависящую только от . Для этого алгоритма они изобрели метод адаптивного округления входных данных : входные числа группируются и округляются до значения максимума в каждой группе. В результате получается экземпляр с небольшим количеством разных размеров, который можно точно решить с помощью линейной программы конфигурации . ^[29] ${\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} ))}$

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

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

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

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

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

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

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

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

Бин-упаковка с фрагментацией

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

Варианты

Проблема имеет два основных варианта.

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

Вычислительная сложность

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

Менакерман и Ром ^[38] показали, что BP-SIF и BP-SPF являются сильно NP-жесткими . Несмотря на сложность, они представляют несколько алгоритмов и исследуют их работу. В их алгоритмах в качестве основы для своих алгоритмов используются классические алгоритмы упаковки контейнеров, такие как уменьшение следующего и первого соответствия .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ресурсы

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

Реализации

• Онлайн : визуализация эвристики для 1D и 2D упаковки контейнеров.
• Python: пакет prtpy содержит код для различных алгоритмов разделения чисел, упаковки и покрытия ячеек. Пакет binpacking содержит жадные алгоритмы для решения двух типичных задач по упаковке bin. ^[55]
• C++ : пакет bin-packing содержит различные жадные алгоритмы, а также тестовые данные. Пакет OR-tools содержит алгоритмы упаковки контейнеров на C++ с оболочками на Python, C# и Java.
• C : Реализация 7 классических алгоритмов приближенной упаковки ячеек на C с результатами и изображениями.
• PHP : класс PHP для упаковки файлов без превышения заданного ограничения размера.
• Haskell : реализация нескольких эвристик упаковки контейнеров, включая FFD и MFFD.
• C : Fpart: инструмент командной строки с открытым исходным кодом для упаковки файлов (C, лицензия BSD).
• C# : Решение для упаковки и резки запасов в контейнерах
• Java : caparf — платформа исследования алгоритмов резки и упаковки, включая ряд алгоритмов упаковки в контейнеры и тестовые данные.

Рекомендации

1. Мартелло, Сильвано; Тот, Паоло (1990), «Проблема упаковки контейнеров» (PDF) , Проблемы с рюкзаком: алгоритмы и компьютерные реализации , Чичестер, Великобритания: John Wiley and Sons, ISBN 0471924202
2. Корте, Бернхард; Виген, Йенс (2006). «Бин-Упаковка». Комбинаторная оптимизация: теория и алгоритмы . Алгоритмы и комбинаторика 21. Спрингер. стр. 426–441. дои : 10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7.
3. Баррингтон, Дэвид Микс (2006). «Бин-упаковка». Архивировано из оригинала 16 февраля 2019 г. Проверено 27 февраля 2016 г.
4. Коффман младший, Эдвард Г.; Чирик, Янош; Галамбос, Габор; Мартелло, Сильвано; Виго, Даниэле (2013), Пардалос, Панос М.; Ду, Дин-Чжу; Грэм, Рональд Л. (ред.), «Алгоритмы аппроксимации упаковки контейнеров: обзор и классификация», Справочник по комбинаторной оптимизации , Нью-Йорк, Нью-Йорк: Springer, стр. 455–531, doi : 10.1007/978-1-4419-7997 -1_35, ISBN 978-1-4419-7997-1, получено 8 августа 2021 г.
5. Льюис, Р. (2009), «Общий метод восхождения на холм для решения задач минимальной группировки, не зависящих от порядка: пример раскраски графов и упаковки ячеек» (PDF) , Computers and Operations Research , 36 (7): 2295 –2310, номер doi :10.1016/j.cor.2008.09.004, S2CID  1577334
6. Синделар, Майкл; Ситараман, Рамеш ; Шеной, Прашант (2011), «Алгоритмы совместного использования для колокации виртуальных машин» (PDF) , Материалы 23-го симпозиума ACM по параллелизму в алгоритмах и архитектурах (SPAA), Сан-Хосе, Калифорния, июнь 2011 г .: 367–378
7. Гари, MR ; Джонсон, Д.С. (1979). Виктор Клее (ред.). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам. Сан-Франциско, Калифорния: WH Freeman and Co., стр. x+338. ISBN 0-7167-1045-5. МР  0519066.
8. Мартелло и Тот 1990, с. 221
9. Вазирани, Виджай В. (14 марта 2013 г.). Алгоритмы аппроксимации . Шпрингер Берлин Гейдельберг. п. 74. ИСБН 978-3662045657.
10. Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский Институт Технологий .
11. Гонсалес, Теофило Ф. (23 мая 2018 г.). Справочник по аппроксимационным алгоритмам и метаэвристике. Том 2 Современные и новые приложения . Тейлор и Фрэнсис Инкорпорейтед. ISBN 9781498770156.
12. Доса, Дьёрдь; Сгалл, Иржи (2013). «Упаковка контейнера с первой посадкой: тщательный анализ». 30-й Международный симпозиум по теоретическим аспектам информатики (STACS 2013) . Замок Дагштуль – Центр информатики Лейбница. 20 : 538–549. doi : 10.4230/LIPIcs.STACS.2013.538.
13. Дьёрдь, Доса; Сгалл, Иржи (2014). «Оптимальный анализ наилучшей подходящей упаковки в контейнеры». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 8572. стр. 429–441. дои : 10.1007/978-3-662-43948-7_36. ISBN 978-3-662-43947-0. {{cite book}}: |journal=игнорируется ( помощь )
14. Яо, Эндрю Чи-Чи (апрель 1980 г.). «Новые алгоритмы упаковки контейнеров». Журнал АКМ . 27 (2): 207–227. дои : 10.1145/322186.322187 . S2CID  7903339.
15. Ли, CC; Ли, DT (июль 1985 г.). «Простой онлайн-алгоритм упаковки в корзину». Журнал АКМ . 32 (3): 562–572. дои : 10.1145/3828.3833 . S2CID  15441740.
16. Донна Дж, Браун (1979). «Нижняя граница для онлайн-алгоритмов упаковки одномерных контейнеров» (PDF) . Технический представитель . Архивировано (PDF) из оригинала 17 марта 2022 г.
17. Лян, Фрэнк М. (1980). «Нижняя граница для упаковки контейнеров в режиме онлайн». Письма об обработке информации . 10 (2): 76–79. дои : 10.1016/S0020-0190(80)90077-0.
18. ван Влит, Андре (1992). «Улучшенная нижняя граница для алгоритмов упаковки контейнеров в режиме онлайн». Письма об обработке информации . 43 (5): 277–284. дои : 10.1016/0020-0190(92)90223-I.
19. Балог, Янош; Бекеши, Йожеф; Галамбос, Габор (июль 2012 г.). «Новые нижние оценки для некоторых классов алгоритмов упаковки контейнеров». Теоретическая информатика . 440–441: 1–13. дои : 10.1016/j.tcs.2012.04.017 .
20. Раманан, Пракаш; Браун, Донна Дж; Ли, CC; Ли, DT (сентябрь 1989 г.). «Онлайн-упаковка контейнеров в линейное время». Журнал алгоритмов . 10 (3): 305–326. дои : 10.1016/0196-6774(89)90031-X. hdl : 2142/74206 .
21. Seiden, Стивен С. (2002). «О проблеме онлайн-упаковки корзин». Журнал АКМ . 49 (5): 640–671. дои : 10.1145/585265.585269. S2CID  14164016.
22. Доса, Дьёрдь (2007). «Точная граница алгоритма упаковки ячеек с уменьшением первого соответствия равна FFD(I) ≤ 11/9\mathrm{OPT}(I) + 6/9». Комбинаторика, алгоритмы, вероятностные и экспериментальные методологии. ПОБЕГ . дои : 10.1007/978-3-540-74450-4_1.
23. Бейкер, Б.С.; Коффман-младший, Э.Г. (1 июня 1981 г.). «Точная асимптотическая граница для следующей убывающей упаковки контейнеров». SIAM Journal по алгебраическим и дискретным методам . 2 (2): 147–152. дои : 10.1137/0602019. ISSN  0196-5212.{{cite journal}}: CS1 maint: multiple names: authors list (link)
24. Чирик, Дж.; Галамбос, Г.; Фрэнк, JBG; Фриз, AM; Риннуй Кан, AHG (1 ноября 1986 г.). «Вероятностный анализ следующей эвристики упаковки контейнеров, уменьшающей соответствие». Письма об исследованиях операций . 5 (5): 233–236. дои : 10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN  0167-6377. S2CID  50663185.
25. Фишер, Дэвид К. (1 декабря 1988 г.). «Next-fit упаковывает список и его обратную сторону в одинаковое количество ячеек». Письма об исследованиях операций . 7 (6): 291–293. дои : 10.1016/0167-6377(88)90060-0. ISSN  0167-6377.
26. Джонсон, Дэвид С; Гэри, Майкл Р. (октябрь 1985 г.). «Теорема 7160 для упаковки контейнеров». Журнал сложности . 1 (1): 65–106. дои : 10.1016/0885-064X(85)90022-6 .
27. Юэ, Миньи; Чжан, Лей (июль 1995 г.). «Простое доказательство неравенства MFFD(L) ≤ 71/60 OPT(L) + 1,L для алгоритма упаковки бинов MFFD». Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. дои : 10.1007/BF02011198. S2CID  118263129.
28. Фернандес де ла Вега, В.; Люкер, Г.С. (1981). «Упаковку контейнеров можно решить за 1 + ε за линейное время». Комбинаторика . 1 (4): 349–355. дои : 10.1007/BF02579456. ISSN  1439-6912. S2CID  10519631.
29. Клэр Матье. «Алгоритмы аппроксимации. Часть I, неделя 3: упаковка контейнеров». Курсера . Архивировано из оригинала 15 июля 2021 г.
30. Ротвосс, Т. (01 октября 2013 г.). «Аппроксимация упаковки бункеров в бункерах O (log OPT · Log Log OPT)». 54-й ежегодный симпозиум IEEE по основам информатики, 2013 г. стр. 20–29. arXiv : 1301.4010 . дои : 10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID  15905063.
31. Хоберг, Ребекка; Ротвосс, Томас (01 января 2017 г.), «Логарифмический аддитивный разрыв целостности для упаковки контейнеров», Труды ежегодного симпозиума ACM-SIAM 2017 г. по дискретным алгоритмам , Труды Общества промышленной и прикладной математики, стр. 2616–2625, arXiv : 1503.08796 , doi : 10.1137/1.9781611974782.172 , ISBN 978-1-61197-478-2, S2CID  1647463
32. Кармаркар, Нарендра; Карп, Ричард М. (ноябрь 1982 г.). «Эффективная аппроксимационная схема одномерной задачи упаковки контейнеров». 23-й ежегодный симпозиум по основам информатики (SFCS 1982) : 312–320. дои : 10.1109/SFCS.1982.61. S2CID  18583908.
33. Мартелло и Тот 1990, стр. 237–240.
34. Корф, Ричард Э. (2002). Новый алгоритм оптимальной упаковки контейнеров (PDF) . АААИ-02.
35. RE Korf (2003), Улучшенный алгоритм оптимальной упаковки контейнеров . Материалы Международной совместной конференции по искусственному интеллекту (стр. 1252–1258).
36. Шрайбер, Итан Л.; Корф, Ричард Э. (2013), «Улучшенное заполнение бинов для оптимальной упаковки бинов и разделения номеров» (PDF) , Материалы двадцать третьей международной совместной конференции по искусственному интеллекту , IJCAI '13, Пекин, Китай: AAAI Press, стр. 651–658, ISBN 978-1-57735-633-2
37. Мандал, Калифорния; Чакрабарти, ПП; Гоуз, С. (1 июня 1998 г.). «Сложность упаковки фрагментируемых объектов и применение». Компьютеры и математика с приложениями . 35 (11): 91–97. дои : 10.1016/S0898-1221(98)00087-X. ISSN  0898-1221.
38. Нир Менакерман и Рафаэль Ром «Упаковка мусорного ведра с фрагментацией предметов». Алгоритмы и структуры данных, 7-й международный семинар, WADS 2001, Провиденс, Род-Айленд, США, 8-10 августа 2001 г., Материалы.
39. Бертацци, Лука; Голден, Брюс; Ван, Синъинь (31 мая 2019 г.). «Проблема упаковки контейнеров с фрагментацией предметов: анализ наихудшего случая». Дискретная прикладная математика . Встреча GO X, Риги Кальтбад (Швейцария), 10–14 июля 2016 г. 261 : 63–77. дои : 10.1016/j.dam.2018.08.023 . ISSN  0166-218X. S2CID  125361557.
40. Шахнай, Хадас; Тамир, Тами; Йехезкели, Омер (2006). «Аппроксимационные схемы упаковки с фрагментацией изделий». В Эрлебахе, Томас; Персинао, Джузеппе (ред.). Приближение и онлайн-алгоритмы . Конспекты лекций по информатике. Том. 3879. Берлин, Гейдельберг: Springer. стр. 334–347. дои : 10.1007/11671411_26. ISBN 978-3-540-32208-5.
41. Экичи, Али (01 февраля 2021 г.). «Проблема упаковки корзин с конфликтами и фрагментацией предметов». Компьютеры и исследования операций . 126 : 105113. doi : 10.1016/j.cor.2020.105113. ISSN  0305-0548. S2CID  225002556.
42. Касацца, Марко; Чезелли, Альберто (01 июня 2014 г.). «Алгоритмы математического программирования для задач упаковки корзин с фрагментацией предметов». Компьютеры и исследования операций . 46 : 1–11. дои : 10.1016/j.cor.2013.12.008. ISSN  0305-0548.
43. Малагути, Энрико; Моначи, Мишель; Паронуцци, Паоло; Пферши, Ульрих (16 марта 2019 г.). «Целочисленная оптимизация с дробными значениями со штрафом: случай с рюкзаком». Европейский журнал операционных исследований . 273 (3): 874–888. дои : 10.1016/j.ejor.2018.09.020. hdl : 11585/657029 . ISSN  0377-2217. S2CID  31722681.
44. Краузе, КЛ; Шен, В.Я.; Шветман, HD (1 октября 1975 г.). «Анализ нескольких алгоритмов планирования задач для модели мультипрограммных компьютерных систем». Журнал АКМ . 22 (4): 522–550. дои : 10.1145/321906.321917 . ISSN  0004-5411. S2CID  10214857.
45. Келлерер, Х.; Пферши, У. (1 января 1999 г.). «Проблемы упаковки контейнеров с ограничением по мощности». Анналы исследования операций . 92 : 335–348. дои : 10.1023/А: 1018947117526. ISSN  1572-9338. S2CID  28963291.
46. Анили, Шошана; Брамель, Жюльен; Симчи-Леви, Дэвид (1 апреля 1994 г.). «Эвристический анализ наихудшего случая для задачи упаковки контейнеров с общей структурой затрат». Исследование операций . 42 (2): 287–298. дои : 10.1287/опре.42.2.287. ISSN  0030-364X.
47. Коэн, Максим К.; Келлер, Филипп В.; Миррокни, Вахаб; Задимогадам, Мортеза (01 июля 2019 г.). «Чрезмерные обязательства в сфере облачных сервисов: упаковка контейнеров со случайными ограничениями». Наука управления . 65 (7): 3255–3271. arXiv : 1705.09335 . дои : 10.1287/mnsc.2018.3091. ISSN  0025-1909. S2CID  159270392.
48. Чунг, Йерим; Пак, Мён Джу (01 января 2015 г.). «Заметки о проблемах с обратной упаковкой в ​​контейнер». Письма об обработке информации . 115 (1): 60–68. дои : 10.1016/j.ipl.2014.09.005. ISSN  0020-0190.
49. Бояр, Жанна ; Эпштейн, Лия; Фаврхольдт, Лене М.; Корт, Йенс С.; Ларсен, Ким С.; Педерсен, Мортен М.; Вёлк, Санне (11 октября 2006 г.). «Проблема упаковки контейнера с максимальным ресурсом». Теоретическая информатика . 362 (1): 127–139. дои : 10.1016/j.tcs.2006.06.001. ISSN  0304-3975.
50. Хуан, Синь; Лу, Пиньян (10 ноября 2020 г.). «Алгоритмическая основа для приближенного распределения долей по дому». arXiv : 1907.04505 [cs.GT].
51. Ма, Жуйсин; Доса, Дьёрдь; Хан, Синь; Тинг, Хин-Фунг; Да, Деши; Чжан, Юн (01 августа 2013 г.). «Заметка об эгоистичной проблеме с упаковкой мусорных баков». Журнал глобальной оптимизации . 56 (4): 1457–1462. дои : 10.1007/s10898-012-9856-9. ISSN  0925-5001. S2CID  3082040.
52. Лоди А., Мартелло С., Моначи, М., Виго, Д. (2010) «Проблемы упаковки двумерных контейнеров». В В.Т. Пашос (ред.), «Парадигмы комбинаторной оптимизации» , Wiley/ISTE, стр. 107–129.
53. Оптимизация трехмерной упаковки в контейнеры посредством моделирования
54. Бенко А., Доса Г., Туза З. (2010) «Упаковка/покрытие контейнеров с доставкой, решение с помощью эволюции алгоритмов», Труды 2010 г. 5-я Международная конференция IEEE по биовычислениям: теории и приложения, BIC-TA 2010 г. , ст. нет. 5645312, стр. 298–302.
55. Ваккаро, Алессио (13 ноября 2020 г.). «🧱 4 шага для простого распределения ресурсов с помощью Python и Bin Packing». Середина . Проверено 21 марта 2021 г.