Тип публикации: статья из журнала
Год издания: 2020
Идентификатор DOI: 10.17513/snt.38096
Ключевые слова: упаковка прямоугольников в контейнер, упаковка прямоугольников в полосу, метаэвристика, несовместимые категории, приоритет, Bin Packing problem, strip packing problem, metaheuristic, incompatible categories, priority
Аннотация: В статье рассматривается задача упаковки прямоугольников, а именно ее новая постановка. Она заключается во введении приоритетов и несовместимых категорий. Эта задача называется задачей приоритетной упаковки с несовместимыми категориями и динамически изменяющимися размерами контейнера. Данная оптимизационная задача возникает при расПоказать полностьюкрое металлических слитков, где приоритеты отражают порядок производства заготовок, а отдельные группы деталей, обладающие разной толщиной, несовместимы между собой. Часто при изготовлении деталей используется гильотина. Производство деталей разной толщины происходит путем прокатки слитка, в результате чего его размеры изменяются. Это делает необходимым не только вычисление оптимальной схемы раскроя, но и определение длины субконтейнера для каждой группы. В статье предлагается новый последовательный метаэвристический алгоритм для решения поставленной задачи. В ходе упаковки весь набор прямоугольников разделяется на группы, которые упаковываются отдельно. В результате схемы раскроя одинаковых групп объединяются. Предлагаемая метаэвристика использует однопроходной детерминированный приоритетный эвристический алгоритм. Структура метаэвристики позволяет применять любые алгоритмы упаковки, удовлетворяющие приведенным ограничениям. Это дает возможность сохранять и комбинировать свойства используемых алгоритмов. Качество работы алгоритма оценено на основе тестовых примеров, составленных для приведенной постановки задачи. The paper considers the bin packing problem, namely its new formulation. It consists of introducing priorities and incompatible categories. This problem is called a priority packaging problem with incompatible categories and dynamically changing container sizes. This optimization problem arises when cutting metal ingots, where the priorities reflect the order of production of parts, and individual groups of parts with different thicknesses are incompatible with each other. Often, the guillotine is used in the manufacture of parts. The production of parts of different thicknesses occurs by rolling the ingot, as a result of which its dimensions change. This makes it necessary not only to calculate the optimal cutting scheme, but also to determine the length of the sub-container for each group. The paper proposes a new sequential metaheuristic algorithm for solving this problem. During packaging, the entire set of rectangles is divided into groups that are packed separately. As a result, the cutting schemes of the same groups are combined. The proposed metaheuristics uses a single-pass deterministic priority heuristic algorithm. The metaheuristics structure allows you to use any packaging algorithms that meet the above restrictions. This allows you to save and combine the properties of the algorithms used. The quality of the algorithm is evaluated based on test examples compiled for the given problem formulation.
Журнал: Современные наукоемкие технологии
Выпуск журнала: № 6-2
Номера страниц: 220-227
ISSN журнала: 18127320
Место издания: Москва
Издатель: ООО "Издательский дом "Академия естествознания"