Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу

• Published in: Кибернетика и системный анализ
• Date: 2019
• Main Authors: Козин, И.В., Батовский, C.Е.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2019
• Subjects: Системний аналіз
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/181439
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Фрагментарные структуры в задаче двумерной упаковки в полуограниченную полосу / И.В. Козин, C.Е. Батовский // Кибернетика и системный анализ. — 2019. — Т. 55, № 6. — С. 73–79. — Бібліогр.: 16 назв. — рос.

Рассмотрена общая задача двумерной упаковки в полуограниченную полосу. Показано, что ее можно рассматривать как задачу оптимизации на фрагментарной структуре, которая сводится к задаче комбинаторной оптимизации на множестве перестановок. Рассмотрены универсальный способ представления плоских фигур и алгоритм их упаковки в полосу. Предложен способ модификации исходной задачи для достижимости оптимального решения. Розглянуто загальну задачу двовимірного пакування в напівобмежену смугу. Показано, що її можна розглядати як задачу оптимізації на фрагментарній структурі, яка зводиться до задачі комбінаторної оптимізації на множині переставлень. Розглянуто універсальний спосіб представлення плоских фігур та алгоритм їхнього пакування в смугу. Запропоновано спосіб модифікації початкової задачі для досяжності оптимального розв’язку. The paper considers a two-dimensional strip packing problem. It is shown that the problem can be considered as an optimization problem on a fragmented structure, which reduces to the problem of combinatorial optimization on a set of permutations. A universal approach of representing two-dimensional figures and the algorithm of their packing into the strip are considered. An approach to the modification of the original problem for the attainability of the optimal solution is proposed.