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

Abstract

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

Розглянуто загальну задачу двовимірного пакування в напівобмежену смугу. Показано, що її можна розглядати як задачу оптимізації на фрагментарній структурі, яка зводиться до задачі комбінаторної оптимізації на множині переставлень. Розглянуто універсальний спосіб представлення плоских фігур та алгоритм їхнього пакування в смугу. Запропоновано спосіб модифікації початкової задачі для досяжності оптимального розв’язку.

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.