articles

< Back to articles list

Authors: Chekanin V., Chekanin A. Published in № 5(71) 31 october 2017 year
Rubric: Models and althorithms

Buy an article

Download the first page

Program realization of an effective data structure for the orthogonal packing problems of arbitrary dimension

In the paper is considered a well-known NP-completed orthogonal packing problem which has many applications in industry and economics. The orthogonal packing problem is a problem related with the searching of the optimal placement of a given set of small orthogonal items (objects) into a set of large orthogonal items (containers). The effective approach to solve NP-completed problems is application of heuristic methods which provide obtaining of suboptimal decisions. The maximal efficiency of such will be achieved when delays on packing generation will be minimized. In the paper is considered a multilevel linked data structure which provides the possibility of fast management of free spaces into orthogonal containers during the process of filling them with objects. The program realization of the proposed data structure, which is implemented invariantly on the dimension of the considered packing problem, makes it universal and applicable for solving of rectangular packing and orthogonal packing problems of arbitrary dimension. The paper presents results of the carried out computational experiment. The results demonstrate that the efficiency of proposed data structure increases with the number of objects and it tends to double the effectiveness of the time compared with the simple linear linked list. In paper is also given a description of the developed applied software intended for various types of rectangular cutting and orthogonal packing problems. This work was carried out with the financial support of the Ministry of Education and Science of Russian Federation in the framework of the state task in the field of scientific activity of MGTU «STANKIN» (No. 1.7706.2017/8.9).

Key words

packing problem, three-dimensional orthogonal packing problem, data structure, linked data structure, software

The author:

Chekanin V.

Degree:

Dr. Sci. (Eng.), Associate Professor, Theoretical Mechanics and Strength of Materials Department, Moscow State University of Technology "STANKIN"; Leading Researcher, V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences