Введение
Математическая и вычислительная задача
Задача об упаковке контейнеров – это задача оптимизации, в которой элементы различных размеров необходимо упаковать в конечное число контейнеров или ящиков, каждый из которых имеет фиксированную заданную вместимость, таким образом, чтобы минимизировать количество используемых контейнеров. Эта задача имеет множество применений, таких как заполнение контейнеров, загрузка грузовиков с ограничениями по грузоподъемности, создание резервных копий файлов на носителях и технологическое отображение при проектировании полупроводниковых чипов FPGA. С вычислительной точки зрения, задача является NP-трудной, а соответствующая задача принятия решения, определяющая, могут ли элементы поместиться в заданное количество контейнеров, является NP-полной. Несмотря на свою сложность в худшем случае, оптимальные решения для очень больших экземпляров задачи могут быть получены с использованием сложных алгоритмов. Кроме того, существует множество приближенных алгоритмов. Например, алгоритм первого подходящего размера обеспечивает быстрое, но часто неоптимальное решение, заключающееся в размещении каждого элемента в первый контейнер, в который он поместится. Для этого требуется Θ(n log n) времени, где n – количество элементов, которые необходимо упаковать. Алгоритм может быть значительно эффективнее, если предварительно отсортировать список элементов в порядке убывания (иногда называемый алгоритмом убывающего первого подходящего размера), хотя это все еще не гарантирует оптимального решения и для более длинных списков может увеличить время работы алгоритма. Однако известно, что всегда существует хотя бы один порядок элементов, который позволяет алгоритму первого подходящего размера найти оптимальное решение. Существует множество вариантов этой задачи, таких как двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и так далее. Задача об упаковке контейнеров также может рассматриваться как частный случай задачи раскроя. Когда количество контейнеров ограничено 1, а каждый элемент характеризуется как объемом, так и стоимостью, задача максимизации стоимости элементов, которые могут поместиться в контейнер, известна как задача о рюкзаке. Вариант упаковки контейнеров, который встречается на практике, заключается в том, что элементы могут совместно использовать пространство при упаковке в контейнер. В частности, набор элементов может занимать меньше места при совместной упаковке, чем сумма их индивидуальных размеров. Этот вариант известен как упаковка виртуальных машин, поскольку при упаковке виртуальных машин (ВМ) на сервере их общие требования к памяти могут уменьшиться за счет совместно используемых страниц, которые необходимо хранить только один раз. Если элементы могут совместно использовать пространство произвольным образом, задача об упаковке контейнеров становится трудно даже приближенно решить. Однако, если совместное использование пространства подчиняется иерархии, как это происходит при совместном использовании памяти в виртуальных машинах, задачу об упаковке контейнеров можно эффективно приближенно решить. Другой вариант упаковки контейнеров, представляющий интерес на практике, – это так называемая онлайн-упаковка контейнеров. Здесь элементы разного объема поступают последовательно, и принимающий решение должен решить, выбрать и упаковать текущий наблюдаемый элемент или пропустить его. Каждое решение является окончательным и не может быть изменено. В отличие от этого, оффлайн-упаковка контейнеров позволяет переупорядочивать элементы в надежде на получение лучшей упаковки после поступления дополнительных элементов. Это, конечно, требует дополнительного хранилища для хранения элементов, которые необходимо переупорядочить.
Твердость упаковки в контейнеры
Проблема упаковки в контейнеры является сильно NP-полной. Это можно доказать, сведя сильно NP-полную задачу о 3-разбиении к задаче об упаковке в контейнеры. Для данного экземпляра задачи о 3-разбиении, где сумма всех входных чисел равна S, построим экземпляр задачи об упаковке в контейнеры, в котором размер контейнера равен T. Если существует разделение входных чисел на две равные части, то оптимальная упаковка требует 2 контейнера; следовательно, любой алгоритм с коэффициентом аппроксимации меньше, чем 2/3, должен возвращать менее 3 контейнеров, то есть 2 контейнера. Напротив, если такого разделения не существует, то оптимальная упаковка требует не менее 3 контейнеров. С другой стороны, задача об упаковке в контейнеры разрешима за псевдополиномиальное время для любого фиксированного числа контейнеров K и разрешима за полиномиальное время для любой фиксированной вместимости контейнера B.
Адитивная приближенность
Алгоритм упаковки рюкзаков Карп-Кармакара находит решение с размером не более , и выполняется за время, полиномиальное от n (полином имеет высокую степень, не менее 8). Ротфосс представил алгоритм, который генерирует решение, использующее не более корзин. Хоберг и Ротфосс улучшили этот алгоритм, чтобы генерировать решение, использующее не более корзин. Алгоритм рандомизирован, и его время работы полиномиально от n.
Небольшое количество различных размеров
Особый случай задачи упаковки в контейнеры возникает, когда существует небольшое количество d различных размеров предметов. При этом количество предметов каждого размера может быть большим. Этот случай также называют задачей упаковки с высокой кратностью, и для него существуют более эффективные алгоритмы, чем для общей задачи.
Упаковка в корзину с фрагментацией
Упаковка контейнеров с фрагментацией, или упаковка контейнеров с фрагментируемыми объектами, — это вариант задачи об упаковке контейнеров, в котором допускается разбиение предметов на части и размещение каждой части в отдельном контейнере. Разбиение предметов на части может способствовать повышению общей эффективности, например, минимизации общего количества используемых контейнеров. Кроме того, вычислительная задача поиска оптимального решения может упроститься, поскольку некоторые переменные оптимизации становятся непрерывными. С другой стороны, разбиение предметов на части может быть сопряжено с затратами. Впервые эта проблема была рассмотрена Мандалом, Чакрабари и Гоушем.
Варианты
Проблема имеет два основных варианта. В первом варианте, называемом задачей упаковки в контейнеры с возрастающей фрагментацией (BP SIF), каждый элемент может быть разбит на фрагменты, при этом к размеру каждого фрагмента добавляются накладные единицы. Во втором варианте, называемом задачей упаковки в контейнеры с сохранением размера при фрагментации (BP SPF), каждый элемент имеет размер и стоимость; разбиение элемента на фрагменты увеличивает его стоимость, но не изменяет его размер.
Комплексность вычислений
Мандал, Чакрабари и Госэ показали, что задачи BP SIF и BP SPF являются сильно NP-трудными. Несмотря на эту трудность, они представили несколько алгоритмов и исследовали их эффективность. В основе их алгоритмов лежат классические алгоритмы для задачи о размещении предметов в контейнерах, такие как "следующий подходящий" и "первый подходящий убывающий". Бертацци, Голден и Ван предложили вариант BP SIF с правилом разбиения: предмет можно разбить только одним способом в зависимости от его размера. Это полезно, например, для задачи маршрутизации транспортных средств. В своей работе они приводят оценку производительности в наихудшем случае для этого варианта. Шахнай, Тамир и Йезекели разработали схемы аппроксимации для BP SIF и BP SPF: двойной PTAS (PTAS для двойственной версии задачи), асимптотический PTAS, называемый APTAS, и двойной асимптотический FPTAS, называемый AFPTAS, для обеих версий. Экиджи предложила вариант BP SPF, в котором некоторые предметы находятся в конфликте, и запрещено помещать фрагменты конфликтующих предметов в один и тот же контейнер. Они доказали, что этот вариант также является NP-трудным. Кассацца и Чезелли представили вариант без стоимости и накладных расходов, где число контейнеров фиксировано. Однако необходимо минимизировать количество фрагментаций. Они представили алгоритмы математического программирования для получения как точных, так и приближенных решений.
Связанные проблемы
Проблема дробного рюкзака с штрафами была предложена Малагути, Моначи, Паронуцци и Пферши. Они разработали FPTAS и алгоритм динамического программирования для этой задачи, а также провели обширное вычислительное исследование для сравнения эффективности своих моделей. См. также: Планирование заданий с дробным временем.
Производительность с делящимися размерами элементов
Важным частным случаем задачи упаковки в контейнеры является ситуация, когда размеры предметов образуют делимую последовательность (также называемую факторизованной). Особый случай делимых размеров предметов возникает при выделении памяти в компьютерных системах, где размеры предметов являются степенями двойки. Если размеры предметов делимы, некоторые эвристические алгоритмы для задачи упаковки в контейнеры находят оптимальное решение.
Ограничения кардинальности на контейнерах
Существует вариант задачи об упаковке контейнеров, в котором накладываются ограничения на кардинальность контейнеров: каждый контейнер может содержать не более k элементов, где k – некоторое фиксированное целое число.
Краузе, Шен и Шветман представляют эту задачу как вариант оптимального планирования заданий: имеется компьютер с k процессорами. Есть n заданий, каждое из которых занимает единицу времени (1), но требует разный объем памяти. Каждая единица времени рассматривается как отдельный контейнер. Цель состоит в том, чтобы использовать минимальное количество контейнеров (= единиц времени), при этом в каждом контейнере должно выполняться не более k заданий. Они предлагают несколько эвристических алгоритмов, находящих решение, использующее не более контейнеров. Келлер и Пферши представляют алгоритм со временем работы , находящий решение, использующее не более контейнеров. Их алгоритм выполняет бинарный поиск оптимального решения. Для каждого проверяемого значения m алгоритм пытается упаковать элементы в 3m/2 контейнеров.
Связанные проблемы
В задаче упаковки контейнеров размер контейнеров фиксирован, и их количество может быть увеличено (но должно быть как можно меньше). В отличие от этого, в задаче многостороннего разбиения на группы число контейнеров фиксировано, а их размер может быть увеличен. Цель состоит в том, чтобы найти разбиение, в котором размеры контейнеров были бы максимально близки друг к другу (в варианте, называемом задачей планирования на многопроцессорном оборудовании или задачей минимизации максимальной загрузки, целью является конкретно минимизация размера наибольшего контейнера). В задаче обратной упаковки контейнеров как количество контейнеров, так и их размеры фиксированы, но размеры предметов могут быть изменены. Цель состоит в том, чтобы минимизировать изменения в векторе размеров предметов, чтобы все предметы можно было упаковать в заданное количество контейнеров. В задаче максимальной упаковки ресурсов цель состоит в том, чтобы максимизировать количество используемых контейнеров, при этом для некоторого порядка контейнеров ни один предмет из последующего контейнера не помещался бы в предыдущий. В двойственной задаче количество контейнеров фиксировано, и цель состоит в том, чтобы минимизировать общее количество или общий размер предметов, помещенных в контейнеры, так, чтобы ни один оставшийся предмет не помещался в незаполненный контейнер. В задаче покрытия контейнерами размер контейнера ограничен снизу: цель состоит в том, чтобы максимизировать количество используемых контейнеров таким образом, чтобы общий размер в каждом контейнере был не меньше заданного порога. В задаче справедливого распределения однородных задач (вариант справедливого распределения предметов) предметы представляют собой задачи, и есть различные люди, каждый из которых оценивает сложность каждой задачи по-разному. Цель состоит в том, чтобы распределить каждому человеку набор задач с ограничением на общую сложность (таким образом, каждый человек соответствует контейнеру). Многие методы, используемые в задаче упаковки контейнеров, применяются и в этой задаче. В задаче гильотинной резки как предметы, так и "контейнеры" являются двумерными прямоугольниками, а не одномерными числами, и предметы должны быть вырезаны из контейнера прямыми разрезами от края до края. В задаче эгоистичной упаковки контейнеров каждый предмет является игроком, стремящимся минимизировать свои затраты. Существует также вариант упаковки контейнеров, в котором минимизируемой величиной является не количество контейнеров, а некоторая вогнутая функция от количества предметов в каждом контейнере. трехмерная упаковка контейнеров, упаковка контейнеров с доставкой,
Ресурсы
BPPLIB – библиотека обследований, кодов, эталонных значений, генераторов, решателей и библиографии.