BIO-INSPIRED DENSE PACKING ALGORITHM TO INCREASE THE EFFICIENCY OF SEMI-LIMITED STRIP CUTTING
Keywords:
Packing in an endless strip, decomposition, distribution of blocks into containers, compaction, swarm intelligence, ant colony, adaptive behavior, search engine optimizationAbstract
A methodology has been developed for finding solutions to the semi-infinite strip packing problem
based on models of adaptive behavior of biological systems. To reduce the overall labor intensity of the
search procedure, an approach based on decomposition of the problem being solved is proposed.
The packaging is designed for cutting by guillotine cutting of the tape into containers and non-guillotine
cutting of containers into elements. Packaging is carried out by sequentially filling the strip with containers.
The problem of packing rectangles into strips is solved in three stages. At the first stage, the agent
solves the problem of distributing a set A of rectangular-shaped elements in a set of blocks B. The problem
of forming a set of blocks B, including sets of rectangular-shaped elements A, is solved by an algorithm for
one-dimensional packing of elements into identical blocks. At the second stage, the problem of distributing
blocks among containers is solved. All containers have the same width D, equal to the width of the strip.
Each container holds two blocks. The process of distributing blocks into containers is accompanied by a
compaction procedure for each pair of blocks assigned to one container. The purpose of compaction is to
minimize the total area of the container by densely placing the blocks. Compaction is carried out sequentially
in all containers. The problem of distributing blocks into containers is reduced to the problem of
finding the maximum matching of the minimum cost. In contrast to the canonical paradigm of the ant algorithm,
when working as an agent, a clique is built on the solution search graph, on the edges of which a
pheromone is deposited. A technique has been developed for the formation of pheromone points and data
structures of collective evolutionary memory. To conduct objective experiments, well-known test problems
presented in the literature and on the Internet were used. Compared to existing algorithms, a 3-5% improvement
in results was achieved. The time complexity of the algorithm, obtained experimentally, practically
coincides with theoretical studies and for the considered test problems is ≈ О(n2).
