Экспоненциальная окрестность для задачи упаковки контейнеров

Аннотация

Exponential neighborhood for Bin Packing Problem

УСМАНОВА Анжелика Рашитовна, ВАЛИАХМЕТОВА Юлия Ильясовна

Статья посвящена известной задаче одномерной упаковки – Bin Packing Task (BPP). Проблема упаковки контейнеров широко распространена в различных отраслях промышленности и техники. BPP является NP-сложным, поэтому множество решений имеет экспоненциальную мощность по отношению к упакованным элементам. Авторы рассматривают модифицированную модель задачи – по сути, решают задачу планирования цеха. Цель состоит в том, чтобы устранить так называемое общее переполнение (ТО) – сумму разностей между емкостью корзины и весом совпадающих предметов в каждой корзине. Различные методы, использующие полиномиальные окрестности, требуют много времени. Авторы предлагают экспоненциальную окрестность, требующую полиномиального времени для поиска лучшего решения. Рассматривается линейная задача о назначениях для построения экспоненциальной окрестности. Несмотря на то, что есть n! решений, оптимальное решение можно найти за O(n3). Авторы рассматривают несколько алгоритмов построения экспоненциальной окрестности. Основная идея состоит в том, чтобы удалить по одному элементу из каждого контейнера в некотором осуществимом решении. И тогда нам следует такие распакованные предметы переназначить в использованные контейнеры, чтобы ТО было минимальным. Однако предлагаемый метод построения показательных решений не позволяет напрямую изменять количество предметов в корзине. Поэтому желательно сочетать поиск в экспоненциальной окрестности с некоторыми стратегиями, позволяющими изменять количество элементов, связанных с каждым контейнером. Результаты численного эксперимента сравнивают поиск в полиномиальных окрестностях и предложенный экспоненциальный.