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).