SEMI-INFINITE STRIP PACKAGING BASED ON DECOMPOSITION AND HYBRIDIZATION OF BIOINSPIRED METHODS

Abstract

In this work, the object of study is the problem of rectangular packing in a semi-infinite
strip. Given a set of rectangles. Given one large object (called a strip), whose width D is given,
and whose height HP is the desired value of the variable. The goal is to minimize the HP height of
a strip containing rectangles placed in the strip without overlapping each other. To solve the
packaging problem, a new hybrid approach is proposed based on the decomposition of the general
packaging problem and hybridization of bioinspired methods, as well as a new hybrid approach to
the decomposition of the general packaging problem. New architecture and methods for solving
the packing problem have been developed, built on the basis of decomposition and hybridization of
swarm methods developed by the authors, using various search strategies, operating in parallel and sequentially and implementing a wider overview of the solution space, which allows for a
higher probability of localizing a global extremum in an acceptable time. A methodology has been
developed for a new direction in searching for solutions to orthogonal packing problems based on
models of adaptive behavior of biological systems. A highly effective hybrid bioinspired method
for solving one-dimensional and rectangular packaging problems has been developed, based on
the decomposition of the problem into many subtasks and the integration of search optimization
methods. New mechanisms for solving the packaging problem are proposed, using mathematical
methods that incorporate the principles of natural decision-making mechanisms. In contrast to the
canonical paradigm of the ant algorithm, the agent forms a partition of the set of rectangular elements
A into subsets Aki on the solution search graph as a solution, where Akj is a subset of elements
assigned by the agent to the block. Search methods have been developed for solving problems
of guillotine and non-guillotine rectangular cutting. To conduct objective experiments, wellknown
test tasks presented in the literature and the Internet were used. Better results were obtained
compared to the tested methods. The theoretical principles proposed in the work for solving
problems of packaging and cutting industrial objects in single production conditions are implemented
in the form of methods, algorithms and application software. 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).