articles

< Back to articles list

Authors: Chekanin V., Chekanin A. Published in № 3(75) 29 june 2018 year
Rubric: Algorithmic efficiency

Buy an article

Download the first page

Development of packing compacting algorithm to improve the efficiency of rectangular cutting

In this article is considered the NP-hard optimization strip packing problem that is actual in solving many practical problems of automation and control, in particular, it takes a place in solving such problems as cutting of materials, calendar scheduling and planning, placement of resources in multiprogramming systems and a lot of other problems. With the aim to optimize the placement of objects in a container, the iterative packing compaction algorithm which insures the increasing of the density of packed objects was developed. In the basis of the proposed algorithm lays usage of six rules which select several placed objects with the aim of removing them with subsequent more rational filling of the freed spaces in a container by the deleted objects through a single-pass heuristic algorithm. The results of carried out computational experiments on the investigation of the packing compaction algorithm on the standard test instances of the strip packing problem with the given random and optimized placements are presented. On the average the packing compaction algorithm provides increasing the density of random placements to 3% and density of optimized placements to 0.4%. The developed algorithm has been implemented in a general form, which makes it possible to use it not only for two-dimensional problems as well as for three-dimensional orthogonal packing problems.

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