Алгоритм имитации отжига в задаче плоского прямоугольного раскроя

The problem of flat rectangular cutting belongs to the class of NP-hard problems, that is, for its exact solution, algorithms of polynomial complexity are unknown. Until now, there have not been developed effective and sufficiently accurate methods for calculating the lower bounds for this problem, which make it possible to determine the achievement of the optimum. Thus, exact algorithms are reduced to a complete enumeration of options. In this regard, the use of exact algorithms for solving the problem of flat rectangular cutting often turns out to be inappropriate and impossible due to the large time costs. Therefore, great importance is given to the development and research of heuristic optimization methods. In this paper, we consider an annealing simulation algorithm and describe a variant of this algorithm as applied to an optimization problem on a set of permutations. It is shown that a number of classes of problems of flat rectangular cutting have a fragmented structure and, thus, the search for optimal (suboptimal) solutions to these problems can be reduced to the search for an optimal permutation. This made it possible to create a hybrid algorithm for finding suboptimal solutions to problems of flat rectangular cutting based on a combination of an annealing simulation algorithm and a fragmentary algorithm.

Hali tarjima qilinmagan